Source-linked AI summary
Overlapping Community Detection in Networks: the State of the Art and Comparative Study
Jierui Xie, Stephen Kelley, Boleslaw K. Szymanski
TL;DR
Overlapping community detection must account for nodes belonging to multiple communities, but existing benchmarks and overall measures have important limitations. The paper reviews fourteen algorithms, quality measures, and benchmarks, evaluates community- and node-level performance, and finds that performance varies with overlap while dense, diverse overlap remains unresolved.
Problem
Nodes in real-world networks may belong to multiple communities, while existing benchmarks may fail to represent overlapping and heterogeneous network structure.
Method
The paper reviews fourteen overlapping community detection algorithms, quality measures, and benchmarks, testing community- and node-level performance on LFR networks.
Results
SLPA, OSLOM, Game, and COPRA perform better in low-overlapping-density networks, while SLPA and Game are relatively stable at high overlap; high-density, high-diversity detection remains unresolved.
Takeaways & Limitations
Node-level evaluation reveals over-detection and under-detection, while real-world networks commonly contain relatively few overlapping nodes belonging to only a few communities.
Takeaways & Limitations
NMI and Omega do not provide a satisfying answer about whether overlapping detection captures information that disjoint detection misses.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
Community overlap is a significant feature of real-world networks, where people or nodes can belong to multiple groups or functional communities. This motivates overlapping community detection methods that identify clusters which need not be disjoint.
- 1. INTRODUCTION: Multiple memberships commonly arise in social and biological networks, where individuals or nodes participate in several groups or have multiple functions.Examples include family, friends, and colleagues for people, and multiple functions for biological nodes.
- 1. INTRODUCTION: Online social-network nodes can associate with essentially unlimited numbers of groups, making overlap a fundamental network property.
- 1. INTRODUCTION: Overlap has been shown to be a significant feature of many real-world social networks.
- 1. INTRODUCTION: Overlapping community detection identifies clusters that are not necessarily disjoint, allowing nodes to belong to more than one cluster.
- 1. INTRODUCTION: The paper reviews the state of the art in overlapping community detection algorithms.
2. PRELIMINARIES
The paper represents networks with nodes, edges, and adjacency or weight matrices, then defines overlapping communities as covers allowing multiple memberships. Node–community association may be crisp or fuzzy, although belonging factors can lack clear physical meaning.
- 2. PRELIMINARIES: A network is represented as G = {E, V}, with n nodes and m edges, and its structure encoded by an adjacency matrix A or weight matrix W.For dense graphs m = O(n^2), while sparse networks have m = O(n).
- 2. PRELIMINARIES: An overlapping-community result is a cover C whose clusters may share nodes.
- 2. PRELIMINARIES: Each node has a belonging-factor vector measuring its association strength with each cluster.
- 2. PRELIMINARIES: Fuzzy belonging factors may be artificial weights without clear or unambiguous physical meaning.
- 2. PRELIMINARIES: Crisp assignments use binary node–cluster membership, whereas fuzzy assignments represent community association through belonging factors.
3. ALGORITHMS
The reviewed algorithms detect overlapping communities through clique structure, link or line-graph partitioning, local expansion, seed-based optimization, and statistical significance testing. Their approaches involve trade-offs in structural assumptions, parameter dependence, computational cost, and detection quality.
- Clique Percolation: CPM identifies overlapping communities by connecting adjacent k-cliques that share k−1 members, making it suitable for dense connected network regions.Its implementation can have polynomial complexity in many applications but may fail to terminate on large social networks.
- Clique Percolation: CPM-like methods may act more like localized pattern matching than general community detection because they target specific structures.
- Line Graph and Link Partitioning: Link-partitioning methods infer overlapping nodes when their incident links are assigned to multiple clusters, including approaches based on edge similarity and line-graph transformations.Ahn et al. use Jaccard similarity and hierarchical clustering, while line-graph methods apply node-based community detection to transformed networks.
- Line Graph and Link Partitioning: Link-based detection has no guarantee of higher quality than node-based detection because both rely on an ambiguous definition of community.
- Local Expansion and Optimization: Local expansion and optimization methods grow communities from seeds using local benefit or density functions, with procedures such as RankRemoval followed by Iterative Scan.IS expands or removes nodes until its local density function cannot be improved, while LFM expands from random seeds until a fitness function is locally maximal.
- Local Expansion and Optimization: Several local methods depend strongly on design choices such as seeds, resolution parameters, thresholds, and connectivity checks.MONC merges nested communities during processing, OSLOM tests statistical significance against a configuration-model null graph, and CIS checks connectedness after each iteration.
4. EVALUATION CRITERIA
Evaluating overlapping community covers requires specialized measures because extending disjoint-community metrics is rarely straightforward. Extended NMI and the Omega Index compare covers while accounting for overlap, with both reaching 1 for perfect matching.
- Measures for overlapping covers: Only a few measures are suitable for comparing overlapping communities, with extended NMI and the Omega Index among the most widely used.Other proposed measures include generalized external indexes and the fuzzy rand index.
- Normalized Mutual Information: Each node’s membership in a cover is represented as a binary vector, whose entries define cluster-membership random variables.Their marginal and joint distributions support entropy calculations for comparing covers.
- Normalized Mutual Information: Extended NMI uses conditional entropy and best matching between clusters to compare two overlapping covers.The construction defines entropy of one cluster with respect to the entire other cover and symmetrizes the comparison.
- Normalized Mutual Information: The extended NMI ranges from 0 to 1, with 1 indicating a perfect matching, but does not reduce to standard NMI without overlap.This distinguishes its overlapping-cover formulation from the standard disjoint-case measure.
- Omega Index: The Omega Index evaluates node pairs by whether they belong together in exactly the same number of communities across two covers.It corrects for chance agreement; larger values indicate better matching, 1 indicates perfect matching, and no-overlap cases reduce to ARI.
5. BENCHMARKS
Overlapping-community benchmarks are needed because real-world networks generally lack ground truth, while traditional benchmarks omit important network heterogeneity or overlap. LFR adds heterogeneous degree and community-size distributions and exposes many topology controls, but its equal-membership assumption for overlapping nodes is unrealistic.
- Benchmark motivation: Known ground truth is needed to study algorithm behavior and compare overlapping community detection performance, but real-world networks usually lack it.Observed or online-interaction networks therefore do not provide a clear evaluation reference.
- Benchmark families: The GN benchmark embeds equal-size communities using expected degree and mixing parameter µ, but omits heterogeneity and community overlap.These limitations motivate specialized benchmarks for overlapping community detection.
- Benchmark families: Sawardecker’s GN extension makes edge probability depend monotonically on the number of shared community memberships.Its connection probabilities satisfy p0 < p1 ≤ p2 ≤ · · · .
- Benchmark families: LFR16 introduces power-law heterogeneity in degree and community-size distributions, specifies the fraction of overlapping nodes and their memberships, and provides multiple topology controls.Controls include µ, average degree, maximum degree, and minimum and maximum community sizes.
- Benchmark limitations: LFR better reflects real-world features, but requiring every overlapping node to join the same number of communities is unrealistic.A generalization allows different overlapping nodes to belong to different numbers of communities.
- Benchmark families: A fuzzy benchmark variant converts crisp LFR communities into fuzzy associations by assigning belonging coefficients to node occurrences.The coefficient is linked to the connection-probability formulation used in Sawardecker’s model.
6. TESTS ON SYNTHETIC NETWORKS
Experiments on LFR networks compare 14 crisp-assignment algorithms across community-level and overlapping-node detection. Performance depends on overlap density, community structure, and membership diversity, with SLPA and Game most stable under difficult high-overlap conditions.
- Experimental setup: 14 crisp-assignment algorithms were collected and tested on LFR networks.The experiments evaluate algorithms producing crisp vertex-to-community assignments.
- Community-level evaluation: Higher mixing values generally reduce NMI, whereas increasing network size from 1000 to 5000 typically produces slightly better performance.The mixing effect is attributed to weaker within-community connections at larger µ; NMF is noted as an exception.
- Community-level evaluation: 50% overlap density consistently lowers detection performance relative to 10% overlap density across algorithms.The difference between small and large community-size ranges is more prominent at low overlap density.
- Community-level evaluation: Small community ranges typically yield higher NMI than large ranges, despite the tested algorithms not being based on modularity or extended modularity.The reported gap is substantial for CFinder, LFM, Link, MOSES, Game, iLCD, CIS, and OSLOM.
- Final community ranking: For low overlap density, SLPA, Game, COPRA, GCE, OSLOM, CIS, and LFM rank among the strongest algorithms, while high-overlap performance remains unsatisfactory for most algorithms when Om > 2.For high overlap density, the top seven also include MOSES, CFinder, and Link; most scores are below 0.5 for Om > 2.
- Overlapping-node evaluation: Overlapping-node evaluation reveals precision–recall imbalance: EAGLE under-detects, while Link and other algorithms can over-detect, reducing F-score.SLPA shows stable and good performance at low overlap density, while F-score generally declines as membership diversity increases and drops rapidly for OSLOM at large Om.
7. TESTS ON REAL-WORLD SOCIAL NETWORKS
Tests on real-world social networks show that overlapping-community quality varies with network structure, while most detected overlap is relatively limited in prevalence and membership diversity.
- The high school friendship network has six grade-based communities, with grade 9 divided into white and black student subgroups.
- Overlapping nodes detected in the high school network connect to at least two different groups, including grade boundaries, within-grade subgroup boundaries, and bridges without strong group coherence.
- Quality measures QE_ov and QNi_ov are used for broader social networks because ground truth is unavailable for most of them.
- SLPA, LFM, COPRA, OSLOM, and GCE achieve higher QNi_ov performance on larger networks, while Link and iLCD perform lower on that measure.
- Performance depends on network structure: SLPA, LFM, CIS, and Game perform satisfactorily on sparse P2P networks, whereas COPRA and GCE fail to identify suitable structure there.
- Over-detection can reduce performance: CIS and Link find too many overlapping nodes or memberships, while COPRA, GCE, and UEOC over-detect on specific networks.
- Most algorithms detect fewer than 30% overlapping nodes in real-world social networks, and these nodes typically belong to only 2 or 3 communities.
8. CONCLUSIONS AND DISCUSSIONS
The paper compares overlapping community detection across benchmarks and evaluates both communities and overlapping nodes. It concludes that high-overlap networks remain difficult, while real-world networks typically contain relatively few overlapping nodes.
- The study reviews overlapping community detection algorithms, quality measures, and benchmarks, using complementary community- and node-level evaluation.The node-level framework addresses over-detection and under-detection.
- High overlapping density and diversity remain challenging, leaving detection performance in such networks unresolved.
- Real-world social networks typically contain relatively few overlapping nodes, most belonging to only a few communities.
- The review focuses mostly on unweighted networks, although weighted applications may favor algorithms that explicitly incorporate weights and overlap.CPMw and SLPAw are identified as examples expected to have advantages in such settings.
- Determining when overlapping methods should be applied and how significant overlap is remains a fundamental open question.
- NMI and Omega do not satisfactorily determine whether overlapping detection captures information that disjoint methods would miss.