基于节点间依赖度的社团结构划分方法

王兴元; 赵仲祥

doi:10.7498/aps.63.178901

摘要

本文提出了一种基于节点间依赖度的在复杂网络中划分社团结构的算法，定义了节点对其邻居的依赖度以及节点对社团的依赖度和条件依赖度. 算法的基本要点是优先将最大依赖度不小于其他节点且有惟一依赖节点的节点划分到社团，并将对社团的依赖度或条件依赖度达到一定值的节点吸收进社团，直到所有节点都得到准确的社团划分. 本算法在几个实际网络的测试上，都成功地划分出了满足条件的社团，并且对社团结构已知的网络的划分结果符合实际情况.

关键词:

复杂网络 /
社团结构 /
划分 /
依赖度

Abstract

In this paper, we present a new approach to partitioning communities in a complex network via degree of dependence of nodes. We define the dependence degree of a node on its neighbors, the dependencetce degree and the conditional dependence degree of a node on a cluster. The main point of the approach is to partition the nodes, which have the biggest dependence degree and are only dependent on nodes, firstly to clusters, then to absorb nodes whose dependence degree or conditional dependence degree on cluster gets the right value, until all the nodes are partitioned to the right communities. The partition of our approach in some real-world network satisfies the definition of communities, and in the network whose communities are already known, our partition method fits the physical truth.

Keywords:

作者及机构信息

1.
大连理工大学电子信息与电气工程学部, 大连 116024

基金项目: 国家自然科学基金（批准号：61370145，61173183，60973152）、高等学校博士学科点专项科研基金（批准号：20070141014）、辽宁省高等学校优秀人才支持计划（批准号：LR2012003）和中央高校基本科研基金（批准号：DUT12JB06）资助的课题.

Authors and contacts

1.
Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, china

Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61370145, 61173183, 60973152), the Doctoral Program Foundation of Institution of Higher Education of China (Grant No. 20070141014), Program for Liaoning Excellent Talents in University, china (Grant No. LR2012003), and the Fundamental Research Funds for the Central Universities, china (Grant No. DUT12JB06).

参考文献

[1]	Erds P, Rnyi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[2]	Garey M R, Johnson D S 1979 Computers and Intractability: A Guide to the Theory of NP-Completeness (vol. 1) (San Francisco: Freeman Publishers) p1
[3]
[4]	Scott J 2002 Social Network Analysis: A Handbook (vol. 2) (London: Sage Publications) p1
[5]
[6]	Wang Z, Zhang J Z 2007 PLoS Computational Biology 3 e107
[7]
[8]
[9]	Givan M, Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821
[10]
[11]	Ino H, Kudo M, Nakamura A 2005 Partitioning of web graphs by community topology Chiba, May 10-14, 2005 661
[12]
[13]	Zhang Z Z, Lin Y, Gao S Y, Zhou S G, Guan J H, Li M 2009 Phys. Rev. E 80 051120
[14]
[15]	Zhang Z Z, Yang Y H, Lin Y 2012 Phys. Rev. E 85 011106
[16]	Kernighan B W, Lin S 1970 Bell System Technical Journal 49 291
[17]
[18]
[19]	Fiedler M 1973 Czechoslovak Mathematical Journal 23 298
[20]
[21]	Pothen A, Simon H D, Liou K P 1990 SIAM J. Matrix Anal. Appl. 11 430
[22]	Newman M E J 2004 Phys. Rev. E 69 066133
[23]
[24]
[25]	Clauset A, Newman M E J, Moore C 2004 Phys. Rev. E 70 066111
[26]
[27]	Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113
[28]	Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D 2004 Proc. Natl. Acad. Sci. USA 101 2658
[29]
[30]
[31]	Reichardt J, Bornholdt S 2004 Phys. Rev. Lett. 93 218701
[32]
[33]	Reichardt J, Bornholdt S 2006 Phys. Rev. E 93 016110
[34]	Wu F, Huberman B A 2004 Eur. Phys. J. B 38 331
[35]
[36]	Zanjani A A H, Darooneh A H 2011 Phys. Rev. E 84 036109
[37]
[38]	Chen D B, Fu Y, Shang M S 2009 Phys. A 388 2741
[39]
[40]
[41]	Pan Y, Li D H, Liu J G, Liang J Z 2010 Phys. A 389 2849
[42]	Wang X Y, Li J Q 2013 Phys. A 392 2555
[43]
[44]
[45]	Shen Y, Xu H L 2010 Acta Phys. Sin. 59 6022 (in Chinese)[沈毅, 徐焕良 2010 59 6022]
[46]	Newman M E J 2004 Eur. Phys. J. B 38 321
[47]
[48]
[49]	Yuan C, Chai Y 2012 Acta Phys. Sin. 61 218901 (in Chinese)[袁超, 柴毅 2012 61 218901]
[50]
[51]	Zhan W H, Zhang Z Z, Guan J H, Zhou S G 2011 Phys. Rev. E 83 066120
[52]	Shen Y 2011 Chin. Phys. B 20 040511
[53]
[54]	Shen Y 2013 Chin. Phys. B 22 058903
[55]
[56]
[57]	Zachary W W 1977 J. Anthropol. Res. 33 452
[58]
[59]	Lusseau D 2003 Proc R Soc. Lond. B 270 186
[60]
[61]	Tyler J, Wilkinson D, Huberman B 2005 The Information Society: An International Journal 21 81

施引文献

