Module detection in complex networks using integer optimisation
Tóm tắt
The detection of modules or community structure is widely used to reveal the underlying properties of complex networks in biology, as well as physical and social sciences. Since the adoption of modularity as a measure of network topological properties, several methodologies for the discovery of community structure based on modularity maximisation have been developed. However, satisfactory partitions of large graphs with modest computational resources are particularly challenging due to the NP-hard nature of the related optimisation problem. Furthermore, it has been suggested that optimising the modularity metric can reach a resolution limit whereby the algorithm fails to detect smaller communities than a specific size in large networks. We present a novel solution approach to identify community structure in large complex networks and address resolution limitations in module detection. The proposed algorithm employs modularity to express network community structure and it is based on mixed integer optimisation models. The solution procedure is extended through an iterative procedure to diminish effects that tend to agglomerate smaller modules (resolution limitations). A comprehensive comparative analysis of methodologies for module detection based on modularity maximisation shows that our approach outperforms previously reported methods. Furthermore, in contrast to previous reports, we propose a strategy to handle resolution limitations in modularity maximisation. Overall, we illustrate ways to improve existing methodologies for community structure identification so as to increase its efficiency and applicability.
Tài liệu tham khảo
Barabasi AL, Albert R: Emergence of scaling in random networks. Science. 1999, 286: 509-512. 10.1126/science.286.5439.509
Spirin V, Gelfand MS, Mironov AA, Mirny LA: A metabolic network in the evolutionary context: multiscale structure and modularity. Proc Natl Acad Sci USA. 2006, 103: 8774-8779. 10.1073/pnas.0510258103
Guimera R, Amaral LAN: Functional cartography of complex metabolic networks. Nature. 2005, 433: 895-900. 10.1038/nature03288
Sales-Pardo M, Guimera R, Moreira AA, Amaral LA: Extracting the hierarchical organization of complex systems. Proc Natl Acad Sci USA. 2007, 104: 15224-15229. 10.1073/pnas.0703740104
Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U: Superfamilies of evolved and designed networks. Science. 2004, 303: 1538-1542. 10.1126/science.1089167
Grunwald S, Speer A, Ackermann J, Koch I: Petri net modelling of gene regulation of the Duchenne muscular dystrophy. Biosystems. 2008, 92: 189-205. 10.1016/j.biosystems.2008.02.005
von Mering C, Zdobnov EM, Tsoka S, Ciccarelli FD, Pereira-Leal JB, Ouzounis CA, Bork P: Genome evolution reveals biochemical networks and functional modules. Proc Natl Acad Sci USA. 2003, 100: 15428-15433. 10.1073/pnas.2136809100
Ravasz E, Somera AL, Mongru DA, Oltvai ZN, Barabasi AL: Hierarchical Organization of Modularity in Metabolic Networks. Science. 2002, 297: 1551-1555. 10.1126/science.1073374
Newman MEJ: Modularity and community structure in networks. Proc Natl Acad Sci USA. 2006, 103: 8577-8582. 10.1073/pnas.0601602103
Tamames J, Moya A, Valencia A: Modular organization in the reductive evolution of protein-protein interaction networks. Genome Biol. 2007, 8: R94- 10.1186/gb-2007-8-5-r94
Dartnell L, Simeonidis E, Hubank M, Tsoka S, Bogle ID, Papageorgiou LG: Robustness of the p53 network and biological hackers. FEBS Lett. 2005, 579: 3037-3042. 10.1016/j.febslet.2005.03.101
Albert R, Jeong H, Barabasi AL: Error and attack tolerance of complex networks. Nature. 2000, 406: 378-382. 10.1038/35019019
Koonin EV, Wolf YI, Karev GP: The structure of the protein universe and genome evolution. Nature. 2002, 420: 218-223. 10.1038/nature01256
Kunin V, Pereira-Leal JB, Ouzounis CA: Functional Evolution of the Yeast Protein Interaction Network. Molecular Biology and Evolution. 2004, 21: 1171-1176. 10.1093/molbev/msh085
Newman MEJ: The structure of scientific collaboration networks. Proc Natl Acad Sci USA. 2001, 98: 404-409. 10.1073/pnas.021544898
Holme P, Huss M, Jeong H: Subnetwork hierarchies of biochemical pathways. Bioinformatics. 2003, 19: 532-538. 10.1093/bioinformatics/btg033
Fortunato S, Castellano C: Community structure in graphs. Encyclopedia of Complexity and System Science. 2008, arXiv:0712.2716,
Fortunato S: Community detection in graphs. Physics Reports. 2010, 486: 75-174. 10.1016/j.physrep.2009.11.002
Garey MR, Johnson DS: Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979, San Francisco: W.H.Freeman & Co Ltd,
Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang DU: Complex networks: Structure and dynamics. Physics Reports. 2006, 424: 175-308. 10.1016/j.physrep.2005.10.009
Rives AW, Galitski T: Modular organization of cellular networks. Proc Natl Acad Sci USA. 2003, 100: 1128-1133. 10.1073/pnas.0237338100
Gustafsson M, Hornquist M, Lombardi A: Comparison and validation of community structures in complex networks. Physica A. 2006, 367: 559-576. 10.1016/j.physa.2005.12.017
Grafahrend-Belau E, Schreiber F, Heiner M, Sackmann A, Junker BH, Grunwald S, Speer A, Winder K, Koch I: Modularization of biochemical networks based on classification of Petri net t-invariants. BMC Bioinformatics. 2008, 9: 90- 10.1186/1471-2105-9-90
Palla G, Derenyi I, Farkas I, Vicsek T: Uncovering the overlapping community structure of complex networks in nature and society. Nature. 2005, 435: 814-818. 10.1038/nature03607
Newman MEJ, Girvan M: Finding and evaluating community structure in networks. Phys Rev E. 2004, 69: 026113-10.1103/PhysRevE.69.026113. 10.1103/PhysRevE.69.026113
Newman MEJ: Fast algorithm for detecting community structure in networks. Phys Rev E. 2004, 69: 066133-10.1103/PhysRevE.69.066133. 10.1103/PhysRevE.69.066133
Girvan M, Newman MEJ: Community structure in social and biological networks. Proc Natl Acad Sci USA. 2002, 99: 7821-7826. 10.1073/pnas.122653799
Brandes U, Delling D, Gaertler M, Gorke R, Hoefer M, Nikoloski Z: On Modularity Clustering. IEEE Transactions on Knowledge and Data Engineering. 2008, 20: 172-188. 10.1109/TKDE.2007.190689
Cafieri S, Hansen P, Liberti L: Edge ratio and community structure in networks. Phys Rev E. 2010, 81: 026105-10.1103/PhysRevE.81.026105. 10.1103/PhysRevE.81.026105
Xu G, Tsoka S, Papageorgiou LG: Finding community structures in complex networks using mixed integer optimisation. Eur Phys J B. 2007, 60: 231-239. 10.1140/epjb/e2007-00331-0
Medus A, Acuna G, Dorso CO: Detection of community structures in networks via global optimization. Physica A. 2005, 358: 593-604. 10.1016/j.physa.2005.04.022
Duch J, Arenas A: Community detection in complex networks using extremal optimization. Phys Rev E. 2005, 72: 027104-027200. 10.1103/PhysRevE.72.027104
Fortunato S, Barthelemy M: Resolution limit in community detection. Proc Natl Acad Sci USA. 2007, 104: 36-41. 10.1073/pnas.0605965104
Ruan J, Zhang W: Identifying network communities with a high resolution. Phys Rev E. 2008, 77: 016104-10.1103/PhysRevE.77.016104. 10.1103/PhysRevE.77.016104
Arenas A, Fernandez A, Gomez S: Analysis of the structure of complex networks at different resolution levels. New Journal of Physics. 2008, 10: 053039-10.1088/1367-2630/10/5/053039. 10.1088/1367-2630/10/5/053039
Li Z, Zhang S, Wang RS, Zhang XS, Chen L: Quantitative function for community detection. Phys Rev E. 2008, 77: 036109-10.1103/PhysRevE.77.036109. 10.1103/PhysRevE.77.036109
Reichardt J, Bornholdt S: Detecting Fuzzy Community Structures in Complex Networks with a Potts Model. Phys Rev Lett. 2004, 93: 218701- 10.1103/PhysRevLett.93.218701
Kumpula JM, Saramaki J, Kaski K, Kertesz J: Limited resolution in complex network community detection with Potts model approach. Eur Phys J B. 2007, 56: 41-45. 10.1140/epjb/e2007-00088-4
Brooke A, Kendrick D, Meeraus A, Raman R: GAMS: A user's guide. 2003, Washington, DC: GAMS Development Corp,
The GAMS SBB solver. http://www.gams.com/dd/docs/solvers/sbb.pdf
, : ILOG CPLEX10.0 User's Manual. 2006,
Zachary WW: An information flow model for conflict and fission in small groups. J Anthropol Res. 1977, 33: 452-473.
Lusseau D: The emergent properties of a dolphin social network. Biology Letters. 2003, 270: S186-S188.
Lusseau D, Schneider K, Boisseau OJ, Haase P, Slooten E, Dawson SM: The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Can geographic isolation explain this unique trait?. Behavioral Ecology and Sociobiology. 2003, 54: 396-405. 10.1007/s00265-003-0651-y
Knuth DE: The Stanford graphbase: a platform for combinatorial computing. 1993, Reading, MA: Addison-Wesley,
Gleiser PM, Danon L: Community Structure in Jazz. Advances in Complex Systems. 2003, 6: 565-574. 10.1142/S0219525903001067
Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A: Self-similar community structure in a network of human interactions. Phys Rev E. 2003, 68: 065103-10.1103/PhysRevE.68.065103. 10.1103/PhysRevE.68.065103
Shen-Orr SS, Milo R, Mangan S, Alon U: Network motifs in the transcriptional regulation network of Escherichia coli. Nat Genet. 2002, 31: 64-68. 10.1038/ng881
Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U: Network motifs: simple building blocks of complex networks. Science. 2002, 298: 824-827. 10.1126/science.298.5594.824
Jeong H, Tombor B, Albert R, Oltvai ZN, Barabasi AL: The large-scale organization of metabolic networks. Nature. 2000, 407: 651-654. 10.1038/35036627
Xiang J, Hu K, Tang Y: A class of improved algorithms for detecting communities in complex networks. Physica A. 2008, 387: 3327-3334. 10.1016/j.physa.2008.01.105
Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E: Fast unfolding of communities in large networks. J Stat Mech. 2008, P10008-10.1088/1742-5468/2008/10/P10008.
Li C, Li X, Miao Y, Wang Q, Jiang W, Xu C, Li J, Han J, Zhang F, Gong B, Xu L: SubpathwayMiner: a software package for flexible identification of pathways. Nucleic Acids Res. 2009, 37: e131- 10.1093/nar/gkp667
Lancichinetti A, Fortunato S, Radicchi F: Benchmark graphs for testing community detection algorithms. Phys Rev E. 2008, 78: 046110-10.1103/PhysRevE.78.046110. 10.1103/PhysRevE.78.046110
Lancichinetti A, Fortunato S, Kertesz J: Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics. 2009, 11: 033015-10.1088/1367-2630/11/3/033015. 10.1088/1367-2630/11/3/033015
Danon L, Diaz-Guilera A, Duch J, Arenas A: Comparing community structure identification. J Stat Mech. 2005, P09008-10.1088/1742-5468/2005/09/P09008.
Rosvall M, Bergstrom CT: An information-theoretic framework for resolving community structure in complex networks. Proc Natl Acad Sci USA. 2007, 104: 7327-7331. 10.1073/pnas.0611034104
Lozano S, Arenas A, Sanchez A: Mesoscopic structure conditions the emergence of cooperation on social networks. PLoS One. 2008, 3: e1892- 10.1371/journal.pone.0001892
Taylor IW, Linding R, Warde-Farley D, Liu Y, Pesquita C, Faria D, Bull S, Pawson T, Morris Q, Wrana JL: Dynamic modularity in protein interaction networks predicts breast cancer outcome. Nat Biotechnol. 2009, 27: 199-204. 10.1038/nbt.1522
Jiang X, Liu B, Jiang J, Zhao H, Fan M, Zhang J, Fan Z, Jiang T: Modularity in the genetic disease-phenotype network. FEBS Lett. 2008, 582: 2549-2554. 10.1016/j.febslet.2008.06.023
Lee DS, Park J, Kay KA, Christakis NA, Oltvai ZN, Barabasi AL: The implications of human metabolic network topology for disease comorbidity. Proc Natl Acad Sci USA. 2008, 105: 9880-9885. 10.1073/pnas.0802208105
Slonim N, Elemento O, Tavazoie S: Ab initio genotype-phenotype association reveals intrinsic modularity in genetic networks. Mol Syst Biol. 2006, 2: 2006 0005,