复杂网络中的社团结构特性研究
|
摘要
现代的复杂网络科学极大促进了人们对现实复杂系统的理解。社团结构是复杂网络的一个极其重要的特性,社团结构就是一组其内部节点间联系非常紧密而与网络中的其他部分联系相对比较稀疏的节点的子集。复杂网络中的社团结构研究在社会学、生物学和计算机科学等多个领域都具有很重要的意义。
近年来,针对不同类型的大规模复杂网络,人们提出了很多寻找社团结构的算法。本文首先对最新的社团结构划分算法进行了综述,给出了该领域重要的研究进展。其次,网络的社团结构特性本质上是由网络的几阶度分布决定一直是网络科学领域悬而未决的问题之一。为此,本文采用高阶随机重连方法和社团检测算法进行仿真实验对该问题进行了研究。最后,有针对性地提出了一种基于Louvain的改进新算法,可以用于寻找加权网络中具有重叠性和层次性的社团结构,并利用该算法分析了在线社会网络Wealink的各种特性,重点分析了Wealink社团特性的发展和演化。
本论文所作的主要贡献如下:
1综述了该领域最新的比较有代表性的一些寻找社团结构的算法,重点分析了基于模块度指标的改进算法,能够体现社团层次性和重叠性的新算法,衡量社团划分算法好坏的基准图。最后展望了该领域的未来研究方向。
2在保持网络一阶、二阶和三阶度相关特性不变的情形下,利用随机重连方法和社团检测算法研究了复杂网络的社团结构特性。仿真分析发现保持网络三阶度相关特性不变的随机重连方法所构造的网络则可以很高精度地呈现原有网络的社团特性,从而表明网络的社团结构可以由三阶度相关特性有效地刻画(不需要更高阶)。本文的研究提供了一种网络构造方法,即利用三阶随机重连方法可构造出能够体现真实网络社团结构这一特性的随机网络。
3提出了一种可用于寻找加权网络中社团结构特性的算法,使得新算法能够同时体现出网络中社团的层次性和重叠性,并能够在较短时间内处理大规模的网络数据。其次提出了一种基于微调策略分析动态网络演化中社团特性的算法,能够在网络规模变化不大的前提下对网络高效地进行社团特性的分析。从而为动态网络的社团研究提供了一种较好的途径。最后利用基准图对三种经典算法的优劣性进行了比较。
4利用新算法对在线社会网络Wealink(http://www.wealink.com)的结构特性和动态演化进行了实证分析,其中包含了网络规模、社团结构、重叠性节点、聚类系数和度分布等特性,重点研究了若邻网中社团结构的动态演化。
The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of complex networks is community structure. A community structure is a densely connected subset of nodes that is only sparsely linked to the remaining networks. Detecting communities in complex networks is of great importance in sociology, biology and computer science and so on.
In recent years, a lot of community discovery algorithms have been proposed aiming at different kinds of large scale complex networks. In this paper, we have summarized some latest representative algorithms and have pointed out the important progress in this research area. By which order of degree distribution of networks, the community structure in complex networks can be remarkably maintained is always one problem up in the air in the network science. Then, we have studied the problem with the aid of random rewiring algorithm and community structure detection algorithm. Finally, we have constructed a new algorithm which can detect the hierarchical and overlapping communities in weighted networks. We have analyzed the characteristics of Wealink, especially the dynamic evolutions of communities in the network.
The main contributions of the dissertation are summarized as follows.
1 We have reviewed some latest representative algorithms, focusing on the improved methods based on the modularity function, algorithms which can detect overlapping and hierarchical community structure in networks, benchmark in detecting communities. We have pointed out some promising directions in this area.
2 We have compared the community structures of real networks with computer-generated network models on which the random rewiring process took place and have found that community structure is well maintained after third-order random rewiring. We have established a path towards construction of random graphs matching the community structure property of real networks after the third-order random rewiring.
3 We have designed a new community detection algorithm which can detect the hierarchical and overlapping communities of networks in a reasonably short time. We have proposed another new algorithm which can detect the dynamic evolution of communities when the evolution of networks is not so significant when compared to the whole size of networks. We have also used the benchmark graphs to compare the advantages and disadvantages of three main algorithms.
4 We have studied characteristics and structural evolutions of a large online social network-Wealink (http://www.wealink.com), including network size, community structure, overlapping nodes, clustering coefficient and the distributions of degree and so on, especially the dynamic evolutions of community structure in the network.
近年来,针对不同类型的大规模复杂网络,人们提出了很多寻找社团结构的算法。本文首先对最新的社团结构划分算法进行了综述,给出了该领域重要的研究进展。其次,网络的社团结构特性本质上是由网络的几阶度分布决定一直是网络科学领域悬而未决的问题之一。为此,本文采用高阶随机重连方法和社团检测算法进行仿真实验对该问题进行了研究。最后,有针对性地提出了一种基于Louvain的改进新算法,可以用于寻找加权网络中具有重叠性和层次性的社团结构,并利用该算法分析了在线社会网络Wealink的各种特性,重点分析了Wealink社团特性的发展和演化。
本论文所作的主要贡献如下:
1综述了该领域最新的比较有代表性的一些寻找社团结构的算法,重点分析了基于模块度指标的改进算法,能够体现社团层次性和重叠性的新算法,衡量社团划分算法好坏的基准图。最后展望了该领域的未来研究方向。
2在保持网络一阶、二阶和三阶度相关特性不变的情形下,利用随机重连方法和社团检测算法研究了复杂网络的社团结构特性。仿真分析发现保持网络三阶度相关特性不变的随机重连方法所构造的网络则可以很高精度地呈现原有网络的社团特性,从而表明网络的社团结构可以由三阶度相关特性有效地刻画(不需要更高阶)。本文的研究提供了一种网络构造方法,即利用三阶随机重连方法可构造出能够体现真实网络社团结构这一特性的随机网络。
3提出了一种可用于寻找加权网络中社团结构特性的算法,使得新算法能够同时体现出网络中社团的层次性和重叠性,并能够在较短时间内处理大规模的网络数据。其次提出了一种基于微调策略分析动态网络演化中社团特性的算法,能够在网络规模变化不大的前提下对网络高效地进行社团特性的分析。从而为动态网络的社团研究提供了一种较好的途径。最后利用基准图对三种经典算法的优劣性进行了比较。
4利用新算法对在线社会网络Wealink(http://www.wealink.com)的结构特性和动态演化进行了实证分析,其中包含了网络规模、社团结构、重叠性节点、聚类系数和度分布等特性,重点研究了若邻网中社团结构的动态演化。
The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of complex networks is community structure. A community structure is a densely connected subset of nodes that is only sparsely linked to the remaining networks. Detecting communities in complex networks is of great importance in sociology, biology and computer science and so on.
In recent years, a lot of community discovery algorithms have been proposed aiming at different kinds of large scale complex networks. In this paper, we have summarized some latest representative algorithms and have pointed out the important progress in this research area. By which order of degree distribution of networks, the community structure in complex networks can be remarkably maintained is always one problem up in the air in the network science. Then, we have studied the problem with the aid of random rewiring algorithm and community structure detection algorithm. Finally, we have constructed a new algorithm which can detect the hierarchical and overlapping communities in weighted networks. We have analyzed the characteristics of Wealink, especially the dynamic evolutions of communities in the network.
The main contributions of the dissertation are summarized as follows.
1 We have reviewed some latest representative algorithms, focusing on the improved methods based on the modularity function, algorithms which can detect overlapping and hierarchical community structure in networks, benchmark in detecting communities. We have pointed out some promising directions in this area.
2 We have compared the community structures of real networks with computer-generated network models on which the random rewiring process took place and have found that community structure is well maintained after third-order random rewiring. We have established a path towards construction of random graphs matching the community structure property of real networks after the third-order random rewiring.
3 We have designed a new community detection algorithm which can detect the hierarchical and overlapping communities of networks in a reasonably short time. We have proposed another new algorithm which can detect the dynamic evolution of communities when the evolution of networks is not so significant when compared to the whole size of networks. We have also used the benchmark graphs to compare the advantages and disadvantages of three main algorithms.
4 We have studied characteristics and structural evolutions of a large online social network-Wealink (http://www.wealink.com), including network size, community structure, overlapping nodes, clustering coefficient and the distributions of degree and so on, especially the dynamic evolutions of community structure in the network.
引文
[1] Dorogovtsev S N, Mendes J F. Evolution of networks. Adv. Phys, 2002, 51: 1079.
[2] Strogatz S H. Exploring complex networks. Nature, 2001, 410: 268-276.
[3] Girvan M, Newman M E J. Community structure in social and biological networks. Proc. Natl. Acad. Sci, 2002, 99: 7821-7826.
[4] Newman M E J. Scientific collaboration networks. Phys. Rev. E, 2001, 64: 016132.
[5] Jeong H, Mason S P, Oltvai Z N, et al. Lethality and centrality in protein networks. Nature, 2001, 411: 41-42.
[6] Albert R, Jeong H, Barabási A L. The diameter of the World-Wide Web. Nature, 1999, 401: 130.
[7] Flake G W, Lawrence S R, Giles C L, Coetzee F M. Self-organization and identification of Web communities. IEEE Computer, 2002, 35: 66-71.
[8] Newman M E J, Girvan M. Finding and evaluating community structure in networks, Phys. Rev. E, 2004, 69: 026113.
[9] Newman M E J. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 2004, 69: 066133.
[10] Girvan M, Newman M E J. Community structure in social and biological networks. Proc. Natl. Acad. Sci, 2001, 99: 7821-7826.
[11] Gleiser P, Danon L. Community structure in jazz. Advances in Complex Systems, 2003, 6: 565-573.
[12] HoLouvaine P, Huss M, Jeong H. Subnetwork hierarchies of biochemical pathways. Bioinformatics, 2003, 19: 532-538.
[13] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks. New Journal of Physics, 2009, 11(3): 033015.
[14] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435: 814.
[15] Karrer B, Levina E, Newman M E J. Robustness of community structure in networks [J]. Phys. Rev. E, 2008, 77: 046119.
[16] Palla G, Barabasi A L, Vicsek T. Quantifying social group evolution[J]. Nature,2007, 446(7136): 664-667.
[17] Watts D J, Strogatz S H. Collective dynamics of‘small-world’networks. Nature, 1998, 393: 440-442.
[18] B?rner K, Dallasta L, Ke W M, et al. Studying the emerging global brain: Analyzing and visualizing the impact of co-authorship teams. Complexity, 2005, 10(4): 57-67.
[19] Ramasco J, Morris S A. Social inertia in collaboration networks. Phys. Rev. E, 2006, 73: 016122.
[20] Hu H B, Wang X F. Evolution of a large online social network. Physics Letters A. 2009, 373: 1105–1110
[1]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006.
[2] Fortunato S, Castellano C. Community structure in graphs[J/OL]. Eprint arXiv, 2007, 0712: 2716. [2009-03-10]. http://www.arXiv.org.
[3] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Phys. Rev. E, 2004, 69 (2): 026113.
[4] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Phys. Rev. E, 2004, 70: 066111.
[5] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities hierarchies in large networks[J]. J. Stat. Mech., 2008, P10008.
[6] Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435: 814-818.
[7] Hartmanis J, Stearns R E. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 1965, 117: 285-306
[8] Fortunato S, Barthelemy M. Resolution limit in community detection [J]. PPNAS, 2007, 104(1): 36-41.
[9] Newman M E J. Analysis of weighted networks[J]. Phys. Rev. E, 2004, 70: 056131.
[10] Arenas A, Duch J, Fernandez A, et al. Community Structure in Directed Networks. New J. Phys, 2007, 9: 176.
[11] Newman M E J, Leicht E A. Community Structure in Directed Networks[J]. Proc. Natl. Acad. Sci., 2007, 104: 9564.
[12] Shen H, Cheng X, Cai K, et al. Detect overlapping and hierarchical community structure in networks [J]. Physica A, 2009, 388: 1706-1712.
[13] Nicosia V, Mangioni G, Carchiolo V, et al. Extending the definition of modularity to directed graphs with overlapping communities. J. Stat. Mech., 2009, 3: 03024.
[14] Kaplan T D, Forrest S. A dual assortative measure of community structure [J]. Eprint arXiv, 2008, 0801: 3290. [2009-03-10]. http://www.arXiv.org.
[15] Gomez S, Jensen P, Arenas A. Analysis of community structure in networks of correlated data [J]. Eprint arXiv, 2008, 0812: 3030. [2009-03-10]. http://www.arXiv.org.
[16] Traag V A, Bruggeman J. Community detection in networks with positive and negative links [J]. Phys. Rev. E, 2009, 80: 036115
[17] Ruan J H, Zhang W X. Identifying network communities with a high resolution [J]. 2008. Phys. Rev. E, 77: 016104.
[18] Sun Y, Danila B, Josic K, et al. Improved community structure detection using a modified fine-tuning strategy. Europhysics Letters. 2009, 86: 28004
[19] Newman M E J. Detecting community structure in networks. Eur. Phys. J. B, 2004, 38(2): 321.
[20] Sales-Pardo M R, Guimera A, Moreira A, et al. Extracting the hierarchical organization of complex systems [J]. Proc. Natl. Acad. Sci., 2007, 104: 15224.
[21] Palla G., Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005, 435: 814-818.
[22] Farkas I,ábel D, Palla G, et al. Weighted network modules [J]. New J. Phys., 2007, 9(6): 180.
[23] Farkas I,ábel D, Palla G, et al. Directed network modules [J]. New J. Phys., 2007, 9(6): 186.
[24] Girvan M, Newman M E J. Community structure in social and biological networks [J]. Proc. Natl. Acad. Sci., 2002, 99 (6): 7821–7826.
[25] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks [J]. New J. Phys., 2009,11: 033015.
[26] Shen H W, Cheng X Q, Cai K, et al. Detect overlapping and hierarchical community structure in networks [J]. Physical A, 2009, 388(8): 1706-1712.
[27] Bron C, Kerbosch J. Algorithm 457: finding all cliques of an undirected graph [J]. Commun. ACM, 1973, 16(9): 575-577.
[28] Ahn Y Y, Bagrow J P, Lehmann S. Communities and Hierarchical Organization of Links in Complex Networks [J/OL]. Eprint arXiv, 2009, 0903: 3178. [2009-03-12]. http://www.arXiv.org.
[29] Evans T S, Lambiotte R. Line Graphs, Link Partitions and Overlapping Communities[J/OL]. Eprint arXiv, 2009, 0903: 2181. [2009-04-01]. ttp://www.arXiv.org.
[30] Noack A, Rotta R. Multi-Level Algorithms for Modularity Clustering[J]. Eprint arXiv, 2008, 0812: 4073. [2009-04-16]. http://www.arXiv.org.
[31] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks [J]. Phys. Rev. E, 2007, 76: 036106.
[32] Hu Y Q, Nie Y C, Yang H, et al. Measuring Significance of Community Structure in Complex Networks [J]. Eprint arXiv, 2009, 0902.3331. [2009-04-16]. http://www.arXiv.org.
[33] Hildebrand R. Identification of community structure in networks with convex optimization. Eprint arXiv, 2008, 0806: 1896. [2009-04-16]. http://www.arXiv.org.
[34] Condon A, Karp R M. Algorithms for graph partitioning on the planted partition model [J]. Random Struct. Algor, 2001, 18(2): 116-140.
[35] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proc. Natl. Acad. Sci., 2002, 99: 8271–8276.
[36] Fan Y, Li M, Zhang P, et al. Accuracy and precision of methods for community identification in weighted networks[J]. Physica A, 2007, 377: 363-372.
[37] Lancichinetti A, Fortunato S, Radicchi F. New benchmark in community detection[J]. Eprint arXiv, 2008, 0805: 4770v2. [2009-04-16]. http://www.arXiv.org.
[38] Sawardecker E N, Sales-Pardo M, Amaral L A N. Detection of node groupmembership in networks with group overlap[J]. Eur. Phys. J. B, 2009, 67: 277.
[39] Karrer B, Levina E, Newman M E J. Robustness of community structure in networks [J]. Phys. Rev. E, 2008, 77: 046119.
[40] Palla G, Barabasi A L, Vicsek T. Quantifying social group evolution[J]. Nature, 2007, 446(7136): 664-667.
[41] Fortunato S. Community detection in graphs[J/OL]. Eprint arXiv, 2009, 0906: 0612v1. [2009-04-20]. http://www.arXiv.org.
[1]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006.
[2] Aiello W, Chung F, Lu L. A random graph model for massive graphs. In STOC, 2000.
[3] Mahadevan P, Krioukov D, Fall K, et al. Systematic topology analysis and generation using degree correlations[J]. ACM SIGCOMM Computer Communication Review, 2006, 36(4): 135-146.
[4] Zachary W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33: 452-473.
[5] M Girvan, Newman M E J. Community structure in social and biological networks[J]. Proc. Natl. Acad. Sci. USA, 2002, 99: 7821-7826.
[6] Jeong H, Mason S P, Barabási A L, et al. Centrality and lethality of proteinnetworks[J]. Nature, 2001, 411: 41-42.
[7] Newman M E J. Scientific collaboration networks. I. Network construction and fundamental results[J]. Phys. Rev. E, 2001, 64: 016131.
[8] Fortunato S, Castellano C. Community structure in graphs[C]. Encyclopedia of Complexity and Systems Science. 2009, 00238.
[9] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities hierarchies in large networks[J]. J. Stat. Mech., 2008, 10008.
[10] Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435: 814-818.
[11] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks[J]. New Journal of Physics, 2009, 11: 033015.
[12] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Phys. Rev. E, 2004, 70: 066111.
[1] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005, 435: 814-818.
[2] Farkas I,ábel D, Palla G, et al. Weighted network modules [J]. New J Phys, 2007, 9(6): 180.
[3] Farkas I,ábel D, Palla G, et al. Directed network modules [J]. New J Phys, 2007, 9(6): 186.
[4] Nicosia V, Mangioni G, Carchiolo V, et al. Extending the definition of modularity to directed graphs with overlapping communities. J Stat Mech., 2009, 3: 03024.
[6] Evans T S, Lambiotte R. Line Graphs, Link Partitions and Overlapping Communities [J/OL]. Eprint arXiv, 2009, 0903: 2181. [2009-04-01]. http://www.arXiv.org.
[7] Gregory S. A Fast Algorithm to Find Overlapping Communities in Networks [J]. Machine Learning and Knowledge Discovery in Databases, 2008, 408-423.
[8] Fortunato S, Castellano C. Community structure in graphs[J/OL]. Eprint arXiv, 2007, 0712: 2716. [2009-03-10]. http://www.arXiv.org.
[9] Karrer B, Levina E, Newman M E J. Robustness of community structure in networks [J]. Phys. Rev. E, 2008, 77: 046119.
[10] Palla G, Barabasi A L, Vicsek T. Quantifying social group evolution[J]. Nature, 2007, 446(7136): 664-667.
[11] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of community hierarchies in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 10: 10008.
[12] Hansen S K, Rainey P B, Haagensen J A J, et al. Evolution of species interactions in a biofiLouvain community. Nature, 2007, 445: 533-536
[13] Fortunato S. Community detection in graphs[J/OL]. Eprint arXiv, 2009, 0906: 0612v1. [2009-04-20]. http://www.arXiv.org.
[14] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005, 435: 814-818.
[15] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks [J]. New J. Phys. 2009, 11: 033015.
[16] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Phys. Rev. E, 2008, 78: 046110
[17] Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E, 2009, 80: 016118
[18] Lancichinetti A, Fortunato S. Community detection algorithms: A comparative analysis.Phys. Rev. E, 2009, 80: 056117.
[1] Katz J E, Rice R E. Social Consequences of Internet Use: Access, Involvement and Interaction [M]. Cambridge MA: The MIT Press, 2002.
[2] WelLouvainan B. Computer networks as social networks [J]. Science, 2001, 293(5537): 2031-2034.
[3] Wasserman S, Faust K. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1994.
[4] HoLouvaine P, Edling C R, Liljeros F. Structure and time evolution of an Internet dating community. Social Networks, 2004, 26: 155–174.
[5]汪小帆,李翔,陈关荣.复杂网络理论及其应用,清华大学出版社,2006.
[6] Barabási A L, Jeong H, Néda Z, et al. Evolution of the social network of scientific collaborations. Physica A, 2002, 311: 590-614.
[7] Hu H B, Wang X F. Evolution of a large online social network. Physics Letters A. 2009, 373: 1105–1110
[8] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Phys. Rev. E, 2004, 70: 066111.
[9] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of community hierarchies in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 10: 10008.
[10] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435: 814-818.
[11] Watts D J, Strogatz S H. Collective dynamics of‘small-world’networks. Nature, 1998, 393: 440-442.
[12] Newman M E J. Assortative mixing in networks. Phys. Rev. Lett., 2002, 89: 208701.
[2] Strogatz S H. Exploring complex networks. Nature, 2001, 410: 268-276.
[3] Girvan M, Newman M E J. Community structure in social and biological networks. Proc. Natl. Acad. Sci, 2002, 99: 7821-7826.
[4] Newman M E J. Scientific collaboration networks. Phys. Rev. E, 2001, 64: 016132.
[5] Jeong H, Mason S P, Oltvai Z N, et al. Lethality and centrality in protein networks. Nature, 2001, 411: 41-42.
[6] Albert R, Jeong H, Barabási A L. The diameter of the World-Wide Web. Nature, 1999, 401: 130.
[7] Flake G W, Lawrence S R, Giles C L, Coetzee F M. Self-organization and identification of Web communities. IEEE Computer, 2002, 35: 66-71.
[8] Newman M E J, Girvan M. Finding and evaluating community structure in networks, Phys. Rev. E, 2004, 69: 026113.
[9] Newman M E J. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 2004, 69: 066133.
[10] Girvan M, Newman M E J. Community structure in social and biological networks. Proc. Natl. Acad. Sci, 2001, 99: 7821-7826.
[11] Gleiser P, Danon L. Community structure in jazz. Advances in Complex Systems, 2003, 6: 565-573.
[12] HoLouvaine P, Huss M, Jeong H. Subnetwork hierarchies of biochemical pathways. Bioinformatics, 2003, 19: 532-538.
[13] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks. New Journal of Physics, 2009, 11(3): 033015.
[14] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435: 814.
[15] Karrer B, Levina E, Newman M E J. Robustness of community structure in networks [J]. Phys. Rev. E, 2008, 77: 046119.
[16] Palla G, Barabasi A L, Vicsek T. Quantifying social group evolution[J]. Nature,2007, 446(7136): 664-667.
[17] Watts D J, Strogatz S H. Collective dynamics of‘small-world’networks. Nature, 1998, 393: 440-442.
[18] B?rner K, Dallasta L, Ke W M, et al. Studying the emerging global brain: Analyzing and visualizing the impact of co-authorship teams. Complexity, 2005, 10(4): 57-67.
[19] Ramasco J, Morris S A. Social inertia in collaboration networks. Phys. Rev. E, 2006, 73: 016122.
[20] Hu H B, Wang X F. Evolution of a large online social network. Physics Letters A. 2009, 373: 1105–1110
[1]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006.
[2] Fortunato S, Castellano C. Community structure in graphs[J/OL]. Eprint arXiv, 2007, 0712: 2716. [2009-03-10]. http://www.arXiv.org.
[3] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Phys. Rev. E, 2004, 69 (2): 026113.
[4] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Phys. Rev. E, 2004, 70: 066111.
[5] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities hierarchies in large networks[J]. J. Stat. Mech., 2008, P10008.
[6] Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435: 814-818.
[7] Hartmanis J, Stearns R E. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 1965, 117: 285-306
[8] Fortunato S, Barthelemy M. Resolution limit in community detection [J]. PPNAS, 2007, 104(1): 36-41.
[9] Newman M E J. Analysis of weighted networks[J]. Phys. Rev. E, 2004, 70: 056131.
[10] Arenas A, Duch J, Fernandez A, et al. Community Structure in Directed Networks. New J. Phys, 2007, 9: 176.
[11] Newman M E J, Leicht E A. Community Structure in Directed Networks[J]. Proc. Natl. Acad. Sci., 2007, 104: 9564.
[12] Shen H, Cheng X, Cai K, et al. Detect overlapping and hierarchical community structure in networks [J]. Physica A, 2009, 388: 1706-1712.
[13] Nicosia V, Mangioni G, Carchiolo V, et al. Extending the definition of modularity to directed graphs with overlapping communities. J. Stat. Mech., 2009, 3: 03024.
[14] Kaplan T D, Forrest S. A dual assortative measure of community structure [J]. Eprint arXiv, 2008, 0801: 3290. [2009-03-10]. http://www.arXiv.org.
[15] Gomez S, Jensen P, Arenas A. Analysis of community structure in networks of correlated data [J]. Eprint arXiv, 2008, 0812: 3030. [2009-03-10]. http://www.arXiv.org.
[16] Traag V A, Bruggeman J. Community detection in networks with positive and negative links [J]. Phys. Rev. E, 2009, 80: 036115
[17] Ruan J H, Zhang W X. Identifying network communities with a high resolution [J]. 2008. Phys. Rev. E, 77: 016104.
[18] Sun Y, Danila B, Josic K, et al. Improved community structure detection using a modified fine-tuning strategy. Europhysics Letters. 2009, 86: 28004
[19] Newman M E J. Detecting community structure in networks. Eur. Phys. J. B, 2004, 38(2): 321.
[20] Sales-Pardo M R, Guimera A, Moreira A, et al. Extracting the hierarchical organization of complex systems [J]. Proc. Natl. Acad. Sci., 2007, 104: 15224.
[21] Palla G., Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005, 435: 814-818.
[22] Farkas I,ábel D, Palla G, et al. Weighted network modules [J]. New J. Phys., 2007, 9(6): 180.
[23] Farkas I,ábel D, Palla G, et al. Directed network modules [J]. New J. Phys., 2007, 9(6): 186.
[24] Girvan M, Newman M E J. Community structure in social and biological networks [J]. Proc. Natl. Acad. Sci., 2002, 99 (6): 7821–7826.
[25] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks [J]. New J. Phys., 2009,11: 033015.
[26] Shen H W, Cheng X Q, Cai K, et al. Detect overlapping and hierarchical community structure in networks [J]. Physical A, 2009, 388(8): 1706-1712.
[27] Bron C, Kerbosch J. Algorithm 457: finding all cliques of an undirected graph [J]. Commun. ACM, 1973, 16(9): 575-577.
[28] Ahn Y Y, Bagrow J P, Lehmann S. Communities and Hierarchical Organization of Links in Complex Networks [J/OL]. Eprint arXiv, 2009, 0903: 3178. [2009-03-12]. http://www.arXiv.org.
[29] Evans T S, Lambiotte R. Line Graphs, Link Partitions and Overlapping Communities[J/OL]. Eprint arXiv, 2009, 0903: 2181. [2009-04-01]. ttp://www.arXiv.org.
[30] Noack A, Rotta R. Multi-Level Algorithms for Modularity Clustering[J]. Eprint arXiv, 2008, 0812: 4073. [2009-04-16]. http://www.arXiv.org.
[31] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks [J]. Phys. Rev. E, 2007, 76: 036106.
[32] Hu Y Q, Nie Y C, Yang H, et al. Measuring Significance of Community Structure in Complex Networks [J]. Eprint arXiv, 2009, 0902.3331. [2009-04-16]. http://www.arXiv.org.
[33] Hildebrand R. Identification of community structure in networks with convex optimization. Eprint arXiv, 2008, 0806: 1896. [2009-04-16]. http://www.arXiv.org.
[34] Condon A, Karp R M. Algorithms for graph partitioning on the planted partition model [J]. Random Struct. Algor, 2001, 18(2): 116-140.
[35] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proc. Natl. Acad. Sci., 2002, 99: 8271–8276.
[36] Fan Y, Li M, Zhang P, et al. Accuracy and precision of methods for community identification in weighted networks[J]. Physica A, 2007, 377: 363-372.
[37] Lancichinetti A, Fortunato S, Radicchi F. New benchmark in community detection[J]. Eprint arXiv, 2008, 0805: 4770v2. [2009-04-16]. http://www.arXiv.org.
[38] Sawardecker E N, Sales-Pardo M, Amaral L A N. Detection of node groupmembership in networks with group overlap[J]. Eur. Phys. J. B, 2009, 67: 277.
[39] Karrer B, Levina E, Newman M E J. Robustness of community structure in networks [J]. Phys. Rev. E, 2008, 77: 046119.
[40] Palla G, Barabasi A L, Vicsek T. Quantifying social group evolution[J]. Nature, 2007, 446(7136): 664-667.
[41] Fortunato S. Community detection in graphs[J/OL]. Eprint arXiv, 2009, 0906: 0612v1. [2009-04-20]. http://www.arXiv.org.
[1]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006.
[2] Aiello W, Chung F, Lu L. A random graph model for massive graphs. In STOC, 2000.
[3] Mahadevan P, Krioukov D, Fall K, et al. Systematic topology analysis and generation using degree correlations[J]. ACM SIGCOMM Computer Communication Review, 2006, 36(4): 135-146.
[4] Zachary W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33: 452-473.
[5] M Girvan, Newman M E J. Community structure in social and biological networks[J]. Proc. Natl. Acad. Sci. USA, 2002, 99: 7821-7826.
[6] Jeong H, Mason S P, Barabási A L, et al. Centrality and lethality of proteinnetworks[J]. Nature, 2001, 411: 41-42.
[7] Newman M E J. Scientific collaboration networks. I. Network construction and fundamental results[J]. Phys. Rev. E, 2001, 64: 016131.
[8] Fortunato S, Castellano C. Community structure in graphs[C]. Encyclopedia of Complexity and Systems Science. 2009, 00238.
[9] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities hierarchies in large networks[J]. J. Stat. Mech., 2008, 10008.
[10] Palla G, Derenyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435: 814-818.
[11] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks[J]. New Journal of Physics, 2009, 11: 033015.
[12] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Phys. Rev. E, 2004, 70: 066111.
[1] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005, 435: 814-818.
[2] Farkas I,ábel D, Palla G, et al. Weighted network modules [J]. New J Phys, 2007, 9(6): 180.
[3] Farkas I,ábel D, Palla G, et al. Directed network modules [J]. New J Phys, 2007, 9(6): 186.
[4] Nicosia V, Mangioni G, Carchiolo V, et al. Extending the definition of modularity to directed graphs with overlapping communities. J Stat Mech., 2009, 3: 03024.
[6] Evans T S, Lambiotte R. Line Graphs, Link Partitions and Overlapping Communities [J/OL]. Eprint arXiv, 2009, 0903: 2181. [2009-04-01]. http://www.arXiv.org.
[7] Gregory S. A Fast Algorithm to Find Overlapping Communities in Networks [J]. Machine Learning and Knowledge Discovery in Databases, 2008, 408-423.
[8] Fortunato S, Castellano C. Community structure in graphs[J/OL]. Eprint arXiv, 2007, 0712: 2716. [2009-03-10]. http://www.arXiv.org.
[9] Karrer B, Levina E, Newman M E J. Robustness of community structure in networks [J]. Phys. Rev. E, 2008, 77: 046119.
[10] Palla G, Barabasi A L, Vicsek T. Quantifying social group evolution[J]. Nature, 2007, 446(7136): 664-667.
[11] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of community hierarchies in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 10: 10008.
[12] Hansen S K, Rainey P B, Haagensen J A J, et al. Evolution of species interactions in a biofiLouvain community. Nature, 2007, 445: 533-536
[13] Fortunato S. Community detection in graphs[J/OL]. Eprint arXiv, 2009, 0906: 0612v1. [2009-04-20]. http://www.arXiv.org.
[14] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005, 435: 814-818.
[15] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks [J]. New J. Phys. 2009, 11: 033015.
[16] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Phys. Rev. E, 2008, 78: 046110
[17] Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E, 2009, 80: 016118
[18] Lancichinetti A, Fortunato S. Community detection algorithms: A comparative analysis.Phys. Rev. E, 2009, 80: 056117.
[1] Katz J E, Rice R E. Social Consequences of Internet Use: Access, Involvement and Interaction [M]. Cambridge MA: The MIT Press, 2002.
[2] WelLouvainan B. Computer networks as social networks [J]. Science, 2001, 293(5537): 2031-2034.
[3] Wasserman S, Faust K. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1994.
[4] HoLouvaine P, Edling C R, Liljeros F. Structure and time evolution of an Internet dating community. Social Networks, 2004, 26: 155–174.
[5]汪小帆,李翔,陈关荣.复杂网络理论及其应用,清华大学出版社,2006.
[6] Barabási A L, Jeong H, Néda Z, et al. Evolution of the social network of scientific collaborations. Physica A, 2002, 311: 590-614.
[7] Hu H B, Wang X F. Evolution of a large online social network. Physics Letters A. 2009, 373: 1105–1110
[8] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Phys. Rev. E, 2004, 70: 066111.
[9] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of community hierarchies in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 10: 10008.
[10] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435: 814-818.
[11] Watts D J, Strogatz S H. Collective dynamics of‘small-world’networks. Nature, 1998, 393: 440-442.
[12] Newman M E J. Assortative mixing in networks. Phys. Rev. Lett., 2002, 89: 208701.