[1]	Erds P, Rnyi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[2]	Garey M R, Johnson D S 1979 Computers and Intractability: A Guide to the Theory of NP-Completeness (vol. 1) (San Francisco: Freeman Publishers) p1
[3]
[4]	Scott J 2002 Social Network Analysis: A Handbook (vol. 2) (London: Sage Publications) p1
[5]
[6]	Wang Z, Zhang J Z 2007 PLoS Computational Biology 3 e107
[7]
[8]
[9]	Givan M, Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821
[10]
[11]	Ino H, Kudo M, Nakamura A 2005 Partitioning of web graphs by community topology Chiba, May 10-14, 2005 661
[12]
[13]	Zhang Z Z, Lin Y, Gao S Y, Zhou S G, Guan J H, Li M 2009 Phys. Rev. E 80 051120
[14]
[15]	Zhang Z Z, Yang Y H, Lin Y 2012 Phys. Rev. E 85 011106
[16]	Kernighan B W, Lin S 1970 Bell System Technical Journal 49 291
[17]
[18]
[19]	Fiedler M 1973 Czechoslovak Mathematical Journal 23 298
[20]
[21]	Pothen A, Simon H D, Liou K P 1990 SIAM J. Matrix Anal. Appl. 11 430
[22]	Newman M E J 2004 Phys. Rev. E 69 066133
[23]
[24]
[25]	Clauset A, Newman M E J, Moore C 2004 Phys. Rev. E 70 066111
[26]
[27]	Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113
[28]	Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D 2004 Proc. Natl. Acad. Sci. USA 101 2658
[29]
[30]
[31]	Reichardt J, Bornholdt S 2004 Phys. Rev. Lett. 93 218701
[32]
[33]	Reichardt J, Bornholdt S 2006 Phys. Rev. E 93 016110
[34]	Wu F, Huberman B A 2004 Eur. Phys. J. B 38 331
[35]
[36]	Zanjani A A H, Darooneh A H 2011 Phys. Rev. E 84 036109
[37]
[38]	Chen D B, Fu Y, Shang M S 2009 Phys. A 388 2741
[39]
[40]
[41]	Pan Y, Li D H, Liu J G, Liang J Z 2010 Phys. A 389 2849
[42]	Wang X Y, Li J Q 2013 Phys. A 392 2555
[43]
[44]
[45]	Shen Y, Xu H L 2010 Acta Phys. Sin. 59 6022 (in Chinese)[沈毅, 徐焕良 2010 59 6022]
[46]	Newman M E J 2004 Eur. Phys. J. B 38 321
[47]
[48]
[49]	Yuan C, Chai Y 2012 Acta Phys. Sin. 61 218901 (in Chinese)[袁超, 柴毅 2012 61 218901]
[50]
[51]	Zhan W H, Zhang Z Z, Guan J H, Zhou S G 2011 Phys. Rev. E 83 066120
[52]	Shen Y 2011 Chin. Phys. B 20 040511
[53]
[54]	Shen Y 2013 Chin. Phys. B 22 058903
[55]
[56]
[57]	Zachary W W 1977 J. Anthropol. Res. 33 452
[58]
[59]	Lusseau D 2003 Proc R Soc. Lond. B 270 186
[60]
[61]	Tyler J, Wilkinson D, Huberman B 2005 The Information Society: An International Journal 21 81

[1]	沈力峰, 王建波, 杜占玮, 许小可. 基于社团结构和活跃性驱动的双层网络传播动力学. , 2023, 72(6): 068701. doi: 10.7498/aps.72.20222206
[2]	阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. , 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
[3]	阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. , 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
[4]	韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. , 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
[5]	苏晓萍, 宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点. , 2015, 64(2): 020101. doi: 10.7498/aps.64.020101
[6]	丁益民, 丁卓, 杨昌平. 基于社团结构的城市地铁网络模型研究. , 2013, 62(9): 098901. doi: 10.7498/aps.62.098901
[7]	刘金良. 具有随机节点结构的复杂网络同步研究. , 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
[8]	杨浦, 郑志刚. 基于动力学同步的复杂网络结构识别速度研究. , 2012, 61(12): 120508. doi: 10.7498/aps.61.120508
[9]	吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. , 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
[10]	周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. , 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
[11]	吕天阳, 谢文艳, 郑纬民, 朴秀峰. 加权复杂网络社团的评价指标及其发现算法分析. , 2012, 61(21): 210511. doi: 10.7498/aps.61.210511
[12]	高忠科, 金宁德, 杨丹, 翟路生, 杜萌. 多元时间序列复杂网络流型动力学分析. , 2012, 61(12): 120510. doi: 10.7498/aps.61.120510
[13]	袁超, 柴毅. 基于簇相似度的网络社团结构探测算法. , 2012, 61(21): 218901. doi: 10.7498/aps.61.218901
[14]	张聪, 沈惠璋, 李峰, 杨何群. 复杂网络中社团结构发现的多分辨率密度模块度. , 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
[15]	崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. , 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
[16]	邵斐, 蒋国平. 基于社团结构的负载传输优化策略研究. , 2011, 60(7): 078902. doi: 10.7498/aps.60.078902
[17]	沈毅, 徐焕良. 加权网络权重自相似评判函数及其社团结构检测. , 2010, 59(9): 6022-6028. doi: 10.7498/aps.59.6022
[18]	王高峡, 沈轶. 网络的模块矩阵及其社团结构指标. , 2010, 59(2): 842-850. doi: 10.7498/aps.59.842
[19]	吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. , 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
[20]	高忠科, 金宁德. 两相流流型复杂网络社团结构及其统计特性. , 2008, 57(11): 6909-6920. doi: 10.7498/aps.57.6909

计量

文章访问数: 6175
PDF下载量: 675
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

搜索

留言板