Mathematical and Algorithmic Analysis of Network and Biological Data.

摘要

The first main topic of this dissertation is network science. Complexity in social, biological and economical systems, and more generally in complex systems, arises through pairwise interactions. Therefore, there exists a surging interest in understanding networks. Our work is motivated by the following questions: How do we model real-world planar networks such as transportation networks? How can we transfer classified information between agencies in communication networks safely? How can we compute efficiently important graph statistics, such as the number of triangles in a graph? How can we extract dense subgraphs from large-scale graphs in order to detect spam link farms and more generally thematic groups? What is the structure of the Web graph? How do real-world networks evolve over time? This dissertation approaches these important applications' questions from different angles by combining a mathematical, an algorithmic and an experimental analysis of networks.;The second main topic of our work is cancer evolution. High-throughput sequencing technologies allow us to study tumors by providing us various types of datasets, such as datasets measuring gains and losses of chromosomal regions in tumor cells. Can we understand how cancer progresses by analyzing these datasets? Can we detect in an unsupervised manner cancer subtypes in order to improve cancer therapeutics? Motivated by these questions, we provide new models, theoretical insights into existing models, novel algorithmic techniques and detailed experimental analysis of various datasets.;Finally, the third central topic of our thesis is big graph data. The scale of graph data that is nowadays collected and required to be processed is massive. This fact poses numerous challenges. In this work we tackle with two major challenges, engineering an efficient graph processing platform and balanced graph partitioning of dynamic graphs.