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

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

Altmetrics

Downloads

61 downloads since deposited on 29 Oct 2008
15 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

Preview Icon on Download
Preview
Filetype: PDF
Size: 1MB
View at publisher
Preview Icon on Download
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