Community Structure in Large-Scale Complex Networks

Abstract

Vertices in complex networks can be grouped into communities, where vertices inside communities are densely connected to each other and vertices from one community are sparsely connected to vertices in other communities. This is the so-called community structure in complex networks. Identifying the community structure of networks has many applications, ranging from data mining, webpage clustering and market- ing to extracting proteins with the same functionality in protein-protein-interaction networks and beyond.

This thesis addresses a number of the primary problems surrounding community structure in large-scale networks. These problems generally revolve around two of the principal challenges of the area, accuracy and soundness of modelling and scala- bility to real-world networks. The problems include identifying top-k structural hole spanners, detecting the hierarchy of communities, detecting overlapping communi- ties, and community search in large-scale complex networks. The thesis formally de- fines the cohesive hierarchies of communities in complex networks. Since scalability is a major challenge for cohesive hierarchical community detection, the thesis incor- porates a network sparsification technique to leverage the network size and finds co- hesive hierarchies of communities in large-scale complex networks. The problem of identifying top-k structural hole spanners is formally defined in this thesis and several scalable algorithms have been presented for this problem. Furthermore, the thesis delves into the problem of overlapping community detection and proposes an accu- rate fitness metric to find overlapping communities in large-scale complex networks. The thesis finally studies the problem of community search and introduces a new al- gorithm for community search in complex networks.

The thesis develops novel models, algorithms, and evaluation measures for these problems, and presents the experimental results of these algorithms using real-world datasets, which outperform considerably on the scalability and accuracy of the state of the art, in several cases.