复杂网络社团结构探测研究
|
摘要
复杂网络社团结构的研究为人类发现更多实际意义的社团提供了更多的借鉴。本文主要研究了复杂网络的社团结构探测算法,通过对已有算法的学习和研究,改进了一种基于K-means的算法,在不知道社团结构的前提下对复杂网络进行划分,算法简单、易理解,把算法应用在karate网络中,实验结果表明此算法是有效的。另外借鉴基于节点密度等性质,提出了一种基于节点间相似度的复杂网络社团结构探测算法(BSTN),此算法迭代次数大大减少,在计算机生成的已知社团结构的随机网络中检验,结果表明此算法比GN算法具有更高的准确率。另外还在实际网络中进行验证,本文使用的是空手道俱乐部网络(karate网络)、美国大学足球俱乐部网络(Football网络)和电子邮件网络(Email网络),实验结果与Newman算法进行了比较,本文提出的算法拥有更少的迭代次数,近似或者更大的模块化函数值,说明此算是有效的;并且能够对算法得出的社团结构进行了合理地解释,说明算法划分得出的结果是符合实际的,是合理的。
The research on complex network community structure has provided more references for people find more practical significance of the communities. This paper mainly studies the complex network detection algorithm, through learning and research on existing algorithms, and improves an algorithm based on K-means, which detects the community structure of complex networks under the premise of unknown community structure. The algorithm is simple, easy understanding. Using the algorithm in network, the experimental results show that this algorithm is effective. Another reference node density properties, this paper puts forward a method community structure detection algorithms (BSTN) based on similarity between the nodes of the complex network, the algorithm greatly reduce iteration times, using the algorithm in the computer generated stochastic network known community structure, the result shows that this algorithm has higher accuracy than GN algorithm. Also in the actual network, this paper uses karate club network (karate network), the American College Football club network (football network) and the Email network, experimental results compare to Newman algorithm, the proposed algorithm can have less iteration, approximate or more larger value of the module, it shows the BSTN algorithm is effective, and reasonable explain the community structure getting from the BSTN algorithm, the result of from the BSTN algorithm is practical, is reasonable.
The research on complex network community structure has provided more references for people find more practical significance of the communities. This paper mainly studies the complex network detection algorithm, through learning and research on existing algorithms, and improves an algorithm based on K-means, which detects the community structure of complex networks under the premise of unknown community structure. The algorithm is simple, easy understanding. Using the algorithm in network, the experimental results show that this algorithm is effective. Another reference node density properties, this paper puts forward a method community structure detection algorithms (BSTN) based on similarity between the nodes of the complex network, the algorithm greatly reduce iteration times, using the algorithm in the computer generated stochastic network known community structure, the result shows that this algorithm has higher accuracy than GN algorithm. Also in the actual network, this paper uses karate club network (karate network), the American College Football club network (football network) and the Email network, experimental results compare to Newman algorithm, the proposed algorithm can have less iteration, approximate or more larger value of the module, it shows the BSTN algorithm is effective, and reasonable explain the community structure getting from the BSTN algorithm, the result of from the BSTN algorithm is practical, is reasonable.
引文
[1]丁连红,时鹏.网络社区发现.化学工业出版社[M].2008.8.
[2]汪小帆,李翔,陈关荣.复杂网络理论及其应用.清华大学出版社[M].2006.4.
[3]李晓佳等.复杂网络中的社团结构.复杂系统与复杂性科学[J].2008,9(5):19-42.
[4] Xie Weihao,Chen Huimin,Yang xiumei,Xiongyong.The study on degree distribution property of complex network based on cooperative communication.Journal of Electronics(China)[J].2010,3(27):224-229.
[5] HAO Fei,JIANG Guo-ping. Structural Properties of Complex Networks.南京邮电大学学报(自然科学版)[J].2010,2(30):71-76.
[6] Yang Dai,Yun-ze Cai,Xiao-Ming Xu.Synchronization and Exponential Estimates of Complex Networks with Mixed Time-varying Coupling Delays.International Journal of Automation and Computing[J].2009,8(6):301-307.
[7] Huizhong YANG,Li SHENG.Pinning control of a generalized complex dynamical network model.Journal of Control Theory and Applications[J].2009,7(1):1-8.
[8] Chengyi xia,Zhongxin Liu,Zengqiang Chen. Epidemic spreading behavior in local-world evolving networks.Progress in Natural Science[J].2008,6:763-768.
[9] Zhengquan Yang,Zhongxin LIU,Zengqiang CHEN,Zhuzhi YUAN.Controlled synchronization of complex network with different kinds of nodes.Journal of Control Theory and Applications[J].2008,6(1):11-15.
[10] Girvan M, Newman MEJ. Community structure in social and biological networks[J]. Proc Natl Acad Sci USA, 2002, 99:7821-7826.
[11] Park J and Newman MEJ. The origin of degree correlations in the Internet and other networks[J]. Phys Rev E, 2003, 68(2):026112.
[12] Newman MEJ, Girvan M. Finding and evaluating community structure in networks[J]. Phys Rev E, 2004,69(2):026113.
[13] Vincent D, Blondel, etc. Fast unfolding of communities in large networks[C]. Eprint arXiv:0803. 0476v 1 at arxiv.org.2008.
[14] Nan Du ,Bai Wang, Bin Wu.Community Detection in Complex Networks. Journal of Computer Science&Technology[J].2008,4:672-683.
[15] ZHAO Jing,YU Hong,LUO Jianhua,CAO Z W,LI Yixue.Complex networks theory for analyzing metabolic networks.Chinese Science Bulletin[J].2007,51:1529-1537.
[16] Nan Du, Bin Wu, Bai Wang. Community detection in complex networks[J]. J. Comput.Sci. &Technol, 2008,23(4):672-683.
[17] Bryan Klimt, Yiming Yang. The Enron corpus. A New Dataset for Email 57 Classification Research[OL].
[18] Jian WANG,yanheng LIU,Yu JIAO.A new cascading failure model with delay time in congested complex networks. Journal of Systems Science and Systems Engineering[J].2009,18(3):369-381.
[19] ZHANG Juan,WU Wen-feng.Topological Properties of Complex Networks with Different Types of Nodes.Journal of Donghua University(English Edition)[J].2009,4(26):384-386.
[20]胡建,董月华,杨炳儒.大型复杂网络中的社团结构发现算法.计算机工程[J].2008,10(34):92-94.
[21]王林,戴冠中.复杂网络中的社区发现_理论与应用[J].科技导报,2005,8.
[22]解绉,汪小帆.复杂网络的一种快速局部社团划分方法.计算机仿真[J].2007,11(24).
[23]胡海波,王科,徐玲,汪小帆.基于复杂网络理论的在线社会网络分析.复杂系统与复杂性科学[J].2008,6.
[24]杨建新,周献中,葛银茂.基于拉普拉斯图谱和K均值的多社团发现方法.计算机工程[J].2008,6.
[25]蔡晓妍,戴冠中,杨黎斌.基于谱聚类的复杂网络社团发现算法.计算机科学[J].2009,9.
[26]段晓东,王存睿,刘向东,张庆灵.基于网络权重的多社团网络结构划分算法.复杂系统与复杂性科学[J].2009,9.
[27]王立敏,高学东,宫雨,马红权.基于相对密度的社团结构探测算法.计算机工程[J].2009,1.
[28]史伟,赵政,薛桂香.基于节点类型的复杂网络模块探测算法.计算机应用[J].2008,10.
[29]戴飞飞,唐普英.基于PSO微粒群算法的复杂网络社区结构发现.计算机工程与应用[J].2008,44(22).
[30]刘绍海,刘青昆,谢福鼎,安娜.复杂网络基于局部模块度的社团划分方法.计算机工程与技术[J].2009,30(20).
[31]王小红.改进的k-均值聚类算法在社团划分中的应用.青海师范大学学报(自然科学版)[J].2009.2:22-24.
[32]高忠科,金宁德.基于k-means聚类和数据场理论的复杂网络社团结构探寻.控制与决策[J].2009,3(24):377-382.
[33] Jin-li Guo.A difference equation approach to statistical mechanics of complex networks.Applied Mathematics and Mechanics(English Edition)[J].2009,8:1063-1068.
[34] Xiangping Ni,Shengwei MEI.A novel decomposition and coordination algorithm forcomplex networks and its application to power grids.Journal of Control Theory and Applications[J].2008,6(1):53-58.
[35] Roger Guinera and Luis A, Nunes Ariaral. Functional cartography of complex metabolic networks: Nature, 2005.
[36] Mendes, J. F. F. & Dorogovtsev, S. N. Evolution of Networks: From Biological Nets to the Internet and WWW (Oxford University Press, Oxford, 2003).
[37] Spirin, V. & Mirny, L. A. Protein complexes and functional modules in molecular networks. Proc. Natl. Acad. Sci. USA 100, 12123–12128 (2003).
[38] Watts, D. J., Dodds, P. S., & Newman, M. E. J. Identity and search in social networks. Science 296,1302–1305 (2002).
[39] Yan Ma,Qin Yang,Juhua Zhang. A research on a grid community groud model based education resource.2009ISECS International Colloquium on Computing,Communication,Control,and Management Proceedings(volume I),2009.
[40] FANG Jin-qing,BI Qiao,LI Yong,LU Xin-biao,LIU Qiang.Toward a harmonious unifying hybrid model for any evolving complex networks.Annual Report of China Institute of atomic energy[J].2007:228-230.
[2]汪小帆,李翔,陈关荣.复杂网络理论及其应用.清华大学出版社[M].2006.4.
[3]李晓佳等.复杂网络中的社团结构.复杂系统与复杂性科学[J].2008,9(5):19-42.
[4] Xie Weihao,Chen Huimin,Yang xiumei,Xiongyong.The study on degree distribution property of complex network based on cooperative communication.Journal of Electronics(China)[J].2010,3(27):224-229.
[5] HAO Fei,JIANG Guo-ping. Structural Properties of Complex Networks.南京邮电大学学报(自然科学版)[J].2010,2(30):71-76.
[6] Yang Dai,Yun-ze Cai,Xiao-Ming Xu.Synchronization and Exponential Estimates of Complex Networks with Mixed Time-varying Coupling Delays.International Journal of Automation and Computing[J].2009,8(6):301-307.
[7] Huizhong YANG,Li SHENG.Pinning control of a generalized complex dynamical network model.Journal of Control Theory and Applications[J].2009,7(1):1-8.
[8] Chengyi xia,Zhongxin Liu,Zengqiang Chen. Epidemic spreading behavior in local-world evolving networks.Progress in Natural Science[J].2008,6:763-768.
[9] Zhengquan Yang,Zhongxin LIU,Zengqiang CHEN,Zhuzhi YUAN.Controlled synchronization of complex network with different kinds of nodes.Journal of Control Theory and Applications[J].2008,6(1):11-15.
[10] Girvan M, Newman MEJ. Community structure in social and biological networks[J]. Proc Natl Acad Sci USA, 2002, 99:7821-7826.
[11] Park J and Newman MEJ. The origin of degree correlations in the Internet and other networks[J]. Phys Rev E, 2003, 68(2):026112.
[12] Newman MEJ, Girvan M. Finding and evaluating community structure in networks[J]. Phys Rev E, 2004,69(2):026113.
[13] Vincent D, Blondel, etc. Fast unfolding of communities in large networks[C]. Eprint arXiv:0803. 0476v 1 at arxiv.org.2008.
[14] Nan Du ,Bai Wang, Bin Wu.Community Detection in Complex Networks. Journal of Computer Science&Technology[J].2008,4:672-683.
[15] ZHAO Jing,YU Hong,LUO Jianhua,CAO Z W,LI Yixue.Complex networks theory for analyzing metabolic networks.Chinese Science Bulletin[J].2007,51:1529-1537.
[16] Nan Du, Bin Wu, Bai Wang. Community detection in complex networks[J]. J. Comput.Sci. &Technol, 2008,23(4):672-683.
[17] Bryan Klimt, Yiming Yang. The Enron corpus. A New Dataset for Email 57 Classification Research[OL].
[18] Jian WANG,yanheng LIU,Yu JIAO.A new cascading failure model with delay time in congested complex networks. Journal of Systems Science and Systems Engineering[J].2009,18(3):369-381.
[19] ZHANG Juan,WU Wen-feng.Topological Properties of Complex Networks with Different Types of Nodes.Journal of Donghua University(English Edition)[J].2009,4(26):384-386.
[20]胡建,董月华,杨炳儒.大型复杂网络中的社团结构发现算法.计算机工程[J].2008,10(34):92-94.
[21]王林,戴冠中.复杂网络中的社区发现_理论与应用[J].科技导报,2005,8.
[22]解绉,汪小帆.复杂网络的一种快速局部社团划分方法.计算机仿真[J].2007,11(24).
[23]胡海波,王科,徐玲,汪小帆.基于复杂网络理论的在线社会网络分析.复杂系统与复杂性科学[J].2008,6.
[24]杨建新,周献中,葛银茂.基于拉普拉斯图谱和K均值的多社团发现方法.计算机工程[J].2008,6.
[25]蔡晓妍,戴冠中,杨黎斌.基于谱聚类的复杂网络社团发现算法.计算机科学[J].2009,9.
[26]段晓东,王存睿,刘向东,张庆灵.基于网络权重的多社团网络结构划分算法.复杂系统与复杂性科学[J].2009,9.
[27]王立敏,高学东,宫雨,马红权.基于相对密度的社团结构探测算法.计算机工程[J].2009,1.
[28]史伟,赵政,薛桂香.基于节点类型的复杂网络模块探测算法.计算机应用[J].2008,10.
[29]戴飞飞,唐普英.基于PSO微粒群算法的复杂网络社区结构发现.计算机工程与应用[J].2008,44(22).
[30]刘绍海,刘青昆,谢福鼎,安娜.复杂网络基于局部模块度的社团划分方法.计算机工程与技术[J].2009,30(20).
[31]王小红.改进的k-均值聚类算法在社团划分中的应用.青海师范大学学报(自然科学版)[J].2009.2:22-24.
[32]高忠科,金宁德.基于k-means聚类和数据场理论的复杂网络社团结构探寻.控制与决策[J].2009,3(24):377-382.
[33] Jin-li Guo.A difference equation approach to statistical mechanics of complex networks.Applied Mathematics and Mechanics(English Edition)[J].2009,8:1063-1068.
[34] Xiangping Ni,Shengwei MEI.A novel decomposition and coordination algorithm forcomplex networks and its application to power grids.Journal of Control Theory and Applications[J].2008,6(1):53-58.
[35] Roger Guinera and Luis A, Nunes Ariaral. Functional cartography of complex metabolic networks: Nature, 2005.
[36] Mendes, J. F. F. & Dorogovtsev, S. N. Evolution of Networks: From Biological Nets to the Internet and WWW (Oxford University Press, Oxford, 2003).
[37] Spirin, V. & Mirny, L. A. Protein complexes and functional modules in molecular networks. Proc. Natl. Acad. Sci. USA 100, 12123–12128 (2003).
[38] Watts, D. J., Dodds, P. S., & Newman, M. E. J. Identity and search in social networks. Science 296,1302–1305 (2002).
[39] Yan Ma,Qin Yang,Juhua Zhang. A research on a grid community groud model based education resource.2009ISECS International Colloquium on Computing,Communication,Control,and Management Proceedings(volume I),2009.
[40] FANG Jin-qing,BI Qiao,LI Yong,LU Xin-biao,LIU Qiang.Toward a harmonious unifying hybrid model for any evolving complex networks.Annual Report of China Institute of atomic energy[J].2007:228-230.