Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement

Abstract

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.

7 pages, parts of text rewritten, illustrations and pseudocode representation of algorithms added

References in corpus (17)

• Emergence of scaling in random networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and 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
• Limited resolution in complex network community detection with Potts model approach

Cited by in corpus (22)

• Community detection in graphs
• A smart local moving algorithm for large-scale modularity-based community detection
• Detecting modules in quantitative bipartite networks: the QuaBiMo algorithm
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Modularity clustering is force-directed layout
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Improved community structure detection using a modified fine tuning strategy
• Surprise maximization reveals the community structure of complex networks
• Exploring the limits of community detection strategies in complex networks
• Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
• Communities in Networks
• Combinatorial approach to Modularity
• Detecting Communities in Tripartite Hypergraphs
• Label propagation for clustering
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Automatic exploration of structural regularities in networks
• The Atlas for the Aspiring Network Scientist
• Detecting hierarchical and overlapping network communities using locally optimal modularity changes
• Correlation-Based Community Detection