搜索

x

留言板

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

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

加权网络中基于冗余边过滤的k-核分解排序算法

罗仕龙 龚凯 唐朝生 周靖

引用本文:
Citation:

加权网络中基于冗余边过滤的k-核分解排序算法

罗仕龙, 龚凯, 唐朝生, 周靖

A ranking approach based on k-shell decomposition method by filtering out redundant link in weighted networks

Luo Shi-Long, Gong Kai, Tang Chao-Sheng, Zhou Jing
PDF
导出引用
  • k-核分解排序法对于度量复杂网络上重要节点的传播影响力具有重要的理论意义和应用价值,但其排序粗粒化的缺陷也不容忽视.最新研究发现,一些真实网络中存在局域连接稠密的特殊构型是导致上述问题的根本原因之一.当前的解决方法是利用边两端节点的外部连边数度量边的扩散性,采取过滤网络边来减少这种稠密结构给k-核分解过程造成的干扰,但这种方法并没有考虑现实网络上存在权重的普遍性.本文利用节点权重和权重分布重新定义边的扩散性,提出适用于加权网络结构的基于冗余边过滤的k-核分解排序算法:filter-core.通过世界贸易网、线虫脑细胞网和科学家合著网等真实网络的SIR(susceptible-infected-recovered)传播模型的仿真结果表明,该算法相比其他加权k-核分解法,能够更准确地度量加权网络上具有重要传播影响力的核心节点及核心层.
    The k-shell decomposition method of identifying the influential nodes which accelerate spread or hinder propagation, plays an important role in analyzing the spreading performance of complex network, but it is too coarse in terms of ranking granularity. Recent study shows that the accuracy of the k-shell decomposition method in determining node coreness is significantly affected by the mutually densely connected local structures. Existing approach tries to filter out the confusion of the classical k-shell decomposition method, caused by such densely local structures, through redefining a diffusion importance value which is the number of out-leaving links at/from the nodes connected by a link. This value is used to quantify the potential influence of a link in spreading process. However, the existing approach is not suitable for ubiquitously weighted networks. In this paper, we develop a new ranking approach (filter-core) to identify the node spreading influence in weighted network. Here, we concern that the redundant links, although they are less important in the spreading process, form mutually densely connected local structures, which lead to the classical k-shell decomposition method unable to accurately determine the coreness of node in network. By redefining a new diffusion importance value for each link based on the weights of its connected nodes and the weight distribution, we filter out the redundant links which have a relatively low diffusion importance in the spreading process. After filtering out all redundant links and applying the classical k-shell decomposition method to the residual network, we obtain a new coreness for each node, which is more accurate to indicate spreading influence of node in the original network. Our approach is applied to three real weighted networks, i.e., the international trading network, the neural network of C. elegans, and the coauthorship network of scientists. And the susceptible-infected-recovered epidemic spreading model is used to make a comparison of performance between our approach and other three k-shell methods (including the weighted degree decomposition method, the s-core decomposition method, and the weighted k-shell method) in terms of four quantitative indices, i.e., the imprecision function, the standard deviation of infected fraction of max coreness node, the spreading time, and the number of recovered nodes at the end of spreading process. The experimental results show that our proposed approach is more accurate to identify the influential spreaders than the weighted degree decomposition method, the s-core decomposition method, and the weighted k-shell method, and also helps to more accurately decompose the network core structure for an optimal analysis in weighted network.
      通信作者: 龚凯, gongkai1210@swufe.edu.cn
    • 基金项目: 国家自然科学基金(批准号:61602331)、中央高校基本科研业务费专项资金(批准号:JBK170133,JBK160130,JBK150503)、四川省教育厅科研基金(批准号:J17ZB0434)和互联网金融创新及监管协同创新中心资助的课题.
      Corresponding author: Gong Kai, gongkai1210@swufe.edu.cn
    • Funds: Project supported by the National Natural Science Foundation of China (Grant No. 61602331), the Fundamental Research Funds for the Central Universities of Ministry of Education of China (Grant Nos. JBK170133, JBK160130, JBK150503), the Scientific Research Foundation of the Education Department of Sichuan Province, China (Grant No. 17ZB0434), and the Collaborative Innovation Center for Electronic Finance and Financial Regulation.
    [1]

    Wang X F, Li X, Chen G R 2012 Network Science:an Introduction (Beijing:Higher Education Press) pp3-18(in Chinese)[汪小帆, 李翔, 陈关荣2012网络科学导论(北京:高等教育出版社)第3–18页]

    [2]

    Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106(in Chinese)[刘宏鲲, 周涛2007物理学报 56 106]

    [3]

    Zhang Z K, Liu C, Zhan X X, Lu X, Zhang C X, Zhang Y C 2016 Phys. Rep. 651 1

    [4]

    Liu C, Zhan X X, Zhang Z K, Sun G Q, Hui P M 2015 New J. Phys. 17 113045

    [5]

    Cohen R, Erez K, Benavraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682

    [6]

    Liu J G, Lin J H, Guo Q, Zhou T 2016 Sci. Rep. 6 21380

    [7]

    Keeling M J, Rohani P 2008 Modeling Infectious Diseases in Humans and Animals (Princeton:Princeton University Press) p366

    [8]

    Gong K, Tang M, Hui P M, Zhang H F, Younghae D, Lai Y C 2013 Plos One 8 e83489

    [9]

    Liu C, Zhang Z K 2014 Commun. Nonlinear Sci. 19 896

    [10]

    Crucitti P, Latora V, Marchiori M, Rapisarda A 2004 Physica A 340 388

    [11]

    Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901(in Chinese)[刘建国, 任卓明, 郭强, 汪秉宏2013物理学报 62 178901]

    [12]

    Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175(in Chinese)[任晓龙, 吕琳媛2014科学通报 59 1175]

    [13]

    Rombach M P, Porter M A, Fowler J H, Mucha P J 2014 Siam J. Appl. Math. 74 167

    [14]

    Bassett D S, Wymbs N F, Rombach M P, Porter M A, Mucha P J, Grafton S T 2013 Plos Comput. Biol. 9 e1003171

    [15]

    Liu J G, Ren Z M, Guo Q, Chen D B 2014 Plos One 9 e104028

    [16]

    Seidman S B 1983 Social Networks 5 269

    [17]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888

    [18]

    Chen D, L L, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777

    [19]

    Freeman L 1977 Sociometry 40 35

    [20]

    Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031

    [21]

    Hou B, Yao Y, Liao D 2012 Physica A 391 4012

    [22]

    Liu J G, Ren Z M, Guo Q 2013 Physica A 392 4154

    [23]

    Hu Q C, Yin Y S, Ma P F, Gao Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101(in Chinese)[胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓2013物理学报 62 140101]

    [24]

    Ren Z M, Liu J G, Shao F, Hu Z L, Guo Q 2013 Acta Phys. Sin. 62 108902(in Chinese)[任卓明, 刘建国, 邵凤, 胡兆龙, 郭强2013物理学报 62 108902]

    [25]

    Cao J X, Dong D, Xu S, Zheng X, Liu B, Luo J Z 2015 Chin. J. Comput. 38 238(in Chinese)[曹玖新, 董丹, 徐顺, 郑啸, 刘波, 罗军舟2015计算机学报 38 238]

    [26]

    Garas A, Schweitzer F, Havlin S 2012 New J. Phys. 14 83030

    [27]

    Eidsaa M, Almaas E 2013 Phys. Rev. E 88 062819

    [28]

    Wei B, Liu J, Wei D, Gao C, Deng Y 2015 Physica A 420 277

    [29]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602

    [30]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 13172

    [31]

    Barrat A, Barthélemy M, Pastor-Satorras R, Vespignani A 2004 Proc. Natl. Acad. Sci. USA 101 3747

    [32]

    Yan W, Zhou T, Wang J, Fu Z Q, Wang B H 2005 Chin. Phys. Lett. 22 510

    [33]

    Hu H B, Wang X F 2008 Physica A 387 3769

    [34]

    Kendall M G 1938 Biometrika 30 81

    [35]

    Batagelj V, Zaversnik M 2003 arXiv:cs/0310049v1

    [36]

    Lee K M, Yang J S, Kim G, Lee J, Goh K I, Kim I M 2011 Plos One 6 e18443

    [37]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [38]

    Newman M E J 2006 Phys. Rev. E 74 036104

    [39]

    Saramäki J, Kivelä M, Onnela J P, Kaski K, Kertész J 2007 Phys. Rev. E 75 027105

    [40]

    Li X, Jin Y Y, Chen G R 2003 Physica A 328 287

    [41]

    Yan G, Fu Z Q, Chen G 2008 Eur. Phys. J. B 65 591

  • [1]

    Wang X F, Li X, Chen G R 2012 Network Science:an Introduction (Beijing:Higher Education Press) pp3-18(in Chinese)[汪小帆, 李翔, 陈关荣2012网络科学导论(北京:高等教育出版社)第3–18页]

    [2]

    Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106(in Chinese)[刘宏鲲, 周涛2007物理学报 56 106]

    [3]

    Zhang Z K, Liu C, Zhan X X, Lu X, Zhang C X, Zhang Y C 2016 Phys. Rep. 651 1

    [4]

    Liu C, Zhan X X, Zhang Z K, Sun G Q, Hui P M 2015 New J. Phys. 17 113045

    [5]

    Cohen R, Erez K, Benavraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682

    [6]

    Liu J G, Lin J H, Guo Q, Zhou T 2016 Sci. Rep. 6 21380

    [7]

    Keeling M J, Rohani P 2008 Modeling Infectious Diseases in Humans and Animals (Princeton:Princeton University Press) p366

    [8]

    Gong K, Tang M, Hui P M, Zhang H F, Younghae D, Lai Y C 2013 Plos One 8 e83489

    [9]

    Liu C, Zhang Z K 2014 Commun. Nonlinear Sci. 19 896

    [10]

    Crucitti P, Latora V, Marchiori M, Rapisarda A 2004 Physica A 340 388

    [11]

    Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901(in Chinese)[刘建国, 任卓明, 郭强, 汪秉宏2013物理学报 62 178901]

    [12]

    Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175(in Chinese)[任晓龙, 吕琳媛2014科学通报 59 1175]

    [13]

    Rombach M P, Porter M A, Fowler J H, Mucha P J 2014 Siam J. Appl. Math. 74 167

    [14]

    Bassett D S, Wymbs N F, Rombach M P, Porter M A, Mucha P J, Grafton S T 2013 Plos Comput. Biol. 9 e1003171

    [15]

    Liu J G, Ren Z M, Guo Q, Chen D B 2014 Plos One 9 e104028

    [16]

    Seidman S B 1983 Social Networks 5 269

    [17]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888

    [18]

    Chen D, L L, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777

    [19]

    Freeman L 1977 Sociometry 40 35

    [20]

    Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031

    [21]

    Hou B, Yao Y, Liao D 2012 Physica A 391 4012

    [22]

    Liu J G, Ren Z M, Guo Q 2013 Physica A 392 4154

    [23]

    Hu Q C, Yin Y S, Ma P F, Gao Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101(in Chinese)[胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓2013物理学报 62 140101]

    [24]

    Ren Z M, Liu J G, Shao F, Hu Z L, Guo Q 2013 Acta Phys. Sin. 62 108902(in Chinese)[任卓明, 刘建国, 邵凤, 胡兆龙, 郭强2013物理学报 62 108902]

    [25]

    Cao J X, Dong D, Xu S, Zheng X, Liu B, Luo J Z 2015 Chin. J. Comput. 38 238(in Chinese)[曹玖新, 董丹, 徐顺, 郑啸, 刘波, 罗军舟2015计算机学报 38 238]

    [26]

    Garas A, Schweitzer F, Havlin S 2012 New J. Phys. 14 83030

    [27]

    Eidsaa M, Almaas E 2013 Phys. Rev. E 88 062819

    [28]

    Wei B, Liu J, Wei D, Gao C, Deng Y 2015 Physica A 420 277

    [29]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602

    [30]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 13172

    [31]

    Barrat A, Barthélemy M, Pastor-Satorras R, Vespignani A 2004 Proc. Natl. Acad. Sci. USA 101 3747

    [32]

    Yan W, Zhou T, Wang J, Fu Z Q, Wang B H 2005 Chin. Phys. Lett. 22 510

    [33]

    Hu H B, Wang X F 2008 Physica A 387 3769

    [34]

    Kendall M G 1938 Biometrika 30 81

    [35]

    Batagelj V, Zaversnik M 2003 arXiv:cs/0310049v1

    [36]

    Lee K M, Yang J S, Kim G, Lee J, Goh K I, Kim I M 2011 Plos One 6 e18443

    [37]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [38]

    Newman M E J 2006 Phys. Rev. E 74 036104

    [39]

    Saramäki J, Kivelä M, Onnela J P, Kaski K, Kertész J 2007 Phys. Rev. E 75 027105

    [40]

    Li X, Jin Y Y, Chen G R 2003 Physica A 328 287

    [41]

    Yan G, Fu Z Q, Chen G 2008 Eur. Phys. J. B 65 591

  • [1] 李江, 刘影, 王伟, 周涛. 识别高阶网络传播中最有影响力的节点. 物理学报, 2024, 73(4): 048901. doi: 10.7498/aps.73.20231416
    [2] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [3] 任卓明. 动态复杂网络中节点影响力的研究进展. 物理学报, 2020, 69(4): 048901. doi: 10.7498/aps.69.20190830
    [4] 黄丽亚, 汤平川, 霍宥良, 郑义, 成谢锋. 基于加权K-阶传播数的节点重要性. 物理学报, 2019, 68(12): 128901. doi: 10.7498/aps.68.20190087
    [5] 王雨, 郭进利. 基于多重影响力矩阵的有向加权网络节点重要性评估方法. 物理学报, 2017, 66(5): 050201. doi: 10.7498/aps.66.050201
    [6] 阮逸润, 老松杨, 王竣德, 白亮, 侯绿林. 一种改进的基于信息传播率的复杂网络影响力评估算法. 物理学报, 2017, 66(20): 208901. doi: 10.7498/aps.66.208901
    [7] 苏晓萍, 宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点. 物理学报, 2015, 64(2): 020101. doi: 10.7498/aps.64.020101
    [8] 闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙). 基于扩展度的复杂网络传播影响力评估算法. 物理学报, 2015, 64(8): 088901. doi: 10.7498/aps.64.088901
    [9] 胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓. 一种新的网络传播中最有影响力的节点发现方法. 物理学报, 2013, 62(14): 140101. doi: 10.7498/aps.62.140101
    [10] 苑卫国, 刘云, 程军军, 熊菲. 微博双向关注网络节点中心性及传播 影响力的分析. 物理学报, 2013, 62(3): 038901. doi: 10.7498/aps.62.038901
    [11] 王丹, 郝彬彬. 一类高聚类系数的加权无标度网络及其同步能力分析. 物理学报, 2013, 62(22): 220506. doi: 10.7498/aps.62.220506
    [12] 戴存礼, 吴威, 赵艳艳, 姚雪霞, 赵志刚. 权重分布对加权局域世界网络动力学同步的影响. 物理学报, 2013, 62(10): 108903. doi: 10.7498/aps.62.108903
    [13] 任卓明, 刘建国, 邵凤, 胡兆龙, 郭强. 复杂网络中最小K-核节点的传播能力分析. 物理学报, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
    [14] 王丹, 井元伟, 郝彬彬. 加权方式对网络同步能力的影响. 物理学报, 2012, 61(17): 170513. doi: 10.7498/aps.61.170513
    [15] 王丹, 金小峥. 可调聚类系数加权无标度网络建模及其拥塞问题研究. 物理学报, 2012, 61(22): 228901. doi: 10.7498/aps.61.228901
    [16] 吕翎, 孟乐, 郭丽, 邹家蕊, 杨明. 激光时空混沌模型的加权网络投影同步. 物理学报, 2011, 60(3): 030506. doi: 10.7498/aps.60.030506
    [17] 田柳, 狄增如, 姚虹. 权重分布对加权网络效率的影响. 物理学报, 2011, 60(2): 028901. doi: 10.7498/aps.60.028901
    [18] 沈毅, 徐焕良. 加权网络权重自相似评判函数及其社团结构检测. 物理学报, 2010, 59(9): 6022-6028. doi: 10.7498/aps.59.6022
    [19] 李岩, 吕翎, 栾玲. 环形加权网络的时空混沌延迟同步. 物理学报, 2009, 58(7): 4463-4468. doi: 10.7498/aps.58.4463
    [20] 潘灶烽, 汪小帆. 一种可大范围调节聚类系数的加权无标度网络模型. 物理学报, 2006, 55(8): 4058-4064. doi: 10.7498/aps.55.4058
计量
  • 文章访问数:  5023
  • PDF下载量:  253
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-12-16
  • 修回日期:  2017-06-21
  • 刊出日期:  2017-09-05

/

返回文章
返回