基于节点亲密度的链路预测算法

doi:10.11896／j.issn.1002-137X.2018.11.013

摘要/Abstract

摘要： 链路预测作为复杂网络分析的一个重要分支,在不同领域中有着广泛的应用。现有的链路预测算法通常根据共同邻居节点的结构信息来度量节点对之间的相似性,忽略了节点对与其共同邻居节点之间的连接紧密程度。针对此问题,提出了一种基于节点亲密度的链路预测算法。该算法利用边聚集系数来测量节点对与其共同邻居节点之间的紧密程度,以AUC值作为链路预测的精确度评价指标。在4个真实网络上的实验结果表明,相比于其他相似性算法,所提出的算法提高了链路预测的预测精度。

关键词: 复杂网络, 链路预测, 亲密度, 相似性

Abstract: As an important branch of complex network analysis,link prediction has extensive application in different fields.The existing link prediction algorithms usually measure the similarity between two nodes only through the structure information of their common neighborhoods,ignoring the tightness between nodes and their common neighbor nodes.To solve this problem,the paper proposed a link prediction algorithm based on node intimate degree.This algorithm employs the clustering coefficients of edge to measure the intimacy between nodes and their common neighbor nodes,and adopts the receiver operation characteristic Area Under Curve (AUC) as the standard index of link prediction accuracy.The experimental results on four real networks show that the proposed algorithm can improve the prediction precision compared with other link prediction algorithms.

Key words: Complex networks, Intimate degree, Link prediction, Similarity

中图分类号:

TP393

吕亚楠, 韩华, 贾承丰, 完颜娟. 基于节点亲密度的链路预测算法[J]. 计算机科学, 2018, 45(11): 92-96. https://doi.org/10.11896／j.issn.1002-137X.2018.11.013

LV Ya-nan, HAN Hua, JIA Cheng-feng, WAN Yan-juan. Link Prediction Algorithm Based on Node Intimate Degree[J]. Computer Science, 2018, 45(11): 92-96. https://doi.org/10.11896／j.issn.1002-137X.2018.11.013

参考文献

[1]LV L Y,LU J A,ZHANG Z K,et al.Looking into Complex Networks[J].Complex Systems & Complexity Science,2010,7(2):173-186.
[2]CANNISTRA 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(4):1613.
[3]CANNISTRA C V,ALANIS-LOBATO G,RAVASI T.Minimum Curvilinearity to Enhance Topological Prediction of Protein Interactions by Network Embedding[J].Bioinformatics,2013,29(13):199-209.
[4]CRONE S F,SOOPRAMANIEN D.Predicting Customer Online Shopping Adoption-an Evaluation of Data Mining and Market Modelling Approaches[C]∥International Conference on Data Mining,Dmin 2005.Las Vegas,Nevada,USA,DBLP,2005:215-221.
[5]MA C,ZHOU T,ZHANG H F.Playing the Role of Weak Clique Property in Link Prediction:A Friend Recommendation Model[J].Scientific Reports,2016,6:30098.
[6]FU Y B,CHEN Y Z.Relationship Analysis of Microblogging User with Link Prediction[J].Computer Science,2014,41(2):201-205.(in Chinese)
傅颖斌,陈羽中.基于链路预测的微博用户关系分析[J].计算机科学,2014,41(2):201-205.
[7]CHEN B,CHEN L.A Link Prediction Algorithm Based on Ant Colony Optimization[J].Applied Intelligence,2014,41(3):694-708.
[8]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.
[9]SARUKKAI R R.Link Prediction and Path Analysis Using Markov Chains[J].Computer Networks,2000,33(1):377-386.
[10]LV L Y,ZHOU T.Link Prediction in Complex Networks:A Survey[J].Physica A:Statistical Mechanics and its Applications,2011,390(6):1150-1170.
[11]YANG J X,ZHANG X D.Prediction Missing Links in Complex Networks Based on Common Neighbors and Distance[J].Scientific Reports,2016,6:38208.
[12]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.(in Chinese)
陈嘉颖,于炯,杨兴耀,等.基于复杂网络节点重要性的链路预测算法[J].计算机应用,2016,36(12):3251-3255.
[13]GAO Y,ZHANG 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)
高扬,张平,钱付兰,等.结合节点度和节点聚集系数的链路预测算法[J].小型微型计算机系统,2017,38(7):1436-1441.
[14]LORRAIN F,WHITE H C.Structural Equivalence of Indivi- duals in Social Networks[J].The Journal of Mathematical Socio-logy,1971,1(1):49-80.
[15]ADAMICd L A,ADAR E.Friends and Neighbors on the Web[J].Social Networks,2003,25(3):211-230.
[16]ZHOU T,LV L Y,ZHANG Y C.Predicting Missing Links via Local Information[J].European Physical Journal B,2009,71(4):623-630.
[17]WU Z H,LIN Y F,WANG J,et al.Link Prediction with Node Clustering Coefficient[J].Physica A:Statistical Mechanics and its Applications,2016,45(2):1-8.
[18]JIA J,HU X F,HE X Y.On the Relationship Between Network Structure Features and Link Prediction Algorithms[J].Complex Systems and Complexity Science,2017,14(1):28-37.(in Chinese)
贾珺,胡晓峰,贺筱媛.网络结构特征与链路预测算法关系研究[J].复杂系统与复杂性科学,2017,14(1):28-37.
[19]ZHAO T,LV L,ZHANG Y C.Predicting Missing Links via Local Information[J].The European Physical Journal B-Condensed Matter and Complex Systems,2009,71(4):623-630.
[20]KATZ L.A New Status Index Derived from Sociometric Index[J].Psychometrika,1953,18(1):39-43.
[21]LEICHT E A,HOLME P,NEWMAN M E J.Verter Similarity in Networks[J].Physical Review E,2006,73(2):026120-026130.
[22]ZHU X,TAIN H,CAI S.Predicting Missing Links via Effective Paths[J].Physica A:Statistical Mechanics and its Applications,2014,413(11):515-522.
[23]KLEIN D J,RANDIC M.Resistance Distance[J].Journal of Mathematical Chemistry,1993,12(1):81-95.
[24]BRIN S,PAGE L.The Anatomy of a Large-Scale Hypertextual Web Search Engine[J].Computer Network and ISDN Systems,1998,30(1):107-117.
[25]LIU W P,LV L Y.Link Predicting Based on Local Random Walk[J].Europhysics Letters,2010,89(5):58007-58012.
[26]LIU S,LIU H,CHEN Q M,et al.Link Prediction Algorithm Based on Network Representation Learning and Random Walk[J].Journal of Computer Applications,2017,37(8):2234-2239.(in Chinese)
刘思,刘海,陈启买,等.基于网络表示学习与随机游走的链路预测算法[J].计算机应用,2017,37(8):2234-2239.
[27]HU J,YANG B R.Community Structure Discovery Algorithm Based on Edge Clustering Coefficient[J].Application Research of Computers,2009,26(3):858-859.(in Chinese)
胡徤,杨炳儒.基于边聚集系数的社区结构发现算法[J].计算机应用研究,2009,26(3):858-859.
[28]FAWCETT T.An Introduction to ROC Analysis[J].Pattern Recognition Letters,2006,27(8):861-874.
[29]NEWMAN M E J.Finding Community Structure in Networks Using the Eigen Vectors of Matrices[J].Physical Review E,2006,74(3):036104-036113.
[30]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.
[31]ULANOWICZl R E,BONDAVALLI C,EGNOTOVICH M S.Network Analysis of Trophic Dynamics in South Florida Ecosystem[R].FY 97:The Florida Bay Ecosystem,1997.
[32]ACKLAND R.Mapping the US Political Blogosphere:Are Conservative Bloggers more Prominent?[C]∥Blog Talk Downunder 2005 Conference.Sydney,2005.
[33]DONG Y X,KE Q,WU B.Link Prediction Based on Node Similarity[J].Computer Science,2011,18(7):162-164.(in Chinese)
东昱晓,柯庆,吴斌.基于节点相似性的链接预测[J].计算机科学,2011,18(7):162-164.
[34]LV L Y.Link Prediction on Complex Networks[J].Journal of University of Electronic Science and Technology of China,2010,39(5):651-661.(in Chinese)
吕琳媛.复杂网络链路预测[J].电子科技大学学报,2010,39(5):651-661.

