复杂网络社团结构分析方法研究
|
摘要
复杂网络研究作为一个新兴的学科方向,极大地吸引了来自不同学科研究人员的广泛关注。对复杂网络的定性和定量特征的研究,有助于揭示复杂网络表示下的不同复杂系统中普遍存在的一般规律,在生物科学、社会科学等诸多学科中具有重要意义。社团结构是复杂网络的一个关键结构规律,因此准确分析复杂网络的社团结构是复杂网络研究中的一个非常重要的课题。
在复杂网络社团结构的分析研究中,模块度度量(及其变种)起了很重要的作用,催生了一大类重要的社团结构分析方法。但是这类通过对模块度度量(及其变种)优化来获得网络社团划分的方法存在分辨率问题,从而极大地限制了基于模块度方法的有效性和应用广度。
另一方面,目前社团结构分析研究主要集中在无向网络上,系统地直接分析有向网络社团结构的研究还远远不及对无向网络社团结构的分析研究。实际上,当前有向网络社团结构划分的普遍做法是通过简单地忽略有向网络中边的方向,将有向网络当成无向网络分析。这种方法在大多数情况下由于忽略了有向网络中边的方向包含的重要拓扑结构信息,从而无法正确有效地划分网络的社团结构。另外,在有向网络上扩展多数无向网络社团结构的分析方法往往不是简单的工作。
本论文从模块度度量的相关问题出发,将无向二元网络上模块度优化时的分辨率问题的分析扩展到无向加权网络中,并在此基础上提出了一种结合网络预处理的增强型模块度优化社团结构分析方法。通过分析无向网络上的模块度优化产生分辨率问题的条件,提出通过有效地获得关于社团之间边的信息来处理模块度优化时可能产生的分辨率问题。基于网络上的动力学过程反映网络的潜在结构这一事实,利用无向网络上的随机游走过程获取关于社团内部边和社团外部边的信息,并通过边的迭代重加权操作使得网络边的权值不断向社团内部集中,而社团之间的边权值越来越小,从而有效地克服模块度优化时的分辨率问题。实验分析表明,这种结合了网络预处理的无向网络社团分析方法极大地增强了基于模块度优化的无向网络社团结构分析方法的有效性和应用广度。
针对传统的有向网络社团结构分析方法简单忽略边的方向将使得社团划分不准确的问题,提出了一种基于有向网络嵌入的有向网络社团结构分析方法。该方法通过在有向网络上扩展无向网络的网络嵌入分析,从有向网络嵌入目标函数关联的拉普拉斯矩阵中分离出包含了边的方向信息的对称矩阵作为有向网络对等的无向加权网络的邻接矩阵,并导出一种关于有向网络社团结构划分的新模块度定义。一方面,新模块度度量进一步解释了有向网络社团的另一种物理内涵:同一社团内的结点是最大程度保持了有向网络局部结构的相邻结点集合;另一方面,它建立了有向网络与某种无向网络的联系,这种联系表明有向网络的社团结构可以通过应用已有的无向网络社团结构分析方法可靠并且有效地在所导出的无向网络上分析得到。
进一步扩展了基于有向网络嵌入的有向网络社团结构分析方法的分析思路,提出了一种基于边的方向信息抽取的有向网络社团结构分析方法。该方法基于具有社团结构的有向网络上的流运动将更加容易地在社团内部结点之间进行的事实,通过有向网络上的PageRank型随机游走过程有效地抽取有向网络边的方向包含的信息,并采用适当的相似性函数将其转化为边的权值与有向网络中边的互联性集成共同定义有向网络的社团结构。在抽取足够多的关于边的方向信息后,通过忽略边的方向将有向网络的社团划分问题等价为所导出的无向加权网络的社团划分问题,在保持社团结构划分准确性的同时有效地简化了有向网络社团结构划分问题的分析,避免了无向网络分析方法常常难以直接扩展到有向网络社团结构分析中的问题。
在分析前述关于无向网络和有向网络社团结构分析方法的可统一性基础上,提出了一种基于网络结点间消息传递的社团结构分析的一致框架。通过随机游走将网络结点表示成向量空间中的点,并以此有效地定义表达结点属于同一社团可能程度的相似性。利用affinity propagation算法的消息传递机制将网络的社团结构划分问题转换成社团领导者的推选过程。在实际网络和标准测试网络上的分析表明,这种消息传递的网络社团结构分析框架能够:(i)有效地处理分辨率问题,即有效地分析那些通过模块度优化会出现分辨率问题的网络的社团结构;(ii)在一个一致的框架中分析有向网络和无向网络的社团结构;(iii)揭示网络中可能存在的多级社团结构。
As a new emerging discipline, research on complex networks attracts scientists from a varietyof different fields. In fact, studies that can qualitatively and quantitatively characterize complexnetworks will help to unveil the general laws regulating different real systems modeled by complexnetworks, and therefore will be relevant in a number of disciplines (biology, social sciences, etc).Community structure is one of the crucial structural characteristics of complex networks; therefore,accurately analyzing their community structure represents a very relevant topic.
In the research related to the analysis of community structure in complex networks, a measurenamed modularity (and variants) plays a crucial role, and from it a large amount of importantapproaches for analyzing community structure have been derived. However, it has been foundthat the optimization of modularity (and of its variants) suffers from resolution limit. This greatlyreduces the effectiveness and the range of applicability of those modularity based methods.
Additionally, current studies on community structure analysis are mainly focusing on undi-rected networks, thus analyzing community structure in directed networks represents a yet poorlyunexplored direction in this research area. Indeed, so far, the common approach to communitystructure analysis in directed networks has simply proceeded by discarding the direction of edgesand treating directed networks as undirected ones. Such type of approach frequently fails sincesimply discarding edges’direction removes valuable information and thus results in inaccuratecommunity partitions. Furthermore, very often, the extension of methods for community detectionin undirected networks to those for directed networks is far from trivial.
Starting from the issues related to modularity, this thesis extends the analysis of the resolutionlimit from the case of binary undirected networks to that of weighted ones, and thus proposes an en-hanced modularity-based method for community structure analysis via network preprocessing. Byanalyzing the conditions relative to the resolution limit in undirected networks, it can be observedthat the problem can be effectively addressed by acquiring information on inter-community edges.Based on the fact that dynamics events occurring on a network will re?ect its underlying structure,random walks on undirected networks can be used as a surrogate to obtain effective informationon intra-community and inter-community edges. After such information is obtained, iteratively reweighting intra-community and inter-community edges will cause weights to concentrate moreand more into communities, while becoming very small or even vanishing among communities.As a result, the resolution limit problem can be effectively addressed when optimizing modularity.The applications of such a method on real and benchmark networks demonstrate that the effective-ness and the range of applications of using modularity based methods for detecting communitiesin undirected networks is greatly enhanced via network preprocessing.
With respect to the problem of inaccurate communities partitioning by discarding the infor-mation contained in edges’direction, a method for analyzing community structure by directednetwork embedding is then proposed. By extending network embedding for undirected networksto directed ones, this method extracts a symmetric matrix from the Laplacian matrix associatedwith the target function for directed network embedding. Such a symmetric matrix can be re-garded as an adjacency matrix for a weighted undirected network that contains the informationon edge direction in the original directed network. Consequently, a new modularity definitionfor directed networks is derived by reformulating the modularity for undirected networks on theinduced adjacency matrix. This new modularity measure provides on one hand an additional phys-ical meaning of communities in directed networks: nodes in the same community are neighboringnodes that preserve as much as possible the local structure of a network. On the other hand, itdiscloses the relationship between the directed network under study and its induced undirectedone. Therefore, methods designed to partition undirected networks, can successfully, safely andefficiently be applied to directed ones, via the definition of the induced undirected network.
By further extending this idea, another community analysis method for directed networks isproposed. This method is based on the fact that the ?ow on a directed network with a communitystructure will move more easily among nodes within the same community. It thus employs PageR-ank random walks on directed networks as a proxy of ?ow to effectively extract the informationcontained in edges’direction. By choosing a suitable similarity function, the obtained informationis transformed into edges’weight that will be integrated with edges’connectedness to define com-munity structure in directed networks. After the information contained in the edge directions hasbeen extracted iteratively following this procedure, the edge directions can be safely discarded, andthe community partitioning of a directed network can be obtained via partitioning the undirectedweighted network. This strategy simplifies the problem while retaining the accuracy in analyzingcommunity structure in directed networks.
Based on the possible uniformity of the above methods for analyzing community structurein undirected and directed networks, a message passing based unified framework for communitydetection is proposed. In this frame, nodes in a network are expressed in terms of points in avectorial space via random walks on networks. Similarity between nodes can thus be effectivelydefined, and this similarity represents the likelihood of a pair of nodes to be in the same commu- nity. By using message passing mechanism from the affinity propagation method, the communitypartitioning can be regarded as the process of electing community leaders. The applications ofthis message passing based community detection method on real and benchmark networks demon-strate that this framework can effectively: (i) address the problem of the resolution limit, i.e., itcan effectively and correctly partition into communities those networks on which resolution limitwill occur by optimizing modularity; (ii) analyze community structure of undirected networks anddirected networks in a uniform way; (iii) uncover the possible hierarchical community structure innetworks.
在复杂网络社团结构的分析研究中,模块度度量(及其变种)起了很重要的作用,催生了一大类重要的社团结构分析方法。但是这类通过对模块度度量(及其变种)优化来获得网络社团划分的方法存在分辨率问题,从而极大地限制了基于模块度方法的有效性和应用广度。
另一方面,目前社团结构分析研究主要集中在无向网络上,系统地直接分析有向网络社团结构的研究还远远不及对无向网络社团结构的分析研究。实际上,当前有向网络社团结构划分的普遍做法是通过简单地忽略有向网络中边的方向,将有向网络当成无向网络分析。这种方法在大多数情况下由于忽略了有向网络中边的方向包含的重要拓扑结构信息,从而无法正确有效地划分网络的社团结构。另外,在有向网络上扩展多数无向网络社团结构的分析方法往往不是简单的工作。
本论文从模块度度量的相关问题出发,将无向二元网络上模块度优化时的分辨率问题的分析扩展到无向加权网络中,并在此基础上提出了一种结合网络预处理的增强型模块度优化社团结构分析方法。通过分析无向网络上的模块度优化产生分辨率问题的条件,提出通过有效地获得关于社团之间边的信息来处理模块度优化时可能产生的分辨率问题。基于网络上的动力学过程反映网络的潜在结构这一事实,利用无向网络上的随机游走过程获取关于社团内部边和社团外部边的信息,并通过边的迭代重加权操作使得网络边的权值不断向社团内部集中,而社团之间的边权值越来越小,从而有效地克服模块度优化时的分辨率问题。实验分析表明,这种结合了网络预处理的无向网络社团分析方法极大地增强了基于模块度优化的无向网络社团结构分析方法的有效性和应用广度。
针对传统的有向网络社团结构分析方法简单忽略边的方向将使得社团划分不准确的问题,提出了一种基于有向网络嵌入的有向网络社团结构分析方法。该方法通过在有向网络上扩展无向网络的网络嵌入分析,从有向网络嵌入目标函数关联的拉普拉斯矩阵中分离出包含了边的方向信息的对称矩阵作为有向网络对等的无向加权网络的邻接矩阵,并导出一种关于有向网络社团结构划分的新模块度定义。一方面,新模块度度量进一步解释了有向网络社团的另一种物理内涵:同一社团内的结点是最大程度保持了有向网络局部结构的相邻结点集合;另一方面,它建立了有向网络与某种无向网络的联系,这种联系表明有向网络的社团结构可以通过应用已有的无向网络社团结构分析方法可靠并且有效地在所导出的无向网络上分析得到。
进一步扩展了基于有向网络嵌入的有向网络社团结构分析方法的分析思路,提出了一种基于边的方向信息抽取的有向网络社团结构分析方法。该方法基于具有社团结构的有向网络上的流运动将更加容易地在社团内部结点之间进行的事实,通过有向网络上的PageRank型随机游走过程有效地抽取有向网络边的方向包含的信息,并采用适当的相似性函数将其转化为边的权值与有向网络中边的互联性集成共同定义有向网络的社团结构。在抽取足够多的关于边的方向信息后,通过忽略边的方向将有向网络的社团划分问题等价为所导出的无向加权网络的社团划分问题,在保持社团结构划分准确性的同时有效地简化了有向网络社团结构划分问题的分析,避免了无向网络分析方法常常难以直接扩展到有向网络社团结构分析中的问题。
在分析前述关于无向网络和有向网络社团结构分析方法的可统一性基础上,提出了一种基于网络结点间消息传递的社团结构分析的一致框架。通过随机游走将网络结点表示成向量空间中的点,并以此有效地定义表达结点属于同一社团可能程度的相似性。利用affinity propagation算法的消息传递机制将网络的社团结构划分问题转换成社团领导者的推选过程。在实际网络和标准测试网络上的分析表明,这种消息传递的网络社团结构分析框架能够:(i)有效地处理分辨率问题,即有效地分析那些通过模块度优化会出现分辨率问题的网络的社团结构;(ii)在一个一致的框架中分析有向网络和无向网络的社团结构;(iii)揭示网络中可能存在的多级社团结构。
As a new emerging discipline, research on complex networks attracts scientists from a varietyof different fields. In fact, studies that can qualitatively and quantitatively characterize complexnetworks will help to unveil the general laws regulating different real systems modeled by complexnetworks, and therefore will be relevant in a number of disciplines (biology, social sciences, etc).Community structure is one of the crucial structural characteristics of complex networks; therefore,accurately analyzing their community structure represents a very relevant topic.
In the research related to the analysis of community structure in complex networks, a measurenamed modularity (and variants) plays a crucial role, and from it a large amount of importantapproaches for analyzing community structure have been derived. However, it has been foundthat the optimization of modularity (and of its variants) suffers from resolution limit. This greatlyreduces the effectiveness and the range of applicability of those modularity based methods.
Additionally, current studies on community structure analysis are mainly focusing on undi-rected networks, thus analyzing community structure in directed networks represents a yet poorlyunexplored direction in this research area. Indeed, so far, the common approach to communitystructure analysis in directed networks has simply proceeded by discarding the direction of edgesand treating directed networks as undirected ones. Such type of approach frequently fails sincesimply discarding edges’direction removes valuable information and thus results in inaccuratecommunity partitions. Furthermore, very often, the extension of methods for community detectionin undirected networks to those for directed networks is far from trivial.
Starting from the issues related to modularity, this thesis extends the analysis of the resolutionlimit from the case of binary undirected networks to that of weighted ones, and thus proposes an en-hanced modularity-based method for community structure analysis via network preprocessing. Byanalyzing the conditions relative to the resolution limit in undirected networks, it can be observedthat the problem can be effectively addressed by acquiring information on inter-community edges.Based on the fact that dynamics events occurring on a network will re?ect its underlying structure,random walks on undirected networks can be used as a surrogate to obtain effective informationon intra-community and inter-community edges. After such information is obtained, iteratively reweighting intra-community and inter-community edges will cause weights to concentrate moreand more into communities, while becoming very small or even vanishing among communities.As a result, the resolution limit problem can be effectively addressed when optimizing modularity.The applications of such a method on real and benchmark networks demonstrate that the effective-ness and the range of applications of using modularity based methods for detecting communitiesin undirected networks is greatly enhanced via network preprocessing.
With respect to the problem of inaccurate communities partitioning by discarding the infor-mation contained in edges’direction, a method for analyzing community structure by directednetwork embedding is then proposed. By extending network embedding for undirected networksto directed ones, this method extracts a symmetric matrix from the Laplacian matrix associatedwith the target function for directed network embedding. Such a symmetric matrix can be re-garded as an adjacency matrix for a weighted undirected network that contains the informationon edge direction in the original directed network. Consequently, a new modularity definitionfor directed networks is derived by reformulating the modularity for undirected networks on theinduced adjacency matrix. This new modularity measure provides on one hand an additional phys-ical meaning of communities in directed networks: nodes in the same community are neighboringnodes that preserve as much as possible the local structure of a network. On the other hand, itdiscloses the relationship between the directed network under study and its induced undirectedone. Therefore, methods designed to partition undirected networks, can successfully, safely andefficiently be applied to directed ones, via the definition of the induced undirected network.
By further extending this idea, another community analysis method for directed networks isproposed. This method is based on the fact that the ?ow on a directed network with a communitystructure will move more easily among nodes within the same community. It thus employs PageR-ank random walks on directed networks as a proxy of ?ow to effectively extract the informationcontained in edges’direction. By choosing a suitable similarity function, the obtained informationis transformed into edges’weight that will be integrated with edges’connectedness to define com-munity structure in directed networks. After the information contained in the edge directions hasbeen extracted iteratively following this procedure, the edge directions can be safely discarded, andthe community partitioning of a directed network can be obtained via partitioning the undirectedweighted network. This strategy simplifies the problem while retaining the accuracy in analyzingcommunity structure in directed networks.
Based on the possible uniformity of the above methods for analyzing community structurein undirected and directed networks, a message passing based unified framework for communitydetection is proposed. In this frame, nodes in a network are expressed in terms of points in avectorial space via random walks on networks. Similarity between nodes can thus be effectivelydefined, and this similarity represents the likelihood of a pair of nodes to be in the same commu- nity. By using message passing mechanism from the affinity propagation method, the communitypartitioning can be regarded as the process of electing community leaders. The applications ofthis message passing based community detection method on real and benchmark networks demon-strate that this framework can effectively: (i) address the problem of the resolution limit, i.e., itcan effectively and correctly partition into communities those networks on which resolution limitwill occur by optimizing modularity; (ii) analyze community structure of undirected networks anddirected networks in a uniform way; (iii) uncover the possible hierarchical community structure innetworks.
引文
[1] WILSON R J. Introduction to graph theory[M].[S.l.]: Addison-Wesley, 1996.
[2] WASSERMAN S, FAUST K. Social network analysis: Methods and applications[M].[S.l.]:Cambridge University Press, 1994.
[3] SCOTT J P. Social Network Analysis: A Handbook[M].[S.l.]: SAGE Publications, 2nd ed.,2000.
[4] SOUTH S J, HAYNIE D L. Friendship networks of mobile adolescents[J]. Social Forces,2004, 83(1):315–350.
[5] NEWMAN M E J. Coauthorship networks and patterns of scientific collaboration[J]. Pro-ceedings of the National Academy of Sciences of the United States of America, 2004,101(Suppl 1):5200.
[6] RAMASCO J J, DOROGOVTSEV S N, PASTOR-SATORRAS R. Self-organization of collab-oration networks[J]. Physical review E, 2004, 70(3):36106.
[7] NEWMAN M E J, FORREST S, BALTHROP J. Email networks and the spread of computerviruses[J]. Physical Review E, 2002, 66(3):035101.
[8] GUIMERA R, DANON L, DIAZ-GUILERA A, et al. Self-similar community structure in anetwork of human interactions[J]. Physical Review E, 2003, 68(6):065103.
[9] ONNELA J P, SARAM A¨KI J, HYV O¨NEN J, et al. Structure and tie strengths in mobilecommunication networks[J]. Proceedings of the National Academy of Sciences, 2007,104(18):7332.
[10] SMITH R D. Instant messaging as a scale-free network[J]. Arxiv preprint cond-mat/0206378, 2002.
[11] LEICHT E A, CLARKSON G, SHEDDEN K, et al. Large-scale structure of time evolvingcitation networks[J]. The European Physical Journal B, 2007, 59(1):75–83.
[12] PASTOR-SATORRAS R, VESPIGNANI A. Evolution and structure of the Internet: A statis-tical physics approach[M].[S.l.]: Cambridge University Press, 2004.
[13] ADAMIC L A, et al. Power-law distribution of the world wide web[J]. Science, 2000,287(5461):2115.
[14] JEONG H, TOMBOR B, ALBERT R, et al. The large-scale organization of metabolic net-works[J]. Nature, 2000, 407(6804):651–654.
[15] JEONG H, MASON S P, BARAB A′SI A L, et al. Lethality and centrality in protein net-works[J]. Nature, 2001, 411(6833):41–42.
[16] GUELZIM N, BOTTANI S, BOURGINE P, et al. Topological and causal structure of the yeasttranscriptional regulatory network[J]. Nature genetics, 2002, 31(1):60–63.
[17] SPORNS O. Network analysis, complexity, and brain function[J]. Complexity, 2002,8(1):56–60.
[18] MONTOYA J M, et al. Small world patterns in food webs[J]. Journal of theoretical biology,2002, 214(3):405–412.
[19] FREEMAN L C. Some antecedents of social network analysis[J]. Connections, 1996,19(1):39–42.
[20] ALBERT R, BARAB A′SI A L. Statistical mechanics of complex networks[J]. Reviews ofmodern physics, 2002, 74(1):47–97.
[21] WATTS D J, STROGATZ S H. Collective dynamics of‘small-world’networks[J]. Nature,1998, 393(6684):440–442.
[22] BARAB A′SI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999,286(5439):509.
[23] JANSON S, ?UCZAK T, RUCI N′SKI A. Random graphs[M].[S.l.]: John Wiley, New York,1999.
[24] MILGRAM S. The small world problem[J]. Psychology today, 1967, 2(1):60–67.
[25] NEWMAN M E J. The structure of scientific collaboration networks[J]. Proceedings of theNational Academy of Sciences of the United States of America, 2001, 98(2):404.
[26] PASTOR-SATORRAS R, V A′ZQUEZ A, VESPIGNANI A. Dynamical and correlation proper-ties of the Internet[J]. Physical Review Letters, 2001, 87(25):258701.
[27] NEWMAN M E J, WATTS D J. Renormalization group analysis of the small-world networkmodel[J]. Physics Letters A, 1999, 263(4-6):341–346.
[28] BIANCONI G, BARAB A′SI A L. Bose-Einstein condensation in complex networks[J]. Phys-ical Review Letters, 2001, 86(24):5632–5635.
[29] SINGH P. The small-world effect: The in?uence of macro-level properties of developercollaboration networks on open-source project success[J]. ACM Transactions on SoftwareEngineering and Methodology (TOSEM), 2010, 20(2):1–27.
[30] BAGLER G. Analysis of the Airport Network of India as a complex weighted network[J].Physica A: Statistical Mechanics and its Applications, 2008, 387(12):2972–2980.
[31] LI X, CHEN G. A local-world evolving network model[J]. Physica A: Statistical Mechanicsand its Applications, 2003, 328(1-2):274–286.
[32] ALBERT R, JEONG H, BARAB A′SI A L. Attack and error tolerance of complex networks[J].Nature, 2000, 406(6794):378–382.
[33] HOLME P, KIM B J, YOON C N, et al. Attack vulnerability of complex networks[J]. Phys-ical Review E, 2002, 65(5):056109.
[34] ARIANOS S, BOMPARD E, CARBONE A, et al. Power grid vulnerability: A complexnetwork approach[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2009,19:013119.
[35] MOREIRA A A, ANDRADE JR J S, HERRMANN H J, et al. How to make a fragile networkrobust and vice versa[J]. Physical Review Letters, 2009, 102(1):018701.
[36] ARRELL D K, TERZIC A. Network systems biology for drug discovery[J]. Clinical Phar-macology & Therapeutics, 2010.
[37] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic spreading in scale-free networks[J].Physical review letters, 2001, 86(14):3200–3203.
[38] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic dynamics and endemic states in com-plex networks[J]. Physical Review E, 2001, 63(6):66117.
[39] ZHANG H F, SMALL M, FU X C. Different epidemic models on complex networks[J].Communications in Theoretical Physics, 2009, 52:180–184.
[40] CASTELLANO C, PASTOR-SATORRAS R. Thresholds for epidemic spreading in net-works[J]. Physical review letters, 2010, 105(21):0218701.
[41] ZHANG H, FU X. Spreading of epidemics on scale-free networks with nonlinear infectiv-ity[J]. Nonlinear Analysis: Theory, Methods & Applications, 2009, 70(9):3273–3278.
[42] VAN MIEGHEM P, OMIC J, KOOIJ R. Virus spread in networks[J]. Networking, IEEE/ACMTransactions on, 2009, 17(1):1–14.
[43] MORENO Y, NEKOVEE M, PACHECO A F. Dynamics of rumor spreading in complexnetworks[J]. Physical Review E, 2004, 69(6):066130.
[44] BETTENCOURT L, CINTR O′N-ARIAS A, KAISER D I, et al. The power of a good idea:Quantitative modeling of the spread of ideas from epidemiological models[J]. Physica A:Statistical Mechanics and its Applications, 2006, 364:513–536.
[45] BARAHONA M, PECORA L M. Synchronization in small-world systems[J]. Physical Re-view Letters, 2002, 89(5):054101.
[46] WANG X F, CHEN G. Synchronization in small-world dynamical networks[J]. InternationalJournal of Bifurcation and chaos, 2002, 12(1):187–192.
[47] LI X, CHEN G. Synchronization and desynchronization of complex dynamical networks:an engineering viewpoint[J]. Circuits and Systems I: Fundamental Theory and Applications,IEEE Transactions on, 2003, 50(11):1381–1390.
[48] LU W, CHEN T. Synchronization of coupled connected neural networks with delays[J].Circuits and Systems I: Regular Papers, IEEE Transactions on, 2004, 51(12):2491–2503.
[49] WU C W. Synchronization in networks of nonlinear dynamical systems coupled via adirected graph[J]. Nonlinearity, 2005, 18:1057.
[50] GU L, ZHANG X D, ZHOU Q. Consensus and synchronization problems on small-worldnetworks[J]. Journal of Mathematical Physics, 2010, 51:082701.
[51] LI Z, XUE X. Outer synchronization of coupled networks using arbitrary couplingstrength[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2010, 20:023106.
[52] CHAO L, RONG L, ZHI-SHENG D, et al. Average Range and Network Synchronizability[J].Communications in Theoretical Physics, 2010, 53:115.
[53] WANG X F, CHEN G. Pinning control of scale-free dynamical networks[J]. Physica A:Statistical Mechanics and its Applications, 2002, 310(3-4):521–531.
[54] LI X, WANG X, CHEN G. Pinning a complex dynamical network to its equilibrium[J].Circuits and Systems I: Regular Papers, IEEE Transactions on, 2004, 51(10):2074–2087.
[55] CHEN T, LIU X, LU W. Pinning complex networks by a single controller[J]. Circuits andSystems I: Regular Papers, IEEE Transactions on, 2007, 54(6):1317–1326.
[56] SORRENTINO F, DI BERNARDO M, GAROFALO F, et al. Controllability of complex net-works via pinning[J]. Physical Review E, 2007, 75(4):46103.
[57] ARENAS A, D′IAZ-GUILERA A, KURTHS J, et al. Synchronization in complex networks[J].Physics Reports, 2008, 469(3):93–153.
[58] ADAMIC L A, LUKOSE R M, PUNIYANI A R, et al. Search in power-law networks[J].Physical review E, 2001, 64(4):046135.
[59] KLEINBERG J M. Navigation in a small world[J]. Nature, 2000, 406(6798):845.
[60] KLEINBERG J. The small-world phenomenon: an algorithm perspective[C]//Proceedingsof the thirty-second annual ACM symposium on Theory of computing. .[S.l.]: [s.n.] ,2000:163–170.
[61] WATTS D J, DODDS P S, NEWMAN M E J. Identity and search in social networks[J].Science, 2002, 296(5571):1302.
[62] DODDS P S, MUHAMAD R, WATTS D J. An experimental study of search in global socialnetworks[J]. Science, 2003, 301(5634):827.
[63] GUIMER A` R, D′IAZ-GUILERA A, VEGA-REDONDO F, et al. Optimal network topologiesfor local search with congestion[J]. Physical Review Letters, 2002, 89(24):0248701.
[64] WANG W X, WANG B H, YIN C Y, et al. Traffic dynamics based on local routing protocolon a scale-free network[J]. Physical Review E, 2006, 73(2):026111.
[65] SZAB O′G, F A′TH G. Evolutionary games on graphs[J]. Physics Reports, 2007, 446(4-6):97–216.
[66] ABRAMSON G, KUPERMAN M. Social games in a social network[J]. Physical Review E,2001, 63(3):030901.
[67] PUSCH A, WEBER S, PORTO M. Impact of topology on the dynamical organization ofcooperation in the prisoner’s dilemma game[J]. Physical Review E, 2008, 77(3):036120.
[68] SHEN-ORR S S, MILO R, MANGAN S, et al. Network motifs in the transcriptional regula-tion network of Escherichia coli[J]. Nature genetics, 2002, 31(1):64–68.
[69] MILO R, SHEN-ORR S, ITZKOVITZ S, et al. Network motifs: simple building blocks ofcomplex networks[J]. Science, 2002, 298(5594):824.
[70] JUSZCZYSZYN K, KAZIENKO P, MUSIA? K. Local topology of social network basedon motif analysis[C]//Knowledge-Based Intelligent Information and Engineering Systems..[S.l.]: [s.n.] , 2010:97–105.
[71] ALLAN E, TURKETT W H, FULP E W. Using network motifs to identify application proto-cols[C]//Global Telecommunications Conference, 2009. GLOBECOM 2009. IEEE. .[S.l.]:[s.n.] , 2010:1–7.
[72] ZHANG Y, XUAN J, DE LOS REYES B G, et al. Network motif-based identification oftranscription factor-target gene relationships by integrating multi-source biological data[J].BMC bioinformatics, 2008, 9(1):203.
[73] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America, 2002,99(12):7821.
[74] BARABASI A L. The origin of bursts and heavy tails in human dynamics[J]. Nature, 2005,435(7039):207–211.
[75] NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003.
[76] BOCCALETTI S, LATORA V, MORENO Y, et al. Complex networks: Structure and dynam-ics[J]. Physics reports, 2006, 424(4-5):175–308.
[77] COSTA L F, RODRIGUES F A, TRAVIESO G, et al. Characterization of complex networks:A survey of measurements[J]. Advances in Physics, 2007, 56(1):167–242.
[78]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].[S.l.]:清华大学出版社, 2006.
[79]郭雷,徐晓鸣等.复杂网络[M].[S.l.]:上海科技教育出版社, 2006.
[80]史定华.网络度分布理论[M].[S.l.]:高等教育出版社, 2011.
[81] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J].Physical Review E, 2004, 69(2):026113.
[82] GLEISER P, DANON L. Community structure in jazz[J]. Arxiv preprint cond-mat/0307434,2003.
[83] TRAUD A L, KELSIC E D, MUCHA P, et al. Comparing community structure to character-istics in online collegiate social networks[J]. Arxiv preprint arXiv:0809.0690, 2008.
[84] TYLER J R, WILKINSON D M, HUBERMAN B A. Email as spectroscopy: Auto-mated discovery of community structure within organizations[C]//Communities and tech-nologies.[S.l.]: Kluwer, B.V., 2003:81–96.
[85] FLAKE G W, LAWRENCE S, GILES C L, et al. Self-organization and identification of webcommunities[J]. IEEE Computer, 2002, 35(3):66–70.
[86] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities inlarge networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008:P10008.
[87] HOLME P, HUSS M, JEONG H. Subnetwork hierarchies of biochemical pathways[J]. Bioin-formatics, 2003, 19(4):532.
[88] LEWIS A C F, JONES N S, PORTER M A, et al. The function of communities in proteininteraction networks[J]. BMC Systems Biology.
[89] WILKINSON D M, HUBERMAN B A. A method for finding communities of relatedgenes[J]. Proceedings of the National Academy of Sciences of the United States of America,2004, 101(Suppl 1):5241.
[90] ZHOU T, ZHAO M, CHEN G, et al. Phase synchronization on scale-free networks withcommunity structure[J]. Physics Letters A, 2007, 368(6):431–434.
[91] PARK K, LAI Y C, GUPTE S, et al. Synchronization in complex networks with a modularstructure[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2006, 16:015105.
[92] YAN G, FU Z Q, REN J, et al. Collective synchronization induced by epidemic dynamicson complex networks with communities[J]. Physical Review E, 2007, 75(1):016108.
[93] NEWMAN M E J. Detecting community structure in networks[J]. The European PhysicalJournal B-Condensed Matter and Complex Systems, 2004, 38(2):321–330.
[94] DANON L, DIAZ-GUILERA A, DUCH J, et al. Comparing community structure identifica-tion[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005:P09008.
[95] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3-5):75–174.
[96] KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs[J]. BellSystem Technical Journal, 1970, 49(2):291–307.
[97] POTHEN A, SIMON H D, LIOU K P. Partitioning sparse matrices with eigenvectors ofgraphs[J]. SIAM J. Matrix Anal. Appl., 1990, 11(3):430–452.
[98] FIEDLER M. Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal,1973, 23(2):298–305.
[99]戈卢布G H,范洛恩(著) C F,亚湘袁(译).矩阵计算[M].[S.l.]:科学出版社, 2001.
[100] CORMEN T H, LEIZERSON C E, RIVEST R L.算法导论(影印版,第二版)[M].[S.l.]:北京:机械工业出版社, 2006.
[101] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977,40(1):35–41.
[102] RADICCHI F, CASTELLANO C, CECCONI F, et al. Defining and identifying communitiesin networks[J]. Proceedings of the National Academy of Sciences of the United States ofAmerica, 2004, 101(9):2658.
[103] CASTELLANO C, CECCONI F, LORETO V, et al. Self-contained algorithms to detect com-munities in networks[J]. The European Physical Journal B-Condensed Matter and ComplexSystems, 2004, 38(2):311–319.
[104] CHEN J, YUAN B. Detecting functional modules in the yeast protein–protein interactionnetwork[J]. Bioinformatics, 2006, 22(18):2283.
[105] FORTUNATO S, LATORA V, MARCHIORI M. Method to find community structures basedon information centrality[J]. Phys. Rev. E, 2004, 70.
[106] GREGORY S. An algorithm to find overlapping community structure in networks[J]. Knowl-edge Discovery in Databases: PKDD 2007, 2007:91–102.
[107] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. PhysicalReview E, 2004, 69(6):066133.
[108] BRANDES U, DELLING D, GAERTLER M, et al. On modularity clustering[J]. IEEE Trans-actions on Knowledge and Data Engineering, 2007:172–188.
[109] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very largenetworks[J]. Physical Review E, 2004, 70(6):066111.
[110] DANON L, D′IAZ-GUILERA A, ARENAS A. The effect of size heterogeneity on commu-nity identification in complex networks[J]. Journal of Statistical Mechanics: Theory andExperiment, 2006, 2006:P11010.
[111] WAKITA K, TSURUMI T. Finding community structure in mega-scale social net-works:[extended abstract][C]//Proceedings of the 16th international conference on WorldWide Web. .[S.l.]: [s.n.] , 2007:1275–1276.
[112] SCHUETZ P, CAFLISCH A. Efficient modularity optimization by multistep greedy algorithmand vertex mover refinement[J]. Physical Review E, 2008, 77(4):046112.
[113] SCHUETZ P, CAFLISCH A. Multistep greedy algorithm identifies community structure inreal-world and computer-generated networks[J]. Physical Review E, 2008, 78(2):026112.
[114] PUJOL J M, BE′JAR J, DELGADO J. Clustering algorithm for determining community struc-ture in large networks[J]. Physical Review E, 2006, 74(1):016107.
[115] DU H, FELDMAN M W, LI S, et al. An algorithm for detecting community structure ofsocial networks based on prior knowledge and modularity[J]. Complexity, 2007, 12(3):53–60.
[116] YE Z, HU S, YU J. Adaptive clustering algorithm for community detection in complexnetworks[J]. Physical Review E, 2008, 78(4):046115.
[117] MEI J, HE S, SHI G, et al. Revealing network communities through modularity maximiza-tion by a contraction–dilation method[J]. New Journal of Physics, 2009, 11:043025.
[118] KIRKPATRICK S, JR. D G, VECCHI M P. Optimization by simmulated annealing[J]. sci-ence, 1983, 220(4598):671–680.
[119] GUIMERA R, AMARAL L A N. Functional cartography of complex metabolic networks[J].Nature, 2005, 433(7028):895–900.
[120] GUIMERA R, AMARAL L A N. Cartography of complex networks: modules and universalroles[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005:P02001.
[121] BOETTCHER S, PERCUS A G. Optimization with extremal dynamics[J]. Physical ReviewLetters, 2001, 86(23):5211–5214.
[122] DUCH J, ARENAS A. Community detection in complex networks using extremal optimiza-tion[J]. Physical Review E, 2005, 72(2):027104.
[123] HOLLAND J H. Adaptation in natural and artificial systems[J]. 1975.
[124] GLOVER F. Future paths for integer programming and links to artificial intelligence[J].Computers & Operations Research, 1986, 13(5):533–549.
[125] TASGIN M, HERDAGDELEN A, BINGOL H. Community detection in complex networksusing genetic algorithms[J]. Arxiv preprint arXiv:0711.0491, 2007.
[126] LIU X, LI D, WANG S, et al. Effective algorithm for detecting community structure incomplex networks based on GA and clustering[J]. Computational Science–ICCS 2007,2007:657–664.
[127] ARENAS A, FERNANDEZ A, GOMEZ S. Analysis of the structure of complex networks atdifferent resolution levels[J]. New Journal of Physics, 2008, 10:053039.
[128] L U¨Z, HUANG W. Iterated tabu search for identifying community structure in complexnetworks[J]. Physical Review E, 2009, 80(2):026130.
[129] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of theNational Academy of Sciences, 2006, 103(23):8577.
[130] NEWMAN M E J. Finding community structure in networks using the eigenvectors of ma-trices[J]. Physical Review E, 2006, 74(3):036104.
[131] LEICHT E A, NEWMAN M E J. Community structure in directed networks[J]. PhysicalReview Letters, 2008, 100(11):118703.
[132] BARBER M J. Modularity and community detection in bipartite networks[J]. PhysicalReview E, 2007, 76(6):066102.
[133] BARBER M J, FARIA M, STREIT L, et al. Searching for communities in bipartite net-works[J]. Arxiv preprint arXiv:0803.2854, 2008.
[134] RICHARDSON T, MUCHA P, PORTER M A. Spectral tripartitioning of networks[J]. PhysicalReview E, 2009, 80(3):036111.
[135] WHITE S, SMYTH P. A spectral clustering approach to finding communities ingraphs[C]//Proceedings of the fifth SIAM international conference on data mining. .[S.l.]:[s.n.] , 2005:274.
[136] RUAN J, ZHANG W. An efficient spectral algorithm for network community discovery andits applications to biological and social networks[C]//icdm. .[S.l.]: [s.n.] , 2007:643–648.
[137] DONETTI L, MUNOZ M A. Detecting network communities: a new systematic and efficientalgorithm[J]. Journal of Statistical Mechanics: Theory and Experiment, 2004, 2004:P10012.
[138] XU G, TSOKA S, PAPAGEORGIOU L G. Finding community structures in complex net-works using mixed integer optimisation[J]. The European Physical Journal B-CondensedMatter and Complex Systems, 2007, 60(2):231–239.
[139] AGARWAL G, KEMPE D. Modularity-maximizing graph communities via mathematicalprogramming[J]. The European Physical Journal B-Condensed Matter and Complex Sys-tems, 2008, 66(3):409–418.
[140] ARENAS A, DUCH J, FERN A′NDEZ A, et al. Size reduction of complex networks preservingmodularity[J]. New Journal of Physics, 2007, 9:176.
[141] MASSEN C P, DOYE J P K. Identifying communities within energy landscapes[J]. PhysicalReview E, 2005, 71(4):046101.
[142] MUFF S, RAO F, CAFLISCH A. Local modularity measure for network clusterizations[J].Physical Review E, 2005, 72(5):056107.
[143] REICHARDT J, BORNHOLDT S. Detecting fuzzy community structures in complex net-works with a Potts model[J]. Physical Review Letters, 2004, 93(21):218701.
[144] REICHARDT J, BORNHOLDT S. Statistical mechanics of community detection[J]. PhysicalReview E, 2006, 74(1):016110.
[145] ARENAS A, FERNANDEZ A, FORTUNATO S, et al. Motif-based communities in complexnetworks[J]. Journal of Physics A: Mathematical and Theoretical, 2008, 41:224001.
[146] G O′MEZ S, JENSEN P, ARENAS A. Analysis of community structure in networks of corre-lated data[J]. Physical Review E, 2009, 80(1):016114.
[147] KAPLAN T D, FORREST S. A dual assortative measure of community structure[J]. Arxivpreprint arXiv:0801.3290, 2008.
[148] TRAAG V, BRUGGEMAN J. Community detection in networks with positive and negativelinks[J]. Physical Review E, 2009, 80(3):036115.
[149] GUIMER A` R, SALES-PARDO M, AMARAL L A N. Module identification in bipartite anddirected networks[J]. Physical Review E, 2007, 76(3):036102.
[150] LI Z, ZHANG S, WANG R S, et al. Quantitative function for community detection[J].Physical Review E, 2008, 77(3):036109.
[151] GUIMERA R, SALES-PARDO M, AMARAL L A N. Modularity from ?uctuations in randomgraphs and complex networks[J]. Physical Review E, 2004, 70(2):025101.
[152] FORTUNATO S, BARTHE′LEMY M. Resolution limit in community detection[J]. Proceed-ings of the National Academy of Sciences, 2007, 104(1):36.
[153] KUMPULA J, SARAM A¨KI J, KASKI K, et al. Limited resolution in complex networkcommunity detection with Potts model approach[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2007, 56(1):41–45.
[154] RONHOVDE P, NUSSINOV Z. Local resolution-limit-free Potts model for community de-tection[J]. Physical Review E, 2010, 81(4):046114.
[155] LAI D, LU H, NARDINI C. Enhanced modularity-based community detection by randomwalk network preprocessing[J]. Physical Review E, 2010, 81(6):066118.
[156] RUAN J, ZHANG W. Identifying network communities with a high resolution[J]. PhysicalReview E, 2008, 77(1):016104.
[157] NOH J D, RIEGER H. Random walks on complex networks[J]. Phys. Rev. Lett., 2004,92(11):118701.
[158] VAN DONGEN S. Graph clustering by ?ow simulation[J]. PhD Thesis University of Utrecht,2000.
[159] ZHOU H. Network landscape from a Brownian particle’s perspective[J]. Phys. Rev. E, 2003,67(4):041908.
[160] ZHOU H. Distance, dissimilarity index, and network community structure[J]. Phys. Rev. E,2003, 67(6):061901.
[161] ZHOU H, LIPOWSKY R. Network Brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities[J]. Lecture Notes inComputer Science, 2004, 3038:1062–1069.
[162] PONS P, LATAPY M. Computing communities in large networks using random walks[J].Lecture notes in computer science, 2005, 3733:284.
[163] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine* 1[J].Computer networks and ISDN systems, 1998, 30(1-7):107–117.
[164] ROSVALL M, BERGSTROM C T. Maps of random walks on complex networks reveal com-munity structure[J]. Proceedings of the National Academy of Sciences, 2008, 105(4):1118.
[165] LAI D, LU H, NARDINI C. Finding communities in directed networks by PageRank randomwalk induced network embedding[J]. Physica A: Statistical Mechanics and its Applications,2010, 389(12):2443–2454.
[166] DELVENNE J C, YALIRAKI S, BARAHONA M. Stability of graph communities across timescales[J]. Proceedings of the National Academy of Sciences, 2010, 107(29):12755.
[167] LAMBIOTTE R, DELVENNE J, BARAHONA M. Laplacian dynamics and multiscale modularstructure in networks[J]. arXiv:, 2009, 0812.1770.
[168] EVANS T S, LAMBIOTTE R. Line graphs, link partitions, and overlapping communities[J].Phys. Rev. E, 2009, 80(1):016105.
[169] ARENAS A, DIAZ-GUILERA A, PE′REZ-VICENTE C. Synchronization reveals topologicalscales in complex networks[J]. Physical Review Letters, 2006, 96(11):114102.
[170] ARENAS A, DIAZ-GUILERA A. Synchronization and modularity in complex networks[J].The European Physical Journal-Special Topics, 2007, 143(1):19–25.
[171] BOCCALETTI S, IVANCHENKO M, LATORA V, et al. Detecting complex network modu-larity by dynamical clustering[J]. Physical Review E, 2007, 75(4):045102.
[172] LI D, LEYVA I, ALMENDRAL J A, et al. Synchronization interfaces and overlapping com-munities in complex networks[J]. Physical Review Letters, 2008, 101(16):168701.
[173] ISPOLATOV I, MAZO I, YURYEV A. Finding mesoscopic communities in sparse net-works[J]. Journal of Statistical Mechanics: Theory and Experiment, 2006, 2006:P09014.
[174] SON S W, JEONG H, NOH J D. Random field Ising model and community structure incomplex networks[J]. The European Physical Journal B-Condensed Matter and ComplexSystems, 2006, 50(3):431–437.
[175] RONHOVDE P, NUSSINOV Z. Multiresolution community detection for megascale networksby information-based replica correlations[J]. Physical Review E, 2009, 80(1):016109.
[176] HASTINGS M. Community detection as an inference problem.[J]. Physical Review. E, 2006,74(3):035102.
[177] NEWMAN M, LEICHT E. Mixture models and exploratory analysis in networks[J]. Pro-ceedings of the National Academy of Sciences, 2007, 104(23):9564.
[178] RAMASCO J J, MUNGAN M. Inversion method for content-based networks[J]. PhysicalReview E, 2008, 77(3):036122.
[179] HOFMAN J, WIGGINS C. Bayesian approach to network modularity[J]. Physical reviewletters, 2008, 100(25):258701.
[180] BAGROW J P, BOLLT E M. Local method for detecting communities[J]. Physical ReviewE, 2005, 72(4):046108.
[181] CLAUSET A. Finding local community structure in networks[J]. Physical Review E, 2005,72(2):026132.
[182] WU F, HUBERMAN B A. Finding communities in linear time: a physics approach[J]. TheEuropean Physical Journal B-Condensed Matter and Complex Systems, 2004, 38(2):331–338.
[183] GUDKOV V, MONTEALEGRE V, NUSSINOV S, et al. Community detection in complexnetworks by dynamical simplex evolution.[J]. Physical review. E, Statistical, nonlinear, andsoft matter physics, 2008, 78(1):016113.
[184] KRAWCZYK M J. Differential equations as a tool for community identification[J]. PhysicalReview E, 2008, 77(6):065701.
[185] RAGHAVAN U, ALBERT R, KUMARA S. Near linear time algorithm to detect communitystructures in large-scale networks[J]. Physical Review E, 2007, 76(3):036106.
[186] TIBE′LY G, KERTE′SZ J. On the equivalence of the label propagation method of communitydetection and a Potts model approach[J]. Physica A: Statistical Mechanics and its Applica-tions, 2008, 387(19-20):4982–4984.
[187] LEUNG I X Y, HUI P, LIO P, et al. Towards real-time community detection in large net-works[J]. Physical Review E, 2009, 79(6):066107.
[188] BARBER M J, CLARK J W. Detecting network communities by propagating labels underconstraints[J]. Physical Review E, 2009, 80(2):026129.
[189] PALLA G, DERE′NYI I, FARKAS I, et al. Uncovering the overlapping community structureof complex networks in nature and society[J]. Nature, 2005, 435(7043):814–818.
[190] FARKAS I, A′BEL D, PALLA G, et al. Weighted network modules[J]. New Journal ofPhysics, 2007, 9:180.
[191] PALLA G, FARKAS I J, POLLNER P, et al. Directed network modules[J]. New Journal ofPhysics, 2007, 9:186.
[192] LEHMANN S, SCHWARTZ M, HANSEN L K. Biclique communities[J]. Physical ReviewE, 2008, 78(1):016108.
[193] KUMPULA J M, KIVEL A¨M, KASKI K, et al. Sequential algorithm for fast clique percola-tion[J]. Physical Review E, 2008, 78(2):026109.
[194] ZHANG S H, WANG R S, ZHANG X S. Identification of overlapping community structurein complex networks using fuzzy c-means clustering[J]. Physica A: Statistical Mechanicsand its Applications, 2007, 374(1):483–490.
[195] NEPUSZ T, PETR O′CZI A, NE′GYESSY L, et al. Fuzzy communities and the concept ofbridgeness in complex networks[J]. Physical Review E, 2008, 77(1):016107.
[196] AHN Y Y, BAGROW J P, LEHMANN S. Link communities reveal multiscale complexity innetworks[J]. Nature, 2010, 466(7307):761–764.
[197] GREGORY S. Finding Overlapping Communities Using Disjoint Community DetectionAlgorithms[J]. Complex Networks, 2009:47–61.
[198] WEN H, LEICHT E, D’SOUZA R M. Improving community detection in networks bytargeted node removal[J]. Physical Review E, 2011, 83(1):016114.
[199] LAI D, NARDINI C, LU H. Partitioning networks into communities by message passing[J].Physical Review E, 2011, 83(1):016115.
[200] LANCICHINETTI A, FORTUNATO S, KERTE′SZ J. Detecting the overlapping and hierarchi-cal community structure in complex networks[J]. New Journal of Physics, 2009, 11:033015.
[201] SALES-PARDO M, GUIMERA R, MOREIRA A A, et al. Extracting the hierarchical orga-nization of complex systems[J]. Proceedings of the National Academy of Sciences, 2007,104(39):15224.
[202] CLAUSET A, MOORE C, NEWMAN M E J. Structural inference of hierarchies in net-works[J]. Statistical network analysis: models, issues, and new directions, 2007:1–13.
[203] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction ofmissing links in networks[J]. Nature, 2008, 453(7191):98–101.
[204] PALLA G, BARAB A′SI A L, VICSEK T. Quantifying social group evolution[J]. Nature,2007, 446(7136):664–667.
[205] FENN D J, PORTER M A, MCDONALD M, et al. Dynamic communities in multichanneldata: An application to the foreign exchange market during the 2007–2008 credit crisis[J].Chaos: An Interdisciplinary Journal of Nonlinear Science, 2009, 19:033119.
[206] SUN J, FALOUTSOS C, PAPADIMITRIOU S, et al. Graphscope: parameter-free mining oflarge time-evolving graphs[C]//Proceedings of the 13th ACM SIGKDD international con-ference on Knowledge discovery and data mining. .[S.l.]: [s.n.] , 2007:687–696.
[207] DHILLON I S, GUAN Y, KULIS B. Kernel k-means: spectral clustering and normalizedcuts[C]//Proceedings of the tenth ACM SIGKDD international conference on Knowledgediscovery and data mining. .[S.l.]: [s.n.] , 2004:551–556.
[208] NEWMAN M E J. Analysis of weighted networks[J]. Phys. Rev. E, 2004, 70(5):056131.
[209] ZACHARY W W. An information ?ow model for con?ict and fission in small groups[J].Journal of Anthropological Research, 1977, 33(4):452–473.
[210] HAREL D, KOREN Y. On clustering using random walks[J]. Lecture Notes in ComputerScience, 2001, 2245:18–41.
[211] LANCICHINETTI A, FORTUNATO S. Benchmarks for testing community detection algo-rithms on directed and weighted graphs with overlapping communities[J]. Phys. Rev. E,2009, 80(1):016118.
[212] STOUFFER D B, CAMACHO J, GUIMER A` R, et al. Quantitative patterns in the structure ofmodel and empirical food webs[J]. Ecology, 2005, 86(5):1301–1311.
[213] KIM Y, SON S W, JEONG H. Finding communities in directed networks[J]. PhysicalReview E, 2010, 81(1):016103.
[214] KIM Y, SON S W, JEONG H. Link Rank: Finding communities in directed networks[J].arXiv, 2009(arXiv:0902.3728v1).
[215] LANGVILLE A N, MEYER C D. Deeper inside pagerank[J]. Internet Mathematics, 2004,1(3):335–380.
[216] VON LUXBURG U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007,17(4):395–416.
[217] CAPOCCI A, SERVEDIO V, CALDARELLI G, et al. Detecting communities in large net-works[J]. Physica A: Statistical Mechanics and its Applications, 2005, 352(2-4):669–676.
[218] ZHU X. Semi-supervised learning literature survey[J]. Computer Science, University ofWisconsin-Madison, 2006.
[219] CHUNG F. Laplacians and the Cheeger inequality for directed graphs[J]. Annals of Combi-natorics, 2005, 9(1):1–19.
[220] HAN J, KAMBER M. Data mining: concepts and techniques[M].[S.l.]: Morgan Kaufmann,2006.
[221] ZHOU D, HUANG J, SCH O¨LKOPF B. Learning from labeled and unlabeled data on adirected graph[C]//Proceedings of the 22nd international conference on Machine learning..[S.l.]: [s.n.] , 2005:1036–1043.
[222] CHEN M, YANG Q, TANG X. Directed graph embedding[C]//Proceedings of the Interna-tional Joint Conference on Artificial Intelligence (IJCAI). .[S.l.]: [s.n.] , 2007:2707–2712.
[223] CAI D, HE X, HAN J. Spectral regression: a unified subspace learning framework forcontent-based image retrieval[C]//Proceedings of the 15th international conference on Mul-timedia. .[S.l.]: [s.n.] , 2007:403–412.
[224] JAMES M. Race, school integration, and friendship segregation in America[J]. AmericanJournal of Sociology, 2001, 107(3):679–716.
[225] LANCICHINETTI A, FORTUNATO S. Community detection algorithms: A comparativeanalysis[J]. Physical Review E, 2009, 80(5):056117.
[226] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science,2007, 315(5814):972.
[227] LAI D, LU H. Identification of community structure in complex networks using affinitypropagation clustering method[J]. Modern Physics Letters B, 2008, 22:1547–1566.
[228] LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks[J]. Phys. Rev. E,2006, 73(2):026120.
[229] CALI N′SKI T, HARABASZ J. A dendrite method for cluster analysis[J]. Communications inStatistics-Simulation and Computation, 1974, 3(1):1–27.
[230] LUSSEAU D. The emergent properties of a dolphin social network[J]. Proceedings of theRoyal Society of London. Series B: Biological Sciences, 2003, 270(Suppl 2):S186.
[231] RAVASZ E, BARAB A′SI A L. Hierarchical organization in complex networks[J]. Phys. Rev.E, 2003, 67(2):026112.
[232] ARENAS A, FERN A′NDEZ A, G O′MEZ S. Analysis of the structure of complex networks atdifferent resolution levels[J]. New J. Phys., 2008, 10:053039.
[233] LAMBIOTTE R. Multi-scale modularity in complex networks[C]//Modeling and Optimiza-tion in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2010 Proceedings of the 8th Inter-national Symposium on. .[S.l.]: [s.n.] , 2010:546–553.
[234] SHAWE-TAYLOR J, CRISTIANINI N. Kernel methods for pattern analysis[M].[S.l.]: Cam-bridge University Press, 2004.
[235] LAI D, YANG X, WU G, et al. Inference of gene networks―application to Bifidobac-terium[J]. Bioinformatics, 2011, 27(2):232.
[236] GARDNER T, DI BERNARDO D, LORENZ D, et al. Inferring genetic networks and identi-fying compound mode of action via expression profiling[J]. Science, 2003, 301(5629):102.
[2] WASSERMAN S, FAUST K. Social network analysis: Methods and applications[M].[S.l.]:Cambridge University Press, 1994.
[3] SCOTT J P. Social Network Analysis: A Handbook[M].[S.l.]: SAGE Publications, 2nd ed.,2000.
[4] SOUTH S J, HAYNIE D L. Friendship networks of mobile adolescents[J]. Social Forces,2004, 83(1):315–350.
[5] NEWMAN M E J. Coauthorship networks and patterns of scientific collaboration[J]. Pro-ceedings of the National Academy of Sciences of the United States of America, 2004,101(Suppl 1):5200.
[6] RAMASCO J J, DOROGOVTSEV S N, PASTOR-SATORRAS R. Self-organization of collab-oration networks[J]. Physical review E, 2004, 70(3):36106.
[7] NEWMAN M E J, FORREST S, BALTHROP J. Email networks and the spread of computerviruses[J]. Physical Review E, 2002, 66(3):035101.
[8] GUIMERA R, DANON L, DIAZ-GUILERA A, et al. Self-similar community structure in anetwork of human interactions[J]. Physical Review E, 2003, 68(6):065103.
[9] ONNELA J P, SARAM A¨KI J, HYV O¨NEN J, et al. Structure and tie strengths in mobilecommunication networks[J]. Proceedings of the National Academy of Sciences, 2007,104(18):7332.
[10] SMITH R D. Instant messaging as a scale-free network[J]. Arxiv preprint cond-mat/0206378, 2002.
[11] LEICHT E A, CLARKSON G, SHEDDEN K, et al. Large-scale structure of time evolvingcitation networks[J]. The European Physical Journal B, 2007, 59(1):75–83.
[12] PASTOR-SATORRAS R, VESPIGNANI A. Evolution and structure of the Internet: A statis-tical physics approach[M].[S.l.]: Cambridge University Press, 2004.
[13] ADAMIC L A, et al. Power-law distribution of the world wide web[J]. Science, 2000,287(5461):2115.
[14] JEONG H, TOMBOR B, ALBERT R, et al. The large-scale organization of metabolic net-works[J]. Nature, 2000, 407(6804):651–654.
[15] JEONG H, MASON S P, BARAB A′SI A L, et al. Lethality and centrality in protein net-works[J]. Nature, 2001, 411(6833):41–42.
[16] GUELZIM N, BOTTANI S, BOURGINE P, et al. Topological and causal structure of the yeasttranscriptional regulatory network[J]. Nature genetics, 2002, 31(1):60–63.
[17] SPORNS O. Network analysis, complexity, and brain function[J]. Complexity, 2002,8(1):56–60.
[18] MONTOYA J M, et al. Small world patterns in food webs[J]. Journal of theoretical biology,2002, 214(3):405–412.
[19] FREEMAN L C. Some antecedents of social network analysis[J]. Connections, 1996,19(1):39–42.
[20] ALBERT R, BARAB A′SI A L. Statistical mechanics of complex networks[J]. Reviews ofmodern physics, 2002, 74(1):47–97.
[21] WATTS D J, STROGATZ S H. Collective dynamics of‘small-world’networks[J]. Nature,1998, 393(6684):440–442.
[22] BARAB A′SI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999,286(5439):509.
[23] JANSON S, ?UCZAK T, RUCI N′SKI A. Random graphs[M].[S.l.]: John Wiley, New York,1999.
[24] MILGRAM S. The small world problem[J]. Psychology today, 1967, 2(1):60–67.
[25] NEWMAN M E J. The structure of scientific collaboration networks[J]. Proceedings of theNational Academy of Sciences of the United States of America, 2001, 98(2):404.
[26] PASTOR-SATORRAS R, V A′ZQUEZ A, VESPIGNANI A. Dynamical and correlation proper-ties of the Internet[J]. Physical Review Letters, 2001, 87(25):258701.
[27] NEWMAN M E J, WATTS D J. Renormalization group analysis of the small-world networkmodel[J]. Physics Letters A, 1999, 263(4-6):341–346.
[28] BIANCONI G, BARAB A′SI A L. Bose-Einstein condensation in complex networks[J]. Phys-ical Review Letters, 2001, 86(24):5632–5635.
[29] SINGH P. The small-world effect: The in?uence of macro-level properties of developercollaboration networks on open-source project success[J]. ACM Transactions on SoftwareEngineering and Methodology (TOSEM), 2010, 20(2):1–27.
[30] BAGLER G. Analysis of the Airport Network of India as a complex weighted network[J].Physica A: Statistical Mechanics and its Applications, 2008, 387(12):2972–2980.
[31] LI X, CHEN G. A local-world evolving network model[J]. Physica A: Statistical Mechanicsand its Applications, 2003, 328(1-2):274–286.
[32] ALBERT R, JEONG H, BARAB A′SI A L. Attack and error tolerance of complex networks[J].Nature, 2000, 406(6794):378–382.
[33] HOLME P, KIM B J, YOON C N, et al. Attack vulnerability of complex networks[J]. Phys-ical Review E, 2002, 65(5):056109.
[34] ARIANOS S, BOMPARD E, CARBONE A, et al. Power grid vulnerability: A complexnetwork approach[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2009,19:013119.
[35] MOREIRA A A, ANDRADE JR J S, HERRMANN H J, et al. How to make a fragile networkrobust and vice versa[J]. Physical Review Letters, 2009, 102(1):018701.
[36] ARRELL D K, TERZIC A. Network systems biology for drug discovery[J]. Clinical Phar-macology & Therapeutics, 2010.
[37] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic spreading in scale-free networks[J].Physical review letters, 2001, 86(14):3200–3203.
[38] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic dynamics and endemic states in com-plex networks[J]. Physical Review E, 2001, 63(6):66117.
[39] ZHANG H F, SMALL M, FU X C. Different epidemic models on complex networks[J].Communications in Theoretical Physics, 2009, 52:180–184.
[40] CASTELLANO C, PASTOR-SATORRAS R. Thresholds for epidemic spreading in net-works[J]. Physical review letters, 2010, 105(21):0218701.
[41] ZHANG H, FU X. Spreading of epidemics on scale-free networks with nonlinear infectiv-ity[J]. Nonlinear Analysis: Theory, Methods & Applications, 2009, 70(9):3273–3278.
[42] VAN MIEGHEM P, OMIC J, KOOIJ R. Virus spread in networks[J]. Networking, IEEE/ACMTransactions on, 2009, 17(1):1–14.
[43] MORENO Y, NEKOVEE M, PACHECO A F. Dynamics of rumor spreading in complexnetworks[J]. Physical Review E, 2004, 69(6):066130.
[44] BETTENCOURT L, CINTR O′N-ARIAS A, KAISER D I, et al. The power of a good idea:Quantitative modeling of the spread of ideas from epidemiological models[J]. Physica A:Statistical Mechanics and its Applications, 2006, 364:513–536.
[45] BARAHONA M, PECORA L M. Synchronization in small-world systems[J]. Physical Re-view Letters, 2002, 89(5):054101.
[46] WANG X F, CHEN G. Synchronization in small-world dynamical networks[J]. InternationalJournal of Bifurcation and chaos, 2002, 12(1):187–192.
[47] LI X, CHEN G. Synchronization and desynchronization of complex dynamical networks:an engineering viewpoint[J]. Circuits and Systems I: Fundamental Theory and Applications,IEEE Transactions on, 2003, 50(11):1381–1390.
[48] LU W, CHEN T. Synchronization of coupled connected neural networks with delays[J].Circuits and Systems I: Regular Papers, IEEE Transactions on, 2004, 51(12):2491–2503.
[49] WU C W. Synchronization in networks of nonlinear dynamical systems coupled via adirected graph[J]. Nonlinearity, 2005, 18:1057.
[50] GU L, ZHANG X D, ZHOU Q. Consensus and synchronization problems on small-worldnetworks[J]. Journal of Mathematical Physics, 2010, 51:082701.
[51] LI Z, XUE X. Outer synchronization of coupled networks using arbitrary couplingstrength[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2010, 20:023106.
[52] CHAO L, RONG L, ZHI-SHENG D, et al. Average Range and Network Synchronizability[J].Communications in Theoretical Physics, 2010, 53:115.
[53] WANG X F, CHEN G. Pinning control of scale-free dynamical networks[J]. Physica A:Statistical Mechanics and its Applications, 2002, 310(3-4):521–531.
[54] LI X, WANG X, CHEN G. Pinning a complex dynamical network to its equilibrium[J].Circuits and Systems I: Regular Papers, IEEE Transactions on, 2004, 51(10):2074–2087.
[55] CHEN T, LIU X, LU W. Pinning complex networks by a single controller[J]. Circuits andSystems I: Regular Papers, IEEE Transactions on, 2007, 54(6):1317–1326.
[56] SORRENTINO F, DI BERNARDO M, GAROFALO F, et al. Controllability of complex net-works via pinning[J]. Physical Review E, 2007, 75(4):46103.
[57] ARENAS A, D′IAZ-GUILERA A, KURTHS J, et al. Synchronization in complex networks[J].Physics Reports, 2008, 469(3):93–153.
[58] ADAMIC L A, LUKOSE R M, PUNIYANI A R, et al. Search in power-law networks[J].Physical review E, 2001, 64(4):046135.
[59] KLEINBERG J M. Navigation in a small world[J]. Nature, 2000, 406(6798):845.
[60] KLEINBERG J. The small-world phenomenon: an algorithm perspective[C]//Proceedingsof the thirty-second annual ACM symposium on Theory of computing. .[S.l.]: [s.n.] ,2000:163–170.
[61] WATTS D J, DODDS P S, NEWMAN M E J. Identity and search in social networks[J].Science, 2002, 296(5571):1302.
[62] DODDS P S, MUHAMAD R, WATTS D J. An experimental study of search in global socialnetworks[J]. Science, 2003, 301(5634):827.
[63] GUIMER A` R, D′IAZ-GUILERA A, VEGA-REDONDO F, et al. Optimal network topologiesfor local search with congestion[J]. Physical Review Letters, 2002, 89(24):0248701.
[64] WANG W X, WANG B H, YIN C Y, et al. Traffic dynamics based on local routing protocolon a scale-free network[J]. Physical Review E, 2006, 73(2):026111.
[65] SZAB O′G, F A′TH G. Evolutionary games on graphs[J]. Physics Reports, 2007, 446(4-6):97–216.
[66] ABRAMSON G, KUPERMAN M. Social games in a social network[J]. Physical Review E,2001, 63(3):030901.
[67] PUSCH A, WEBER S, PORTO M. Impact of topology on the dynamical organization ofcooperation in the prisoner’s dilemma game[J]. Physical Review E, 2008, 77(3):036120.
[68] SHEN-ORR S S, MILO R, MANGAN S, et al. Network motifs in the transcriptional regula-tion network of Escherichia coli[J]. Nature genetics, 2002, 31(1):64–68.
[69] MILO R, SHEN-ORR S, ITZKOVITZ S, et al. Network motifs: simple building blocks ofcomplex networks[J]. Science, 2002, 298(5594):824.
[70] JUSZCZYSZYN K, KAZIENKO P, MUSIA? K. Local topology of social network basedon motif analysis[C]//Knowledge-Based Intelligent Information and Engineering Systems..[S.l.]: [s.n.] , 2010:97–105.
[71] ALLAN E, TURKETT W H, FULP E W. Using network motifs to identify application proto-cols[C]//Global Telecommunications Conference, 2009. GLOBECOM 2009. IEEE. .[S.l.]:[s.n.] , 2010:1–7.
[72] ZHANG Y, XUAN J, DE LOS REYES B G, et al. Network motif-based identification oftranscription factor-target gene relationships by integrating multi-source biological data[J].BMC bioinformatics, 2008, 9(1):203.
[73] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America, 2002,99(12):7821.
[74] BARABASI A L. The origin of bursts and heavy tails in human dynamics[J]. Nature, 2005,435(7039):207–211.
[75] NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003.
[76] BOCCALETTI S, LATORA V, MORENO Y, et al. Complex networks: Structure and dynam-ics[J]. Physics reports, 2006, 424(4-5):175–308.
[77] COSTA L F, RODRIGUES F A, TRAVIESO G, et al. Characterization of complex networks:A survey of measurements[J]. Advances in Physics, 2007, 56(1):167–242.
[78]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].[S.l.]:清华大学出版社, 2006.
[79]郭雷,徐晓鸣等.复杂网络[M].[S.l.]:上海科技教育出版社, 2006.
[80]史定华.网络度分布理论[M].[S.l.]:高等教育出版社, 2011.
[81] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J].Physical Review E, 2004, 69(2):026113.
[82] GLEISER P, DANON L. Community structure in jazz[J]. Arxiv preprint cond-mat/0307434,2003.
[83] TRAUD A L, KELSIC E D, MUCHA P, et al. Comparing community structure to character-istics in online collegiate social networks[J]. Arxiv preprint arXiv:0809.0690, 2008.
[84] TYLER J R, WILKINSON D M, HUBERMAN B A. Email as spectroscopy: Auto-mated discovery of community structure within organizations[C]//Communities and tech-nologies.[S.l.]: Kluwer, B.V., 2003:81–96.
[85] FLAKE G W, LAWRENCE S, GILES C L, et al. Self-organization and identification of webcommunities[J]. IEEE Computer, 2002, 35(3):66–70.
[86] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities inlarge networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008:P10008.
[87] HOLME P, HUSS M, JEONG H. Subnetwork hierarchies of biochemical pathways[J]. Bioin-formatics, 2003, 19(4):532.
[88] LEWIS A C F, JONES N S, PORTER M A, et al. The function of communities in proteininteraction networks[J]. BMC Systems Biology.
[89] WILKINSON D M, HUBERMAN B A. A method for finding communities of relatedgenes[J]. Proceedings of the National Academy of Sciences of the United States of America,2004, 101(Suppl 1):5241.
[90] ZHOU T, ZHAO M, CHEN G, et al. Phase synchronization on scale-free networks withcommunity structure[J]. Physics Letters A, 2007, 368(6):431–434.
[91] PARK K, LAI Y C, GUPTE S, et al. Synchronization in complex networks with a modularstructure[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2006, 16:015105.
[92] YAN G, FU Z Q, REN J, et al. Collective synchronization induced by epidemic dynamicson complex networks with communities[J]. Physical Review E, 2007, 75(1):016108.
[93] NEWMAN M E J. Detecting community structure in networks[J]. The European PhysicalJournal B-Condensed Matter and Complex Systems, 2004, 38(2):321–330.
[94] DANON L, DIAZ-GUILERA A, DUCH J, et al. Comparing community structure identifica-tion[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005:P09008.
[95] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3-5):75–174.
[96] KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs[J]. BellSystem Technical Journal, 1970, 49(2):291–307.
[97] POTHEN A, SIMON H D, LIOU K P. Partitioning sparse matrices with eigenvectors ofgraphs[J]. SIAM J. Matrix Anal. Appl., 1990, 11(3):430–452.
[98] FIEDLER M. Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal,1973, 23(2):298–305.
[99]戈卢布G H,范洛恩(著) C F,亚湘袁(译).矩阵计算[M].[S.l.]:科学出版社, 2001.
[100] CORMEN T H, LEIZERSON C E, RIVEST R L.算法导论(影印版,第二版)[M].[S.l.]:北京:机械工业出版社, 2006.
[101] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977,40(1):35–41.
[102] RADICCHI F, CASTELLANO C, CECCONI F, et al. Defining and identifying communitiesin networks[J]. Proceedings of the National Academy of Sciences of the United States ofAmerica, 2004, 101(9):2658.
[103] CASTELLANO C, CECCONI F, LORETO V, et al. Self-contained algorithms to detect com-munities in networks[J]. The European Physical Journal B-Condensed Matter and ComplexSystems, 2004, 38(2):311–319.
[104] CHEN J, YUAN B. Detecting functional modules in the yeast protein–protein interactionnetwork[J]. Bioinformatics, 2006, 22(18):2283.
[105] FORTUNATO S, LATORA V, MARCHIORI M. Method to find community structures basedon information centrality[J]. Phys. Rev. E, 2004, 70.
[106] GREGORY S. An algorithm to find overlapping community structure in networks[J]. Knowl-edge Discovery in Databases: PKDD 2007, 2007:91–102.
[107] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. PhysicalReview E, 2004, 69(6):066133.
[108] BRANDES U, DELLING D, GAERTLER M, et al. On modularity clustering[J]. IEEE Trans-actions on Knowledge and Data Engineering, 2007:172–188.
[109] CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very largenetworks[J]. Physical Review E, 2004, 70(6):066111.
[110] DANON L, D′IAZ-GUILERA A, ARENAS A. The effect of size heterogeneity on commu-nity identification in complex networks[J]. Journal of Statistical Mechanics: Theory andExperiment, 2006, 2006:P11010.
[111] WAKITA K, TSURUMI T. Finding community structure in mega-scale social net-works:[extended abstract][C]//Proceedings of the 16th international conference on WorldWide Web. .[S.l.]: [s.n.] , 2007:1275–1276.
[112] SCHUETZ P, CAFLISCH A. Efficient modularity optimization by multistep greedy algorithmand vertex mover refinement[J]. Physical Review E, 2008, 77(4):046112.
[113] SCHUETZ P, CAFLISCH A. Multistep greedy algorithm identifies community structure inreal-world and computer-generated networks[J]. Physical Review E, 2008, 78(2):026112.
[114] PUJOL J M, BE′JAR J, DELGADO J. Clustering algorithm for determining community struc-ture in large networks[J]. Physical Review E, 2006, 74(1):016107.
[115] DU H, FELDMAN M W, LI S, et al. An algorithm for detecting community structure ofsocial networks based on prior knowledge and modularity[J]. Complexity, 2007, 12(3):53–60.
[116] YE Z, HU S, YU J. Adaptive clustering algorithm for community detection in complexnetworks[J]. Physical Review E, 2008, 78(4):046115.
[117] MEI J, HE S, SHI G, et al. Revealing network communities through modularity maximiza-tion by a contraction–dilation method[J]. New Journal of Physics, 2009, 11:043025.
[118] KIRKPATRICK S, JR. D G, VECCHI M P. Optimization by simmulated annealing[J]. sci-ence, 1983, 220(4598):671–680.
[119] GUIMERA R, AMARAL L A N. Functional cartography of complex metabolic networks[J].Nature, 2005, 433(7028):895–900.
[120] GUIMERA R, AMARAL L A N. Cartography of complex networks: modules and universalroles[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005:P02001.
[121] BOETTCHER S, PERCUS A G. Optimization with extremal dynamics[J]. Physical ReviewLetters, 2001, 86(23):5211–5214.
[122] DUCH J, ARENAS A. Community detection in complex networks using extremal optimiza-tion[J]. Physical Review E, 2005, 72(2):027104.
[123] HOLLAND J H. Adaptation in natural and artificial systems[J]. 1975.
[124] GLOVER F. Future paths for integer programming and links to artificial intelligence[J].Computers & Operations Research, 1986, 13(5):533–549.
[125] TASGIN M, HERDAGDELEN A, BINGOL H. Community detection in complex networksusing genetic algorithms[J]. Arxiv preprint arXiv:0711.0491, 2007.
[126] LIU X, LI D, WANG S, et al. Effective algorithm for detecting community structure incomplex networks based on GA and clustering[J]. Computational Science–ICCS 2007,2007:657–664.
[127] ARENAS A, FERNANDEZ A, GOMEZ S. Analysis of the structure of complex networks atdifferent resolution levels[J]. New Journal of Physics, 2008, 10:053039.
[128] L U¨Z, HUANG W. Iterated tabu search for identifying community structure in complexnetworks[J]. Physical Review E, 2009, 80(2):026130.
[129] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of theNational Academy of Sciences, 2006, 103(23):8577.
[130] NEWMAN M E J. Finding community structure in networks using the eigenvectors of ma-trices[J]. Physical Review E, 2006, 74(3):036104.
[131] LEICHT E A, NEWMAN M E J. Community structure in directed networks[J]. PhysicalReview Letters, 2008, 100(11):118703.
[132] BARBER M J. Modularity and community detection in bipartite networks[J]. PhysicalReview E, 2007, 76(6):066102.
[133] BARBER M J, FARIA M, STREIT L, et al. Searching for communities in bipartite net-works[J]. Arxiv preprint arXiv:0803.2854, 2008.
[134] RICHARDSON T, MUCHA P, PORTER M A. Spectral tripartitioning of networks[J]. PhysicalReview E, 2009, 80(3):036111.
[135] WHITE S, SMYTH P. A spectral clustering approach to finding communities ingraphs[C]//Proceedings of the fifth SIAM international conference on data mining. .[S.l.]:[s.n.] , 2005:274.
[136] RUAN J, ZHANG W. An efficient spectral algorithm for network community discovery andits applications to biological and social networks[C]//icdm. .[S.l.]: [s.n.] , 2007:643–648.
[137] DONETTI L, MUNOZ M A. Detecting network communities: a new systematic and efficientalgorithm[J]. Journal of Statistical Mechanics: Theory and Experiment, 2004, 2004:P10012.
[138] XU G, TSOKA S, PAPAGEORGIOU L G. Finding community structures in complex net-works using mixed integer optimisation[J]. The European Physical Journal B-CondensedMatter and Complex Systems, 2007, 60(2):231–239.
[139] AGARWAL G, KEMPE D. Modularity-maximizing graph communities via mathematicalprogramming[J]. The European Physical Journal B-Condensed Matter and Complex Sys-tems, 2008, 66(3):409–418.
[140] ARENAS A, DUCH J, FERN A′NDEZ A, et al. Size reduction of complex networks preservingmodularity[J]. New Journal of Physics, 2007, 9:176.
[141] MASSEN C P, DOYE J P K. Identifying communities within energy landscapes[J]. PhysicalReview E, 2005, 71(4):046101.
[142] MUFF S, RAO F, CAFLISCH A. Local modularity measure for network clusterizations[J].Physical Review E, 2005, 72(5):056107.
[143] REICHARDT J, BORNHOLDT S. Detecting fuzzy community structures in complex net-works with a Potts model[J]. Physical Review Letters, 2004, 93(21):218701.
[144] REICHARDT J, BORNHOLDT S. Statistical mechanics of community detection[J]. PhysicalReview E, 2006, 74(1):016110.
[145] ARENAS A, FERNANDEZ A, FORTUNATO S, et al. Motif-based communities in complexnetworks[J]. Journal of Physics A: Mathematical and Theoretical, 2008, 41:224001.
[146] G O′MEZ S, JENSEN P, ARENAS A. Analysis of community structure in networks of corre-lated data[J]. Physical Review E, 2009, 80(1):016114.
[147] KAPLAN T D, FORREST S. A dual assortative measure of community structure[J]. Arxivpreprint arXiv:0801.3290, 2008.
[148] TRAAG V, BRUGGEMAN J. Community detection in networks with positive and negativelinks[J]. Physical Review E, 2009, 80(3):036115.
[149] GUIMER A` R, SALES-PARDO M, AMARAL L A N. Module identification in bipartite anddirected networks[J]. Physical Review E, 2007, 76(3):036102.
[150] LI Z, ZHANG S, WANG R S, et al. Quantitative function for community detection[J].Physical Review E, 2008, 77(3):036109.
[151] GUIMERA R, SALES-PARDO M, AMARAL L A N. Modularity from ?uctuations in randomgraphs and complex networks[J]. Physical Review E, 2004, 70(2):025101.
[152] FORTUNATO S, BARTHE′LEMY M. Resolution limit in community detection[J]. Proceed-ings of the National Academy of Sciences, 2007, 104(1):36.
[153] KUMPULA J, SARAM A¨KI J, KASKI K, et al. Limited resolution in complex networkcommunity detection with Potts model approach[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2007, 56(1):41–45.
[154] RONHOVDE P, NUSSINOV Z. Local resolution-limit-free Potts model for community de-tection[J]. Physical Review E, 2010, 81(4):046114.
[155] LAI D, LU H, NARDINI C. Enhanced modularity-based community detection by randomwalk network preprocessing[J]. Physical Review E, 2010, 81(6):066118.
[156] RUAN J, ZHANG W. Identifying network communities with a high resolution[J]. PhysicalReview E, 2008, 77(1):016104.
[157] NOH J D, RIEGER H. Random walks on complex networks[J]. Phys. Rev. Lett., 2004,92(11):118701.
[158] VAN DONGEN S. Graph clustering by ?ow simulation[J]. PhD Thesis University of Utrecht,2000.
[159] ZHOU H. Network landscape from a Brownian particle’s perspective[J]. Phys. Rev. E, 2003,67(4):041908.
[160] ZHOU H. Distance, dissimilarity index, and network community structure[J]. Phys. Rev. E,2003, 67(6):061901.
[161] ZHOU H, LIPOWSKY R. Network Brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities[J]. Lecture Notes inComputer Science, 2004, 3038:1062–1069.
[162] PONS P, LATAPY M. Computing communities in large networks using random walks[J].Lecture notes in computer science, 2005, 3733:284.
[163] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine* 1[J].Computer networks and ISDN systems, 1998, 30(1-7):107–117.
[164] ROSVALL M, BERGSTROM C T. Maps of random walks on complex networks reveal com-munity structure[J]. Proceedings of the National Academy of Sciences, 2008, 105(4):1118.
[165] LAI D, LU H, NARDINI C. Finding communities in directed networks by PageRank randomwalk induced network embedding[J]. Physica A: Statistical Mechanics and its Applications,2010, 389(12):2443–2454.
[166] DELVENNE J C, YALIRAKI S, BARAHONA M. Stability of graph communities across timescales[J]. Proceedings of the National Academy of Sciences, 2010, 107(29):12755.
[167] LAMBIOTTE R, DELVENNE J, BARAHONA M. Laplacian dynamics and multiscale modularstructure in networks[J]. arXiv:, 2009, 0812.1770.
[168] EVANS T S, LAMBIOTTE R. Line graphs, link partitions, and overlapping communities[J].Phys. Rev. E, 2009, 80(1):016105.
[169] ARENAS A, DIAZ-GUILERA A, PE′REZ-VICENTE C. Synchronization reveals topologicalscales in complex networks[J]. Physical Review Letters, 2006, 96(11):114102.
[170] ARENAS A, DIAZ-GUILERA A. Synchronization and modularity in complex networks[J].The European Physical Journal-Special Topics, 2007, 143(1):19–25.
[171] BOCCALETTI S, IVANCHENKO M, LATORA V, et al. Detecting complex network modu-larity by dynamical clustering[J]. Physical Review E, 2007, 75(4):045102.
[172] LI D, LEYVA I, ALMENDRAL J A, et al. Synchronization interfaces and overlapping com-munities in complex networks[J]. Physical Review Letters, 2008, 101(16):168701.
[173] ISPOLATOV I, MAZO I, YURYEV A. Finding mesoscopic communities in sparse net-works[J]. Journal of Statistical Mechanics: Theory and Experiment, 2006, 2006:P09014.
[174] SON S W, JEONG H, NOH J D. Random field Ising model and community structure incomplex networks[J]. The European Physical Journal B-Condensed Matter and ComplexSystems, 2006, 50(3):431–437.
[175] RONHOVDE P, NUSSINOV Z. Multiresolution community detection for megascale networksby information-based replica correlations[J]. Physical Review E, 2009, 80(1):016109.
[176] HASTINGS M. Community detection as an inference problem.[J]. Physical Review. E, 2006,74(3):035102.
[177] NEWMAN M, LEICHT E. Mixture models and exploratory analysis in networks[J]. Pro-ceedings of the National Academy of Sciences, 2007, 104(23):9564.
[178] RAMASCO J J, MUNGAN M. Inversion method for content-based networks[J]. PhysicalReview E, 2008, 77(3):036122.
[179] HOFMAN J, WIGGINS C. Bayesian approach to network modularity[J]. Physical reviewletters, 2008, 100(25):258701.
[180] BAGROW J P, BOLLT E M. Local method for detecting communities[J]. Physical ReviewE, 2005, 72(4):046108.
[181] CLAUSET A. Finding local community structure in networks[J]. Physical Review E, 2005,72(2):026132.
[182] WU F, HUBERMAN B A. Finding communities in linear time: a physics approach[J]. TheEuropean Physical Journal B-Condensed Matter and Complex Systems, 2004, 38(2):331–338.
[183] GUDKOV V, MONTEALEGRE V, NUSSINOV S, et al. Community detection in complexnetworks by dynamical simplex evolution.[J]. Physical review. E, Statistical, nonlinear, andsoft matter physics, 2008, 78(1):016113.
[184] KRAWCZYK M J. Differential equations as a tool for community identification[J]. PhysicalReview E, 2008, 77(6):065701.
[185] RAGHAVAN U, ALBERT R, KUMARA S. Near linear time algorithm to detect communitystructures in large-scale networks[J]. Physical Review E, 2007, 76(3):036106.
[186] TIBE′LY G, KERTE′SZ J. On the equivalence of the label propagation method of communitydetection and a Potts model approach[J]. Physica A: Statistical Mechanics and its Applica-tions, 2008, 387(19-20):4982–4984.
[187] LEUNG I X Y, HUI P, LIO P, et al. Towards real-time community detection in large net-works[J]. Physical Review E, 2009, 79(6):066107.
[188] BARBER M J, CLARK J W. Detecting network communities by propagating labels underconstraints[J]. Physical Review E, 2009, 80(2):026129.
[189] PALLA G, DERE′NYI I, FARKAS I, et al. Uncovering the overlapping community structureof complex networks in nature and society[J]. Nature, 2005, 435(7043):814–818.
[190] FARKAS I, A′BEL D, PALLA G, et al. Weighted network modules[J]. New Journal ofPhysics, 2007, 9:180.
[191] PALLA G, FARKAS I J, POLLNER P, et al. Directed network modules[J]. New Journal ofPhysics, 2007, 9:186.
[192] LEHMANN S, SCHWARTZ M, HANSEN L K. Biclique communities[J]. Physical ReviewE, 2008, 78(1):016108.
[193] KUMPULA J M, KIVEL A¨M, KASKI K, et al. Sequential algorithm for fast clique percola-tion[J]. Physical Review E, 2008, 78(2):026109.
[194] ZHANG S H, WANG R S, ZHANG X S. Identification of overlapping community structurein complex networks using fuzzy c-means clustering[J]. Physica A: Statistical Mechanicsand its Applications, 2007, 374(1):483–490.
[195] NEPUSZ T, PETR O′CZI A, NE′GYESSY L, et al. Fuzzy communities and the concept ofbridgeness in complex networks[J]. Physical Review E, 2008, 77(1):016107.
[196] AHN Y Y, BAGROW J P, LEHMANN S. Link communities reveal multiscale complexity innetworks[J]. Nature, 2010, 466(7307):761–764.
[197] GREGORY S. Finding Overlapping Communities Using Disjoint Community DetectionAlgorithms[J]. Complex Networks, 2009:47–61.
[198] WEN H, LEICHT E, D’SOUZA R M. Improving community detection in networks bytargeted node removal[J]. Physical Review E, 2011, 83(1):016114.
[199] LAI D, NARDINI C, LU H. Partitioning networks into communities by message passing[J].Physical Review E, 2011, 83(1):016115.
[200] LANCICHINETTI A, FORTUNATO S, KERTE′SZ J. Detecting the overlapping and hierarchi-cal community structure in complex networks[J]. New Journal of Physics, 2009, 11:033015.
[201] SALES-PARDO M, GUIMERA R, MOREIRA A A, et al. Extracting the hierarchical orga-nization of complex systems[J]. Proceedings of the National Academy of Sciences, 2007,104(39):15224.
[202] CLAUSET A, MOORE C, NEWMAN M E J. Structural inference of hierarchies in net-works[J]. Statistical network analysis: models, issues, and new directions, 2007:1–13.
[203] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction ofmissing links in networks[J]. Nature, 2008, 453(7191):98–101.
[204] PALLA G, BARAB A′SI A L, VICSEK T. Quantifying social group evolution[J]. Nature,2007, 446(7136):664–667.
[205] FENN D J, PORTER M A, MCDONALD M, et al. Dynamic communities in multichanneldata: An application to the foreign exchange market during the 2007–2008 credit crisis[J].Chaos: An Interdisciplinary Journal of Nonlinear Science, 2009, 19:033119.
[206] SUN J, FALOUTSOS C, PAPADIMITRIOU S, et al. Graphscope: parameter-free mining oflarge time-evolving graphs[C]//Proceedings of the 13th ACM SIGKDD international con-ference on Knowledge discovery and data mining. .[S.l.]: [s.n.] , 2007:687–696.
[207] DHILLON I S, GUAN Y, KULIS B. Kernel k-means: spectral clustering and normalizedcuts[C]//Proceedings of the tenth ACM SIGKDD international conference on Knowledgediscovery and data mining. .[S.l.]: [s.n.] , 2004:551–556.
[208] NEWMAN M E J. Analysis of weighted networks[J]. Phys. Rev. E, 2004, 70(5):056131.
[209] ZACHARY W W. An information ?ow model for con?ict and fission in small groups[J].Journal of Anthropological Research, 1977, 33(4):452–473.
[210] HAREL D, KOREN Y. On clustering using random walks[J]. Lecture Notes in ComputerScience, 2001, 2245:18–41.
[211] LANCICHINETTI A, FORTUNATO S. Benchmarks for testing community detection algo-rithms on directed and weighted graphs with overlapping communities[J]. Phys. Rev. E,2009, 80(1):016118.
[212] STOUFFER D B, CAMACHO J, GUIMER A` R, et al. Quantitative patterns in the structure ofmodel and empirical food webs[J]. Ecology, 2005, 86(5):1301–1311.
[213] KIM Y, SON S W, JEONG H. Finding communities in directed networks[J]. PhysicalReview E, 2010, 81(1):016103.
[214] KIM Y, SON S W, JEONG H. Link Rank: Finding communities in directed networks[J].arXiv, 2009(arXiv:0902.3728v1).
[215] LANGVILLE A N, MEYER C D. Deeper inside pagerank[J]. Internet Mathematics, 2004,1(3):335–380.
[216] VON LUXBURG U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007,17(4):395–416.
[217] CAPOCCI A, SERVEDIO V, CALDARELLI G, et al. Detecting communities in large net-works[J]. Physica A: Statistical Mechanics and its Applications, 2005, 352(2-4):669–676.
[218] ZHU X. Semi-supervised learning literature survey[J]. Computer Science, University ofWisconsin-Madison, 2006.
[219] CHUNG F. Laplacians and the Cheeger inequality for directed graphs[J]. Annals of Combi-natorics, 2005, 9(1):1–19.
[220] HAN J, KAMBER M. Data mining: concepts and techniques[M].[S.l.]: Morgan Kaufmann,2006.
[221] ZHOU D, HUANG J, SCH O¨LKOPF B. Learning from labeled and unlabeled data on adirected graph[C]//Proceedings of the 22nd international conference on Machine learning..[S.l.]: [s.n.] , 2005:1036–1043.
[222] CHEN M, YANG Q, TANG X. Directed graph embedding[C]//Proceedings of the Interna-tional Joint Conference on Artificial Intelligence (IJCAI). .[S.l.]: [s.n.] , 2007:2707–2712.
[223] CAI D, HE X, HAN J. Spectral regression: a unified subspace learning framework forcontent-based image retrieval[C]//Proceedings of the 15th international conference on Mul-timedia. .[S.l.]: [s.n.] , 2007:403–412.
[224] JAMES M. Race, school integration, and friendship segregation in America[J]. AmericanJournal of Sociology, 2001, 107(3):679–716.
[225] LANCICHINETTI A, FORTUNATO S. Community detection algorithms: A comparativeanalysis[J]. Physical Review E, 2009, 80(5):056117.
[226] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science,2007, 315(5814):972.
[227] LAI D, LU H. Identification of community structure in complex networks using affinitypropagation clustering method[J]. Modern Physics Letters B, 2008, 22:1547–1566.
[228] LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks[J]. Phys. Rev. E,2006, 73(2):026120.
[229] CALI N′SKI T, HARABASZ J. A dendrite method for cluster analysis[J]. Communications inStatistics-Simulation and Computation, 1974, 3(1):1–27.
[230] LUSSEAU D. The emergent properties of a dolphin social network[J]. Proceedings of theRoyal Society of London. Series B: Biological Sciences, 2003, 270(Suppl 2):S186.
[231] RAVASZ E, BARAB A′SI A L. Hierarchical organization in complex networks[J]. Phys. Rev.E, 2003, 67(2):026112.
[232] ARENAS A, FERN A′NDEZ A, G O′MEZ S. Analysis of the structure of complex networks atdifferent resolution levels[J]. New J. Phys., 2008, 10:053039.
[233] LAMBIOTTE R. Multi-scale modularity in complex networks[C]//Modeling and Optimiza-tion in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2010 Proceedings of the 8th Inter-national Symposium on. .[S.l.]: [s.n.] , 2010:546–553.
[234] SHAWE-TAYLOR J, CRISTIANINI N. Kernel methods for pattern analysis[M].[S.l.]: Cam-bridge University Press, 2004.
[235] LAI D, YANG X, WU G, et al. Inference of gene networks―application to Bifidobac-terium[J]. Bioinformatics, 2011, 27(2):232.
[236] GARDNER T, DI BERNARDO D, LORENZ D, et al. Inferring genetic networks and identi-fying compound mode of action via expression profiling[J]. Science, 2003, 301(5629):102.