高级搜索

一种基于节点间资源承载度的链路预测方法

王凯 刘树新 陈鸿昶 李星

引用本文: 王凯, 刘树新, 陈鸿昶, 李星. 一种基于节点间资源承载度的链路预测方法[J]. 电子与信息学报, 2019, 41(5): 1225-1234. doi: 10.11999/JEIT180553 shu
Citation:  Kai WANG, Shuxin LIU, Hongchang CHEN, Xing LI. A New Link Prediction Method for Complex Networks Based on Resources Carrying Capacity Between Nodes[J]. Journal of Electronics and Information Technology, 2019, 41(5): 1225-1234. doi: 10.11999/JEIT180553 shu

一种基于节点间资源承载度的链路预测方法

    作者简介: 王凯: 男,1980年生,副研究员,博士生,研究方向为链路预测、社会网络分析;
    刘树新: 男,1987年生,助理研究员,博士,研究方向为复杂网络演化、链路预测、通信网络安全;
    陈鸿昶: 男,1964年生,教授,博士生导师,研究方向为电信网安全、社团发现;
    李星: 男,1987年生,助理研究员,博士生,研究方向为社会网络分析
    通讯作者: 刘树新,liushuxin11@126.com;liushuxin11@gmail.com
  • 基金项目: 国家自然科学基金(61521003, 61803384)

摘要: 链路预测旨在发现网络的未知、缺失连接,具有重要的实际应用价值。基于网络结构相似性的链路预测方法具有简单且有效的特点,受到各领域学者的普遍关注。然而,许多现有方法在计算节点间存在连接可能性时,忽视了节点间资源承载能力的影响。鉴于此,该文提出一种基于节点间资源承载度的链路预测方法。该方法首先通过分析节点间资源传输过程,进而对节点间资源承载能力进行量化,提出资源承载度。然后,基于资源承载度对节点间连接可能性的影响进行分析,并提出相应的链路预测方法。9个真实网络的实验结果表明,相比其他链路预测方法,该方法在3个衡量标准下均具有较高的预测精度。

