Source-linked AI summary
Advanced modularity-specialized label propagation algorithm for detecting communities in networks
Xin Liu, Tsuyoshi Murata
TL;DR
LPAm can favor similarly sized communities and become trapped in poor modularity local maxima. The paper combines LPAm with MSG, which merges multiple community pairs before rerunning LPAm. LPAm+ achieves higher modularity, greater stability, and a speed-accuracy compromise across the evaluated networks.
Problem
LPAm can become trapped in poor local maxima because it favors divisions whose communities have similar total degrees.
Method
LPAm+ combines LPAm with MSG to merge multiple community pairs and repeatedly rerun modularity optimization.
Results
LPAm+ consistently obtains higher maximal and average modularity than LPAm across the evaluated networks, with lower modularity variation between runs.
Takeaways & Limitations
LPAm+ finds the highest reported modularity values in eight of nine tested networks while preserving relatively high speed.
Takeaways & Limitations
LPAm+ requires extra computational time and can be diverted toward suboptimal solutions by MSG's aggressive strategy in Condmat2003.
Abstract
from arXiv · showhide
A modularity-specialized label propagation algorithm (LPAm) for detecting network communities was recently proposed. This promising algorithm offers some desirable qualities. However, LPAm favors community divisions where all communities are similar in total degree and thus it is prone to get stuck in poor local maxima in the modularity space. To escape local maxima, we employ a multistep greedy agglomerative algorithm (MSG) that can merge multiple pairs of communities at a time. Combining LPAm and MSG, we propose an advanced modularity-specialized label propagation algorithm (LPAm+). Experiments show that LPAm+ successfully detects communities with higher modularity values than ever reported in two commonly used real-world networks. Moreover, LPAm+ offers a fair compromise between accuracy and speed.
1. Introduction
Community detection seeks densely connected subnetworks and commonly uses modularity optimization, but exact optimization is intractable. This paper improves LPAm to address its tendency to become trapped in poor modularity local maxima.
- Community detection identifies densely connected subnetworks that are sparsely linked to the rest of a network.
- Modularity optimization searches network divisions for high modularity, a scalar measure of division quality.
- Finding the division with highest modularity is NP-hard, so practical algorithms rely on approximate optimization.
- LPAm combines label propagation with modularity optimization but can become trapped in poor local maxima.
- LPAm+ drives LPAm out of local maxima and detects communities with the highest modularity values in several real-world networks.
2. Modularity
Modularity evaluates a network partition by comparing observed within-community connectivity with connectivity expected under a random null model. It can also be decomposed into community-level contributions.
- Modularity measures the actual fraction of intra-community edges minus its expected fraction in a random null model.
- The network is represented by an adjacency matrix A, node degrees k_u, and labels l_u assigning nodes to communities.
- The null-model edge probability is P_uv = k_uk_v/2m, and the modularity matrix uses B_uv = A_uv − P_uv.
- Modularity can be reformulated as a sum of contributions from all communities.
- Each community contribution depends on its number of intra-community edges I_t and total node degree D_t.
3. LPA
LPA propagates node labels according to neighboring label frequencies, offering near-linear speed but unstable results. LPAm modifies this process to maximize modularity while retaining speed, yet remains vulnerable to poor local maxima.
- LPA starts each node with a unique label and sequentially assigns labels based on the most frequent neighboring label.
- After iterative propagation, nodes sharing labels form the detected communities.
- LPA has near-linear time complexity but is sensitive to update order, producing different solutions across runs.
- LPA can sometimes produce a trivial solution in which all nodes belong to one community.
- LPAm selects labels to maximize modularity, producing monotonic modularity increases while preserving LPA's high speed.
- LPAm remains unstable and tends to become stuck in poor local maxima when communities have similar total degrees.
4. LPAm+
LPAm+ alternates modularity-based label propagation with multistep greedy community merging to escape local maxima. On a toy network, this process reaches the global maximum after successive modularity increases.
- LPAm+: LPAm+ begins with LPAm, then seeks community pairs whose merger increases modularity when propagation reaches a local maximum.
- Toy-network example: 0.399 is the modularity of LPAm's four-community local maximum in the toy network.
- Toy-network example: 0.008 is the modularity increase after merging communities labeled ‘a’ and ‘e’.
- Toy-network example: 0.413 is the final modularity after another LPAm pass reaches the toy network's global maximum.
- LPAm+: MSG simultaneously merges multiple community pairs that provide favorable modularity changes without conflicting higher-gain pairings.
- LPAm+: LPAm+ repeats merging and LPAm refinement until no further modularity improvement is possible.
5. Experiments
Experiments evaluate LPAm+ on real-world networks, comparing modularity, stability, runtime, and scaling with LPAm and previously published methods. LPAm+ consistently improves modularity and stability over LPAm, achieves the highest reported modularity on eight of nine networks, and offers a compromise between accuracy and speed.
- Experimental setup: LPAm+ and LPAm were applied one hundred times to each real-world network, with maximal and average modularity, standard deviation, and average execution time recorded.The networks were treated uniformly as undirected and unweighted, with self-loop edges excluded.
- Modularity and stability: LPAm+ obtained markedly higher maximal and average modularity than LPAm consistently across all tested networks.The authors interpret this pattern as evidence that the local-maximum escape strategy succeeds.
- Modularity and stability: LPAm+ had significantly lower modularity standard deviation than LPAm, with run-to-run differences normally within 1% and at most 5% in extreme cases.The paper therefore reports LPAm+ as much more stable than LPAm.
- Runtime and scaling: LPAm+ has overall time complexity O(mlog^2n) in hierarchical networks where d∼logn, matching MSG and classical greedy agglomerative algorithms.Its runtime combines LPAm propagation and repeated multistep community-merging rounds.
- Comparison with prior methods: For eight of nine networks, LPAm+ found the highest modularity values ever reported; Condmat2003 was the exception, where SS-ML outperformed it.LPAm+ exceeded previously published modularity values particularly on C. elegans and E-mail.
- Comparison with prior methods: LPAm+ is slower than LPAm but offers a fair compromise between accuracy and speed, while VP/LP and SA do not scale to larger networks such as PGP and Condmat2003.The paper attributes the Condmat2003 shortfall possibly to MSG’s overly aggressive diversion toward a suboptimal solution-space region.
6. Conclusion and discussion
LPAm+ combines LPAm with MSG to escape local maxima, improving modularity and stability while retaining relatively high speed. The authors also identify remaining opportunities to improve speed and determinism.
- Contributions: LPAm+ drives LPAm out of local maxima by using MSG to merge communities with similar total degree.The method combines repeated local-maxima escape with renewed LPAm optimization.
- Contributions: LPAm+ improves LPAm's modularity and stability, with extra computational time.The authors describe this as a compromise between accuracy and speed.
- Limitations and future work: LPAm+'s speed could be substantially improved by updating only affected nodes and introducing a stopping threshold.The proposed optimization restricts candidate labels to neighbors' labels and an unused label; experiments found unused labels were never selected.
- Limitations and future work: MSG is not the only possible route for escaping local maxima; a community-reduction method may also be applicable to LPAm.The paper relates this alternative to work on a different algorithm.
- Limitations and future work: Different LPAm+ runs produce similar high modularity values but non-distinct community compositions, especially in large networks.Making the algorithm more deterministic is left for future work.
Appendix A. The label updating rule for driving LPAm out of local maxima
The appendix explains how LPAm can escape local maxima by jointly updating stubborn nodes, an operation equivalent to merging community pairs. MSG accelerates this process by merging multiple pairs simultaneously.
- Local-maxima mechanism: LPAm can become stuck when stubborn nodes refuse to change labels under its updating rule.In the toy example, nodes 4 and 5 each retain label ‘e’ because the modularity update remains unfavorable for switching individually.
- Local-maxima escape: To escape a local maximum, LPAm jointly updates a set of stubborn nodes while keeping them assigned to the same label.This simultaneous compromise allows the blocked configuration to change as a group.
- Local-maxima escape: The terms independent of the stubborn nodes' label can be omitted when deriving the label update that maximizes modularity.The resulting rule focuses on the label-dependent contribution of the selected node set.
- Community merging: Changing the selected stubborn nodes from their current label to a new label is equivalent to merging the corresponding community pairs.The equivalence holds when the new label differs from the current shared label.
- Community merging: In implementation, the algorithm directly merges the community pair producing the greatest modularity increase instead of explicitly identifying and updating stubborn nodes.This converts the label-update interpretation into a greedy community-merging operation.
- Community merging: MSG improves efficiency by simultaneously merging multiple pairs of communities rather than processing stubborn-node groups pair by pair.The technique is adopted from the multistep greedy agglomerative algorithm.