Navigation auf zora.uzh.ch

Search ZORA

ZORA (Zurich Open Repository and Archive)

Migration von ZORA auf die Software DSpace

ZORA will change to a new software on 8th September 2025. Please note: deadline for new submissions is 21th July 2025!

Information & dates for training courses can be found here: Information on Software Migration.

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.

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
Scopus Subject Areas:Physical Sciences > Statistical and Nonlinear Physics
Physical Sciences > Statistics and Probability
Physical Sciences > Condensed Matter Physics
Language:English
Date:17 April 2008
Deposited On:24 Oct 2008 14:34
Last Modified:02 Jul 2025 03:41
Publisher:American Physical Society
ISSN:1539-3755
OA Status:Green
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 PDF  'Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement.'.
Preview
  • Content: Accepted Version

Metadata Export

Statistics

Citations

Dimensions.ai Metrics
107 citations in Web of Science®
148 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

246 downloads since deposited on 24 Oct 2008
35 downloads since 12 months
Detailed statistics

Authors, Affiliations, Collaborations

Similar Publications