搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

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

面向结构洞的复杂网络关键节点排序

韩忠明 吴杨 谭旭升 段大高 杨伟杰

引用本文:
Citation:

面向结构洞的复杂网络关键节点排序

韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰

Ranking key nodes in complex networks by considering structural holes

Han Zhong-Ming, Wu Yang, Tan Xu-Sheng, Duan Da-Gao, Yang Wei-Jie
PDF
导出引用
  • 复杂网络中的结构洞节点对于信息传播具有重要作用, 现有关键节点排序方法多数没有兼顾结构洞节点和其他类型的关键节点进行排序. 本文根据结构洞理论与关键节点排序相关研究选取了网络约束系数、介数中心性、等级度、效率、网络规模、PageRank值以及聚类系数7个度量指标, 将基于ListNet的排序学习方法引入到复杂网络的关键节点排序问题中, 融合7个度量指标, 构建了一个能够综合评价面向结构洞节点的关键节点排序方法. 采用模拟网络和实际复杂网络进行了大量实验, 人工标准试验结果表明本文排序方法能够综合考虑结构洞节点和核心节点, 关键节点排序与人工排序结果具有较高的一致性. SIR传播模型评估实验结果表明由本文选择TOP-K节点发起的传播能够在较短的传播时间内达到最大的传播范围.
    Structural hole nodes in complex networks play important roles in the network information diffusion. Unfortunately, most of the existing methods of ranking key nodes do not integrate structural hole nodes and other key nodes. According to the relevant research on structural hole theory as well as the key node ranking methods, network constraint coefficient, betweenness centrality, hierarchy, efficiently, network size, PageRank and clustering coefficient, 7 metrics are selected to rank the key nodes. Based on the 7 metrics, a ranking learning method based on ListNet is introduced to solve ranking key nodes by multi metrics. Comprehensive experiments are conducted based on different artificial networks and real complex networks. Experimental results with manual annotation show that the ranking method can comprehensively consider the structural hole nodes and other nodes with different important features. The ranking results on different networks are highly consistent with the manual ranking results. The spreading experiment results using signed to interference ratio propagation model show that SIR model can reach a maximum propagating ratio in a shorter propagating time initiated by TOP-K key nodes selected by our method than TOP-K key nodes selected by other methods.
    • 基金项目: 国家自然科学基金(批准号: 61170112)、中央财政支持地方高校发展专项资金人才培养和创新团队建设项 目(批准号: 19005323132)、教育部人文社会科学研究基金项目(批准号: 13YJC860006)资助的课题.
    • Funds: Project supported by the National Natural Science Foundation of China (Grant No.61170112), the central finance special fund to support the development of local colleges and Universities, China (Grant No. 19005323132), and the of Humanities and Social Science Research Fund Ministry of Education, China(Grant Nos 13YJC860006).
    [1]

    Shen Y 2013 Chin. Phys. B 22 058903

    [2]

    Liang Z W, Li J P, Yang F, Athina P 2014 Chin. Phys. B 23 098902

    [3]

    Shen Y 2011 Chin. Phys. B 20 040511

    [4]

    L L Y, Lu J A, Zhang Z K,Yan X Y,Wu Y,Shi D H,Zhou H P,Fang J Q,Zhou T 2010 Complex System and Complex Science 7 173 (in Chinese) [吕琳媛,陆君安, 张子柯, 闫小勇, 吴晔, 史定华, 周海平, 方锦清, 周涛 2010 复杂系统与复杂性科学 7 173]

    [5]

    Burt R S 1992 Networks and Organizations: Structure, Form, and Action 65 57

    [6]

    Bonacich P 1972 J. Math. Sociol 2 113

    [7]

    Freeman L C 1979 Soc. Netw. 1 215

    [8]

    Freeman L C, Borgatti S P, White D R 1991 Soc. Netw. 13 141

    [9]

    Katz L 1953 Psychometrika 18 39

    [10]

    Kitsak M,Gallos L K,Havlin S,Liljeros F,Muchnik L, Stanley H E, Makse H A 2010 Nature Physics 11 22

    [11]

    Arasu A, Cho J, Garcia-Molina H 2001 ACM Transactions on Internet Technology 1 2

    [12]

    L L, Zhang Y C, Yeung C H 2011 PLoS One E 6 21202

    [13]

    Kleinberg J M 1999 JACM 46 604

    [14]

    Li P X, Ren Y Q, Xi Y M 2004 System Engineering 22 13 (in Chinese) [李鹏翔, 任玉晴, 席酉民 2004 系统工程 22 13]

    [15]

    Chen Y, Hu A Q, Hu X 2004 Journal of China Institute on Communications 25 129 (in Chinese) [陈勇, 胡爱群, 胡啸 2004 通信学报 25 129]

    [16]

    Tan Y J, Wu J, Deng H Z 2006 System Engineering-Theory and Practice 788 79 (in Chinese) [谭跃进, 吴俊, 邓宏钟 2006 系统工程理论与实践 788 79]

    [17]

    Zhang Y, Liu Y H, Xu K H, Luo Z R 2011 Computer Science 38 88 (in Chinese) [张翼, 刘玉华, 许凯华, 骆珍荣 2011 计算机科学 38 88]

    [18]

    Yu H, Liu Z, Li Y J 2013 Acta Phys. Sin. 62 020204 (in Chinese) [于会, 刘尊, 李勇军 2013 物理学报 62 020204]

    [19]

    Hou B N, Yao Y P, Liao D S 2012 Physica A 391 4021

    [20]

    Comin C H, Costa L D 2011 Phys. Rev. E 84 056105

    [21]

    Ren Z M, Shao F, Liu J G 2013 Acta Phys. Sin. 62 128901 (in Chinese) [任卓明, 邵凤, 刘建国 2013 物理学报 62 128901]

    [22]

    Zhou X, Zhang F M, Li K W, Hui X B, Wu H S 2012 Acta Phys. Sin. 61 050201 (in Chinese) [周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜 2012 物理学报 61 050201]

    [23]

    Burt R S 2004 American Journal of Sociology 110 349

    [24]

    Freeman L C 1977 Sociometry 40 35

    [25]

    Liu T Y 2009 Foundations and Trends in Information Retrieval 3 225

    [26]

    Joachims T 2002 Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton, Canada, July 23-26, 2002 p133

    [27]

    Cao Z, Qin T, Liu T Y, Tsai M F, Hang L 2007 Proceedings of the 24th Annual international conference on Machine learning. Corvallis, June 20-24, 2007 p129

    [28]

    Luce R D 1959 Individual Choice Behavior:A Theoretical Analysis (New York: Wiley) pp147-177

  • [1]

    Shen Y 2013 Chin. Phys. B 22 058903

    [2]

    Liang Z W, Li J P, Yang F, Athina P 2014 Chin. Phys. B 23 098902

    [3]

    Shen Y 2011 Chin. Phys. B 20 040511

    [4]

    L L Y, Lu J A, Zhang Z K,Yan X Y,Wu Y,Shi D H,Zhou H P,Fang J Q,Zhou T 2010 Complex System and Complex Science 7 173 (in Chinese) [吕琳媛,陆君安, 张子柯, 闫小勇, 吴晔, 史定华, 周海平, 方锦清, 周涛 2010 复杂系统与复杂性科学 7 173]

    [5]

    Burt R S 1992 Networks and Organizations: Structure, Form, and Action 65 57

    [6]

    Bonacich P 1972 J. Math. Sociol 2 113

    [7]

    Freeman L C 1979 Soc. Netw. 1 215

    [8]

    Freeman L C, Borgatti S P, White D R 1991 Soc. Netw. 13 141

    [9]

    Katz L 1953 Psychometrika 18 39

    [10]

    Kitsak M,Gallos L K,Havlin S,Liljeros F,Muchnik L, Stanley H E, Makse H A 2010 Nature Physics 11 22

    [11]

    Arasu A, Cho J, Garcia-Molina H 2001 ACM Transactions on Internet Technology 1 2

    [12]

    L L, Zhang Y C, Yeung C H 2011 PLoS One E 6 21202

    [13]

    Kleinberg J M 1999 JACM 46 604

    [14]

    Li P X, Ren Y Q, Xi Y M 2004 System Engineering 22 13 (in Chinese) [李鹏翔, 任玉晴, 席酉民 2004 系统工程 22 13]

    [15]

    Chen Y, Hu A Q, Hu X 2004 Journal of China Institute on Communications 25 129 (in Chinese) [陈勇, 胡爱群, 胡啸 2004 通信学报 25 129]

    [16]

    Tan Y J, Wu J, Deng H Z 2006 System Engineering-Theory and Practice 788 79 (in Chinese) [谭跃进, 吴俊, 邓宏钟 2006 系统工程理论与实践 788 79]

    [17]

    Zhang Y, Liu Y H, Xu K H, Luo Z R 2011 Computer Science 38 88 (in Chinese) [张翼, 刘玉华, 许凯华, 骆珍荣 2011 计算机科学 38 88]

    [18]

    Yu H, Liu Z, Li Y J 2013 Acta Phys. Sin. 62 020204 (in Chinese) [于会, 刘尊, 李勇军 2013 物理学报 62 020204]

    [19]

    Hou B N, Yao Y P, Liao D S 2012 Physica A 391 4021

    [20]

    Comin C H, Costa L D 2011 Phys. Rev. E 84 056105

    [21]

    Ren Z M, Shao F, Liu J G 2013 Acta Phys. Sin. 62 128901 (in Chinese) [任卓明, 邵凤, 刘建国 2013 物理学报 62 128901]

    [22]

    Zhou X, Zhang F M, Li K W, Hui X B, Wu H S 2012 Acta Phys. Sin. 61 050201 (in Chinese) [周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜 2012 物理学报 61 050201]

    [23]

    Burt R S 2004 American Journal of Sociology 110 349

    [24]

    Freeman L C 1977 Sociometry 40 35

    [25]

    Liu T Y 2009 Foundations and Trends in Information Retrieval 3 225

    [26]

    Joachims T 2002 Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton, Canada, July 23-26, 2002 p133

    [27]

    Cao Z, Qin T, Liu T Y, Tsai M F, Hang L 2007 Proceedings of the 24th Annual international conference on Machine learning. Corvallis, June 20-24, 2007 p129

    [28]

    Luce R D 1959 Individual Choice Behavior:A Theoretical Analysis (New York: Wiley) pp147-177

  • [1] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 0(0): 0-0. doi: 10.7498/aps.71.20220565
    [2] 杨松青, 蒋沅, 童天驰, 严玉为, 淦各升. 基于Tsallis熵的复杂网络节点重要性评估方法. 物理学报, 2021, 70(21): 216401. doi: 10.7498/aps.70.20210979
    [3] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [4] 苏臻, 高超, 李向华. 节点中心性对复杂网络传播模式的影响分析. 物理学报, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [5] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [6] 韩忠明, 陈炎, 李梦琪, 刘雯, 杨伟杰. 一种有效的基于三角结构的复杂网络节点影响力度量模型. 物理学报, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
    [7] 苏晓萍, 宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点. 物理学报, 2015, 64(2): 020101. doi: 10.7498/aps.64.020101
    [8] 任卓明, 刘建国, 邵凤, 胡兆龙, 郭强. 复杂网络中最小K-核节点的传播能力分析. 物理学报, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
    [9] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [10] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [11] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [12] 张聪, 沈惠璋, 李峰, 杨何群. 复杂网络中社团结构发现的多分辨率密度模块度. 物理学报, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
    [13] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [14] 郝崇清, 王江, 邓斌, 魏熙乐. 基于稀疏贝叶斯学习的复杂网络拓扑估计. 物理学报, 2012, 61(14): 148901. doi: 10.7498/aps.61.148901
    [15] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [16] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [17] 崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. 物理学报, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
    [18] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [19] 高忠科, 金宁德. 两相流流型复杂网络社团结构及其统计特性. 物理学报, 2008, 57(11): 6909-6920. doi: 10.7498/aps.57.6909
    [20] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
