Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement

TitleEfficient modularity optimization by multistep greedy algorithm and vertex mover refinement
Publication TypeJournal Article
Year of Publication2008
AuthorsSchuetz P., Caflisch A.
JournalPhysical Review E: Statistical, Nonlinear, and Soft Matter Physics
Volume77
Issue4.2
Pagination046112
Date Published2008 Apr
Type of ArticleResearch Article
ISSN1539-3755
Keywordsclusterization, communities, graph, greedy algorithm, modularity, network analysis
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.

DOI10.1103/PhysRevE.77.046112
pubindex

0096

Alternate JournalPhys. Rev. E
PubMed ID18517695
Full Text PDF: