Format

Send to

Choose Destination
See comment in PubMed Commons below
Pac Symp Biocomput. 2010:166-77.

Exploring biological network dynamics with ensembles of graph partitions.

Author information

1
Center for Bioinformatics and Computational Biology, and Department of Computer Science, University of Maryland, College Park, MD 20742, USA.

Abstract

Unveiling the modular structure of biological networks can reveal important organizational patterns in the cell. Many graph partitioning algorithms have been proposed towards this end. However, most approaches only consider a single, optimal decomposition of the network. In this work, we make use of the multitude of near-optimal clusterings in order to explore the dynamics of network clusterings and how those dynamics relate to the structure of the underlying network. We recast the modularity optimization problem as an integer linear program with diversity constraints. These constraints produce an ensemble of dissimilar but still highly modular clusterings. We apply our approach to four social and biological networks and show how optimal and near-optimal solutions can be used in conjunction to identify deeper community structure in the network, including inter-community dynamics, communities that are especially resilient to change, and core-and-peripheral community members.

PMID:
19908369
[Indexed for MEDLINE]
Free full text
PubMed Commons home

PubMed Commons

0 comments

    Supplemental Content

    Full text links

    Icon for World Scientific Publishing Company
    Loading ...
    Support Center