基于统一描述网络结构模型的链路预测方法

doi:10.19678/j.issn.1000-3428.0061523

摘要/Abstract

摘要： 面向网络链路预测的随机分块模型和层次结构模型利用全概率思想计算节点对之间的链路形成概率，但无法有效利用从宏观、中观网络结构到微观低阶环或模体结构中的重叠结构信息，导致链路预测结果的准确率较低。根据笛卡尔积和幂集等概念，借鉴随机分块模型和层次结构模型思想，构建一种对层次结构信息、重叠结构信息和微观结构信息进行统一描述的网络结构模型（USI）。基于USI模型提出一种链路预测方法，依据网络结构信息给出USI模型中的集合划分，利用最大似然估计法计算节点对之间的链路形成概率，最终根据概率并联策略得到链路预测结果。实验结果表明，与基于节点相似性的经典链路预测方法相比，该方法在LT、ER、OP网络数据集上的AUC值提升了0.075~0.143，具有更高的链路预测准确性，并且验证了网络规模对链路形成具有一定的影响。

关键词: 复杂网络, 链路预测, 统一描述, 网络结构模型, 前端融合

Abstract: The random block model and hierarchical structure model for network link prediction use the idea of total probability to calculate the link formation probability between node pairs.They, however, cannot effectively use overlapping structural information from macroscopic and mesoscopic network structures in this endeavor.Neither can they effectively use microscopic low-order rings or motif structures, resulting in low accuracy of link prediction results.In this study, according to the concepts of Cartesian product and power set, and drawing on ideas from the random block model and the hierarchical structure model, a network structure model called the USI(Uniform-Structure-Information) model is constructed.The USI model uniformly describes hierarchical, overlapping, and microstructure information.Based on the USI model, a link prediction method is proposed.According to the network structure information, the set division in the USI model is given.The maximum likelihood estimation method is used to calculate the link formation probability between node pairs, and finally, the link prediction result is obtained according to probabilistic parallel strategies.The experimental results show that compared with the classic link prediction method based on node similarity, the AUC(Area Under the Receiver Operation Characteristic Curve) value of this method on the LT(London Transport1), ER(Euroroad), and OP(Opsahl_powergrid) network datasets is improved by 0.075~0.143, and it has higher link prediction accuracy.It is verified that this network scale has a certain influence on the link formation.

Key words: complex network, link prediction, unified description, network structure model, front-end fusion

中图分类号:

TP393

吴翼腾, 于洪涛, 顾泽宇. 基于统一描述网络结构模型的链路预测方法[J]. 计算机工程, 2022, 48(7): 51-58.

WU Yiteng, YU Hongtao, GU Zeyu. Link Prediction Method Based on Network Structure Model for Unified Description[J]. Computer Engineering, 2022, 48(7): 51-58.

http://www.ecice06.com/CN/Y2022/V48/I7/51

图/表 4

参考文献

