Header

UZH-Logo

Maintenance Infos

Multistep greedy algorithm identifies community structure in real-world and computer-generated networks.


Schuetz, P; Caflisch, A (2008). Multistep greedy algorithm identifies community structure in real-world and computer-generated networks. Physical Review E, 78(026112):026112-1.

Abstract

We have recently introduced a multistep extension of the greedy algorithm for modularity optimization. The extension is based on the idea that merging l pairs of communities (l>1) at each iteration prevents premature condensation into few large communities. Here, an empirical formula is presented for the choice of the step width l that generates partitions with (close to) optimal modularity for 17 real-world and 1100 computer-generated networks. Furthermore, an in-depth analysis of the communities of two real-world networks (the metabolic network of the bacterium E. coli and the graph of coappearing words in the titles of papers coauthored by Martin Karplus) provides evidence that the partition obtained by the multistep greedy algorithm is superior to the one generated by the original greedy algorithm not only with respect to modularity, but also according to objective criteria. In other words, the multistep extension of the greedy algorithm reduces the danger of getting trapped in local optima of modularity and generates more reasonable partitions.

Abstract

We have recently introduced a multistep extension of the greedy algorithm for modularity optimization. The extension is based on the idea that merging l pairs of communities (l>1) at each iteration prevents premature condensation into few large communities. Here, an empirical formula is presented for the choice of the step width l that generates partitions with (close to) optimal modularity for 17 real-world and 1100 computer-generated networks. Furthermore, an in-depth analysis of the communities of two real-world networks (the metabolic network of the bacterium E. coli and the graph of coappearing words in the titles of papers coauthored by Martin Karplus) provides evidence that the partition obtained by the multistep greedy algorithm is superior to the one generated by the original greedy algorithm not only with respect to modularity, but also according to objective criteria. In other words, the multistep extension of the greedy algorithm reduces the danger of getting trapped in local optima of modularity and generates more reasonable partitions.

Statistics

Citations

28 citations in Web of Science®
28 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

67 downloads since deposited on 29 Oct 2008
18 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
Uncontrolled Keywords:greedy algorithms; network theory (graphs); nonlinear dynamical systems; optimisation
Language:English
Date:2008
Deposited On:29 Oct 2008 15:36
Last Modified:05 Apr 2016 12:31
Publisher:American Physical Society
ISSN:1539-3755
Publisher DOI:https://doi.org/10.1103/PhysRevE.78.026112
Official URL:http://link.aps.org/abstract/PRE/v78/e026112
PubMed ID:18850902

Download

Download PDF  'Multistep greedy algorithm identifies community structure in real-world and computer-generated networks.'.
Preview
Filetype: PDF
Size: 1MB
View at publisher
Download PDF  'Multistep greedy algorithm identifies community structure in real-world and computer-generated networks.'.
Preview
Content: Accepted Version
Filetype: PDF
Size: 1MB