计量
  • 文章访问数:  5451
  • PDF下载量:  1153
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-07-13
  • 修回日期:  2014-09-30
  • 刊出日期:  2015-03-05

面向结构洞的复杂网络关键节点排序

  • 1. 北京工商大学计算机与信息工程学院, 北京 100048
    基金项目: 国家自然科学基金(批准号: 61170112)、中央财政支持地方高校发展专项资金人才培养和创新团队建设项 目(批准号: 19005323132)、教育部人文社会科学研究基金项目(批准号: 13YJC860006)资助的课题.

摘要: 复杂网络中的结构洞节点对于信息传播具有重要作用, 现有关键节点排序方法多数没有兼顾结构洞节点和其他类型的关键节点进行排序. 本文根据结构洞理论与关键节点排序相关研究选取了网络约束系数、介数中心性、等级度、效率、网络规模、PageRank值以及聚类系数7个度量指标, 将基于ListNet的排序学习方法引入到复杂网络的关键节点排序问题中, 融合7个度量指标, 构建了一个能够综合评价面向结构洞节点的关键节点排序方法. 采用模拟网络和实际复杂网络进行了大量实验, 人工标准试验结果表明本文排序方法能够综合考虑结构洞节点和核心节点, 关键节点排序与人工排序结果具有较高的一致性. SIR传播模型评估实验结果表明由本文选择TOP-K节点发起的传播能够在较短的传播时间内达到最大的传播范围.

English Abstract

参考文献 (28)

目录

    /

    返回文章
    返回