融合聚集系数的链接预测方法

doi:10.11772/j.issn.1001-9081.2019061008

计算机应用 ›› 2020, Vol. 40 ›› Issue (1): 28-35.DOI: 10.11772/j.issn.1001-9081.2019061008

融合聚集系数的链接预测方法

刘昱阳, 李龙杰, 单娜, 陈晓云

兰州大学信息科学与工程学院, 兰州 730000

收稿日期:2019-06-14 修回日期:2019-09-18 发布日期:2019-10-08 出版日期:2020-01-10
通讯作者: 李龙杰
作者简介:刘昱阳(1996-),男,山西临汾人,硕士研究生,主要研究方向:网络信息挖掘、链接预测;李龙杰(1981-),男,河南商丘人,工程师,博士,CCF会员,主要研究方向:数据挖掘、机器学习、网络信息挖掘;单娜(1996-),女,河北保定人,硕士研究生,主要研究方向:网络信息挖掘、链接预测;陈晓云(1954-),女,吉林长春人,教授,博士生导师,CCF高级会员,硕士,主要研究方向:数据挖掘、大数据分析、人工智能、网络信息挖掘。
基金资助:
国家自然科学基金青年基金资助项目（61602225）；中央高校基本科研业务费专项（lzujbky-2019-90）。

Link prediction method fusing clustering coefficients

LIU Yuyang, LI Longjie, SHAN Na, CHEN Xiaoyun

School of Information Science and Engineering, Lanzhou University, Lanzhou Gansu 730000, China

Received:2019-06-14 Revised:2019-09-18 Online:2019-10-08 Published:2020-01-10
Supported by:
This work is partially supported by the Youth Program of National Natural Science Foundation of China (61602225), the Fundamental Research Funds for the Central Universities (lzujbky-2019-90).

摘要/Abstract

摘要： 许多基于网络结构信息的链接预测算法利用节点的聚集程度评估节点间的相似性，进而执行链接预测；然而，该类算法只注重网络中节点的聚集系数，没有考虑预测节点与共同邻居节点之间的链接聚集系数对节点间相似性的影响。针对上述问题，提出了一种融合节点聚集系数和非对称链接聚集系数的链接预测算法。首先，计算共同邻居节点的聚集系数，并利用共同邻居节点对应的两个非对称链接聚集系数计算该预测节点的平均链接聚集系数；然后，基于Dempster-Shafer证据理论将两种聚集系数进行融合生成一个综合性度量指标，并将该指标应用于中间概率模型（IMP），得到一个新的节点相似性指标（IMP_DS）。在9个网络数据上的实验结果表明，该算法的受试者工作特征（ROC）的曲线下方面积（AUC）与精度值（Precision）优于共同邻居（CN）、Adamic-Adar（AA）、资源分配（RA）指标和基于共同邻居的中间概率模型（IMP_CN）。

关键词: 链接预测, 复杂网络, Dempster-Shafer理论, 聚集系数, 相似性指标

Abstract: Many network structure information-based link prediction algorithms estimate the similarity between nodes and perform link prediction by using the clustering degree of nodes. However, these algorithms only focus on the clustering coefficient of nodes in network, and do not consider the influence of link clustering coefficient between the predicted nodes and their common neighbor nodes on the similarity between nodes. Aiming at the problem, a link prediction algorithm combining node clustering coefficient and asymmetric link clustering coefficient was proposed. Firstly, the clustering coefficient of common neighbor node was calculated, and the average link clustering coefficient of the predicted nodes was obtained by using two asymmetric link clustering coefficients of common neighbor node. Then, a comprehensive measurement index was obtained by fusing these two clustering coefficients based on Dempster-Shafer(DS) theory, and by applying the index to Intermediate Probability Model (IMP), a new node similarity index, named IMP_DS, was designed. The experimental results on the data of nine networks show that the proposed algorithm achieves performance in terms of Area Under the Curve (AUC) of Receiver Operating Characteristic (ROC) and Precision in comparison with Common Neighbor (CN), Adamic-Adar (AA), Resource Allocation (RA) indexes and InterMediate Probability model based on Common Neighbor (IMP_CN).

Key words: link prediction, complex network, Dempster-Shafer (DS) theory, clustering coefficient, similarity index

中图分类号:

TP391

刘昱阳, 李龙杰, 单娜, 陈晓云. 融合聚集系数的链接预测方法[J]. 计算机应用, 2020, 40(1): 28-35.

