复杂网络中社团结构的发现
|
摘要
现实中存在的大量复杂系统都可以用各种各样的网络进行刻画。复杂网络是复杂系统的抽象表示,由节点和边组成。网络中的节点代表现实中的不同个体,边则代表这些个体之间的关系。复杂网络理论的研究不仅仅属于数学范畴,而是涉及到了从物理学到生物学,从工程技术到管理学和社会科学等众多领域的研究,并且受到越来越多的重视和关注。人类社会的日益网络化也需要人们对各种人工的和自然的复杂网络有更加深刻的认识和了解。复杂网络已成为网络时代科学研究中的一个极其重要的具有挑战性的课题,甚至被称为“网络的新科学”。
更为重要的是,有越来越多的研究表明,许多看上去各不相同的网络之间都存在着非常惊人的相似之处,社团结构就是其中之一。发现网络中的社团结构,对于了解网络结构和分析网络特性都有着非常重要的意义。社团结构的分析在生物学领域、物理学领域、计算机图形领域和社会学领域等众多不同领域中都有着非常广泛的应用。因此,如何利用网络中的各种信息准确的分析社团结构,是一个值得研究的问题。
本文正是通过对社团性质的深入研究,开展了如下的研究工作。
一种基于共享邻居数的社团结构发现算法。该方法首先选取度最大的节点作为社团的初始节点。其次,计算已知社团与其邻居节点之间的共享邻居数。最后,根据共享邻居数的大小,找到与社团连接最强的节点,并且利用局部模块度判断是否将该点加入到已知社团中去,进而达到发现社团结构、实现网络聚类的目的。为了验证该算法的有效性和可行性,将该方法应用于三个典型的复杂网络,取得了较好的实验结果。
基于局部信息的社团结构发现算法。通过定义边的聚类系数和基于局部信息,提出了一个寻找复杂网络中社团结构的算法。该方法首先在网络的剩余节点中寻找度最大的节点作为社团的初始节点。然后利用该节点的边聚类系数和该点的度数值,判断与社团相连的其他节点是否可以加入到节点所在的社团中。最后得到了复杂网络的社团结构。通过对三社团网络和空手道俱乐部网络的实验,证明了该方法的可行性和有效性。
Many complex systems in the world can be modeled by a variety of complex networks. Complex networks which composed by the nodes and edges are the abstract representation of complex systems. The nodes represent different individuals, and the edges reflect the relationship between these individuals. The study of complex networks gets more and more attention in Mathematics, Physics, biology, engineering, management, science and etc.. The growing network of human society also needs to understand the variety of artificial and natural complex networks well. Complex network has become an extremely important and challenge issue in scientific research of the network age, and even called“the new science of networks”.
More and more research shows that many different networks have very remarkable similarities. One of them is community structure. Detecting community structure in network is more significance for understanding the network structure and analyzing the network properties. There are very extensive applications for analyzing community structure in biology, physic, computer graph, society and many different fields. So, it is Worthwhile to analysis community structure accurately with variety information of network.
By researching deeply in community structure, the following work has been introduced in this dissertation.
An algorithm for detecting community structure based on shared neighbors is proposed. First, the node with maximum degree is chosen as the first node in the community. Then, this algorithm calculates the numbers of shared neighbors between the community and its neighbors. Finally, the shared neighbors are compared to find the closest node with the community. At the same time, the local modularity will be used to decide whether this node can be added into the community. Doing so, the algorithm will detect the community structure and cluster the network. It is tested in three typical networks, and the results prove the viability and effective of this algorithm.
An algorithm for detecting structure in complex network based on local information is proposed. Based on the local information, an algorithm is proposed for discovering the communities in complex networks by introducing the definition of the edge cluster coefficient. To obtain the community structures in the networks, the node with maximum degree in remainder network is first found. And then, some edge cluster coefficients and nodes’degrees are computed to decide whether the nodes connected with the community can be added into the community. At last, the community structure is detected. It is tested at the three group network and the Zachary network, the results show the validity and effective of this algorithm.
更为重要的是,有越来越多的研究表明,许多看上去各不相同的网络之间都存在着非常惊人的相似之处,社团结构就是其中之一。发现网络中的社团结构,对于了解网络结构和分析网络特性都有着非常重要的意义。社团结构的分析在生物学领域、物理学领域、计算机图形领域和社会学领域等众多不同领域中都有着非常广泛的应用。因此,如何利用网络中的各种信息准确的分析社团结构,是一个值得研究的问题。
本文正是通过对社团性质的深入研究,开展了如下的研究工作。
一种基于共享邻居数的社团结构发现算法。该方法首先选取度最大的节点作为社团的初始节点。其次,计算已知社团与其邻居节点之间的共享邻居数。最后,根据共享邻居数的大小,找到与社团连接最强的节点,并且利用局部模块度判断是否将该点加入到已知社团中去,进而达到发现社团结构、实现网络聚类的目的。为了验证该算法的有效性和可行性,将该方法应用于三个典型的复杂网络,取得了较好的实验结果。
基于局部信息的社团结构发现算法。通过定义边的聚类系数和基于局部信息,提出了一个寻找复杂网络中社团结构的算法。该方法首先在网络的剩余节点中寻找度最大的节点作为社团的初始节点。然后利用该节点的边聚类系数和该点的度数值,判断与社团相连的其他节点是否可以加入到节点所在的社团中。最后得到了复杂网络的社团结构。通过对三社团网络和空手道俱乐部网络的实验,证明了该方法的可行性和有效性。
Many complex systems in the world can be modeled by a variety of complex networks. Complex networks which composed by the nodes and edges are the abstract representation of complex systems. The nodes represent different individuals, and the edges reflect the relationship between these individuals. The study of complex networks gets more and more attention in Mathematics, Physics, biology, engineering, management, science and etc.. The growing network of human society also needs to understand the variety of artificial and natural complex networks well. Complex network has become an extremely important and challenge issue in scientific research of the network age, and even called“the new science of networks”.
More and more research shows that many different networks have very remarkable similarities. One of them is community structure. Detecting community structure in network is more significance for understanding the network structure and analyzing the network properties. There are very extensive applications for analyzing community structure in biology, physic, computer graph, society and many different fields. So, it is Worthwhile to analysis community structure accurately with variety information of network.
By researching deeply in community structure, the following work has been introduced in this dissertation.
An algorithm for detecting community structure based on shared neighbors is proposed. First, the node with maximum degree is chosen as the first node in the community. Then, this algorithm calculates the numbers of shared neighbors between the community and its neighbors. Finally, the shared neighbors are compared to find the closest node with the community. At the same time, the local modularity will be used to decide whether this node can be added into the community. Doing so, the algorithm will detect the community structure and cluster the network. It is tested in three typical networks, and the results prove the viability and effective of this algorithm.
An algorithm for detecting structure in complex network based on local information is proposed. Based on the local information, an algorithm is proposed for discovering the communities in complex networks by introducing the definition of the edge cluster coefficient. To obtain the community structures in the networks, the node with maximum degree in remainder network is first found. And then, some edge cluster coefficients and nodes’degrees are computed to decide whether the nodes connected with the community can be added into the community. At last, the community structure is detected. It is tested at the three group network and the Zachary network, the results show the validity and effective of this algorithm.
引文
[1] Newman M E J. The structure and function of complex networks. SIAM Review, 2003, 45(2):167–256.
[2]解,汪小帆.复杂网络中的社团结构分析算法研究综述.复杂系统与复杂性科学, 2005, 2(3):1-12.
[3]Andrei B, Ravi K, Farzin M, et a1. Graph structure in the Web. Compuer Networks, 2000, 33:309-320.
[4] Boccaletti S, Latora V, Moreno Y, et al. Complex networks: Structure and dynamics. Physics Report, 2006, 424:175–308.
[5] Albert R, Barabasi A L. Statistical mechanics of complex networks. Review of Modern Physics, 2002, 74:47–91.
[6]Williams R J, Martinez N D. Simple rules yield complex food webs. Nature, 2000, 404(6774): 180-183.
[7]Barabasi A L, Bonabeau E. Scale-Free Networks. Scientific American, 2003, 288(1):60-69.
[8]Amaral L A N, Scala A, Barthelemy M, et a1. Classes of small-world networks. Proc Natl Acad Sci USA, 2000,97(21):11149-11152.
[9]汪小帆,李翔,陈关荣.复杂网络理论及其应用.北京:清华大学出版社, 2006.
[10]Erdōs P, Rényi A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. ,1960,5:17-60.
[11]Girvan M, Newman M E J. Community structure in social and biological networks. Proc Natl Acad Sci USA, 2002, 99:7821-7826.
[12]Newman M E J, Girvan M. Finding and evaluating community structure in networks. Phys. Rev. E, 2004, 69:02611.
[13]Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Phys. Rev. E, 2004, 70:066111.
[14]Newman M E J. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 2004, 69:066133.
[15] Radicchi F, Castellano C, Cecconi F, Loreto V., Parisi D. Defining and identifying communities in networks. Proc. Natl. Acad. Sci., 2004, 101:2658-2663.
[16]Newman M E J. Analysis of weighted networks. arXiv:cond-mat/0407503v1 [cond-mat.stat-mech], 2004.
[17]Fang Wu, Bernardo A. Huberman. Finding communities in linear time: a physics approach. Eur. Phys. J. B, 2004, 38:331-338.
[18]Donetti L, Munoz M A. Detecting network communities: A new systematic and efficient algorithm, Stat. Mech. Theor. Exp., 2004,P10012.
[19]A. Medus, G. Acun a, C.O. Dorso. Detection of community structures in networks via global optimization. Physica A, 2005, 358:593–604.
[20]Clauset A. Finding local community structure in networks. Phys. Rev. E, 2005, 72:026132
[21]Pascal Pons, Matthieu Latapy. Computing Communities in Large Networks Using Random Walks. Journal of Graph Algorithms and Applications, 2006, 10(2):191-218.
[22]M. E. J. Newman. Modularity and community structure in networks. PNAS. 2006, 103(23): 8577–8582.
[23]Xutao Wang, Guangrong Chen, Hongtao Lu. A very fast algorithm for detecting community structures in complex networks, Physica A, 2007, 384(2):667-664.
[24] Shihua Zhang, Rui-Sheng Wang, Xiang-Sun Zhang. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A, 2007, 374: 483–490.
[25]Ying Fan, Menghui Li, Peng Zhang, Jinshan Wu, Zengru Di. The effect of weight on community structure of networks. Physica A, 2007, 378:583–590.
[26]Yi Shen, Wenjiang Pei, Kai Wang, Tao Li, Shaoping Wang. Recursive filtration method for detecting community structure in networks. Physica A, 2008, 387:6663–6670.
[27]E. A. Leicht, M. E. J. Newman. Community Structure in Directed Networks. PHYSICAL REVIEW LETTERS, 2008,100(11): 118703.
[28]Duanbing Chen, Yan Fu, Mingsheng Shang. A fast and efficient heuristic algorithm for detecting community structures in complex networks. Physica A, 2009, 388(13):2741-2749
[29]Jeffrey Q. Jiang, Andreas W.M. Dress, Genke Yang. A spectral clustering-based framework for detecting community structures in complex networks. Applied Mathematics Letters, 2009, 22: 1479–1482.
[30]XinJian Xu, Xun Zhang, J.F.F. Mendes. Growing community networks with local events. Physica A, 2009, 388:1273–1278.
[31]Santo Fortunato. Community detection in graphs. Physics Reports, 2010, 486:75-174.
[32]Jian Liu, Tingzhan Liu. Detecting community structure in complex networks using simulated annealing with k-means algorithms. Physica A, 2010, 389:2300–2309.
[33]解,汪小帆.复杂网络中的社团结构分析算法研究综述.复杂系统与复杂性科学, 2005, 2(3):1-12.
[34]谭跃进,吴俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法.系统工程理论与实践, 2006, 11:79-83.
[35]解,汪小帆.复杂网络的一种快速局部社团划分算法.计算机仿真, 2007,24(11):82-85.
[36]李晓佳,张鹏,狄增如,樊瑛.复杂网络中的社团结构.复杂系统与复杂性科学, 2008, 5(3): 19-42.
[37]魏芳.基于图挖掘的网络社团结构发现(博士学位论文).上海:复旦大学, 2008.
[38]赵凤霞,谢福鼎.基于K-means聚类算法的复杂网络社团发现新方法.计算机应用研究, 2009, 26(6):2041-2043.
[39]蔡晓妍,戴冠中,杨黎斌.基于谱聚类的复杂网络社团发现算法.计算机科学, 2009, 36(9): 49-50.
[40]王立敏,高学东,宫雨,马红权.基于相对密度的社团结构探测算法.计算机工程. 2009, 35(1):117-119.
[41]高学东,王立敏,马红权,武森.基于共享最近邻探测社团结构的算法.系统工程理论与实践. 2009, 29(10):102-109.
[42]王立敏,高学东,武森.基于最小社团链接度增量的社团结构挖掘算法.北京科技大学学报, 2009, 31(1):112-117.
[43]王立敏,高学东,马红权.基于最大节点接近度的局部社团结构探测算法.计算机工程, 2010, 36(1):25-26.
[44]李峻金,向阳,牛鹏,刘丽明,芦英明.一种新的复杂网络聚类算法.计算机应用研究, 2010, 27(6):2097-2099.
[45]Dawei Zhang, Fuding Xie, Yong Zhang, Fangyan Dong, Kaoru Hirota. Fuzzy analysis of community detection in complex networks. Physica A: Statistical Mechanics and its Applications, 2010, 389 (22):5319-5327.
[46]W W Zachary. An information flow model for conflict and fission in small group. Journal of Anthropological Research, 1977, 33:452-473.
[47] Lusseau D, Newman M E J. Identifying the role that animals play in their social networks. Proceedings of the Royal Society of London Series B-biological Sciences, 2004, 271:477-481.
[48]Knuth D E. The Stanford Graph Base: A Platform for Combinatorial Computing. Addison-Wesley, Reading, MA, 1993.
[49]Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970, 49:291-307.
[50] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl, 1990, 11:430.
[51] Zhou H. Distance, dissimilarity index and network community structure. Phys. Rev. E, 2003, 67:061901.
[52]Fortunato S, Latora V, Marchiori M. A method to find community structures based on informaton centrality. Phys. Rev.E, 2004, 70:056104.
[53]Tsuchiura H, Ogata M, Tanaka Y, Kashiwaya S. Electronic states around a vortex core in high-Tc superconductors based on the t-J model. Phys. Rev. B, 2003, 68:012509.
[2]解,汪小帆.复杂网络中的社团结构分析算法研究综述.复杂系统与复杂性科学, 2005, 2(3):1-12.
[3]Andrei B, Ravi K, Farzin M, et a1. Graph structure in the Web. Compuer Networks, 2000, 33:309-320.
[4] Boccaletti S, Latora V, Moreno Y, et al. Complex networks: Structure and dynamics. Physics Report, 2006, 424:175–308.
[5] Albert R, Barabasi A L. Statistical mechanics of complex networks. Review of Modern Physics, 2002, 74:47–91.
[6]Williams R J, Martinez N D. Simple rules yield complex food webs. Nature, 2000, 404(6774): 180-183.
[7]Barabasi A L, Bonabeau E. Scale-Free Networks. Scientific American, 2003, 288(1):60-69.
[8]Amaral L A N, Scala A, Barthelemy M, et a1. Classes of small-world networks. Proc Natl Acad Sci USA, 2000,97(21):11149-11152.
[9]汪小帆,李翔,陈关荣.复杂网络理论及其应用.北京:清华大学出版社, 2006.
[10]Erdōs P, Rényi A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. ,1960,5:17-60.
[11]Girvan M, Newman M E J. Community structure in social and biological networks. Proc Natl Acad Sci USA, 2002, 99:7821-7826.
[12]Newman M E J, Girvan M. Finding and evaluating community structure in networks. Phys. Rev. E, 2004, 69:02611.
[13]Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Phys. Rev. E, 2004, 70:066111.
[14]Newman M E J. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 2004, 69:066133.
[15] Radicchi F, Castellano C, Cecconi F, Loreto V., Parisi D. Defining and identifying communities in networks. Proc. Natl. Acad. Sci., 2004, 101:2658-2663.
[16]Newman M E J. Analysis of weighted networks. arXiv:cond-mat/0407503v1 [cond-mat.stat-mech], 2004.
[17]Fang Wu, Bernardo A. Huberman. Finding communities in linear time: a physics approach. Eur. Phys. J. B, 2004, 38:331-338.
[18]Donetti L, Munoz M A. Detecting network communities: A new systematic and efficient algorithm, Stat. Mech. Theor. Exp., 2004,P10012.
[19]A. Medus, G. Acun a, C.O. Dorso. Detection of community structures in networks via global optimization. Physica A, 2005, 358:593–604.
[20]Clauset A. Finding local community structure in networks. Phys. Rev. E, 2005, 72:026132
[21]Pascal Pons, Matthieu Latapy. Computing Communities in Large Networks Using Random Walks. Journal of Graph Algorithms and Applications, 2006, 10(2):191-218.
[22]M. E. J. Newman. Modularity and community structure in networks. PNAS. 2006, 103(23): 8577–8582.
[23]Xutao Wang, Guangrong Chen, Hongtao Lu. A very fast algorithm for detecting community structures in complex networks, Physica A, 2007, 384(2):667-664.
[24] Shihua Zhang, Rui-Sheng Wang, Xiang-Sun Zhang. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A, 2007, 374: 483–490.
[25]Ying Fan, Menghui Li, Peng Zhang, Jinshan Wu, Zengru Di. The effect of weight on community structure of networks. Physica A, 2007, 378:583–590.
[26]Yi Shen, Wenjiang Pei, Kai Wang, Tao Li, Shaoping Wang. Recursive filtration method for detecting community structure in networks. Physica A, 2008, 387:6663–6670.
[27]E. A. Leicht, M. E. J. Newman. Community Structure in Directed Networks. PHYSICAL REVIEW LETTERS, 2008,100(11): 118703.
[28]Duanbing Chen, Yan Fu, Mingsheng Shang. A fast and efficient heuristic algorithm for detecting community structures in complex networks. Physica A, 2009, 388(13):2741-2749
[29]Jeffrey Q. Jiang, Andreas W.M. Dress, Genke Yang. A spectral clustering-based framework for detecting community structures in complex networks. Applied Mathematics Letters, 2009, 22: 1479–1482.
[30]XinJian Xu, Xun Zhang, J.F.F. Mendes. Growing community networks with local events. Physica A, 2009, 388:1273–1278.
[31]Santo Fortunato. Community detection in graphs. Physics Reports, 2010, 486:75-174.
[32]Jian Liu, Tingzhan Liu. Detecting community structure in complex networks using simulated annealing with k-means algorithms. Physica A, 2010, 389:2300–2309.
[33]解,汪小帆.复杂网络中的社团结构分析算法研究综述.复杂系统与复杂性科学, 2005, 2(3):1-12.
[34]谭跃进,吴俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法.系统工程理论与实践, 2006, 11:79-83.
[35]解,汪小帆.复杂网络的一种快速局部社团划分算法.计算机仿真, 2007,24(11):82-85.
[36]李晓佳,张鹏,狄增如,樊瑛.复杂网络中的社团结构.复杂系统与复杂性科学, 2008, 5(3): 19-42.
[37]魏芳.基于图挖掘的网络社团结构发现(博士学位论文).上海:复旦大学, 2008.
[38]赵凤霞,谢福鼎.基于K-means聚类算法的复杂网络社团发现新方法.计算机应用研究, 2009, 26(6):2041-2043.
[39]蔡晓妍,戴冠中,杨黎斌.基于谱聚类的复杂网络社团发现算法.计算机科学, 2009, 36(9): 49-50.
[40]王立敏,高学东,宫雨,马红权.基于相对密度的社团结构探测算法.计算机工程. 2009, 35(1):117-119.
[41]高学东,王立敏,马红权,武森.基于共享最近邻探测社团结构的算法.系统工程理论与实践. 2009, 29(10):102-109.
[42]王立敏,高学东,武森.基于最小社团链接度增量的社团结构挖掘算法.北京科技大学学报, 2009, 31(1):112-117.
[43]王立敏,高学东,马红权.基于最大节点接近度的局部社团结构探测算法.计算机工程, 2010, 36(1):25-26.
[44]李峻金,向阳,牛鹏,刘丽明,芦英明.一种新的复杂网络聚类算法.计算机应用研究, 2010, 27(6):2097-2099.
[45]Dawei Zhang, Fuding Xie, Yong Zhang, Fangyan Dong, Kaoru Hirota. Fuzzy analysis of community detection in complex networks. Physica A: Statistical Mechanics and its Applications, 2010, 389 (22):5319-5327.
[46]W W Zachary. An information flow model for conflict and fission in small group. Journal of Anthropological Research, 1977, 33:452-473.
[47] Lusseau D, Newman M E J. Identifying the role that animals play in their social networks. Proceedings of the Royal Society of London Series B-biological Sciences, 2004, 271:477-481.
[48]Knuth D E. The Stanford Graph Base: A Platform for Combinatorial Computing. Addison-Wesley, Reading, MA, 1993.
[49]Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970, 49:291-307.
[50] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl, 1990, 11:430.
[51] Zhou H. Distance, dissimilarity index and network community structure. Phys. Rev. E, 2003, 67:061901.
[52]Fortunato S, Latora V, Marchiori M. A method to find community structures based on informaton centrality. Phys. Rev.E, 2004, 70:056104.
[53]Tsuchiura H, Ogata M, Tanaka Y, Kashiwaya S. Electronic states around a vortex core in high-Tc superconductors based on the t-J model. Phys. Rev. B, 2003, 68:012509.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |