Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2022, Vol. 62 Issue (1): 98-104    DOI: 10.16511/j.cnki.qhdxxb.2021.21.039
  专题:社会媒体处理 本期目录 | 过刊浏览 | 高级检索 |
基于聚类系数和节点中心性的链路预测算法
郁湧1,3, 王莹港1, 罗正国1, 杨燕1, 王鑫锴1, 高涛2, 于倩1,3
1. 云南大学 软件学院, 昆明 650091;
2. 云南经济管理学院 教育学院, 昆明 650033;
3. 云南省软件工程重点实验室, 昆明 650091
Link prediction algorithm based on clustering coefficient and node centrality
YU Yong1,3, WANG Yinggang1, LUO Zhengguo1, YANG Yan1, WANG Xinkai1, GAO Tao2, YU Qian1,3
1. School of Software, Yunnan University, Kunming 650091, China;
2. School of Education, Yunnan University of Business Management, Kunming 650033, China;
3. Key Laboratory in Software Engineering of Yunnan Province, Kunming 650091, China
全文: PDF(1747 KB)   HTML
输出: BibTeX | EndNote (RIS)      
摘要 目前复杂网络领域受到越来越多人的广泛关注。其中链路预测是复杂网络研究中的一个热门的分支,被作为预测缺失链路和识别虚假链路的有效手段。传统基于相似性的复杂网络链路预测主要考虑每个节点的某个相似性指标,而该文提出一种基于聚类系数和节点中心性(CCNC)的链路预测算法,将度、聚类系数和节点中心性3个相似度指标结合,引入到复杂网络链路预测中。该算法使用度和聚类系数作为局部信息的指标,使用节点中心性表征节点在网络中的重要程度。最后,以6个真实网络为例,通过对比曲线下面积(AUC)和精确度(Precision),验证了CCNC算法的可行性和有效性。
服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
郁湧
王莹港
罗正国
杨燕
王鑫锴
高涛
于倩
关键词 复杂网络链路预测聚类系数节点中心性    
Abstract:Currently, more people are becoming interested in the field of complex networks. Link prediction is a popular subdiscipline in complex networks and is used to predict missing links and identify false links. The traditional similarity-based complex network link prediction focuses on a particular similarity index of each node. This paper proposes the link prediction algorithm based on clustering coefficient and node centrality (CCNC), which combines the degree index, clustering coefficient index, and proximity centrality index into the link prediction of a complex network. This algorithm considers local information using clustering coefficient and degree by introducing proximity centrality to consider the importance of nodes in the network. Finally, using six real networks as examples, the feasibility and effectiveness of the CCNC algorithm are verified by comparing the AUC and the precision values.
Key wordscomplex network    link prediction    clustering coefficient    node centrality
收稿日期: 2021-05-18      出版日期: 2022-01-14
基金资助:云南省科技厅面上项目(202001BB050063);云南省教育厅科学研究基金项目(2019J0008,2020J0002);云南省软件工程重点实验室开放项目(2020SE315)
通讯作者: 高涛,二级教师,E-mail:gaotao929@163.com     E-mail: gaotao929@163.com
引用本文:   
郁湧, 王莹港, 罗正国, 杨燕, 王鑫锴, 高涛, 于倩. 基于聚类系数和节点中心性的链路预测算法[J]. 清华大学学报(自然科学版), 2022, 62(1): 98-104.
YU Yong, WANG Yinggang, LUO Zhengguo, YANG Yan, WANG Xinkai, GAO Tao, YU Qian. Link prediction algorithm based on clustering coefficient and node centrality. Journal of Tsinghua University(Science and Technology), 2022, 62(1): 98-104.
链接本文:  
http://jst.tsinghuajournals.com/CN/10.16511/j.cnki.qhdxxb.2021.21.039  或          http://jst.tsinghuajournals.com/CN/Y2022/V62/I1/98
  
  
  
  
  
  
  
  
  
  
[1] GARCÍA-PÉREZ G, ALIAKBARISANI R, GHASEMI A, et al. Predictability of missing links in complex networks[Z/OL]. (2019-01-31)[2021-04-30]. https://arxiv.org/abs/1902.00035.
[2] FARASHAH M V, ETEBARIAN A, AZMI R, et al. A hybrid recommender system based-on link predictionfor movie baskets analysis[J]. Journal of Big Data, 2021, 8(1):32.
[3] SAXENA A, FLETCHER G, PECHENIZKIY M. Nodesim:Node similarity based network embedding for diverse link prediction[Z/OL]. (2021-02-01)[2021-04-30]. https://arxiv.org/abs/2102.00785.
[4] ZHOU Y Z, WU C C, TAN L L. Biased random walk with restart for link prediction with graph embedding method[J]. Physica A:Statistical Mechanics and its Applications, 2021, 570:125783.
[5] YANG X H, YANG X H, LING F, et al. Link prediction based on local major path degree[J]. Modern Physics Letters B, 2018, 32(29):1850348.
[6] XU Z Q, PU C L, YANG J. Link prediction based on pathentropy[J]. Physica A:Statistical Mechanics and its Applications, 2016, 456:294-301.
[7] CHEN X, JIAO P F, YU Y D, et al. Toward link predictability of bipartite networks based on structural enhancement and structural perturbation[J]. Physica A:Statistical Mechanics and its Applications, 2019, 527:121072.
[8] LÜ L Y, PAN L M, ZHOU T, et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences, 2015, 112(8):2325-2330.
[9] 陈嘉颖, 于炯, 杨兴耀, 等. 基于复杂网络节点重要性的链路预测算法[J]. 计算机应用, 2016, 36(12):3251-3255, 3268. CHEN J Y, YU J, YANG X Y, et al. Link prediction algorithm based on node importance in complex networks[J]. Journal of Computer Applications, 2016, 36(12):3251-3255, 3268. (in Chinese)
[10] 贾承丰, 韩华, 吕亚楠, 等. 基于Word2vec和粒子群的链路预测算法[J]. 自动化学报, 2020, 46(8):1703-1713. JIA C F, HAN H, LÜ Y N, et al. Link prediction algorithm based on word2vec and particle swarm[J]. Acta Automatica Sinica, 2020, 46(8):1703-1713. (in Chinese)
[11] 杨旭华, 俞佳, 张端. 基于局部社团和节点相关性的链路预测算法[J]. 计算机科学, 2019, 46(1):155-161. YANG X H, YU J, ZHANG D. Link predictionmethod based on local community and nodes' relativity[J]. Computer Science, 2019, 46(1):155-161. (in Chinese)
[12] SUN Q, HU R, YANG Z, et al. An improved link prediction algorithm based on degrees and similarities ofnodes[C]//2017 IEEE/ACIS 16th International Conference on Computer and Information Science (ICIS). Wuhan, China:IEEE, 2017:13-18.
[13] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684):440-442.
[14] RAPOPORT A. Spread of information through a population with socio-structural bias:I. Assumption of transitivity[J]. The Bulletin of Bathematical Biophysics, 1953, 15(4):523-533.
[15] ADAMIC L A, ADAR E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3):211-230.
[16] ZHOU T, LÜ L Y, ZHANG Y C. Predicting missing links via local information[J]. The European Physical Journal B, 2009, 71(4):623-630.
[17] 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.
[18] JACCARD P. Étude comparative de la distribution florale dans une portion des alpes et des jura[J]. Bulletinde la Societe Vaudoise des Sciences Naturelles, 1901, 37(142):547-579.
[19] 高杨, 张燕平, 钱付兰, 等. 结合节点度和节点聚类系数的链路预测算法[J]. 小型微型计算机系统, 2017, 38(7):1436-1441. GAO Y, ZHANG Y P, QIAN F L, et al. Combined with node degree and node clustering coefficient of link prediction algorithm[J]. Journal of Chinese Computer Systems, 2017, 38(7):1436-1441. (in Chinese)
[20] 陈紫扬, 张月霞. 结合二层节点度和聚类系数的链路预测算法[J]. 计算机工程与应用, 2019, 55(23):40-44. CHEN Z Y, ZHANG Y X. Link prediction algorithm combining two-layer node degree and clustering coefficient[J]. Computer Engineering and Applications, 2019,55(23):40-44. (in Chinese)
[21] KOVÁCS I A, LUCK K, SPIROHN K, et al. Network-based prediction of protein interactions[J]. Nature Communications, 2019, 10(1):1240.
[22] MUMIN D, SHI L L, LIU L. An efficient algorithm for link prediction based on local information:Considering the effect of node degree[C]//2019 15th International Conference on Semantics, Knowledge and Grids (SKG). Guangzhou, China:IEEE, 2019:131-138.
[23] 白桦, 马云龙, 毕玉, 等. 一种基于节点局部相似性的复杂网络链路预测算法[J]. 计算机应用与软件, 2020, 37(5):298-301, 308. BAI H, MA Y L, BI Y, et al. A complicated network link prediction algorithm based on local similarity of nodes[J]. Computer Applications and Software, 2020, 37(5):298-301, 308. (in Chinese)
[24] HANLEY J A, MCNEIL B J. The meaning and use of the area under a receiver operating characteristic (ROC) curve[J]. Radiology, 1982, 143(1):29-36.
[25] HERLOCKER J L, KONSTAN J A, TERVEEN L G, et al. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems (TOIS), 2004, 22(1):5-53.
[1] 李自圆, 孙昊, 李林波. 基于手机信令数据的长三角全域城际出行网络分析[J]. 清华大学学报(自然科学版), 2022, 62(7): 1203-1211.
[2] 谢丽霞, 孙红红, 杨宏宇, 张良. 基于K-shell的复杂网络关键节点识别方法[J]. 清华大学学报(自然科学版), 2022, 62(5): 849-861.
[3] 丁莹, 张健钦, 杨木, 宫鹏, 贾礼朋, 邓少存. 新冠疫情发生城市仿真模型及防控措施评价——以武汉市为例[J]. 清华大学学报(自然科学版), 2021, 61(12): 1452-1461.
[4] 王志如, 苏国锋, 梁作论. 基于信息传递效率的地铁网络小世界特性评价[J]. 清华大学学报(自然科学版), 2016, 56(4): 411-416.
[5] 倪顺江, 翁文国, 张辉. 大规模传染病传播围堵策略的模拟研究[J]. 清华大学学报(自然科学版), 2016, 56(1): 97-101.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn