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.

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.

Citations

48 citations in Web of Science®
77 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

57 downloads since deposited on 24 Oct 2008
14 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:05 Apr 2016 12:30
Publisher:American Physical Society
ISSN:1539-3755
Publisher DOI: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
Permanent URL: http://doi.org/10.5167/uzh-4462

Download

[img]
Preview
Filetype: PDF
Size: 1MB
View at publisher
[img]
Preview
Content: Accepted Version
Filetype: PDF
Size: 2MB

TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.

Author Collaborations