Computer Science ›› 2018, Vol. 45 ›› Issue (11): 92-96.doi: 10.11896/j.issn.1002-137X.2018.11.013

• Network & Communication • Previous Articles     Next Articles

Link Prediction Algorithm Based on Node Intimate Degree

LV Ya-nan, HAN Hua, JIA Cheng-feng, WAN Yan-juan   

  1. (School of Science,Wuhan University of Technology,Wuhan 430070,China)
  • Received:2017-10-09 Published:2019-02-25

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

CLC Number: 

  • TP393
[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.
[1] SONG Jie, LIANG Mei-yu, XUE Zhe, DU Jun-ping, KOU Fei-fei. Scientific Paper Heterogeneous Graph Node Representation Learning Method Based onUnsupervised Clustering Level [J]. Computer Science, 2022, 49(9): 64-69.
[2] CHAI Hui-min, ZHANG Yong, FANG Min. Aerial Target Grouping Method Based on Feature Similarity Clustering [J]. Computer Science, 2022, 49(9): 70-75.
[3] HUANG Li, ZHU Yan, LI Chun-ping. Author’s Academic Behavior Prediction Based on Heterogeneous Network Representation Learning [J]. Computer Science, 2022, 49(9): 76-82.
[4] ZHENG Wen-ping, LIU Mei-lin, YANG Gui. Community Detection Algorithm Based on Node Stability and Neighbor Similarity [J]. Computer Science, 2022, 49(9): 83-91.
[5] WU Zi-yi, LI Shao-mei, JIANG Meng-han, ZHANG Jian-peng. Ontology Alignment Method Based on Self-attention [J]. Computer Science, 2022, 49(9): 215-220.
[6] LI Bin, WAN Yuan. Unsupervised Multi-view Feature Selection Based on Similarity Matrix Learning and Matrix Alignment [J]. Computer Science, 2022, 49(8): 86-96.
[7] ZENG Zhi-xian, CAO Jian-jun, WENG Nian-feng, JIANG Guo-quan, XU Bin. Fine-grained Semantic Association Video-Text Cross-modal Entity Resolution Based on Attention Mechanism [J]. Computer Science, 2022, 49(7): 106-112.
[8] HUANG Shao-bin, SUN Xue-wei, LI Rong-sheng. Relation Classification Method Based on Cross-sentence Contextual Information for Neural Network [J]. Computer Science, 2022, 49(6A): 119-124.
[9] CAI Xiao-juan, TAN Wen-an. Improved Collaborative Filtering Algorithm Combining Similarity and Trust [J]. Computer Science, 2022, 49(6A): 238-241.
[10] WANG Yi, LI Zheng-hao, CHEN Xing. Recommendation of Android Application Services via User Scenarios [J]. Computer Science, 2022, 49(6A): 267-271.
[11] CHENG Ke-yang, WANG Ning, CUI Hong-gang, ZHAN Yong-zhao. Interpretability Optimization Method Based on Mutual Transfer of Local Attention Map [J]. Computer Science, 2022, 49(5): 64-70.
[12] CHEN Zhuang, ZOU Hai-tao, ZHENG Shang, YU Hua-long, GAO Shang. Diversity Recommendation Algorithm Based on User Coverage and Rating Differences [J]. Computer Science, 2022, 49(5): 159-164.
[13] LI Yong, WU Jing-peng, ZHANG Zhong-ying, ZHANG Qiang. Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism [J]. Computer Science, 2022, 49(4): 43-48.
[14] YANG Xu-hua, WANG Lei, YE Lei, ZHANG Duan, ZHOU Yan-bo, LONG Hai-xia. Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding [J]. Computer Science, 2022, 49(3): 121-128.
[15] ZHAO Xue-lei, JI Xin-sheng, LIU Shu-xin, LI Ying-le, LI Hai-tao. Link Prediction Method for Directed Networks Based on Path Connection Strength [J]. Computer Science, 2022, 49(2): 216-222.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!