Source-linked AI summary
Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
Jierui Xie, Boleslaw K. Szymanski
TL;DR
Large-network community detection needs methods that remain fast while producing useful communities, and LPA provides a nearly linear, simple foundation. The paper adds an active-node speedup and a neighborhood-strength update rule; experiments report faster execution and improved community quality, while the best c remains network-dependent.
Problem
Large-network community detection requires algorithms that keep complexity close to linear while maintaining community quality.
Method
The paper improves LPA by skipping unnecessary updates through an active-node list and weighting candidate labels with local neighborhood connectivity controlled by c.
Results
The improved algorithm is at least 1.5 times faster on all tested networks and at least 6 times faster on larger networks, while community quality improves for most tested networks.
Takeaways & Limitations
Positive neighborhood strength is especially beneficial on real-world networks with a sufficiently large fraction of highly clustered nodes.
Abstract
from arXiv · showhide
Studies of community structure and evolution in large social networks require a fast and accurate algorithm for community detection. As the size of analyzed communities grows, complexity of the community detection algorithm needs to be kept close to linear. The Label Propagation Algorithm (LPA) has the benefits of nearly-linear running time and easy implementation, thus it forms a good basis for efficient community detection methods. In this paper, we propose new update rule and label propagation criterion in LPA to improve both its computational efficiency and the quality of communities that it detects. The speed is optimized by avoiding unnecessary updates performed by the original algorithm. This change reduces significantly (by order of magnitude for large networks) the number of iterations that the algorithm executes. We also evaluate our generalization of the LPA update rule that takes into account, with varying strength, connections to the neighborhood of a node considering a new label. Experiments on computer generated networks and a wide range of social networks show that our new rule improves the quality of the detected communities compared to those found by the original LPA. The benefit of considering positive neighborhood strength is pronounced especially on real-world networks containing sufficiently large fraction of nodes with high clustering coefficient.
I. INTRODUCTION
Community detection seeks dense within-group and sparse between-group structures, but scalable detection remains difficult because many methods are expensive. LPA offers a fast, parameter-free basis, and this paper enhances it with update rules targeting speed and community quality.
- Community detection is difficult to scale because algorithms with O(n^2) complexity become prohibitively expensive on large networks.
- LPA assigns each node a unique label and iteratively adopts the majority label among its neighbors, yielding communities from connected nodes sharing labels.
- Prior community-detection approaches include hierarchical, greedy modularity, random-walk, spectral, spin-model, and label-propagation methods with differing computational costs and assumptions.
- LPA uses network structure alone without parameters or objective-function optimization, while retaining nearly linear execution for sparse networks.
- The paper enhances LPA with new update and label-propagation rules intended to increase execution speed and improve detected-community quality.
III. IMPROVING THE SPEED OF LPA
The speed improvement avoids updating nodes whose labels would not change by maintaining an active-node list. This preserves the algorithm’s complexity while substantially reducing iterations on tested social networks.
- The improvement avoids unnecessary updates because interior nodes and passive boundary nodes would not change labels during attempted updates.Nodes are classified as passive interior, passive boundary, or active boundary.
- An active-node list stores currently active nodes, removes nodes that become passive, and adds passive boundary neighbors that become active.
- Convergence occurs when every node is passive, detected in O(1) time by checking whether the active-node list is empty.
- The improved algorithm retains the original complexity: initialization takes O(n), node selection takes O(1), and updating a node and neighbors takes O(d_i).
- 6 or more times faster on larger tested networks, including email, eva, CA-GrQc, and PGP, while achieving at least a 1.5-fold speed improvement on all tested networks.For networks up to ten thousands of nodes, the scaled iteration count remains below 3.
A. Neighborhood Strength Driven LPA
The generalized LPA rule scores candidate labels using both direct connections and a node’s neighborhood connectivity. A parameter c controls the strength of this additional neighborhood information, but selecting it remains non-trivial.
- The generalized rule evaluates a candidate label through sub-communities of neighbors that share that label and are connected to the updating node.
- The score combines the direct link from node j to node i with a neighborhood-strength term based on links from j to node i’s other neighbors.
- c ranges from 0 to 1 and controls how strongly links from a neighbor to the updating node’s neighborhood affect its label influence.At c = 0, the rule reduces to original LPA; at c = 1, all neighborhood links receive equal weight.
- The rule remains local because it excludes links from the considered neighbor to its own or other communities and does not use links outside the updating node’s neighborhood.
- Choosing c is non-trivial because asynchronous choices and ties can trap LPA in local minima, creating a trade-off between rapid convergence and solution quality.
V. EVALUATION OF PERFORMANCE
The evaluation incorporates the generalized rule into the modified LPA framework and examines multiple values of c under asynchronous updating. Random node and tie choices can affect the detected communities by trapping runs in local minima.
- The experiments test c values {0, 0.05, 0.25, 0.65, 0.8, 1} within the modified LPA framework on generated and real-world networks.
- For c = 1, all links are treated as equally important, whereas c = 0 corresponds to the original LPA weighting.
- Asynchronous updating introduces choices of the next node and, when scores tie, the final label; these choices can lead runs to different local minima.
A. Tests on Computer Generated Networks
The experiments use LFR benchmark networks because their heterogeneous degree and community-size distributions resemble real-world networks while retaining known ground-truth labels.
- LFR networks provide pre-assigned true labels, enabling direct evaluation of detected communities.Their community structures are known by construction.
- The benchmark reproduces heterogeneous node degrees and community sizes found in many real-world networks.
1) Benchmark networks and quality measures:
The benchmark compares generalized LPA settings and reference algorithms on LFR networks using partition-quality measures that assess agreement with known communities.
- Benchmark networks and quality measures: NMI measures the information correctly extracted by a detected partition, while ARI measures agreement between node pairs after chance adjustment.
- Benchmark networks and quality measures: Figures 1 and 3 report NMI for LPA variants and different detection algorithms on LFR networks with N = 1000 and < k >= 5.
- Benchmark networks and quality measures: NMI and ARI both equal 1 for a perfect match and 0 for a random or independent partition.
- Benchmark networks and quality measures: The experiments include ExtOpt and MCL as reference algorithms alongside generalized LPA variants.ExtOpt is a modularity-maximization method, while MCL performs well and is fast in practice.
2) Performance analysis:
Positive neighborhood strength improves generalized LPA performance as benchmark community structure becomes harder to detect, with ARI showing sharper differences than NMI.
- Performance analysis: When µ exceeds 0.35, LPA with c > 0 performs better, remaining stable for 0.3 < µ ≤0.5.The paper links this stability to changing clustering coefficients and weaker majority-rule effects.
- Performance analysis: For µ > 0.5, c = 0 usually produces a single community and very low average performance.
- Performance analysis: LPA outperforms MCL and ExtOpt consistently for µ ≤0.5, while positive neighborhood strength extends its advantage to µ = 0.65.Beyond µ = 0.65, LPA variants almost always find the trivial single-community solution.
- Performance analysis: ARI is more sensitive than NMI to algorithmic performance changes, especially for LPA with c = 0.
B. Tests on Real-world Social Networks
On real-world networks, positive neighborhood strength generally improves modularity over original LPA, although the best setting depends on the network.
- Maximum performance: The experiments repeat each run 100 times and measure detected-community quality with modularity Q.
- Maximum performance: Higher modularity is obtained with c = 1.0 or c = 0.25 than with c = 0 on most tested networks.Karate reaches 0.416 for all weights, lesmis favors c = 0.05, and football slightly favors c = 0.
- Average performance: Across repeated runs on networks with at least 100 nodes, c > 0 achieves higher average performance than LPA with c = 0.Complete-consensus runs yielding Q=0 rarely occur for c > 0.
2) Average performance and stability:
Positive neighborhood weight c generally improves average modularity and stability over standard LPA, with the strongest pattern linked to networks containing many highly clustered nodes.
- Average performance and stability: c>0 obtains higher average performance than LPA with c=0 on most networks, except the football network.As c increases, the algorithm becomes more stable on most tested networks.
- Average performance and stability: For networks with n>1000, the c producing higher maximum modularity also produces better average performance.
- Average performance and stability: The football network has average clustering coefficient 0.4032, whereas the netscience network has average cc=0.8125.
- Average performance and stability: Networks such as netscience, email, eva, CA-GrQc, and PGP show similar clustering-coefficient distributions and benefit from the new rule.
- Average performance and stability: Community sizes under c>0 follow a power-law distribution, with α about -1.28 for PGP and -1.65 and -0.45 for email.
4) Community size:
The proposed algorithm improves both speed and detected-community quality relative to original LPA, while linking the optimal c to clustering-coefficient distributions.
- Community size: The new community detection algorithm improves both speed and detected-community quality compared with original LPA.
- Community size: The generalized update rule incorporates neighborhood information, and both maximum and average community quality improve for most tested networks.
- Community size: The parameter c is related to clustering-coefficient distributions, which helps explain different optimal c values across networks.
- Community size: The selection of c remains incompletely understood and is identified as a subject for further study.