Clustering and Network Analysis with Biological Applications

Book excerpt: Abstract: Clustering and network analysis are important areas of research in Computer Science and other disciplines. Clustering is broadly defined as finding sets of similar objects. It has many applications, such as finding groups of similar buyers given their product preferences, and finding groups of similar proteins given their sequences. Network analysis considers data represented by a collection of nodes (vertices), and edges that link these nodes. The structure of the network is studied to find central nodes, identify nodes that are similar to a particular vertex, and find well-connected groups of vertices. The World Wide Web and online social networks are some of the best studied networks today. Network analysis can also be applied to biological networks where nodes are proteins and edges represent relationships or interactions between them. The size of real-world data sets presents many challenges to computational techniques that interpret them. A classic clustering problem is to divide the data set into groups, given the pairwise distances between the objects. However, computing all the pairwise distances may be infeasible if the data set is very large. In this thesis we consider clustering in a limited information setting where we do not know the distances between the objects in advance, and instead must query them during the execution of the algorithm. We present algorithms that find an accurate clustering in this setting using few queries. The networks that we encounter in practice are quite large as well, making computations on the entire network difficult. In this thesis we present techniques for locally exploring networks, which are efficient but still give meaningful information about the local structure of the graph. We develop several tools for locally exploring a network, and show that they give meaningful results when applied to protein networks.