Source-linked AI summary
Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
Philipp Schuetz, Amedeo Caflisch
TL;DR
Community detection by modularity optimization needs methods that avoid premature condensation into a few large communities while retaining efficient search. The paper introduces multistep greedy merging combined with vertex-by-vertex refinement, and reports higher modularity solutions than previously reported, with the combined method outperforming commonly used generic techniques on all but the smallest of seven examples.
Problem
The paper addresses premature condensation into a few large communities during greedy modularity optimization.
Method
The method combines multistep merging of more than one community pair per iteration with a posteriori vertex-by-vertex refinement.
Results
On seven networks with previously published modularity values, MSG-VM outperforms all other frequently used generic techniques except for the smallest example.
Takeaways & Limitations
MSG-VM is an efficient tool for finding network partitions with higher modularity values than previously reported.
Abstract
from arXiv · showhide
Identifying strongly connected substructures in large networks provides insight into their coarse-grained organization. Several approaches based on the optimization of a quality function, e.g., the modularity, have been proposed. We present here a multistep extension of the greedy algorithm (MSG) that allows the merging of more than one pair of communities at each iteration step. The essential idea is to prevent the premature condensation into few large communities. Upon convergence of the MSG a simple refinement procedure called "vertex mover" (VM) is used for reassigning vertices to neighboring communities to improve the final modularity value. With an appropriate choice of the step width, the combined MSG-VM algorithm is able to find solutions of higher modularity than those reported previously. The multistep extension does not alter the scaling of computational cost of the greedy algorithm.
I. INTR ODUCTION
Modularity-based community detection seeks partitions with unusually many within-community edges, but exact optimization is computationally difficult and standard greedy search can miss high-modularity solutions. The paper therefore enhances greedy optimization with multistep merging and local refinement.
- Modularity compares the observed fraction of within-community edges with its random-network expectation under the same degree distribution.
- The partition with the highest modularity is treated as the optimal splitting, although finding that optimum for a generic network is computationally demanding.
- The greedy algorithm is among the fastest modularity-optimization techniques, but often fails to find solutions with the highest modularity value.
- Modularity-based methods can suffer a resolution limit that amalgamates small modules into larger ones.
- The paper enhances greedy optimization with a multistep feature and local refinement to obtain partitions with higher modularity values than previously reported.
results
The study evaluates its methods on real-world undirected networks and compares their performance with previously published results. The paper notes that extension to directed networks is straightforward.
- The evaluation uses a set of real-world networks and compares the results with other published results.
- All networks in the paper are treated as undirected.
- The extension to directed networks is described as straightforward.
A. Multistep Greedy algorithm (MSG)
The multistep greedy algorithm merges several favorable, non-overlapping community pairs within one iteration instead of repeatedly making only one merge. Multiple level choices and exclusion rules limit premature condensation into a few large communities while preserving efficient updates.
- MSG permits simultaneous merging of multiple pairs, while the touched-community exclusion rule prevents a community from appearing in another pair during the same iteration.
- MSG starts with each vertex as its own community and computes modularity changes for merging connected community pairs.Nonconnected pairs are ignored.
- After each merge, MSG updates only affected modularity-change elements, and its convergence criterion is that all remaining pairwise merges decrease modularity.
- Multiple levels promote concurrent formation of community centers and hinder condensation into a few large communities.
- The implementation uses sorted sets and row structures to extract favorable modularity changes efficiently while maintaining community-link information.The paper states that set elements can be found or inserted in O(log(n)) time and extremal entries in constant time.
- At each iteration, MSG selects positive modularity changes among the best l levels and merges pairs in descending priority.The level parameter l remains constant during an iteration.
C. Running time estimation of MSG
MSG retains the classical greedy algorithm’s asymptotic running-time scaling. Its iterative phase has expected complexity O(DM log(N)), with merging processes contributing at most O(M log(N)) per round.
- Running-time components: Each community-merging event contributes O((d_i + d_j) log(N)) to the running time.Here d_i and d_j denote the relevant community degree quantities.
- Running-time components: All merging processes in one MSG algorithm round contribute at most O(M log(N)).The bound follows because the sum of community-degree values is twice the number of distinct edges.
- Overall complexity: At most D algorithm rounds are required, giving the iterative phase an expected complexity of O(DM log(N)).D is the dendrogram depth of the communities.
- Initialization: Initialization contributes O(M log(N)) in the worst case.This includes constructing the initial level set and related initialization data.
- Comparison: MSG has the same worst-case running-time expectation and complexity as the classical greedy algorithm.The paper identifies the classical greedy algorithm as the fastest among published modularity-optimization strategies cited there.
F. Estimation of VM running time
The VM refinement evaluates modularity changes for moving vertices to neighboring communities. Its per-vertex cost is proportional to vertex degree, while the number of required iterations cannot be estimated in advance.
- Per-vertex cost: For one vertex, evaluating reassignment to neighboring communities takes time proportional to its degree.The calculation parses the vertex’s edge list and uses community-affiliation information to compute modularity changes.
- Scope of estimation: The number of VM iterations needed cannot be estimated because it depends on convergence behavior.The supplied passage states that the number of needed iterations is not possible to estimate.
- Empirical behavior: The VM running time depends on the quality of the MSG result.In the tested examples, VM was at least one order of magnitude faster than MSG and took less than one minute on the largest networks studied.
I I I. RESUL TS
Across the tested networks, MSG-VM generally improves modularity over classical greedy optimization and previously published results while avoiding condensation into a few large communities. Its modularity depends only weakly on the level parameter for large networks, and its running time is usually lower than greedy’s.
- Community structure: The MSG-VM partition’s three largest modules contain 1.5–4 times fewer vertices than those in the greedy partition.The multistep approach therefore prevents condensation into a few large modules in the reported comparisons.
- Level-parameter dependence: For large networks, changing the level parameter changes MSG-VM modularity by less than 2%.The maximum modularity is obtained with l < 300 for 14 of the 19 networks in Table I.
- Modularity results: MSG-VM finds modularity values higher than previously published solutions for five of the seven considered networks.Only the Zachary Karate network yields a smaller modularity value, while the jazz network produces an identical value.
- Modularity results: MSG-VM significantly outperforms the original greedy algorithm on networks without published modularity values.The comparison uses the optimal values obtained by MSG-VM and the classical greedy algorithm.
- Performance and running time: With an appropriate level-parameter choice, MSG-VM is faster than classical greedy in almost all cases while reaching higher modularity.The running-time comparison is based on real-world examples in Table I.
IV. CONCLUSIONS
The authors extend greedy modularity optimization by merging multiple community pairs per step and then applying vertex-based refinement. Across seven networks, MSG-VM generally achieves higher modularity than established methods while retaining comparable computational cost.
- Method: The multistep extension is intended to prevent premature condensation into too few large communities.
- Method: MSG extends greedy optimization by merging more than one pair of communities at each step.This multistep design is combined with a vertex-by-vertex a posteriori refinement procedure.
- Results: On seven networks with previously published modularity values, MSG-VM outperforms frequently used generic techniques except on the smallest example.
- Results: A single MSG-VM run requires computer time similar to the greedy algorithm.
- Results: In most cases, fewer than 10 independent parallel MSG-VM runs obtain modularity within 1% of the highest value.An empirical formula is provided for choosing the appropriate step width.
- Conclusion: The authors conclude that MSG-VM is an efficient tool for finding network partitions with high modularity.
V. A CKNO WLEDGMENTS
The acknowledgments thank contributors for discussions, technical support, network data, and maintaining the Matterhorn cluster. The authors also acknowledge financial support from the Swiss National Science Foundation.
- Acknowledgments: The authors thank named colleagues for helpful discussions and assistance maintaining the Matterhorn cluster.
- Acknowledgments: The authors thank Arenas, Barabási, Gleiser, and Newman for providing network data.
- Acknowledgments: The work was supported by a Swiss National Science Foundation grant to A.C.