Extending a configuration model to find communities in complex networks

• Type: Article in International Scientific Journal
• Date: 2013

Authors

Jin, D (Author) Other; He, DX (Author) Other; Hu, QH (Author) Other; Baquero, C (Author) Other; Yang, B (Author) Other

Journal

Title: Journal of Statistical Mechanics: Theory and Experiment

Vol. 2013

ISSN: 1742-5468

Publisher: Institute of Physics Publishing

Indexing

ISI Web of Knowledge - 8 Citations

Scopus - 10 Citations

Other information

Authenticus ID: P-006-7FP

DOI: 10.1088/1742-5468/2013/09/p09013

Abstract (EN): Discovery of communities in complex networks is a fundamental data analysis task in various domains. Generative models are a promising class of techniques for identifying modular properties from networks, which has been actively discussed recently. However, most of them cannot preserve the degree sequence of networks, which will distort the community detection results. Rather than using a blockmodel as most current works do, here we generalize a configuration model, namely, a null model of modularity, to solve this problem. Towards decomposing and combining sub-graphs according to the soft community memberships, our model incorporates the ability to describe community structures, something the original model does not have. Also, it has the property, as with the original model, that it fixes the expected degree sequence to be the same as that of the observed network. We combine both the community property and degree sequence preserving into a single unified model, which gives better community results compared with other models. Thereafter, we learn the model using a technique of nonnegative matrix factorization and determine the number of communities by applying consensus clustering. We test this approach both on synthetic benchmarks and on real-world networks, and compare it with two similar methods. The experimental results demonstrate the superior performance of our method over competing methods in detecting both disjoint and overlapping communities.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 17