Exploring community structure in biological networks with random graphs

BMC Bioinformatics

Pratha Sah⁴  Lisa O Singh³  Aaron Clauset²  Shweta Bansal¹ 

[1] Fogarty International Center, National Institutes of Health, 20892 Bethesda, MD, USA

[2] Santa Fe Institute, 1399 Hyde Park Rd., 87501 Santa Fe, NM, USA

[3] Department of Computer Science, Georgetown University, 20057 Washington DC, USA

[4] Department of Biology, Georgetown University, 20057 Washington DC, USA

关键词: Benchmark graphs;    Modularity;    Random graphs;    Community structure;    Biological networks;   

Others  :  818340
DOI  :  10.1186/1471-2105-15-220

 received in 2013-12-18, accepted in 2014-05-20,  发布年份 2014

【 摘 要 】

Background

Community structure is ubiquitous in biological networks. There has been an increased interest in unraveling the community structure of biological systems as it may provide important insights into a system’s functional components and the impact of local structures on dynamics at a global scale. Choosing an appropriate community detection algorithm to identify the community structure in an empirical network can be difficult, however, as the many algorithms available are based on a variety of cost functions and are difficult to validate. Even when community structure is identified in an empirical system, disentangling the effect of community structure from other network properties such as clustering coefficient and assortativity can be a challenge.

Results

Here, we develop a generative model to produce undirected, simple, connected graphs with a specified degrees and pattern of communities, while maintaining a graph structure that is as random as possible. Additionally, we demonstrate two important applications of our model: (a) to generate networks that can be used to benchmark existing and new algorithms for detecting communities in biological networks; and (b) to generate null models to serve as random controls when investigating the impact of complex network features beyond the byproduct of degree and modularity in empirical biological networks.

Conclusion

Our model allows for the systematic study of the presence of community structure and its impact on network function and dynamics. This process is a crucial step in unraveling the functional consequences of the structural properties of biological systems and uncovering the mechanisms that drive these systems.

【 授权许可】

   
2014 Sah et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 2.

Figure 3.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

【 参考文献 】

