Multistep greedy algorithm identifies community structure in real-world and computer-generated networks

Abstract

We have recently introduced a multistep extension of the greedy algorithm for modularity optimization. The extension is based on the idea that merging l pairs of communities (l>1) at each iteration prevents premature condensation into few large communities. Here, an empirical formula is presented for the choice of the step width l that generates partitions with (close to) optimal modularity for 17 real-world and 1100 computer-generated networks. Furthermore, an in-depth analysis of the communities of two real-world networks (the metabolic network of the bacterium E. coli and the graph of coappearing words in the titles of papers coauthored by Martin Karplus) provides evidence that the partition obtained by the multistep greedy algorithm is superior to the one generated by the original greedy algorithm not only with respect to modularity but also according to objective criteria. In other words, the multistep extension of the greedy algorithm reduces the danger of getting trapped in local optima of modularity and generates more reasonable partitions.

17 pages, 2 figures

References in corpus (18)

• Emergence of scaling in random networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• An index to quantify an individual's scientific research output
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• The diameter of the world wide web
• The large-scale organization of metabolic networks
• Functional cartography of complex metabolic networks
• Resolution limit in community detection
• Comparing community structure identification
• Community detection in complex networks using Extremal Optimization
• Self-similar community structure in organisations
• Community Structure in Jazz
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• Local modularity measure for network clusterizations
• High resolution protein folding with a transferable potential

Cited by in corpus (8)

• Community detection in graphs
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Spectral analysis of deformed random networks
• Combinatorial approach to Modularity
• Detecting network communities beyond assortativity-related attributes
• Multiscale Evolutionary Perturbation Attack on Community Detection
• Detecting hierarchical and overlapping network communities using locally optimal modularity changes
• A framework for community detection in heterogeneous multi-relational networks