融合节点中心性和度相关聚类的有向网络链路预测

计算机与现代化 ›› 2022, Vol. 0 ›› Issue (08): 36-42.

融合节点中心性和度相关聚类的有向网络链路预测

(1.武夷学院数学与计算机学院,福建武夷山354399;2.福建省茶产业大数据应用与智能化重点实验室,福建武夷山354399)

出版日期:2022-08-22 发布日期:2022-08-22
作者简介:陈广福(1979—),男,江西上饶人,讲师,博士,研究方向:链路预测，网络表示,E-mail: cgf21st@163.com; 连雁平(1981—),男,福建莆田人,副教授,硕士,研究方向:机器学习,大数据,E-mail: 30202708@qq.com。
基金资助:
福建省自然科学基金资助项目(2021J011146); 武夷学院引进人才科研启动基金资助项目(YJ202017)

Link Prediction in Directed Network Combining Node Centrality and Degree-related Clustering

(1. College of Mathematics and Computer Science, Wuyi University, Wuyishan 354399, China;
2. Fujian Key Laboratory of Big Data Application and Intellectualization for Tea Industry, Wuyishan 354399, China)

Online:2022-08-22 Published:2022-08-22

摘要/Abstract

摘要： 现存大部分有向网络的链路预测方法仅关注链接方向信息和互惠链接信息而忽略节点重要性及度相关聚类的贡献，导致预测精度下降。针对以上不足，提出基于节点中心性和度相关聚类的有向网络链路预测指标。首先，利用节点中心性统计任意节点邻居数量去衡量节点的影响力;其次，将节点度相关聚类系数方法扩展到有向网络去评估节点聚类能力，并与网络同配系数相融合获得节点对高聚类能力;最后，融合以上2类信息提出一个带参的有向网络链路预测指标。在6个真实世界有向网络上与最近代表性预测指标比较，所提指标AUPR和AUC分别提高了33%和1.6%。

关键词: 有向网络, 链路预测, 节点中心性, 度相关聚类系数

Abstract: Most existing link prediction methods of directed networks only focus on link direction information and reciprocal link information, but ignore the contribution of node importance and degree correlation clustering, which leads to the decrease of prediction accuracy. To solve these problems, a directed network link prediction algorithm based on node centrality and degree correlation clustering is proposed. Firstly, it uses node centrality to calculate the number of neighbors of any node to measure the influence of node. Secondly, the node degree correlation clustering coefficient method is extended to the directed network to evaluate the clustering ability of nodes, and it is combined with the network coordination coefficient to obtain the high clustering ability of nodes. Finally, a parametric directed network link prediction index is proposed by integrating the above two kinds of information. On the six real world network compared with recent representative methods, the AUPR and AUC of the proposed algorithm are improved 33% and 1.6% respectively.

Key words: directed network, link prediction, node centrality, degree-related clustering coefficient

陈广福, 连雁平, . 融合节点中心性和度相关聚类的有向网络链路预测[J]. 计算机与现代化, 2022, 0(08): 36-42.

CHEN Guang-fu, LIAN Yan-ping, . Link Prediction in Directed Network Combining Node Centrality and Degree-related Clustering[J]. Computer and Modernization, 2022, 0(08): 36-42.

参考文献

