Overlapping Community Detection in Networks: the State of the Art and Comparative Study

Abstract

This paper reviews the state of the art in overlapping community detection algorithms, quality measures, and benchmarks. A thorough comparison of different algorithms (a total of fourteen) is provided. In addition to community level evaluation, we propose a framework for evaluating algorithms' ability to detect overlapping nodes, which helps to assess over-detection and under-detection. After considering community level detection performance measured by Normalized Mutual Information, the Omega index, and node level detection performance measured by F-score, we reached the following conclusions. For low overlapping density networks, SLPA, OSLOM, Game and COPRA offer better performance than the other tested algorithms. For networks with high overlapping density and high overlapping diversity, both SLPA and Game provide relatively stable performance. However, test results also suggest that the detection in such networks is still not yet fully resolved. A common feature observed by various algorithms in real-world networks is the relatively small fraction of overlapping nodes (typically less than 30%), each of which belongs to only 2 or 3 communities.

This paper (final version) is accepted in 2012. ACM Computing Surveys, vol. 45, no. 4, 2013 (In press) Contact: [email protected]

References in corpus (29)

• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Detect overlapping and hierarchical community structure in networks
• Line Graphs, Link Partitions and Overlapping Communities
• Mixture models and exploratory analysis in networks
• An efficient and principled method for detecting communities in networks
• Robustness of community structure in networks
• Extending the definition of modularity to directed graphs with overlapping communities
• Graph Evolution: Densification and Shrinking Diameters
• Weighted network modules
• A sequential algorithm for fast clique percolation
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Identifying "communities" within energy landscapes
• Clique Graphs and Overlapping Communities
• Fuzzy overlapping communities in networks
• Quantifying and identifying the overlapping community structure in networks
• When are networks truly modular?
• The Naming Game in Social Networks: Community Formation and Consensus Engineering
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Map equation for link community
• Markov random walk under constraint for discovering overlapping communities in complex networks
• Thermodynamics of Community Structure

Cited by in corpus (45)

• Community detection in networks: A user guide
• Community Detection in Networks with Node Attributes
• Community Discovery in Dynamic Networks: a Survey
• A Comprehensive Survey on Community Detection with Deep Learning
• Community Interaction and Conflict on the Web
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Hiding Individuals and Communities in a Social Network
• Detecting criminal organizations in mobile phone networks
• Hypergraph reconstruction from network data
• Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering
• Comparison of Communities Detection Algorithms for Multiplex
• IEDC: An Integrated Approach for Overlapping and Non-overlapping Community Detection
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• In a World That Counts: Clustering and Detecting Fake Social Engagement at Scale
• Leveraging disjoint communities for detecting overlapping community structure
• Different approaches to community detection
• Extension of Modularity Density for Overlapping Community Structure
• Versatility of nodal affiliation to communities
• Forbidden triads and Creative Success in Jazz: The Miles Davis Factor
• Ensemble Clustering for Graphs: Comparisons and Applications
• Intelligent architectures for robotics: The merging of cognition and emotion
• Detecting Community Structure in Dynamic Social Networks Using the Concept of Leadership
• Discovering the hidden community structure of public transportation networks
• Spread of infectious disease and social awareness as parasitic contagions on clustered networks
• Growing networks of overlapping communities with internal structure
• Seeded PageRank Solution Paths
• Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning
• Link community detection through global optimization and the inverse resolution limit of partition density
• CommAID: Visual Analytics for Communication Analysis through Interactive Dynamics Modeling
• Clique percolation method: memory efficient almost exact communities
• Mixed Membership Graph Clustering via Systematic Edge Query
• Identifying Influential Nodes Using Overlapping Modularity Vitality
• Communities as Well Separated Subgraphs With Cohesive Cores: Identification of Core-Periphery Structures in Link Communities
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• DANI: Fast Diffusion Aware Network Inference with Preserving Topological Structure Property
• Generative models for local network community detection
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Topological aspects of the multi-language phases of the Naming Game on community-based networks
• Finding community structure using the ordered random graph model
• Overlapping community detection in networks via sparse spectral decomposition
• Further insights into the interareal connectivity of a cortical network
• Centrality with Diversity
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
• Overlapping community detection in weighted networks
• Bayesian Modeling of Random Walker for Community Detection in Networks