Source-linked AI summary
SLPA: Uncovering Overlapping Communities in Social Networks via A Speaker-listener Interaction Dynamic Process
Jierui Xie, Boleslaw K. Szymanski, Xiaoming Liu
TL;DR
Overlapping community detection must represent social-network nodes that belong to multiple groups, motivating methods that identify both overlapping nodes and communities. The paper proposes a dynamic label-exchange framework instantiated as SLPA, which uses node memories and speaker-listener interactions. SLPA performs strongly across synthetic and real-world evaluations, identifying overlapping nodes and communities with varied diversity.
Problem
Overlapping social-network structures require detecting both individual nodes with multiple memberships and entire overlapping communities.
Method
SLPA uses dynamic speaker-listener label propagation in which nodes accumulate observed labels in memory before community post-processing.
Results
SLPA achieves the largest F-score for overlapping-node identification across tested mixture levels and the highest Qov on almost all real-world networks.
Takeaways & Limitations
The framework supports efficient detection of overlapping nodes and communities and can be modified for different interaction rules and network types.
Abstract
from arXiv · showhide
Overlap is one of the characteristics 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 novel, general framework to detect and analyze both individual overlapping nodes and entire communities. In this framework, nodes exchange labels according to dynamic interaction rules. A specific implementation called Speaker-listener Label Propagation Algorithm (SLPA1) demonstrates an excellent performance in identifying both overlapping nodes and overlapping communities with different degrees of diversity.
I. INTRODUCTION
Overlapping community detection seeks covers in which nodes may belong to multiple clusters, reflecting the modular and multi-group structure of social networks. Prior approaches include clique-based, local-benefit, divisive, link-partition, fuzzy-clustering, and label-propagation methods.
- A cover is a set of clusters in which each node belongs to at least one cluster.
- The paper proposes an efficient algorithm using network structure alone to identify overlapping nodes and entire overlapping communities.
- CPM detects overlaps by searching for adjacent fully connected subgraphs that share nodes, making it suitable for dense connected parts.
- Local-benefit methods expand seeded communities toward locally optimal density or fitness, but depend on seed quality or a community-size parameter.
- Other approaches include node-splitting divisive clustering, link partitioning, agglomerative clique merging, and fuzzy or optimization-based clustering.
III. SLPA: SPEAKER-LISTENER LABEL PROPAGATION ALGORITHM
SLPA extends label propagation into a speaker-listener interaction process in which nodes accumulate label evidence in memory. Repeated speaking, listening, memory updates, and post-processing produce overlapping memberships.
- SLPA extends LPA, where nodes iteratively adopt neighborhood-majority labels and convergence yields disjoint communities.
- Each SLPA node can speak or listen, retain multiple labels, and favor labels observed more frequently when spreading information.
- SLPA has three stages: memory initialization, repeated speaker-listener interactions, and post-processing to output communities.
- The process initializes each node with its own label, repeatedly selects a listener, gathers one label from each neighbor, and applies speaking and listening rules.
- SLPA reduces to LPA when memory size is one and the stopping rule is convergence of all labels.
- Node memory combines asynchronous-update accuracy with synchronous-update stability and avoids the small-community fragmentation observed in Copra.
A. Stop Criterion
SLPA does not require the original LPA convergence condition for multiple labels. It can stop after collecting sufficient information because special convergence and oscillation states do not affect its stability.
- The original LPA stop criterion does not apply when nodes hold multiple labels.
- SLPA may stop at any time once sufficient information has been collected for post-processing, because convergence to one community or oscillation does not affect stability.
B. Post-processing and Community Detection
SLPA post-processes node memories into label probabilities that represent community-association strengths and can be thresholded for crisp memberships. Its output changes quickly to a stable form as the threshold varies.
- SLPA post-processes stored label information after evolution rather than detecting communities during propagation.
- A node’s memory is converted into a label probability distribution representing its association strength to communities.
- The distribution supports fuzzy communities, while thresholding produces crisp binary community memberships.
- SLPA converges quickly as threshold parameter r varies, with a typically narrow effective range.
- Because the threshold is used only in post-processing, propagation dynamics depend on network structure and interaction rules, while memberships are constrained by node degree.
C. Complexity
SLPA has linear-time complexity in sparse networks, with initialization, dynamic evolution, and post-processing costs governed by the iteration count and network size.
- The initialization of labels requires O(n), where n is the total number of nodes, while the maximum iteration count is set to 100 in experiments.The outer loop uses a user-defined maximum T, treated as a small constant.
- The asynchronous dynamic evolution costs O(T m) on arbitrary networks and O(T n) on sparse networks.Here, m is the total number of edges and n is the number of nodes.
- Post-processing thresholding requires O(T n) operations because each node has a memory of size T.
- The entire algorithm has O(T n) time complexity in sparse networks.A naive implementation scales slightly faster than linearly with n on synthetic networks.
IV. EXPERIMENTS AND RESULTS
Experiments evaluate SLPA on synthetic LFR benchmarks and compare it with CFinder, Copra, and LFM across network mixing and overlap diversity. SLPA achieves the largest F-score and reports quantities closer to benchmark ground truth in the supplied results.
- Experiments use both synthetic and real-world networks, with LFR benchmarks modeling heterogeneous node-degree and community-size distributions.
- The synthetic networks use n = 5000 and k = 10, while the mixing parameter µ varies from 0.1 to 0.3.Community sizes range from 20 to 100, and µ denotes the expected fraction of links connecting a node to other communities.
- SLPA achieves the largest F-score across networks with different mixing levels µ.Its F-score correlates positively with Om, whereas the other algorithms typically show negative correlation.
- The overlap setting fixes overlapping nodes at 10% of the network and varies Om from 2 to 8, with larger Om creating harder detection tasks.
- SLPA is compared with CFinder, Copra, and LFM, using T = 100 and r varied from 0.01 to 0.1 for SLPA.
B. Identifying Overlapping Nodes in Synthetic Networks
Overlapping-node identification is essential for evaluating overlapping communities, so the paper treats it as a binary classification problem and compares algorithms using F-score. SLPA achieves the largest F-score across networks with different mixture levels and remains positively associated with overlap diversity.
- Overlapping-node identification is essential for quantifying the quality of overlapping-community detection.
- The paper evaluates overlapping-node identification as a binary classification problem using F-score, the harmonic mean of precision and recall.
- SLPA achieves the largest F-score in networks with different mixture levels defined by µ.
- SLPA’s F-score has a positive correlation with Om, whereas other algorithms typically show a negative correlation.
C. Identifying Overlapping Communities in Synthetic Networks
On synthetic networks, SLPA achieves higher NMI than the competing algorithms across different network structures. Its NMI decreases relatively slowly as overlapping-node diversity increases, indicating lower sensitivity to Om.
- SLPA’s higher NMI shows that it outperforms other algorithms across network structures with different µ values.
- SLPA’s NMI decreases relatively slowly as Om grows, indicating lower sensitivity to overlapping-node diversity.
- Copra’s NMI drops fastest as Om increases, despite outperforming CFinder and LFM on average.
D. Identifying Overlapping Communities in Real-world Social Networks
On real-world social networks, the paper evaluates overlapping communities with Qov and compares detected community statistics with ground truth. SLPA generally achieves the strongest Qov and reports community counts and memberships close to the ground truth, while detected overlap diversity is generally low.
- Qov extends Newman’s Modularity, ranges from 0 to 1, and assigns better performance to larger values.
- SLPA achieves the highest Qov in almost all test networks, except jazz, where it is 0.01 below Copra.
- SLPA outperforms Copra by > 0.1 on Karate, celegans, and email networks.
- All algorithms indicate that overlapping-node diversity in the tested social networks is small, close to 2, although detected overlap counts differ.
- SLPA identifies fewer overlapping nodes than CFinder, reflecting a stricter concept of overlap.
- SLPA’s community counts agree with other non-overlapping detection algorithms, consistent with relatively low overlap degree in these networks.
V. CONCLUSIONS
The paper presents a dynamic interaction process and SLPA for efficient overlapping-community detection. The framework can accommodate different interaction rules and network types, with fuzzy hierarchy and temporal community detection identified as future directions.
- The paper presents a dynamic interaction process and SLPA for efficient and effective overlapping-community detection.
- The process can be modified through different speaker, listening, memory-update, stopping, and post-processing rules.
- The framework can accommodate different network types, including k-partite graphs.
- Future research directions include fuzzy hierarchy detection and temporal community detection.