Abstract
Detecting overlapping communities in massive, evolving graphs is a critical challenge for modern network analysis. This paper introduces rSLPA (randomized Speaker-Listener Label Propagation Algorithm), a distributed and incremental algorithm designed for this purpose. By replacing the traditional plurality voting mechanism with a "uniform picking" strategy, rSLPA achieves a smoother state transition that allows for efficient incremental updates as the graph structure changes. Experimental results on synthetic benchmarks and large-scale real-world web graphs demonstrate that rSLPA provides significant computational speedups—over 2x faster than static re-computation—while maintaining high detection accuracy.
Introduction
In the era of billion-user social networks and massive web crawls, graphs are characterized by their immense scale and high dynamism. Community detection in these environments faces two primary hurdles: the high computational cost of re-running algorithms on static snapshots and the reality of overlapping communities, where nodes belong to multiple groups simultaneously. Existing distributed frameworks often struggle to provide efficient incremental updates for overlapping structures. This paper addresses this gap with rSLPA.
Methods
The foundation of rSLPA is the Speaker-Listener Label Propagation Algorithm (SLPA). In its standard form, nodes "listen" to their neighbors and adopt the most frequent label through plurality voting. However, this "winner-takes-all" approach is highly sensitive to minor graph perturbations, making incremental updates unstable.
Smoothing via Uniform Picking
The key innovation in rSLPA is "Smoothing via Uniform Picking." Instead of selecting the most frequent label, a node picks a label from a neighbor's history uniformly at random. This ensures that the probability of adopting a label is proportional to its frequency in the neighborhood, creating a more stable and mathematically trackable state.
As illustrated in Figure 6, the uniform-picking approach (b) distributes winning probabilities across a wider range of labels compared to the rigid original voting (a). This probabilistic "smoothing" is what enables the algorithm to handle incremental updates effectively.
Incremental Update Logic
The update process itself is categorized into three scenarios when edges are added or deleted:
- Category 1 (No change): Nodes with no neighborhood changes retain their labels.
- Category 2 (Lost neighbors): Nodes that lose a neighbor providing their current label pick a new one from the remaining neighbors.
- Category 3 (New neighbors): Nodes gaining new neighbors perform a probabilistic "coin flip" to decide whether to adopt a new label or keep the old one.
The general flow of receiving labels and updating the internal label set $L_i$ is shown in Figure 1. By implementing this logic in a distributed MapReduce-style framework (Spark), the authors reduce communication overhead from $O(|E|)$ to $O(|V|)$ per iteration.
Experimental Evaluation
The authors evaluated rSLPA using two primary sources:
- Synthetic Data: LFR Benchmark graphs (10k to 50k nodes) with varying overlap parameters.
- Real-World Data: The EU-2015-TPD dataset, a massive web crawl with 6.6 million nodes and 170 million edges.
Key Results
- Accuracy: rSLPA achieved Normalized Mutual Information (NMI) scores exceeding 0.8 on most synthetic benchmarks, matching or exceeding the original SLPA's performance.
- Static Speedup: On the EU-2015-TPD dataset, rSLPA was more than twice as fast as the original SLPA for static detection.
- Incremental Efficiency: The incremental update approach demonstrated clear superiority. For a batch of $10^5$ edge updates, the incremental method took approximately 150 seconds, compared to 250 seconds for a full re-run. This advantage scales with the size and frequency of graph updates.
Conclusion and Future Work
rSLPA provides a robust solution for overlapping community detection in large-scale dynamic graphs. By leveraging probabilistic smoothing and a distributed architecture, it enables efficient incremental updates without sacrificing accuracy. Future work includes extending the algorithm to natively support weighted and directed graphs and exploring adaptive iteration counts for varying graph complexities.
Summary updated