Modularity-based community detection in large networks: An empirical evaluation

摘要

In complex network analysis, an important problem is to detect the community structure inherent in network vertices. To do this, a mathematical measure, called “modularity”, is often adopted for maximization, which provides a principled way in identifying such network communities. Unfortunately, the optimization process involves non-trivial computation and becomes prohibitive even for medium-sized networks. To overcome the difficulty, our work applied a constrained power method for modularity optimization for large-scale networks. We carried out thorough empirical evaluations by synthesizing twenty different-structured networks with a million vertices each. On these networks the method was able to find the community structures on a desktop computer with a single CPU in less than one hour yet with high accuracy. As far as we know, this is the first result reported in literature by conventional computing approaches.