LIU Yuyang, LI Longjie, SHAN Na, CHEN Xiaoyun. Link prediction method fusing clustering coefficients[J]. Journal of Computer Applications, 2020, 40(1): 28-35.

参考文献

[1] LÜ L, ZHOU T. Link prediction in complex networks:a survey[J]. Physica A:Statistical Mechanics and its Applications, 2011, 390(6):1150-1170.
[2] KOVÁCS I A, LUCK K, SPIROHN K, et al. Network-based prediction of protein interactions[J]. Nature Communications, 2019, 10(1):1240.
[3] 丁超,赵海,司帅宗,等.正常衰老的人脑功能网络演化模型[J].计算机应用,2019,39(4):963-971.(DING C, ZHAO H, SI S Z, et al. Evolution model of normal aging human brain functional network[J]. Journal of Computer Applications, 2019, 39(4):963-971.)
[4] LI D, ZHANG Y, XU Z, et al. Exploiting information diffusion feature for link prediction in Sina Weibo[J]. Scientific Reports, 2016, 6:No.20058.
[5] CRONE S F, SOOPRAMANIEN D. Predicting customer online shopping adoption-an evaluation of data mining and market modelling approaches[EB/OL].[2019-01-11]. https://pdfs.semanticscholar.org/fd1d/f142629dd35ade4260f3d456847330e86016.pdf.
[6] WANG J, MO H, WANG F, et al. Exploring the network structure and nodal centrality of China's air transport network:a complex network approach[J]. Journal of Transport Geography, 2011, 19(4):712-721.
[7] GRABOWSKI A, KRUSZEWSKA N, KOSINSKI R A. Dynamic phenomena and human activity in an artificial society[J]. Physical Review E, 2008, 78(6 Pt 2):No.066110.
[8] LIBEN-NOWELL D, KLEINBERG J. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology, 2007, 58(7):1019-1031.
[9] ZHOU T, LÜ L, ZHANG Y. Predicting missing links via local information[J]. The European Physical Journal B, 2009, 71(4):623-630.
[10] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social Networks, 2003, 25(3):211-230.
[11] KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1):39-43.
[12] KLEIN D J, RANDIC M. Resistance distance[J]. Journal of Mathematical Chemistry, 1993, 12(1):81-95.
[13] FOUSS F, PIROTTE A, RENDERS J M. 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.
[14] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1/2/3/4/5/6/7):107-117.
[15] JEH G, WIDOM J. SimRank:a measure of structural-context similarity[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2002:538-543.
[16] LIU W, LÜ L. Link prediction based on local random walk[J]. EPL (Europhysics Letters), 2010, 89(5):58007.
[17] WU Z, LIN Y, WANG J, et al. Link prediction with node clustering coefficient[J]. Physica A:Statistical Mechanics and its Applications, 2016, 452:1-8.
[18] LIU Z, ZHANG Q, LÜ L, et al. Link prediction in complex networks:A local naive Bayes model[J]. EPL (Europhysics Letters), 2011, 96(4):No.48007.
[19] ZHANG X, PANG W, XIA Y. An intermediary probability model for link prediction[J]. Physica A:Statistical Mechanics and its Applications, 2018, 512:902-912.
[20] WU Z, LIN Y, ZHAO Y, 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.
[21] WANG J, LI M, WANG H, et al. Identification of essential proteins based on edge clustering coefficient[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2012, 9(4):1070-1080.
[22] SHAFER G. A Mathematical Theory of Evidence[M]. Princeton:Princeton University Press, 1976:1-32.
[23] KANG B, CHHIPI-SHRESTHA G, DENG Y, et al. Development of a predictive model for Clostridium difficile infection incidence in hospitals using Gaussian mixture model and Dempster-Shafer theory[J]. Stochastic Environmental Research and Risk Assessment, 2018, 32(6):1743-1758.
[24] LIU T, DENG Y, CHAN F. Evidential supplier selection based on DEMATEL and game theory[J]. International Journal of Fuzzy Systems, 2018, 20(4):1321-1333.
[25] YE F, CHEN J, LI Y, et al. Decision-making algorithm for multisensor fusion based on grey relation and DS evidence theory[J]. Journal of Sensors, 2016, 2016:No. 3954573.
[26] JIANG W, XIE C, ZHUANG M, et al. Sensor data fusion with Z-numbers and its application in fault diagnosis[J]. Sensors, 2016, 16(9):No.1509.
[27] 邰滢滢,庞影,段苛苛,等.基于改进权重的D-S证据理论的动态负载平衡算法[J].计算机应用,2018,38(10):2976-2981,2989.(TAI Y Y, PANG Y, DUAN K K, et al. Dynamic algorithm of load balancing based on D-S evidence theory with improved weight[J]. Journal of Computer Applications, 2018, 38(10):2976-2981, 2989.)
[28] ULANOWICZ R E, 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.
[29] NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3 Pt 2):No.036104.
[30] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4):452-473.
[31] ULANOWICZ R E, DEANGELIS D L. Network analysis of trophic dynamics in south Florida ecosystems[C]//Proceedings of South Florida Restoration Science Forum. Boca Raton:[s.n.], 1999:114-115.
[32] GLEISER P M, DANON L. Community structure in jazz[J]. Advances in Complex Systems, 2003, 6(4):565-573.
[33] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684):440-442.
[34] ISELLA L, STEHLÉ J, BARRAT A, et al. What's in a crowd? Analysis of face-to-face behavioral networks[J]. Journal of Theoretical Biology, 2011, 271(1):166-180.
[35] GUIMERA R, DANON L, DIAZ-GUILERA A, et al. Self-similar community structure in a network of human interactions[J]. Physical Review E, 2003, 68(6 Pt 2):No.065103.
[36] FAWCETT T. An introduction to ROC analysis[J]. Pattern Recognition Letters, 2006, 27(8):861-874.
[37] HERLOCKER J L,KONSTAN J A,TERVEEN L G,et al. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems, 2004, 22(1):5-53.
[38] LI L, BAI S, LENG M, et al. Finding missing links in complex networks:a multiple-attribute decision-making method[J]. Complexity, 2018, 2018:No.3579758.
[39] YANG J, ZHANG X. Predicting missing links in complex networks based on common neighbors and distance[J]. Scientific Reports, 2016, 6:No.38208.

