Source-linked AI summary
Towards Linear Time Overlapping Community Detection in Social Networks
Jierui Xie, Boleslaw K. Szymanski
TL;DR
Overlapping memberships make disjoint community detection insufficient for realistic social-network analysis. The paper introduces SLPA, a dynamic speaker-listener label-propagation algorithm with memory and thresholding, and reports linear edge-time scaling and strong node- and community-level performance across synthetic and real-world networks.
Problem
Most community-detection work focuses on disjoint communities despite people belonging to multiple social groups, motivating detection of overlapping structures.
Method
SLPA uses dynamic speaker-listener interactions, node memories, label-frequency thresholding, and network structure to detect overlapping communities and nested hierarchies.
Results
SLPA scales linearly with edges and performs well on node- and community-level overlap across LFR benchmarks and real-world networks, including nested hierarchies.
Takeaways & Limitations
SLPA provides a unified approach for disjoint, overlapping, and nested community structures in unipartite and bipartite networks.
Takeaways & Limitations
SLPA is nondeterministic because of random selections and ties, although it performs well on average.
Abstract
from arXiv · showhide
Membership diversity is a characteristic aspect of social networks in which a person may belong to more than one social group. For this reason, discovering overlapping structures is necessary for realistic social analysis. In this paper, we present a fast algorithm1, called SLPA, for overlapping community detection in large-scale networks. SLPA spreads labels according to dynamic interaction rules. It can be applied to both unipartite and bipartite networks. It is also able to uncover overlapping nested hierarchy. The time complexity of SLPA scales linearly with the number of edges in the network. Experiments in both synthetic and real- world networks show that SLPA has an excellent performance in identifying both node and community level overlapping structures.
1 Introduction
Social networks commonly contain overlapping memberships, but most community-detection research has focused on disjoint communities. The paper therefore proposes detecting overlapping nodes and communities from network structure alone.
- Motivation: Real-world social-network participants commonly belong to multiple groups simultaneously.Examples include family, friends, professional areas, and Internet groups.
- Motivation: Most existing community-detection work has addressed disjoint rather than overlapping communities.
- Contribution: SLPA is proposed to detect both individual overlapping nodes and overlapping communities using only the underlying network structure.The target output is a cover in which each node belongs to at least one cluster.
2 Related Work
Prior overlapping-community methods span clique, local-expansion, fuzzy, link-partitioning, and dynamical approaches, but they differ in assumptions, parameters, and computational costs.
- Taxonomy: Existing methods are categorized into five classes according to how they identify communities.
- Clique Percolation: Clique-percolation methods detect overlapping communities through adjacent fully connected subgraphs, with weighted variants using an intensity threshold.
- Local Expansion: Local-expansion methods grow communities from cores, random nodes, or maximal cliques using density, fitness, or similarity criteria.Reported costs include O(n^2s) for EAGLE and O(mh) for GCE.
- Fuzzy Clustering: Fuzzy-clustering approaches require the number of communities K, while NMF has complexity O(Kn^2) because of matrix multiplication.
- Link Partitioning: Link partitioning builds communities by partitioning edges, with reported complexity O(nkmax^2).Here kmax is the highest degree among n nodes.
- Dynamical Algorithms: Dynamical label-propagation methods update community memberships from neighboring labels, with COPRA requiring O(vm log(vm/n)) per iteration.The parameter v controls the maximum number of communities associated with a node.
3 SLPA: Speaker-listener Label Propagation Algorithm
SLPA extends label propagation with memory-based speaker-listener interactions and thresholded post-processing to discover overlapping communities. Its reported complexity is linear in the number of edges, and it runs substantially faster than GCE on a large network.
- Algorithm Design: SLPA extends LPA by allowing nodes to retain multiple labels instead of updating to a single neighborhood-majority label.This changes disjoint label propagation into a mechanism capable of representing overlap.
- Algorithm Design: Each communication step selects a speaker and listener, with the listener storing the most popular label received from its neighbors.Neighbor labels are sampled according to their occurrence frequencies in speaker memories.
- Post-processing: SLPA runs for a user-defined maximum iteration T, then thresholds label frequencies in node memories to produce crisp communities.Labels occurring below threshold r ∈[0, 0.5] are deleted.
- Properties: The method does not require the number of communities as input and reduces to LPA when each node’s memory has size one.Outputs are nondeterministic because of random selection and ties, while remaining relatively stable empirically when T is greater than 20.
- Complexity: O(Tm) is SLPA’s total time complexity, linear in the number of network edges m.The outer iteration count T is treated as a small constant in the experiments.
- Empirical Scaling: About six minutes were required for SLPA to process a two-million-node Amazon co-purchasing network, making it ten times faster than GCE there.
4 Tests in Synthetic Networks
Synthetic-network tests use the LFR benchmark to compare SLPA with other overlapping-community algorithms using community-level and node-level measures. SLPA remains stable across NMI and Omega, produces community-size distributions closer to the ground truth, and performs well across both community- and node-level evaluations.
- Experimental setup: The experiments use LFR networks with heterogeneous node-degree and community-size distributions, varying overlap diversity through Om from 2 to 8.Increasing Om creates harder detection tasks; networks have n = 5000 and On is set to 10% of nodes.
- Experimental setup: SLPA is compared with eight algorithms using optimal tunable parameters, repeated evaluations, and averaged rankings across membership settings.For SLPA and COPRA, average performance and error bars are reported over ten repetitions; RSM averages algorithm rankings across Om values with equal weights.
- Community-level evaluation: SLPA remains remarkably stable in NMI and Omega as the number of memberships changes, unlike NMF and COPRA, whose behavior is especially measure-sensitive.The rankings based on RSOmega and RSNMI also change among algorithms.
- Community-level evaluation: SLPA, GCE, and NMF typically produce unimodal community-size distributions peaking at CS = 20, matching the LFR ground-truth design better than bimodal alternatives.The benchmark expects community sizes to follow a power law with exponent 1 and range from 20 to 100; competing bimodal distributions include an extra mode at CS 1–5.
- Node-level evaluation: SLPA estimates overlapping-node counts and memberships close to ground truth and achieves the best F-score, including when overlapping nodes belong to many groups.Its F-score is positively correlated with Om, while other algorithms show negative correlation; high precision and recall support the result.
- Overall assessment: Considering NMI, Omega, and F-score together, SLPA performs well on the LFR benchmarks.The F-score ranking keeps SLPA among the top three algorithms, whereas GCE and NMF no longer remain there.
5 Tests in Real-world Social Networks
Experiments on real-world social networks evaluate SLPA’s overlapping-community quality, robustness, bipartite applicability, and ability to recover nested structures. SLPA generally performs strongly, including the highest average overlapping modularity and meaningful hierarchical organization.
- 5.1 Identifying Overlapping Communities in Social Networks: SLPA achieves the highest average QNi_ov among tested methods on real-world social networks.Its QNi_ov performance fluctuates more than on synthetic networks but remains comparatively stable against COPRA.
- 5.1 Identifying Overlapping Communities in Social Networks: COPRA performs poorly on highly sparse P2P networks and fails on Epinions by over-detecting overlapping nodes.CIS and Link also receive low QNi_ov scores after over-detection of overlapping nodes.
- 5.1 Identifying Overlapping Communities in Social Networks: Results across algorithms typically agree on fewer than 30% of overlapping nodes, with each overlapping node belonging to typically 2 or 3 communities.These comparisons use the clustering with the best QNi_ov.
- 5.2 Identifying Overlapping Communities in Bipartite Networks: SLPA demonstrates relatively good performance on Facebook-like and interlocking-directorate bipartite networks while operating directly on the entire bipartite network.COPRA is applied to each node type alternately and is slightly better by 0.03 on one interlocking-network node type but worse by 0.11 on the other.
- 5.3 Identifying Overlapping Nested Communities: In the high school network, SLPA finds a four-level community tree and nested structures explained by grade, race, and sex.For example, C13 is explained by race while its sub-communities account for grade and sex; overlaps remain present despite treemap limitations.
6 Conclusions
The paper introduces SLPA as a dynamic interaction process for unified overlapping community detection. The algorithm supports multiple community structures across unipartite and bipartite networks, while its process can be adapted to other network types.
- SLPA is introduced as a dynamic interaction process underlying an efficient and effective unified overlapping community detection algorithm.
- SLPA analyzes disjoint communities, individual overlapping nodes, overlapping communities, and overlapping nested hierarchies in unipartite and bipartite topologies.
- The underlying SLPA process can be modified for other network types, such as k-partite graphs.Applying SLPA to temporal community detection is identified as future work.