• [1]Proulx SR, Promislow DEL, Phillips PC: Network thinking in ecology and evolution. Trends Ecol Evol 2005, 20(6):345-53.
• [2]Bansal S, Khandelwal S, Meyers LA: Exploring biological network structure with clustered random networks. BMC Bioinformatics 2009, 10:405. BioMed Central Full Text
• [3]Girvan M, Newman MEJ: Community structure in social and biological networks. Proc Nat Acad Sci USA 2002, 99(12):7821-7826.
• [4]Newman M: Mixing patterns in networks. Phys Rev E 2003, 67(2):026126.
• [5]Ravasz E, Somera AL, Oltvai ZN, Barabási AL, Mongru Da: Hierarchical organization of modularity in metabolic networks. Science (New York, NY) 2002, 297(5586):1551-1555. [http://www.ncbi.nlm.nih.gov/pubmed/12202830 webcite]
• [6]Maslov S, Sneppen K: Specificity and stability in topology of protein networks. Science (New York, NY) 2002, 296(5569):910-913.
• [7]Han JDJ, Bertin N, Hao T, Goldberg DS, Berriz GF, Zhang LV, Dupuy D, Walhout AJM, Cusick ME, Roth FP, Vidal M: Evidence for dynamically organized modularity in the yeast protein-protein interaction network. Nature 2004, 430(6995):88-93.
• [8]Shen-Orr SS, Milo R, Mangan S, Alon U: Network motifs in the transcriptional regulation network of Escherichia coli. Nature Genet 2002, 31:64-68.
• [9]Krause AE, Mason DM, Ulanowicz RE, Taylor WW, Frank Ka: Compartments revealed in food-web structure. Nature 2003, 426(6964):282-285.
• [10]Stouffer DB, Sales-Pardo M, Newman MEJ, Guimerà R: Origin of compartmentalization in food webs. Ecology 2010, 91(10):2941-2951.
• [11]Olesen JM, Bascompte J, Dupont YL, Jordano P: The modularity of pollination networks. Proc Nat Acad Sci USA 2007, 104(50):19891-19896.
• [12]Yang J, Leskovec J: Defining and evaluating network communities based on ground-truth. In Proc ACM SIGKDD Workshop Mining Data Semantics - MDS ‘12. New York: ACM Press; 2012:1-8.
• [13]Molloy M, Reed B: A critical point for random graphs with a given degree sequence. Random Struct Algorithms 1995, 6(2–3):161-180.
• [14]Newman M: Assortative mixing in networks. Phys Rev Lett 2002, 89(20):208701.
• [15]Xulvi-Brunet R, Sokolov I: Reshuffling scale-free networks: from random to assortative. Phys Rev E 2004, 70(6):066102. [http://link.aps.org/doi/10.1103/PhysRevE.70.066102 webcite]
• [16]Lancichinetti A, Fortunato S, Radicchi F: Benchmark graphs for testing community detection algorithms. Phys Rev E 2008, 78(4):1-6.
• [17]Bagrow JP: Evaluating local community methods in networks. J Stat Mech Theory Exper 2008, 2008(05):P05001.
• [18]Arenas A, Díaz-Guilera A, Pérez-Vicente C: Synchronization reveals topological scales in complex networks. Phys Rev Lett 2006, 96(11):114102.
• [19]Hintze A, Adami C: Modularity and anti-modularity in networks with arbitrary degree distribution. Biol Direct 2010, 5:32. BioMed Central Full Text
• [20]Sawardecker EN, Sales-Pardo M, Nunes Amaral LA: Detection of node group membership in networks with group overlap. Eur Phys J B 2008, 67(3):277-284. [http://www.springerlink.com/index/10.1140/epjb/e2008-00418-0 webcite]
• [21]Sales-Pardo M, Nunes Amaral LA, Guimerà R: Module identification in bipartite and directed networks. Phys Rev E, Stat Nonlinear Soft Matter Phys 2007, 76(3 Pt 2):036102.
• [22]Zhao H, Gao ZY: Modular effects on epidemic dynamics in small-world networks. Euro Phys Lett (EPL) 2007, 79(3):38002.
• [23]Yan G, Fu ZQ, Ren J, Wang WX: Collective synchronization induced by epidemic dynamics on complex networks with communities. Phys Rev E 2007, 75:016108.
• [24]Chu X, Guan J, Zhang Z, Zhou S: Epidemic spreading in weighted scale-free networks with community structure. J Stat Mech Theory Exper 2009, 2009(07):P07043.
• [25]Salathe M, Jones JH: Dynamics and control of diseases in networks with community structure. PLoS Comput Biol 2010, 6(4):1-11.
• [26]Clauset A, Shalizi CR, Newman MEJ: Power-law distributions in empirical data. SIAM Rev 2009, 51(4):661-703.
• [27]Wang P, Robins G, Pattison P, Lazega E: Exponential random graph models for multilevel networks. Soc Netw 2013, 35:96-115.
• [28]Chatterjee S, Diaconis P: Estimating and understanding exponential random graph models. Ann Stat 2013, 41(5):2428-2461.
• [29]Karrer B, Newman M: Stochastic blockmodels and community structure in networks. Phys Rev E 2011, 83:1-11.
• [30]Newman MEJ: Detecting community structure in networks. Eur Phys J B - Condensed Matter 2004, 38(2):321-330.
• [31]Good BH, de Montjoye YA, Clauset A: Performance of modularity maximization in practical contexts. Phys Rev E 2010, 81(4):046106.
• [32]Zverovich IE, Zverovich VE: Contributions to the theory of graphic sequences. Discrete Math 1992, 105:293-303.
• [33]Chungphaisan V: Conditions for sequences to be r_graphic. Discrete Math 1974, 7:31-39.
• [34]Iványi A: Degree sequences of multigraphs. Annales Univ Sci Budapest Sect Comp 2012, 37:195-214.
• [35]Havel V: A remark on the existence of finite graphs. Casopis Pest Mat 1955, 80:477-480.
• [36]Hakimi S: On realizability of a set of integers as degrees of the vertices of a linear graph. I. J Soc Industrial Appl 1962, 10(3):496-506.
• [37]Gkantsidis C, Mihail M, Zegura E: The Markov chain simulation method for generating connected power law random graphs. In Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments Edited by Ladner RE. SIAM. 2003 2003:16–25
• [38]Taylor R: Constrained Switchings in Graphs. Berlin, Heidlberg: Springer; 1981.
• [39]Barabási AL, Oltvai ZN: Network biology: understanding the cell’s functional organization. Nat Rev Genet 2004, 5(2):101-113.
• [40]Przulj N: Biological network comparison using graphlet degree distribution. Bioinformatics 2007, 23(2):e177-e183.
• [41]Tanaka R: Scale-rich metabolic networks. Phys Rev Lett 2005, 94(16):168101.
• [42]Jing Z, Lin T, Hong Y, Jian-Hua L: The effects of degree correlations on network topologies and robustness. Chinese 2007, 16(12):3571-3580.
• [43]Dorogovtsev S, Mendes J, Oliveira J: Degree-dependent intervertex separation in complex networks. Phys Rev E 2006, 73(5):056122.
• [44]Hołyst J, Sienkiewicz J, Fronczak A, Fronczak P, Suchecki K: Universal scaling of distances in complex networks. Phys Rev E 2005, 72(2):026108.
• [45]Newman MEJ: Communities, modules and large-scale structure in networks. Nat Phys 2011, 8:25-31.
• [46]Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E: Fast unfolding of communities in large networks. J Stat Mech Theory Exper 2008, 2008(10):P10008.
• [47]Clauset A, Newman M, Moore C: Finding community structure in very large networks. Phys Rev E 2004, 70(6):066111.
• [48]Reichardt J, Bornholdt S: Statistical mechanics of community detection. Phys Rev E 2006, 74:1-16.
• [49]Rosvall M, Axelsson D, Bergstrom CT: The map equation. Eur Phys J Special Topics 2010, 178:13-23.
• [50]Raghavan U, Albert R, Kumara S: Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 2007, 76(3):036106. [http://link.aps.org/doi/10.1103/PhysRevE.76.036106 webcite]
• [51]Pons P, Latapy M: Computing communities in large networks using random walks. J Graph Algorithms Appl 2006, 10(2):191-218.
• [52]Downton M, Brennan T: Comparing classifications: an evaluation of several coefficients of partition agreement. Classification Society, Boulder, CO, vol. 4 1980.
• [53]Meilǎ M: Comparing clusterings by the variation of information. Learn Theory Kernel Mach 2003, 2777:173-187.
• [54]Lancichinetti A, Fortunato S: Community detection algorithms: a comparative analysis. Phys Rev E 2009, 80(5):056117.
• [55]Chen J, Zaïane O, Goebel R: Local community identification in social networks. Soc Netw Anal 2009, 237-242.
• [56]Kim M, Leskovec J: The network completion problem: inferring missing nodes and edges in networks. SDM 2011, 47-58.
• [57]Lin W, Kong X, Yu PS, Wu Q, Jia Y, Li C: Community detection in incomplete information networks. In Proc 21st Int Conf World Wide Web - WWW ‘12. New York: ACM Press; 2012:341-341.
• [58]Martinez N: Artifacts or attributes? Effects of resolution on the Little Rock Lake food web. Ecol Monograph 1991, 61(4):367-392.
• [59]Colizza V, Flammini A, Maritan A, Vespignani A: Characterization and modeling of pro-tein-protein interaction networks. Phys A Stat Mech Appl 2005, 352:1-27.
• [60]Jeong H, Tombor B, Albert R, Oltvai ZN, Barabási aL: The large-scale organization of metabolic networks. Nature 2000, 407(6804):651-654.
• [61]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. Behav Ecol Sociobiol 2003, 54(4):396-405.
• [62]Parter M, Kashtan N, Alon U: Environmental variability and modularity of bacterial metabolic networks. BMC Evol Biol 2007, 7:169. BioMed Central Full Text
• [63]Stouffer DB, Bascompte J: Compartmentalization increases food-web persistence. Proc Nat Acad Sci USA 2011, 108(9):3648-3652.
• [64]Williams RJ, Berlow EL, Barabási AL, Martinez ND, Dunne Ja: Two degrees of separation in complex food webs. Proc Nat Acad Sci USA 2002, 99(20):12913-12916.
• [65]Montoya JM, Sole RV: Small world patterns in food webs. J Theor Biol 2002, 214(3):405-412.
• [66]Williams RJ, Martinez ND, Dunne Ja: Food-web structure and network theory: the role of connectance and size. Proc Nat Acad Sci USA 2002, 99(20):12917-12922.
• [67]Khor S: Concurrency and network disassortativity. Artif Life 2010, 16(3):225-232.
• [68]Wuchty S, Barabási AL, Ferdig MT: Stable evolutionary signal in a yeast protein interaction network. BMC Evol Biol 2006, 6:8. BioMed Central Full Text
• [69]Wagner A, Fell DA: The small world inside large metabolic networks. Proc Biol Sci R Soc 2001, 268(1478):1803-1810.
• [70]Croft D, James R, Ward AJW, Botham MS, Mawdsley D, Krause J: Assortaive interactions and social networks in fish. Oecologia 2005, 143:211-219.
• [71]Newman M: Properties of highly clustered networks. Phys Rev E 2003, 68(2):026121.
• [72]Welch JJ, Waxman D: Modularity and the cost of complexity. Evol Int J Organic Evol 2003, 57(8):1723-1734.
• [73]Krohs U: The cost of modularity. In Functions in Biological and Artificial Worlds: Comparative Philosophical Perspectives. MIT Press; 2009:259-276.
• [74]Aiello W, Chung F, Lu L: A random graph model for massive graphs. In Proc Thirty-Second Annual ACM Symposium on Theory of Computing - STOC ‘00. New York: ACM Press; 2000:171-180.
• [75]Newman MEJ, Strogatz SH, Watts DJ: Random graphs with arbitrary degree distributions and their applications. Phys Rev E 2001, 64(2):026118.