Header

UZH-Logo

Maintenance Infos

Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement.


Schuetz, P; Caflisch, A (2008). Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement. Physical Review E, 77(046112):046112-1-046112-7.

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.

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.

Statistics

Citations

60 citations in Web of Science®
91 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

86 downloads since deposited on 24 Oct 2008
28 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:04 Faculty of Medicine > Department of Biochemistry
07 Faculty of Science > Department of Biochemistry
Dewey Decimal Classification:570 Life sciences; biology
Language:English
Date:17 April 2008
Deposited On:24 Oct 2008 14:34
Last Modified:21 Nov 2017 13:33
Publisher:American Physical Society
ISSN:1539-3755
Publisher DOI:https://doi.org/10.1103/PhysRevE.77.046112
Official URL:http://link.aps.org/abstract/PRE/v77/e046112
Related URLs:http://pre.aps.org/ (Publisher)
PubMed ID:18517695

Download

Download PDF  'Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement.'.
Preview
Filetype: PDF
Size: 1MB
View at publisher
Download PDF  'Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement.'.
Preview
Content: Accepted Version
Filetype: PDF
Size: 2MB