［1］李艳丽,周涛. 链路预测中的局部相似性指标［J］. 电子科技大学学报, 2021,50(3):422-427.
［2］ HUANG Z, ZENG D L, A link prediction approach to anomalous email detection［C］// 2006 IEEE International Conference on Systems, Man and Cybernetics. 2006:1131-1136.
［3］ HUO Z P, HUANG X, HU X. Link prediction with personalized social influence［C］// Proceedings of the 32th AAAI Conference on Artificial Intelligence. 2018:2289-2296.
［4］ YU S Q, ZHAO M H, FU C B, et al. Target defense against link-prediction-based attacks via evolutionary perturbations［J］. IEEE Transactions on Knowledge and Data Engineering, 2019,33(2):754-767.
［5］ 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
［6］ ZHOU T, L L, ZHANG Y C. Predicting missing links via local information［J］. European Physical Journal B, 2009,71(4):623-630.
［7］ ADAMIC L A, ADAR E. Friends and neighbors on the web［J］. Social Networks, 2003,25(3):211-230.
［8］ WU Z H, LIN Y F, WANG J, et al. Link prediction with node clustering coefficient［J］. Social and Information Networks, arXiv preprint arXiv:1510.07819, 2015.
［9］ KUMAR A, SINGH S S, SINGH K, et al. Level-2 node clustering coefficient-based link prediction［J］. Applied Intelligence, 2019,49(7):2762-2779.
［10］郁湧,王莹港,罗正国,等. 基于聚类系数和节点中心性的链路预测算法［J］. 清华大学学报(自然科学版), 2022,62(1):98-104.
［11］CHEN X,FANG L, YANG T H, et al. The application of degree related clustering coefficient in estimating the link predictability and predicting missing links of networks［J］. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2019,29(5):053135.
［12］KATZ L. A new status index derived from sociometric analysis［J］. Psychometrika, 1953,18(1):39-43.
［13］ZHOU T, L L, ZHANG Y C. Predicting missing links via local information［J］. The European Physical Journal B, 2009,71(4):623-630.
［14］MACKAY R S, JOHNSON S, SANSOM B. How directed is a directed network?［J］. Royal Society open science, 2020. DOI:10.10981rsos.201138.
［15］ZHANG X, ZHAO C L, WANG X J, et al. Identifying missing and spurious interactions in directed networks［C］// Proceedings of the 9th International Conference on Wireless Algorithms, Systems, and Applications. 2014:470-481.
［16］BTN E, KAYA M, ALHAJJ R. Extension of neighbor-based link prediction methods for directed, weighted and temporal social networks［J］. Information Sciences, 2018,463:152-165.
［17］LI J S, PENG J H, LIU S X, et al. Link prediction in directed networks utilizing the role of reciprocal links［J］. IEEE Access, 2020,8:28668-28680.
［18］ZHANG Q M, L L, WANG W Q, et al. Potential theory for directed networks［J］. PloS One, 2013,8(2). DOI:10.1371journal.pone.0055437.
［19］GHORBANZADEH H, SHEIKHAHMADI A, JALILI M, et al. A hybrid method of link prediction in directed graphs［J］. Expert Systems with Applications, 2021,165:113896.
［20］YI T, ZHANG S F, BU Z, et al. Link prediction based on higher-order structure extraction and autoencoder learning in directed networks［J］. Knowledge-Based Systems, 2022,241:108241.
［21］TABAK B M, TAKAMI M, ROCHA J M C, et al. Directed clustering coefficient as a measure of systemic risk in complex banking networks［J］. Physica A: Statistical Mechanics and ITs Applications, 2014,394:211-216.
［22］HANLEY J A, MCNELL B J. The meaning and use of the area under a receiver operating characteristic (ROC) curve［J］. Radiology, 1982,143(1):29-36.
［23］YANG Y, LICHTENWALTER R N, CHAWLA N V.Evaluating link prediction methods［J］. Knowledge and Information Systems, 2015,45(3):751-782.
［24］KUNEGIS J. KONECT: The koblenz network collection［C］// Proceedings of the 22nd International Conference on World Wide Web. 2013:1343-1350.
［25］LESKOVEC J, KREVL A. SNAP Datasets: Stanford Large Network Dataset Collection［EB/OL］. ［2021-11-23］. http://snap.stanford.edu/data/.
［26］ROSSI R, AHMED N. Network Repository［EB/OL］. ［2021-11-23］. https://networkrepository. com/platform.php.
［27］PECH R, HAO D, LEE Y L, et al. Linkprediction via linear optimization［J］. Physica A: Statistical Mechanics and its Applications, 2019,528:121319.
［28］YU Y, WANG X X. Link prediction in directed network and its application in microblog［J］. Mathematical Problems in Engineering, 2014(1):1-8.

[1]	祝丁恺, 铁治欣, 洪顺贺. 一种HRG模型初始化算法及在链路预测中的应用[J]. 计算机与现代化, 2022, 0(02): 38-44.
[2]	万杨晔, 郭进利. 基于资源分配与图嵌入加权的链路预测算法[J]. 计算机与现代化, 2021, 0(07): 12-17.
[3]	罗兰花, 袁淑丹, 何巧萍. 一种基于节点中心性近似算法的ICN协作缓存策略[J]. 计算机与现代化, 2021, 0(04): 85-90.
[4]	庄天益，许国艳，孙洁，周星熠，朱进. 一种基于贡献矩阵的有向网络节点关键度计算方法[J]. 计算机与现代化, 2019, 0(12): 108-.