Exploring biological network dynamics with ensembles of graph partitions.
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.
Navlakha
Saket
S
Center for Bioinformatics and Computational Biology, and Department of Computer Science, University of Maryland, College Park, MD 20742, USA.
Kingsford
Carl
C
D000465:Algorithms; D002540:Cerebral Cortex / Q000033:anatomy & histology; D016000:Cluster Analysis; D019295:Computational Biology; D006801:Humans; D020935:MAP Kinase Signaling System; D053858:Metabolic Networks and Pathways; D008954:Models, Biological; D009415:Nerve Net / Q000033:anatomy & histology; D060066:Protein Interaction Maps; D060756:Social Networking