English

    1. [1]

      SHANMUKHAPPA T, HO I W H, and TSE C K. Spatial analysis of bus transport networks using network theory[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 502: 295–314. doi: 10.1016/j.physa.2018.02.111

    2. [2]

      CUI Ying, CAI Meng, DAI Yang, et al. A hybrid network-based method for the detection of disease-related genes[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 389–394. doi: 10.1016/j.physa.2017.10.026

    3. [3]

      VINCENOT C E. How new concepts become universal scientific approaches: insights from citation network analysis of agent-based complex systems science[J]. Proceedings of the Royal Society B: Biological Sciences, 2018, 285(1874): 20172360. doi: 10.1098/rspb.2017.2360

    4. [4]

      CHEN Zhenhao, WU Jiajing, XIA Yongxiang, et al. Robustness of interdependent power grids and communication networks: A complex network perspective[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2018, 65(1): 115–119. doi: 10.1109/TCSII.2017.2705758

    5. [5]

      KIM J and HASTAK M. Social network analysis: characteristics of online social networks after a disaster[J]. International Journal of Information Management, 2018, 38(1): 86–96. doi: 10.1016/j.ijinfomgt.2017.08.003

    6. [6]

      VON MERING C, JENSEN L J, SNEL B, et al. STRING: known and predicted protein-protein associations, integrated and transferred across organisms[J]. Nucleic Acids Research, 2005, 33(1): D433–D437. doi: 10.1093/nar/gki005

    7. [7]

      SCELLATO S, NOULAS A, and MASCOLO C. Exploiting place features in link prediction on location-based social networks[C]. Proceedings of the 17th ACM Sigkdd International Conference on Knowledge Discovery and Data Mining, San Diego, California, USA, 2011: 1046–1054. doi: 10.1145/2020408.2020575.

    8. [8]

      HOLLAND P W, LASKEY K B, and LEINHARDT S. Stochastic blockmodels: first steps[J]. Social Networks, 1983, 5(2): 109–137. doi: 10.1016/0378-8733(83)90021-7

    9. [9]

      SANZ-CRUZADO J, PEPA S M, and CASTELLS P. Structural novelty and diversity in link prediction[C]. Companion of the the Web Conference, 2018, Lyon, France, 2018: 1347–1351.

    10. [10]

      LORRAIN F and WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematical Sociology, 1971, 1(1): 49–80. doi: 10.1080/0022250X.1971.9989788

    11. [11]

      ZHOU Tao, LÜ Linyuan, and ZHANG Yicheng. Predicting missing links via local information[J]. The European Physical Journal B, 2009, 71(4): 623–630. doi: 10.1140/epjb/e2009-00335-8

    12. [12]

      ADAMIC L A and ADAR E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211–230. doi: 10.1016/S0378-8733(03)00009-1

    13. [13]

      CANNISTRACI C V, ALANIS-LOBATO G, and RAVASI T. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J]. Scientific Reports, 2013(3): 1613. doi: 10.1038/srep01613

    14. [14]

      LIU Shuxin, JI Xinsheng, LIU Caixia, et al. Extended resource allocation index for link prediction of complex network[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 479: 174–183. doi: 10.1016/j.physa.2017.02.078

    15. [15]

      KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39–43. doi: 10.1007/BF02289026

    16. [16]

      KLEIN D J and RANDIĆ M. Resistance distance[J]. Journal of Mathematical Chemistry, 1993, 12(1): 81–95. doi: 10.1007/BF01164627

    17. [17]

      FOUSS F, PIROTTE A, RENDERS J M, et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(3): 355–369. doi: 10.1109/tkde.2007.46

    18. [18]

      LÜ Linyuan, JIN Cihang, and ZHOU Tao. Similarity index based on local paths for link prediction of complex networks[J]. Physical Review E, 2009, 80(4): 046122. doi: 10.1103/PhysRevE.80.046122

    19. [19]

      YANG Yujie, ZHANG Jianhua, ZHU Xuzhen, et al. Link prediction via significant influence[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 1523–1530. doi: 10.1016/j.physa.2017.11.078

    20. [20]

      刘树新, 季新生, 刘彩霞, 等. 一种信息传播促进网络增长的网络演化模型[J]. 物理学报, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902
      LIU Shuxin, JI Xinsheng, LIU Caixia, et al. A complex network evolution model for network growth promoted by information transmission[J]. Acta Physica Sinica, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902

    21. [21]

      WANG Xingyuan, ZHOU Wenjie, LI Rui, et al. Improving robustness of interdependent networks by a new coupling strategy[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 1075–1080. doi: 10.1016/j.physa.2017.11.037

    22. [22]

      WANG Xingyuan, CAO Jianye, LI Rui, et al. A preferential attachment strategy for connectivity link addition strategy in improving the robustness of interdependent networks[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 483: 412–422. doi: 10.1016/j.physa.2017.04.128

    23. [23]

      WANG Xingyuan, CAO Jianye, and QIN Xiaomeng. Study of robustness in functionally identical coupled networks against cascading failures[J]. PLoS One, 2016, 11(8): e0160545. doi: 10.1371/journal.pone.0160545

    24. [24]

      DEWHURST D R, DANFORTH C M, and DODDS P S. Continuum rich-get-richer processes: mean field analysis with an application to firm size[J]. Physical Review E, 2018, 97(6): 062317. doi: 10.1103/PhysRevE.97.062317

    25. [25]

      ZENG Guoping and ZENG E. On the three-way equivalence of AUC in credit scoring with tied scores[J]. Communications in Statistics-Theory and Methods, 2017, 46(17): 1–16. doi: 10.1080/03610926.2018.1435814

    26. [26]

      WU Zhihao, LIN Youfang, ZHAO Yiji, et al. Improving local clustering based top-L link prediction methods via asymmetric link clustering information[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 492: 1859–1874. doi: 10.1016/j.physa.2017.11.103

    27. [27]

      ZENG Xiangxiang, LIU Li, LÜ Linyuan, et al. Prediction of potential disease-associated microRNAs using structural perturbation method[J]. Bioinformatics, 2018, 34(14): 2425–2432. doi: 10.1093/bioinformatics/bty112

    28. [28]

      GOPAL S. The evolving social geography of blogs[M]. MILLER H J. Societies and Cities in the Age of Instant Access. Dordrecht, Springer, 2007: 275–293. doi: 10.1007/1-4020-5427-0_18.

    29. [29]

      MICHALSKI R, PALUS S, and KAZIENKO P. Matching organizational structure and social network extracted from email communication[C]. Proceedings of the 14th International Conference on Business Information Systems, Poznań, Poland, 2011.

    30. [30]

      ULANOWICZ R E and DEANGELIS D L. Network analysis of trophic dynamics in south Florida ecosystems[J]. US Geological Survey Program on the South Florida Ecosystem, 2005, 114: 45–47. (未找到本条文献信息, 请核对

    31. [31]

      WATTS D J and STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440–442. doi: 10.1038/30918

    32. [32]

      MICHALSKI R, PALUS S, and KAZIENKO P. Matching organizational structure and social network extracted from email communication[C]. Proceedings of the 14th International Conference on Business Information Systems, Poznań, Poland, 2011: 197–206. doi: 10.1007/978-3-642-21863-7_17.

    33. [33]

      ADAMIC L A and GLANCE N. The political blogosphere and the 2004 U.S. election: divided they blog[C]. Proceedings of the 3rd International Workshop on Link Discovery, Chicago, USA, 2005: 36–43. doi: 10.1145/1134271.1134277.

    34. [34]

      LÜ Linyuan, PAN Liming, ZHOU Tao, et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2015, 112(8): 2325–2330. doi: 10.1073/pnas.1424644112

    35. [35]

      EWING R M, CHU P, ELISMA F, et al. Large-scale mapping of human protein-protein interactions by mass spectrometry[J]. Molecular Systems Biology, 2007, 3: 89. doi: 10.1038/msb4100134

    36. [36]

      OPSAHL T and PANZARASA P. Clustering in weighted networks[J]. Social Networks, 2009, 31(2): 155–163. doi: 10.1016/j.socnet.2009.02.002

    37. [37]

      刘树新, 季新生, 刘彩霞, 等. 局部拓扑信息耦合促进网络演化[J]. 电子与信息学报, 2016, 38(9): 2180–2187. doi: 10.11999/JEIT151338
      LIU Shuxin, JI Xinsheng, LIU Caixia, et al. Information coupling of local topology promoting the network evolution[J]. Journal of Electronics &Information Technology, 2016, 38(9): 2180–2187. doi: 10.11999/JEIT151338

    1. [1]

      王凯, 李星, 兰巨龙, 卫红权, 刘树新. 一种基于资源传输路径拓扑有效性的链路预测方法. 电子与信息学报, 2020, 42(3): 653-660.

    2. [2]

      邓志宏, 老松杨, 白亮. 基于预测误差修正的时序链路预测方法. 电子与信息学报, 2014, 36(2): 325-331.

    3. [3]

      刘树新, 季新生, 刘彩霞, 汤红波, 巩小锐. 局部拓扑信息耦合促进网络演化. 电子与信息学报, 2016, 38(9): 2180-2187.

    4. [4]

      丁永伟, 杨小虎, 陈根才, KavsAJ. 基于弧度距离的时间序列相似度量. 电子与信息学报, 2011, 33(1): 122-128.

    5. [5]

      李春芳, 刘连忠, 刘振国. 数据库复杂网络构造算法及特征分析. 电子与信息学报, 2012, 34(11): 2700-2706.

    6. [6]

      孙昱, 姚佩阳, 张杰勇, 付凯. 基于优化理论的复杂网络节点攻击策略. 电子与信息学报, 2017, 39(3): 518-524.

    7. [7]

      李帆, 丁锦, 沈耿彪, 赵建辉. 基于复杂网络理论的编队电磁兼容网络优化. 电子与信息学报, 2017, 39(3): 724-730.

    8. [8]

      刘阳, 季新生, 刘彩霞. 一种基于边界节点识别的复杂网络局部社区发现算法. 电子与信息学报, 2014, 36(12): 2809-2815.

    9. [9]

      杜洪越, 李春双, 公利滨. 两个带有已知或未知参数的复杂网络的改进函数投影同步. 电子与信息学报, 2016, 38(7): 1816-1822.

    10. [10]

      杨书新, 梁文, 朱凯丽. 基于三级邻居的复杂网络节点影响力度量方法. 电子与信息学报, 2020, 42(0): 1-9.

    11. [11]

      史圣卿, 陈凯, 汪玉, 罗嵘. 基于FPGA的稀疏网络关键节点计算的硬件加速方法研究. 电子与信息学报, 2011, 33(10): 2536-2540.

    12. [12]

      刘功申, 孟魁, 郭弘毅, 苏波, 李建华. 基于贡献函数的重叠社区划分算法. 电子与信息学报, 2017, 39(8): 1964-1971.

    13. [13]

      吴宪云, 高媛媛, 刘凯, 李云松. 基于纹理相似性的高效视频编码帧间预测优化算法. 电子与信息学报, 2016, 38(3): 655-660.

    14. [14]

      刘焕淋, 杜君丹, 易鹏飞, 陈勇, 张明佳. 弹性光网络中面向可靠性的链路故障概率保护与保护资源重配置策略. 电子与信息学报, 2017, 39(11): 2579-2586.

    15. [15]

      丁军, 刘宏伟, 陈渤, 冯博, 王英华. 相似性约束的深度置信网络在SAR图像目标识别的应用. 电子与信息学报, 2016, 38(1): 97-103.

    16. [16]

      葛国栋, 郭云飞, 刘彩霞, 兰巨龙. 命名数据网络中基于局部请求相似性的协作缓存路由机制. 电子与信息学报, 2015, 37(2): 435-442.

    17. [17]

      胡曦, 李喆, 刘军. 移动Ad hoc网络中基于链路稳定性预测的按需路由协议. 电子与信息学报, 2010, 32(2): 284-289.

    18. [18]

      俞鹤伟, 梁根, 秦勇. 异构无线网络多链路接入动态资源分配算法. 电子与信息学报, 2017, 39(4): 817-824.

    19. [19]

      郑博, 黄国策, 张衡阳. 三维移动Ad hoc网络链路动态性研究. 电子与信息学报, 2011, 33(11): 2605-2609.

    20. [20]

      唐治果, 李乐民, 虞红芳. 针对MPLS网络流量工程的链路关键性路由算法. 电子与信息学报, 2007, 29(5): 1187-1190.

  • 图 1  网络中任意两点之间资源承载示意图

    图 2  网络节点间资源传输示意图

    图 3  不同拓扑结构下节点间资源承载度对比

    图 4  不同节点对节点间资源承载度的影响

    图 5  强度参数对AUC结果影响曲线图

    图 6  强度参数对Pre结果影响曲线图

    图 7  9个网络中ROC曲线对比结果

    表 1  网络数据特征参数

    NetworkAIDSFWFBFWFWCEEmailPBHamsterFigeysUC
    |V|146128692971671222185822391899
    |E|1802075880214857841671712534643213838
    C0.0520.3350.5520.3080.5410.3610.09040.040.109
    <k>2.4732.4225.5114.4669.2627.3613.495.7614.57
    <d>3.421.781.642.461.872.743.393.983.06
    r–0.725–0.112–0.298–0.225–0.295–0.221–0.085–0.331–0.188
    下载: 导出CSV

    表 2  AUC结果对比

    NetworkAIDSFWFBFWEWCEEmailPBHamsterFigeysUC
    CN0.5880.6050.6860.8530.9200.9230.8170.5630.782
    RA0.6010.6090.7010.8730.9280.9270.8220.5680.786
    AA0.6020.6080.6950.8700.9220.9260.8210.5670.786
    CAR0.5890.6200.6890.8530.9190.9210.8170.5640.780
    LP-0.0010.8310.6220.7070.8710.9220.9350.9360.8890.891
    LP-0.010.8310.6700.7300.8710.9210.9370.9420.9030.902
    Katz-0.0010.8470.6200.7060.8700.9210.9340.9350.8860.891
    Katz-0.010.8480.6750.7370.8690.9190.9320.9390.9000.901
    ACT0.9510.7220.7840.7550.9000.8910.8710.9180.895
    Cos+0.5840.6500.5140.8620.9060.9250.9610.8430.871
    QN-18.50.9360.9180.9270.8960.9350.9460.9770.9450.928
    QN-max0.9620.9190.9280.8960.9360.9470.9770.9520.928
    下载: 导出CSV

    表 3  Pre结果对比

    NetworkAIDSFWFBFWEWCEEmailPBHamsterFigeysUC
    CN0.0140.0860.1610.1310.7080.4170.0150.0110.022
    RA0.0260.0880.1700.1290.7270.2470.0070.0140.020
    AA0.0260.0900.1640.1380.7200.3800.0100.0120.022
    CAR0.0140.0880.1500.1310.7030.4780.0300.0260.052
    LP-0.0010.0510.0940.1710.1370.7090.4210.0170.0110.025
    LP-0.010.0510.1230.1980.1360.7010.4550.0520.0120.034
    Katz-0.0010.0530.0930.1710.1370.7090.4220.0170.0110.025
    Katz-0.010.0530.1340.2020.1360.6960.4540.0710.0120.037
    ACT0.0000.0000.1260.0000.0000.0000.0000.0000.000
    Cos+0.0000.0390.0000.0810.6200.3330.0170.0080.011
    QN-2.50.0750.3970.4150.1560.7340.4600.2510.1920.114
    QN-max0.0780.6510.5470.2510.9270.5800.9060.2100.165
    下载: 导出CSV
  • 加载中
图(7)表(3)
计量
  • PDF下载量:  25
  • 文章访问数:  263
  • HTML全文浏览量:  101
文章相关
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章