搜索

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

计量
  • 文章访问数:  6562
  • PDF下载量:  1176
  • 被引次数: 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)

目录

    /

    返回文章
    返回