[1] GARCÍA-PÉREZ G, ALIAKBARISANI R, GHASEMI A, et al.Precision as a measure of predictability of missing links in real networks[J].Physical Review E, 2020, 101(5):052318.
[2] ZHANG J, YU P S.Link prediction[EB/OL].[2021-03-17].https://doi.org/10.1007/978-3-030-12528-8_7.
[3] 谭索怡, 祁明泽, 吴俊, 等.复杂网络链路可预测性:基于特征谱视角[J].物理学报, 2020, 69(8):182-191. TAN S Y, QI M Z, WU J, et al.Link predictability of complex network from spectrum perspective[J].Acta Physica Sinica, 2020, 69(8):182-191.(in Chinese)
[4] CANNISTRACI C V, ALANIS-LOBATO G, 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.
[5] 李冬, 申德荣, 寇月, 等.基于层次化混合特征图的链路预测方法[J].中国科学:信息科学, 2020, 50(2):221-238. LI D, SHEN D R, KOU Y, et al.Research on a link-prediction method based on a hierarchical hybrid-feature graph[J].Scientia Sinica Informationis, 2020, 50(2):221-238.(in Chinese)
[6] 汪小帆.无标度网络研究纷争:回顾与评述[J].电子科技大学学报, 2020, 49(4):499-510. WANG X F.Controversial issues in researches on scale-free networks:an overview with a network perspective[J].Journal of University of Electronic Science and Technology of China, 2020, 49(4):499-510.(in Chinese)
[7] 吕琳媛, 周涛.链路预测[M].北京:高等教育出版社, 2013. LÜ L Y, ZHOU T.Link prediction[M].Beijing:Higher Education Press, 2013.(in Chinese)
[8] ZHOU T, LÜ L, ZHANG Y C.Predicting missing links via local information[J].The European Physical Journal B, 2009, 71(4):623-630.
[9] YAO Y B, ZHANG R S, YANG F, et al.Link prediction based on local weighted paths for complex networks[J].International Journal of Modern Physics C, 2017, 28(4):1750053.
[10] LIU S X, JI X S, LIU C X, et al.Similarity indices based on link weight assignment for link prediction of unweighted complex networks[J].International Journal of Modern Physics B, 2017, 31(2):1650254.
[11] 王凯, 李星, 兰巨龙, 等.一种基于资源传输路径拓扑有效性的链路预测方法[J].电子与信息学报, 2020, 42(3):653-660. WANG K, LI X, LAN J L, et al.A new link prediction method for complex networks based on topological effectiveness of resource transmission paths[J].Journal of Electronics & Information Technology, 2020, 42(3):653-660.(in Chinese)
[12] 刘树新, 李星, 陈鸿昶, 等.基于资源传输匹配度的复杂网络链路预测方法[J].通信学报, 2020, 41(6):70-79. LIU S X, LI X, CHEN H C, et al.Link prediction method based on matching degree of resource transmission for complex network[J].Journal on Communications, 2020, 41(6):70-79.(in Chinese)
[13] BISWAS A, BISWAS B.Community-based link prediction[J].Multimedia Tools and Applications, 2017, 76(18):18619-18639.
[14] DE BACCO C, POWER E A, LARREMORE D B, et al.Community detection, link prediction, and layer interdependence in multilayer networks[J].Physical Review E, 2017, 95:042317.
[15] MALLEK S, BOUKHRIS I, ELOUEDI Z, et al.Evidential Link Prediction Based on Group Information[M].Berlin, Germany:Springer, 2015.
[16] HE Y L, LIU J N K, HU Y X, et al.OWA operator based link prediction ensemble for social network[J].Expert Systems with Applications, 2015, 42(1):21-50.
[17] 吴祖峰, 梁棋, 刘峤, 等.基于AdaBoost的链路预测优化算法[J].通信学报, 2014, 35(3):116-123. WU Z F, LIANG Q, LIU Q, et al.Modified link prediction algorithm based on AdaBoost[J].Journal on Communications, 2014, 35(3):116-123.(in Chinese)
[18] YU H T, WANG S H, MA Q Q.Link prediction algorithm based on the Choquet fuzzy integral[J].Intelligent Data Analysis, 2016, 20(4):809-824.
[19] 吴翼腾, 于洪涛, 黄瑞阳, 等.采用组合方法进行链路预测的理论极限研究[J].通信学报, 2020, 41(6):34-50. WU Y T, YU H T, HUANG R Y, et al.Theoretical limit of link prediction using a combination method[J].Journal on Communications, 2020, 41(6):34-50.(in Chinese)
[20] MARTÍNEZ V, BERZAL F, CUBERO J C.A survey of link prediction in complex networks[J].ACM Computing Surveys, 2017, 49(4):69.
[21] HOLLAND P W, LASKEY K B, LEINHARDT S.Stochastic block models:first steps[J].Social Networks, 1983, 5(2):109-137.
[22] GUIMERÀ R, SALES-PARDO M.Missing and spurious interactions and the reconstruction of complex networks[J].Proceedings of the National Academy of Sciences of the United States of America, 2009, 106(52):22073-22078.
[23] CLAUSET A, MOORE C, NEWMAN M E J.Hierarchical structure and the prediction of missing links in networks[J].Nature, 2008, 453(7191):98-101.
[24] WU Y T, YU H T, ZHANG J P, et al.USI-AUC:an evaluation criterion of community detection based on a novel link-prediction method[J].Intelligent Data Analysis, 2018, 22(2):439-462.
[25] 王守辉, 于洪涛, 黄瑞阳, 等.基于模体演化的时序链路预测方法[J].自动化学报, 2016, 42(5):735-745. WANG S H, YU H T, HUANG R Y, et al.A temporal link prediction method based on motif evolution[J].Acta Automatica Sinica, 2016, 42(5):735-745.(in Chinese)
[26] HESPANHA P.An efficient MATLAB algorithm for graph partitioning[EB/OL].[2021-03-17].https://www.researchgate.net/profile/Joao-Hespanha/publication/239563498_An_Efficient_MATLAB_Algorithm_for_Graph_Partitioning/links/545ab7050cf2c46f66438782/An-Efficient-MATLAB-Algorithm-for-Graph-Partitioning.pdf.
[27] GIRVAN M, NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.
[28] NEWMAN M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical Review E, 2006, 74(3):036104.
[29] DE DOMENICO M, SOLÉ-RIBALTA A, GÓMEZ S, et al.Navigability of interconnected networks under random failures[J].Proceedings of the National Academy of Sciences of the United States of America, 2014, 111(23):8351-8356.
[30] COLEMAN J, KATZ E, MENZEL H.The diffusion of an innovation among physicians[J].Sociometry, 1957, 20(4):253-270.
[31] PAJEK datasets[EB/OL].[2021-03-17].http://vlado.fmf.unilj.si/pub/networks/data/mix/mixed.htm.
[32] ŠUBELJ L, BAJEC M.Robust network community detection using balanced propagation[J].The European Physical Journal B, 2011, 81(3):353-362.
[33] WATTS D J, STROGATZ S H.Collective dynamics of 'small-world' networks[J].Nature, 1998, 393(6684):440-442.
[34] ULANOWICZ R E, BONDAVALLI C, EGNOTOVICH M S.Network analysis of trophic dynamics in south Florida ecosystem, FY 97:the Florida Bay ecosystem[EB/OL].[2021-03-17].https://www.researchgate.net/publication/237005294_Network_Analysis_of_Trophic_Dynamics_in_South_Florida_Ecosystem_FY_97_The_Florida_Bay_Ecosystem.
[35] LORRAIN F, WHITE H C.Structural equivalence of individuals in social networks[M].Amsterdam, Holland:Elsevier, 1977.
[36] ADAMIC L A, ADAR E.Friends and neighbors on the Web[J].Social Networks, 2003, 25(3):211-230.
[37] BARABASI A L, ALBERT R.Emergence of scaling in random networks[J].Science, 1999, 286(5439):509-512.
[38] LIU W P, LÜ L.Link prediction based on local random walk[J].Europhysics Letters, 2010, 89(5):58007-58012.
[39] KLEIN D J, RANDIĆ M.Resistance distance[J].Journal of Mathematical Chemistry, 1993, 12(1):81-95.

选择文件类型/文献管理软件名称

选择包含的内容