Source-linked AI summary
LabelRank: A Stabilized Label Propagation Algorithm for Community Detection in Networks
Jierui Xie, Boleslaw K. Szymanski
TL;DR
Large-network community detection needs efficient methods, yet local label propagation can produce different partitions across runs. LabelRank adds operators to stabilize propagation, and real-world comparisons report improved performance against LPA and MCL.
Problem
Large networks create demand for efficient community detection, but local label propagation's random tie breaking yields different partitions across runs and limits its use for tracking dynamic communities.
Source: §I · p. 1Method
LabelRank propagates label-probability distributions and applies cutoff and conditional-update operators to stabilize the process and produce deterministic partitions.
Source: §I · p. 1, §III · p. 2Results
LabelRank's performance increases over LPA by 28.57% on PGP and 87.1% on Enron Email, and it outperforms MCL on HighSchool, Epinions, and Enron Email by 10%, 20.83%, and 25.93%, respectively.
Source: §IV · p. 5Takeaways & Limitations
LabelRank allows label propagation algorithms to work on a wider range of network structures, including Eva and Epinions.
Source: §IV · p. 5
Abstract
from arXiv · showhide
An important challenge in big data analysis nowadays is detection of cohesive groups in large-scale networks, including social networks, genetic networks, communication networks and so. In this paper, we propose LabelRank, an efficient algorithm detecting communities through label propagation. A set of operators is introduced to control and stabilize the propagation dynamics. These operations resolve the randomness issue in traditional label propagation algorithms (LPA), stabilizing the discovered communities in all runs of the same network. Tests on real-world networks demonstrate that LabelRank significantly improves the quality of detected communities compared to LPA, as well as other popular algorithms.
I. INTRODUCTION
Large online networks require efficient community detection, but global-view methods do not scale to millions of nodes. Local label propagation is efficient but unstable across runs; LabelRank aims to stabilize its output.
I. INTRODUCTION
- The growth of large online social networks creates demand for efficient community detection, while methods requiring a global network view do not scale to networks with millions of nodes.Source: §I · p. 1
- Local label propagation algorithms use only local information and are efficient, but random tie breaking produces different partitions across runs, hindering applications such as tracking communities over time.The instability is described as undesirable in practice and as prohibiting extension to dynamic-network community tracking.Source: §I · p. 1
- LabelRank combines strategies to stabilize LPA with an extension of MCL, producing deterministic partitions.Source: §I · p. 1
II. RELATED WORK
Related work spans multiple community-detection approaches, while LabelRank builds on local label propagation and flow-based MCL. Its design addresses LPA's instability and MCL's scalability concerns.
II. RELATED WORK
- Community detection includes random-walk methods,,, spectral clustering,, [15], and modularity maximization [16], [17], [18], [19], [20]; label propagation and random-walk methods are most relevant here.A review is cited as [25].Source: §II · p. 1
- LPA [4] groups nodes by their most common neighboring label, while COPRA [9] and SLPA [6] allow multiple labels but do not resolve run-to-run randomness.LPA begins with distinct node labels and updates each node to the label most common among its neighbors.Source: §II · p. 1
- Unlike MCL, LabelRank inflates label distributions rather than the network matrix and updates distributions using local information, enabling decentralized computation.Source: §II · p. 1
- To address scalability concerns associated with MCL, LabelRank introduces conditional update and a novel stopping criterion while aiming to preserve LPA-based speed and simplicity.Multi-level Regularized MCL is described as a more complex remedy for the scalability issue.Source: §II · pp. 1–2
III. LABELRANK ALGORITHM
LabelRank propagates probability distributions over labels and combines four operators to produce deterministic communities. Cutoff and conditional updating constrain propagation, while a stopping rule and sparse label storage support efficient execution.
III. LABELRANK ALGORITHM
- LabelRank maintains multiple labels per node, propagates their distributions to neighbors, and groups nodes sharing the same highest-probability label into deterministic communities.Self-loops smooth propagation by including each node’s own label distribution.Source: §III · pp. 2–3
- Inflation raises label probabilities to a power, increasing high-probability labels at the expense of low-probability labels and helping form local subgroups.Inflation alone does not fully resolve the memory inefficiency of storing many labels.Source: §III · p. 2
- Cutoff removes labels below threshold r, reducing space complexity from quadratic to linear and typically leaving fewer than three labels per node at r = 0.1.The implementation stores variable-length label vectors rather than a full n × n label matrix.Source: §III · pp. 2–3
- Conditional update preserves high-quality communities by updating only nodes sufficiently different from their neighbors, producing a long-lived high-modularity plateau.The plotted comparison contrasts propagation, inflation, and cutoff alone with those operators plus conditional update.Source: §III · p. 2, Figure 1 · p. 3
- The stopping rule tracks how many nodes update their label distributions and stops when a count repeats often enough or no nodes change.It does not guarantee the best modularity, but the paper reports that it almost always returns satisfying results, including when network states oscillate.Source: §III · pp. 2–3
- LabelRank runs in O(m) time on average, where m is the number of edges; its local propagation can be distributed across nodes.The reported execution-time tests ran on a single computer; the authors expect further improvement on a parallel platform.Source: §III · p. 4
IV. EVALUATION ON REAL-WORLD NETWORKS
Tests on known-group and larger social networks assess LabelRank against known partitions and competing algorithms. LabelRank improves over LPA and MCL on several reported comparisons, while its performance is described as close to Infomap.
IV. EVALUATION ON REAL-WORLD NETWORKS
- On Zachary’s karate club network, LabelRank recovered the two teacher- and manager-centered communities with Q = 0.37.The network has n = 34 nodes.Source: §IV · p. 4
- HighSchool friendship-network results show good agreement with known partitions; Fig. 4 colors communities against known grade labels 7–12.The pictured network has n = 69 and k = 6.4.Source: §IV · p. 4, Figure 4 · p. 5
- The wider-network comparison includes LPA, MCL, and Infomap, with LabelRank parameters q = 0.5 or 0.6 and in selected from {1, 1.5, 2}.LPA was run 10 times and its best performance reported; MCL's best result over inflation values [1.5, 5] was used.Source: §IV · p. 4
- With the paper’s stabilization strategies, LabelRank, a generalized and stable version of LPA, significantly boosts performance, with increases of 28.57% on PGP and 87.1% on Enron Email.LPA generally performs worse than the other three algorithms and completely fails on Eva and Epinions. The passage says LPA may produce a single giant community and that LabelRank’s conditional update appears to prevent such an output.Source: §IV · p. 5
- 10%, 20.83%, and 25.93%: LabelRank outperforms MCL on HighSchool, Epinions, and Enron Email, respectively.The comparisons use modularity because true partitions are unavailable for most tested networks.Source: §IV · pp. 4–5
- LabelRank and Infomap have close performance; the passage reports LabelRank leads by 10.34% on HighSchool and 9.43% on Epinions, and Infomap leads Epinions by 11.76%.The passage reports both Epinions comparisons as written.Source: §IV · p. 5
V. CONCLUSIONS
The conclusion presents LabelRank's operators as stabilizing and improving LPA, avoiding random output while improving community-detection performance. It identifies evolving-network detection, overlapping communities, and million-node parallelization as planned extensions or ongoing work.
V. CONCLUSIONS
- LabelRank's operators stabilize and boost LPA, avoiding random output and improving community-detection performance.The authors suggest stabilization may provide insights for related label-propagation algorithms, including SLPA and COPRA.Source: §V · p. 5
- The authors are working toward extending LabelRank to evolving networks with streaming data and plan to extend it to overlapping-community detection.They connect possible evolving-network extensions to distributed social-based message routing in ad hoc mobile and P2P networks.Source: §V · p. 6
- The authors report parallelizing LabelRank for networks with millions of nodes.Source: §V · p. 6