融合聚集系数的链接预测方法

Link prediction method fusing clustering coefficients

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	黄杰, 武瑞梓, 李均利. 高效的自适应复杂网络鲁棒性优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3530-3539.
[2]	王中钰, 钱晓东. 基于改进期望最大化算法的供应链网络边连接规则优化[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3386-3395.
[3]	周琳, 肖玉芝, 刘鹏, 秦有鹏. 基于节点多关系的社团挖掘算法及其应用[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1489-1496.
[4]	李鹏, 王世林, 陈光武, 闫光辉. 基于改进的局部结构熵复杂网络重要节点挖掘[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1109-1114.
[5]	王可可, 朱宇, 王晓英, 黄建强, 曹腾飞. 超边约束的异质超网络表示学习方法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3654-3661.
[6]	温祥西, 彭娅婷, 毕可心, 衡宇铭, 吴明功. 基于最优样本集在线模糊最小二乘支持向量机的飞行冲突网络态势预测[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3632-3640.
[7]	李占利, 李颖, 罗香玉, 罗颖骁. 基于Monte-Carlo迭代求解策略的局部社区发现算法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 104-110.
[8]	袁立宁, 刘钊. 基于One-Shot聚合自编码器的图表示学习[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 8-14.
[9]	孟昱煜, 郭静. 信息熵改进主成分分析模型的链路预测算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2823-2829.
[10]	余晓鹏, 何儒汉, 黄晋, 张俊杰, 胡新荣. 基于改进Inception结构的知识图谱嵌入模型[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1065-1071.
[11]	郝志刚, 秦丽. 基于多属性综合评价的食品安全标准引用网络重要节点发现方法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1178-1185.
[12]	胡军, 许正康, 刘立, 钟福金. 融合多粒度社区信息的网络嵌入方法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 663-670.
[13]	陈广福, 王海波, 连雁平. 基于高阶自包含协同过滤的有向网络链路预测[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3060-3068.
[14]	蔡彪, 李蕊岑, 吴媛媛. 相似性特征对链路预测的影响与增强[J]. 计算机应用, 2021, 41(9): 2569-2577.
[15]	李亚芳, 梁烨, 冯韦玮, 祖宝开, 康玉健. 基于社区优化的深度网络嵌入方法[J]. 计算机应用, 2021, 41(7): 1956-1963.