相关文章 15

[1]	郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2]	杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[3]	何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[4]	蔡晓娟, 谭文安. 一种改进的融合相似度和信任度的协同过滤算法 Improved Collaborative Filtering Algorithm Combining Similarity and Trust 计算机科学, 2022, 49(6A): 238-241. https://doi.org/10.11896/jsjkx.210400088
[5]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[6]	李勇, 吴京鹏, 张钟颖, 张强. 融合快速注意力机制的节点无特征网络链路预测算法 Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism 计算机科学, 2022, 49(4): 43-48. https://doi.org/10.11896/jsjkx.210800276
[7]	陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[8]	郭磊, 马廷淮. 基于好友亲密度的用户匹配 Friend Closeness Based User Matching 计算机科学, 2022, 49(3): 113-120. https://doi.org/10.11896/jsjkx.210200137
[9]	杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009
[10]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[11]	李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[12]	郑建炜, 黄娟娟, 秦梦洁, 徐宏辉, 刘志. 基于非局部相似及加权截断核范数的高光谱图像去噪 Hyperspectral Image Denoising Based on Non-local Similarity and Weighted-truncated NuclearNorm 计算机科学, 2021, 48(9): 160-167. https://doi.org/10.11896/jsjkx.200600135
[13]	罗月童, 汪涛, 杨梦男, 张延孔. 基于历史行车轨迹集的车辆行为可视分析方法 Historical Driving Track Set Based Visual Vehicle Behavior Analytic Method 计算机科学, 2021, 48(9): 86-94. https://doi.org/10.11896/jsjkx.200900040
[14]	何涛, 赵停, 徐鹤. 基于暗通道先验的单幅图像去雾新算法 Novel Algorithm of Single Image Dehazing Based on Dark Channel Prior 计算机科学, 2021, 48(7): 219-224. https://doi.org/10.11896/jsjkx.200700160
[15]	穆俊芳, 郑文萍, 王杰, 梁吉业. 基于重连机制的复杂网络鲁棒性分析 Robustness Analysis of Complex Network Based on Rewiring Mechanism 计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed