Detecting highly overlapping community structure by greedy clique expansion

Abstract

In complex networks it is common for each node to belong to several communities, implying a highly overlapping community structure. Recent advances in benchmarking indicate that existing community assignment algorithms that are capable of detecting overlapping communities perform well only when the extent of community overlap is kept to modest levels. To overcome this limitation, we introduce a new community assignment algorithm called Greedy Clique Expansion (GCE). The algorithm identifies distinct cliques as seeds and expands these seeds by greedily optimizing a local fitness function. We perform extensive benchmarks on synthetic data to demonstrate that GCE's good performance is robust across diverse graph topologies. Significantly, GCE is the only algorithm to perform well on these synthetic graphs, in which every node belongs to multiple communities. Furthermore, when put to the task of identifying functional modules in protein interaction data, and college dorm assignments in Facebook friendship data, we find that GCE performs competitively.

10 pages, 7 Figures. Implementation source and binaries available at http://sites.google.com/site/greedycliqueexpansion/

References in corpus (11)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Comparing community structure identification
• Community detection algorithms: a comparative analysis
• Detecting the overlapping and hierarchical community structure of complex networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Detect overlapping and hierarchical community structure in networks
• Mixture models and exploratory analysis in networks
• A sequential algorithm for fast clique percolation
• Detecting Communities in Networks by Merging Cliques

Cited by in corpus (30)

• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• Towards Linear Time Overlapping Community Detection in Social Networks
• Leveraging disjoint communities for detecting overlapping community structure
• Overlapping Community Discovery Methods: A Survey
• Revealing Multiple Layers of Hidden Community Structure in Networks
• Detecting Overlapping Communities from Local Spectral Subspaces
• Identifying Overlapping and Hierarchical Thematic Structures in Networks of Scholarly Papers: A Comparison of Three Approaches
• Growing networks of overlapping communities with internal structure
• Ordered community structure in networks
• Identification of Overlapping Communities by Locally Calculating Community-Changing Resolution Levels
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• Overlapping Community Detection via Local Spectral Clustering
• Benchmarking community detection methods on social media data
• Comparison and Benchmark of Graph Clustering Algorithms
• A General Definition of Network Communities and the Corresponding Detection Algorithm
• Exhaustive Search-based Model for Hybrid Sensor Network
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Partitioning Breaks Communities
• Diffusion in Networks With Overlapping Community Structure
• Using Model-based Overlapping Seed Expansion to detect highly overlapping community structure
• Percolation Computation in Complex Networks
• MeetupNet Dublin: Discovering Communities in Dublin's Meetup Network
• Semi-Supervised Overlapping Community Finding based on Label Propagation with Pairwise Constraints
• Structure Amplification on Multi-layer Stochastic Block Models
• Understanding Vulnerability of Communities in Complex Networks
• High-Quality Disjoint and Overlapping Community Structure in Large-Scale Complex Networks