2014/2015
Modularity-based community detection in large networks: An empirical evaluation
Proceedings of 2014 IEEE International Conference on Information and Automation(ICIA),(pp. 1131-1136). IEEE
| Author(s) | Haoming Li
Wenye Li Jiaqi Tan |
|---|---|
| Summary | 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. |