复杂网络社团发现算法的研究及其应用
|
摘要
复杂网络是复杂系统的表现形式，由于这样的网络其节点数量规模较大，而且节点与节点之间的联系较为复杂，所以这样的网络就被称为“复杂网络”。近年来，随着对复杂网络特性的分析不断深入，探索网络中的社团结构逐渐成为研究热点。揭示网络中的社团结构，对于了解网络拓扑结构、分析网络特性、理解网络中各个部分的功能、发现网络中隐藏的规律和预测网络的行为都尤为重要，而揭示社团结构的方法就是利用网络中所已知的特性和信息，将看似无规律的网络划分出隐藏在其中的结构。
由于现存的大部分社团发现算法是基于网络的整体进行计算和划分，其缺点为时间复杂度相对较高，并且其针对性也相对较弱。本论文认为，根据已知的网络局部信息所划分出的“局部社团结构”将对于一些网络的研究更加有针对性。在本文中所提到的“局部社团结构”是指根据提供的网络局部信息，按照某种规则而划分出的社团结构，该结构对所给出的局部信息有着特殊的意义。本文提出了两种针对不同情况的局部社团划分算法：
（1）基于二部图的社团划分算法。二部图结构相对简单，将原网络抽象成为二部图结构的形式，并将原网络的节点作为二部图中的“下集节点”。在已知某两点的条件下，通过二部图得到其对应的初始社团结构，利用初始社团结构在“下集投影”中利用AC算法和边介数等概念，划分出与已知节点相关的“相似性社团”结构。由于在进行局部社团划分时并不需要对整个网络进行计算，该算法在对随机给出的节点进行计算时，有比较好的即时性。此方法适用于发现与已知节点相关的“相似性社团”。
（2）基于中心度发现社团将度中心度与流介数中心度相结合，首先计算出节点的度中心度和流介数中心度，得出网络中的几何中心点和信息、物质或能量在网络上传输时经过路径最多的节点，并将这两个指标作为一个整体考虑，得到这两个指标相对比较大的节点，再在这些节点和其邻居节点上利用CPM社团发现算法，从而发现网络中的“中心社团”。此方法可以发现网络中相对“重要”的社团，这对复杂网络上的传播机理、相继故障等分析都有一定的意义。随后利用该方法分析兰州市公共交通线路网络的中心社团结构，实验结果表明了该社团在网络中的确起到了比较重要的作用。此方法适用于发现网络中的中心社团结构。
A complex network is a simplified representation of a complex system in which theentities of the system are represented by the nodes in the network and the interrelationsbetween entities are represented by the links joining pairs of nodes. Recently, the detec-tion and analysis of community structures in complex networks has attracted a great dealof attention. Network clustering algorithms can be used to analyze the topological struc-tures, understand the functions, recognize the hidden patterns, and predict the behaviorsof complex networks.
Since many algorithms work based on the whole network, and the shortcoming ofthe algorithms is that the time complexity is relatively high, and its relevance is relativelyweak. Here, we consider that the “local community” is more relevance for some networksresearch based on the local information of the networks. This structure is of specialsignificance for the local information given. In this paper, two algorithms are proposed:
(1) Bipartite graphs are relatively simple. We represented complex network asbipartite graph, and transformed the nodes of original network to the “bottom set” ofbipartite graph. In the conditions of two given nodes, we achieve the “relational com-munity”. This algorithm combines the Clauset’s idea of finding local community andconcept with betweenness to find the “relational community” through the network of lo-cal information. Since this algorithm do not need to be calculated base on the entirenetwork, it demonstrates excellent detection when randomly given nodes. This algorithmis for finding the “relational community” of the network.
(2) We combining degree centrality with flow betweenness centrality, a methodto find central community is proposed. Firstly, the node’s degree centrality and flowbetweenness centrality will be calculated for determining the geometric center of thenetwork and the node connecting most paths while information, material or energy trans-mitted through the network. At the same time, these two indicators will be taken intowhole consideration and the node with relatively high indicators will be found out. Then,CPM community discovery algorithm will be used on this node and its neighbor-nodesto find the central community of the network. This method mentioned above can help tofind the relatively”important” community of the network, which has certain significancefor the analysis of the spreading mechanism on the complex network, successive failureand so on. Finally the central community of the public transport network of LanZhou isanalyzed by the method we proposed, and our results indicate that the central commu-nity plays a central role in the whole network. This algorithm is for finding the central community of the network.
由于现存的大部分社团发现算法是基于网络的整体进行计算和划分，其缺点为时间复杂度相对较高，并且其针对性也相对较弱。本论文认为，根据已知的网络局部信息所划分出的“局部社团结构”将对于一些网络的研究更加有针对性。在本文中所提到的“局部社团结构”是指根据提供的网络局部信息，按照某种规则而划分出的社团结构，该结构对所给出的局部信息有着特殊的意义。本文提出了两种针对不同情况的局部社团划分算法：
（1）基于二部图的社团划分算法。二部图结构相对简单，将原网络抽象成为二部图结构的形式，并将原网络的节点作为二部图中的“下集节点”。在已知某两点的条件下，通过二部图得到其对应的初始社团结构，利用初始社团结构在“下集投影”中利用AC算法和边介数等概念，划分出与已知节点相关的“相似性社团”结构。由于在进行局部社团划分时并不需要对整个网络进行计算，该算法在对随机给出的节点进行计算时，有比较好的即时性。此方法适用于发现与已知节点相关的“相似性社团”。
（2）基于中心度发现社团将度中心度与流介数中心度相结合，首先计算出节点的度中心度和流介数中心度，得出网络中的几何中心点和信息、物质或能量在网络上传输时经过路径最多的节点，并将这两个指标作为一个整体考虑，得到这两个指标相对比较大的节点，再在这些节点和其邻居节点上利用CPM社团发现算法，从而发现网络中的“中心社团”。此方法可以发现网络中相对“重要”的社团，这对复杂网络上的传播机理、相继故障等分析都有一定的意义。随后利用该方法分析兰州市公共交通线路网络的中心社团结构，实验结果表明了该社团在网络中的确起到了比较重要的作用。此方法适用于发现网络中的中心社团结构。
A complex network is a simplified representation of a complex system in which theentities of the system are represented by the nodes in the network and the interrelationsbetween entities are represented by the links joining pairs of nodes. Recently, the detec-tion and analysis of community structures in complex networks has attracted a great dealof attention. Network clustering algorithms can be used to analyze the topological struc-tures, understand the functions, recognize the hidden patterns, and predict the behaviorsof complex networks.
Since many algorithms work based on the whole network, and the shortcoming ofthe algorithms is that the time complexity is relatively high, and its relevance is relativelyweak. Here, we consider that the “local community” is more relevance for some networksresearch based on the local information of the networks. This structure is of specialsignificance for the local information given. In this paper, two algorithms are proposed:
(1) Bipartite graphs are relatively simple. We represented complex network asbipartite graph, and transformed the nodes of original network to the “bottom set” ofbipartite graph. In the conditions of two given nodes, we achieve the “relational com-munity”. This algorithm combines the Clauset’s idea of finding local community andconcept with betweenness to find the “relational community” through the network of lo-cal information. Since this algorithm do not need to be calculated base on the entirenetwork, it demonstrates excellent detection when randomly given nodes. This algorithmis for finding the “relational community” of the network.
(2) We combining degree centrality with flow betweenness centrality, a methodto find central community is proposed. Firstly, the node’s degree centrality and flowbetweenness centrality will be calculated for determining the geometric center of thenetwork and the node connecting most paths while information, material or energy trans-mitted through the network. At the same time, these two indicators will be taken intowhole consideration and the node with relatively high indicators will be found out. Then,CPM community discovery algorithm will be used on this node and its neighbor-nodesto find the central community of the network. This method mentioned above can help tofind the relatively”important” community of the network, which has certain significancefor the analysis of the spreading mechanism on the complex network, successive failureand so on. Finally the central community of the public transport network of LanZhou isanalyzed by the method we proposed, and our results indicate that the central commu-nity plays a central role in the whole network. This algorithm is for finding the central community of the network.
引文
[1] Ernesto E. Graph Spectra and the Structure of Complex Networks[M].Cambridge Univer-sity Press,2011,42-81.
[2] Erdo¨s, Rényi. On the evolution of random graphs[J]. Publ. Math. Inst. Hung. Acad. Sci.,1960,5:17-60.
[3] Duncan J, Steven H. Collective Dynamics of Small-world Networks[J]. Nature,1998,393(6684):440-442.
[4] Barabási A, Albert R. Emergency of Scaling in Random Networks[J]. Science,1999,286(5439):509-511.
[5] Costa L. da F, Rodrigues F A, Travieso G, Boas P R V. Characterization of complex net-works: A survey of measurements[J]. Adv.Phys,2007,56:167-242.
[6] Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U. Complex networks: Structureand dynamics[J]. Physics Reports,2006,424:175-308.
[7] Rual J F, Venkatesan K, Hao T, et al. Towards a proteome-scale map of the human pro-tein–protein interaction network[J]. Nature,2005,437:1173-1178.
[8] Bar Y. Making things work: Solving complex problems in a complex world[M]. Cambridge:NECSI Knowledge Press,2004,102-105.
[9] Gibson D, Kleinberg J, Raghavan P. Inferring Web communities from link topology[C]. In:Proceedings of the9th ACM Conference on Hypertext and Hypermedia,1998,225-234.
[10] Flake G W, Lawrence S R, Giles C L,et al. Selforganization and identification of Webcommunities[J]. IEEE Computer,2002,35:66-71.
[11] Adamic L, Adar E. Friends and neighbors on the Web[J]. Social Networks,2003,25:211-230.
[12] Palla G, Barabási A L, Vicsek T. Quantifying social group evolution[J]. Nature,2007,446(7136):664-667.
[13] Newman M E J. Coauthorship networks and patterns of scientific collaboration[J]. Proc. ofthe National Academy of Science,2004,101(1):5200-5205.
[14] Tyler J R, Wilkinson D M, Huberman B A. Email as spectroscopy: Automated discoveryof community structure within organizations[C]. In: Huysman M, Wenger E, Wulf V, eds.Proc. of the1st Int’l Conf. on Communities and Technologies. Dordrecht: Kluwer Aca-demic Publishers,2003,81-96.
[15] Shen Orr S, Milo R, Mangan S, et al. Network motifs in the transcriptional regulation net-work of Escherichia coli[J]. Nature Genetics,2002:31-64.
[16] Milo R, Shen Orr S, Itzkovitz S, et al. Network motifs: Simple building blocks of complexnetworks[J]. Science,2002:298-824.
[17] Ravasz E, Somera A L, Mongru D A. Hierarchical organization of modularity in metabolicnetworks[J]. Science,2002,297(5586):1551-1555.
[18] Wang Z, Zhang J. In serach of the biological significance of modular structures in proteinnetworks[J]. PLOS Computational Biology,2007,3(6):e107.
[19] Spirin V, Mirny L A. Protein complexes and functional modules in molecular networks[J].Proc. of the National Academy of Science,2003,100(21):12123-12128.
[20] Farutin V, Robison K, Lightcap E, et al. Edge-Count probabilities for the identificationof local protein communities and their organization[J]. Proteins: Structure, Function, andBioinformatics,2006,62(3):800-818.
[21] Wilkinson D M, Huberman B A. A method for finding communities of related genes[J].Proc. of the National Academy of Science,2004,101(Suppl.1):5241-5248.
[22] Flake G W, Lawrence S, Giles C L, et al. Self-Organization and identification of Web com-munities[J]. IEEE Computer,2002,35(3):66-71.
[23] Li X, Liu B, Yu P S. Discovering overlapping communities of named entities[C]. In:Fürnkranz J, Scheffer T, Spiliopoulou M, eds. Proc. of the10th European Conf. on Prin-ciples and Practice of Knowledge Discovery in Databases. Berlin: Springer-Verlag,2006.593-600.
[24] Ino H, Kudo M, Nakamura A. Partitioning of Web graphs by community topology[C]. In:Ellis A, Hagino T, eds. Proc. of the14th Int’l Conf. on World Wide Web. New York: ACMPress,2005.661-669.
[25] Kleinberg J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM,1999,46(5):604-632.
[26] Almeida R B, Almeida V A F. A community-aware search engine[C]. In: Feldman SI,Uretsky M, Najork M, Wills CE, eds. Proc. of the13th Int’l Conf. on World Wide Web.New York: ACM Press,2004.413-421.
[27] Sidiropoulos A, Pallis G, Katsaros D, et al. Prefetching in content distribution networks viaWeb communities identification and outsourcing[J]. World Wide Web,2008,11(1):39-70.
[28] Guimera, R, Amaral, L A N. Functional cartography of complex metabolic networks[J].Nature,2005,433:895-900.
[29] Simon H A. The architecture of complexity[J]. Proc. Am. Phil. Soc.,1962,106:467-482.
[30]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006,18-46.
[31]何大韧,刘宗华,汪秉宏.复杂系统与复杂网络[M].北京：高等教育出版社,2009:132-136.
[32] Weiss R S, Jacobson E. A method for the analysis of the structure of complax organiza-tions[J]. Am. Sociol. Rev.,1955,20:661-668.
[33] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in net-works[J]. Proc. of the National Academy of Science,2004,101(9):2658-2663.
[34] Fortunato S, Latora V, Marchiori M. A method to find mommunity structures based oninformation centrality[J]. Phys. Rev. E,2004,70:056104.
[35] Clauset A, Newman M E J, Moore C. Finding community structure in very large net-works[J]. Phys. Rev. E,2004,70:066111.
[36] Fan J, Wang X F. A wavelet view of small-world networks[J]. IEEE Trans. Circuits&Systems-II,2005,52(5):238-242.
[37] Wang Xutao, Chen Guanrong, Lu Hongtao. A very fast algorithm for detecting communitystructures in complex networks[J]. Physica A,2007,384,667-674.
[38]黄丹,谢福鼎,张磊等.一种基于谱平分法的社团划分算法[J].计算机科学,2009,36(11):185-188.
[39] Péter Pollner, Gergely Palla, DánielA′bel, et al. Centrality properties of directed modulemembers in social networks[J]. Physica A,2008,387:4959–4966.
[40] Clauset A, Moore C, Newman M E J. Hierarchical structure and the prediction of missinglinks in networks[J]. Nature,2008,453(7191):98-101.
[41] Chen Duanbing, Shang Mingsheng, Lv Zehua, Fu Yan. Detecting overlapping communitiesof weighted networks via a local algorithm[J]. Physica A,2010,389,4177-4187.
[42] Belkacem S, Alex A, Sergio G. Detecting communities of triangles in complex networksusing spectral optimization[J]. Computer Communications,2010,34(5):629-634.
[43] Kernighan B W, Lin S. A efficient heuristic procedure for partitioning graphs[J]. Bell Sys-tem Technical Journal,1970,49:291-307.
[44] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J].SIAM J. Matrix Anal. Appl,1990,11:430.
[45] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proc.Natl. Acad. Sci.2001,99:7821-7826.
[46] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Phys.Rev. E,2004,69:066133.
[47] Donetti L, Mun oz M A. Detecting network communities: A new systematic and efficientalgorithm.[J] Stat. Mech. Theor. Exp.,2004,2004(10): P10012.
[48] Clauset A. Finding local community structure in networks[J]. Phys. Rev. E,2005,72:026132.
[49] Guillaume J L, Latapy M. Bipartite graphs as models of complex networks[J]. Physica A,2006,371(2):795-813.
[50] Newman M E J. Finding community structure in networks using the eigenvectors of ma-trices[J]. Physical Review E-Statistical, Nonlinear and Soft Matter Physics,2006,74(3):036104.
[51] Zachary W. W. An information flow model for conflict and fission in small groups[J]. Jour-nal of Anthropological Research,1977,33:452-473.
[52] He S, Li S, Ma H. Betweenness centrality in finite components of complex networks[J].Physica A,2009,388(19):4277-4285.
[53] Estrada E, Hatano N. A vibrational approach to node centrality and vulnerability in complexnetworks[J]. Physica A,2010,389(17):3648-3660.
[54] Kermarrec A M, Merrer E L, Sericola B, et al. Second order centrality: Distributed as-sessment of nodes criticity in complex networks[J]. Computer Communications,2011,34:619-628.
[55] Koschutzki D, Schreiber F. Comparison of centralities for biological networks[C]. In: Eds.Proc German Conf Bioinformatics (GCB’04): Giegerich R, Stoye J,2004.199-206.
[56] Kohler E, Mohring R, Skutella M. Traffic networks and flows over time[R]. TU2BerlinTechnical Report.2002.
[57] Palla G, Derenyi I, Farkas I, et al. Uncoving the overlapping community structure of com-plex networks in nature and society[J]. Nature,2005,435:814-818.
[58] Brandes U, Fleischer D. Centrality Measures Based on Current Flow[C]. In: STACS–LNCS: Diekert V. and Durand B,2005,533-544.
[59] Lusseau D, Schneider K, Boisseau O.J, et al. The bottlenose dolphin community of DoubtfulSound features a large proportion of long-lasting associations[J]. Behavioral Ecology andSociobiology.2003,54:396-405.
[60] Nagel K. Particle hopping models and traffic flow theory[J]. Phys Rev E,1996,53(5):4655-4672.
[2] Erdo¨s, Rényi. On the evolution of random graphs[J]. Publ. Math. Inst. Hung. Acad. Sci.,1960,5:17-60.
[3] Duncan J, Steven H. Collective Dynamics of Small-world Networks[J]. Nature,1998,393(6684):440-442.
[4] Barabási A, Albert R. Emergency of Scaling in Random Networks[J]. Science,1999,286(5439):509-511.
[5] Costa L. da F, Rodrigues F A, Travieso G, Boas P R V. Characterization of complex net-works: A survey of measurements[J]. Adv.Phys,2007,56:167-242.
[6] Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U. Complex networks: Structureand dynamics[J]. Physics Reports,2006,424:175-308.
[7] Rual J F, Venkatesan K, Hao T, et al. Towards a proteome-scale map of the human pro-tein–protein interaction network[J]. Nature,2005,437:1173-1178.
[8] Bar Y. Making things work: Solving complex problems in a complex world[M]. Cambridge:NECSI Knowledge Press,2004,102-105.
[9] Gibson D, Kleinberg J, Raghavan P. Inferring Web communities from link topology[C]. In:Proceedings of the9th ACM Conference on Hypertext and Hypermedia,1998,225-234.
[10] Flake G W, Lawrence S R, Giles C L,et al. Selforganization and identification of Webcommunities[J]. IEEE Computer,2002,35:66-71.
[11] Adamic L, Adar E. Friends and neighbors on the Web[J]. Social Networks,2003,25:211-230.
[12] Palla G, Barabási A L, Vicsek T. Quantifying social group evolution[J]. Nature,2007,446(7136):664-667.
[13] Newman M E J. Coauthorship networks and patterns of scientific collaboration[J]. Proc. ofthe National Academy of Science,2004,101(1):5200-5205.
[14] Tyler J R, Wilkinson D M, Huberman B A. Email as spectroscopy: Automated discoveryof community structure within organizations[C]. In: Huysman M, Wenger E, Wulf V, eds.Proc. of the1st Int’l Conf. on Communities and Technologies. Dordrecht: Kluwer Aca-demic Publishers,2003,81-96.
[15] Shen Orr S, Milo R, Mangan S, et al. Network motifs in the transcriptional regulation net-work of Escherichia coli[J]. Nature Genetics,2002:31-64.
[16] Milo R, Shen Orr S, Itzkovitz S, et al. Network motifs: Simple building blocks of complexnetworks[J]. Science,2002:298-824.
[17] Ravasz E, Somera A L, Mongru D A. Hierarchical organization of modularity in metabolicnetworks[J]. Science,2002,297(5586):1551-1555.
[18] Wang Z, Zhang J. In serach of the biological significance of modular structures in proteinnetworks[J]. PLOS Computational Biology,2007,3(6):e107.
[19] Spirin V, Mirny L A. Protein complexes and functional modules in molecular networks[J].Proc. of the National Academy of Science,2003,100(21):12123-12128.
[20] Farutin V, Robison K, Lightcap E, et al. Edge-Count probabilities for the identificationof local protein communities and their organization[J]. Proteins: Structure, Function, andBioinformatics,2006,62(3):800-818.
[21] Wilkinson D M, Huberman B A. A method for finding communities of related genes[J].Proc. of the National Academy of Science,2004,101(Suppl.1):5241-5248.
[22] Flake G W, Lawrence S, Giles C L, et al. Self-Organization and identification of Web com-munities[J]. IEEE Computer,2002,35(3):66-71.
[23] Li X, Liu B, Yu P S. Discovering overlapping communities of named entities[C]. In:Fürnkranz J, Scheffer T, Spiliopoulou M, eds. Proc. of the10th European Conf. on Prin-ciples and Practice of Knowledge Discovery in Databases. Berlin: Springer-Verlag,2006.593-600.
[24] Ino H, Kudo M, Nakamura A. Partitioning of Web graphs by community topology[C]. In:Ellis A, Hagino T, eds. Proc. of the14th Int’l Conf. on World Wide Web. New York: ACMPress,2005.661-669.
[25] Kleinberg J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM,1999,46(5):604-632.
[26] Almeida R B, Almeida V A F. A community-aware search engine[C]. In: Feldman SI,Uretsky M, Najork M, Wills CE, eds. Proc. of the13th Int’l Conf. on World Wide Web.New York: ACM Press,2004.413-421.
[27] Sidiropoulos A, Pallis G, Katsaros D, et al. Prefetching in content distribution networks viaWeb communities identification and outsourcing[J]. World Wide Web,2008,11(1):39-70.
[28] Guimera, R, Amaral, L A N. Functional cartography of complex metabolic networks[J].Nature,2005,433:895-900.
[29] Simon H A. The architecture of complexity[J]. Proc. Am. Phil. Soc.,1962,106:467-482.
[30]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006,18-46.
[31]何大韧,刘宗华,汪秉宏.复杂系统与复杂网络[M].北京：高等教育出版社,2009:132-136.
[32] Weiss R S, Jacobson E. A method for the analysis of the structure of complax organiza-tions[J]. Am. Sociol. Rev.,1955,20:661-668.
[33] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in net-works[J]. Proc. of the National Academy of Science,2004,101(9):2658-2663.
[34] Fortunato S, Latora V, Marchiori M. A method to find mommunity structures based oninformation centrality[J]. Phys. Rev. E,2004,70:056104.
[35] Clauset A, Newman M E J, Moore C. Finding community structure in very large net-works[J]. Phys. Rev. E,2004,70:066111.
[36] Fan J, Wang X F. A wavelet view of small-world networks[J]. IEEE Trans. Circuits&Systems-II,2005,52(5):238-242.
[37] Wang Xutao, Chen Guanrong, Lu Hongtao. A very fast algorithm for detecting communitystructures in complex networks[J]. Physica A,2007,384,667-674.
[38]黄丹,谢福鼎,张磊等.一种基于谱平分法的社团划分算法[J].计算机科学,2009,36(11):185-188.
[39] Péter Pollner, Gergely Palla, DánielA′bel, et al. Centrality properties of directed modulemembers in social networks[J]. Physica A,2008,387:4959–4966.
[40] Clauset A, Moore C, Newman M E J. Hierarchical structure and the prediction of missinglinks in networks[J]. Nature,2008,453(7191):98-101.
[41] Chen Duanbing, Shang Mingsheng, Lv Zehua, Fu Yan. Detecting overlapping communitiesof weighted networks via a local algorithm[J]. Physica A,2010,389,4177-4187.
[42] Belkacem S, Alex A, Sergio G. Detecting communities of triangles in complex networksusing spectral optimization[J]. Computer Communications,2010,34(5):629-634.
[43] Kernighan B W, Lin S. A efficient heuristic procedure for partitioning graphs[J]. Bell Sys-tem Technical Journal,1970,49:291-307.
[44] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J].SIAM J. Matrix Anal. Appl,1990,11:430.
[45] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proc.Natl. Acad. Sci.2001,99:7821-7826.
[46] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Phys.Rev. E,2004,69:066133.
[47] Donetti L, Mun oz M A. Detecting network communities: A new systematic and efficientalgorithm.[J] Stat. Mech. Theor. Exp.,2004,2004(10): P10012.
[48] Clauset A. Finding local community structure in networks[J]. Phys. Rev. E,2005,72:026132.
[49] Guillaume J L, Latapy M. Bipartite graphs as models of complex networks[J]. Physica A,2006,371(2):795-813.
[50] Newman M E J. Finding community structure in networks using the eigenvectors of ma-trices[J]. Physical Review E-Statistical, Nonlinear and Soft Matter Physics,2006,74(3):036104.
[51] Zachary W. W. An information flow model for conflict and fission in small groups[J]. Jour-nal of Anthropological Research,1977,33:452-473.
[52] He S, Li S, Ma H. Betweenness centrality in finite components of complex networks[J].Physica A,2009,388(19):4277-4285.
[53] Estrada E, Hatano N. A vibrational approach to node centrality and vulnerability in complexnetworks[J]. Physica A,2010,389(17):3648-3660.
[54] Kermarrec A M, Merrer E L, Sericola B, et al. Second order centrality: Distributed as-sessment of nodes criticity in complex networks[J]. Computer Communications,2011,34:619-628.
[55] Koschutzki D, Schreiber F. Comparison of centralities for biological networks[C]. In: Eds.Proc German Conf Bioinformatics (GCB’04): Giegerich R, Stoye J,2004.199-206.
[56] Kohler E, Mohring R, Skutella M. Traffic networks and flows over time[R]. TU2BerlinTechnical Report.2002.
[57] Palla G, Derenyi I, Farkas I, et al. Uncoving the overlapping community structure of com-plex networks in nature and society[J]. Nature,2005,435:814-818.
[58] Brandes U, Fleischer D. Centrality Measures Based on Current Flow[C]. In: STACS–LNCS: Diekert V. and Durand B,2005,533-544.
[59] Lusseau D, Schneider K, Boisseau O.J, et al. The bottlenose dolphin community of DoubtfulSound features a large proportion of long-lasting associations[J]. Behavioral Ecology andSociobiology.2003,54:396-405.
[60] Nagel K. Particle hopping models and traffic flow theory[J]. Phys Rev E,1996,53(5):4655-4672.