Community detection in social networks
- 1 June 2015
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 8 (10), 998-1009
- https://doi.org/10.14778/2794367.2794370
Abstract
Revealing the latent community structure, which is crucial to understanding the features of networks, is an important problem in network and graph analysis. During the last decade, many approaches have been proposed to solve this challenging problem in diverse ways, i.e. different measures or data structures. Unfortunately, experimental reports on existing techniques fell short in validity and integrity since many comparisons were not based on a unified code base or merely discussed in theory. We engage in an in-depth benchmarking study of community detection in social networks. We formulate a generalized community detection procedure and propose a procedure-oriented framework for benchmarking. This framework enables us to evaluate and compare various approaches to community detection systematically and thoroughly under identical experimental conditions. Upon that we can analyze and diagnose the inherent defect of existing approaches deeply, and further make effective improvements correspondingly. We have re-implemented ten state-of-the-art representative algorithms upon this framework and make comprehensive evaluations of multiple aspects, including the efficiency evaluation, performance evaluations, sensitivity evaluations, etc. We discuss their merits and faults in depth, and draw a set of take-away interesting conclusions. In addition, we present how we can make diagnoses for these algorithms resulting in significant improvements.Keywords
This publication has 25 references indexed in Scilit:
- Overlapping community detection in networksACM Computing Surveys, 2013
- Community Detection and Mining in Social MediaSynthesis Lectures on Data Mining and Knowledge Discovery, 2010
- Community detection in graphsPhysics Reports, 2009
- Towards real-time community detection in large networksPhysical Review E, 2009
- Benchmark graphs for testing community detection algorithmsPhysical Review E, 2008
- Sequential algorithm for fast clique percolationPhysical Review E, 2008
- Modularity and community structure in networksProceedings of the National Academy of Sciences of the United States of America, 2006
- Comparing community structure identificationJournal of Statistical Mechanics: Theory and Experiment, 2005
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Finding community structure in very large networksPhysical Review E, 2004