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.

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.

Citations

23 citations in Web of Science®
26 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

46 downloads since deposited on 29 Oct 2008
12 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:10.1103/PhysRevE.78.026112
Official URL:http://link.aps.org/abstract/PRE/v78/e026112
PubMed ID:18850902
Permanent URL: http://doi.org/10.5167/uzh-4767

Download

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

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