Hill Climbing-Based Efficient Model for Link Prediction in Undirected Graphs

被引:5
作者
Gul, Haji [1 ]
Al-Obeidat, Feras [2 ]
Amin, Adnan [1 ]
Moreira, Fernando [3 ,4 ]
Huang, Kaizhu [5 ]
机构
[1] Inst Management Sci, Ctr Excellence Informat Technol, Peshawar 25000, Pakistan
[2] Zayed Univ, Coll Technol Innovat, Abu Dhabi 144534, U Arab Emirates
[3] Univ Portucalense, REMIT, IJP, P-4200072 Porto, Portugal
[4] Univ Aveiro, IEETA, P-3810193 Aveiro, Portugal
[5] Duke Kunshan Univ, Div Nat & Appl Sci, Data Sci Res Ctr, Duke Ave 8, Suzhou 215316, Peoples R China
关键词
complex network analysis; local link prediction methods; link prediction; complex networks; hill climbing; MISSING LINKS; COMPLEX NETWORKS; NEIGHBORS;
D O I
10.3390/math10224265
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Link prediction is a key problem in the field of undirected graph, and it can be used in a variety of contexts, including information retrieval and market analysis. By "undirected graphs", we mean undirected complex networks in this study. The ability to predict new links in complex networks has a significant impact on society. Many complex systems can be modelled using networks. For example, links represent relationships (such as friendships, etc.) in social networks, whereas nodes represent users. Embedding methods, which produce the feature vector of each node in a graph and identify unknown links, are one of the newest approaches to link prediction. The Deep Walk algorithm is a common graph embedding approach that uses pure random walking to capture network structure. In this paper, we propose an efficient model for link prediction based on a hill climbing algorithm. It is used as a cost function. The lower the cost is, the higher the accuracy for link prediction between the source and destination node will be. Unlike other algorithms that predict links based on a single feature, it takes advantage of multiple features. The proposed method has been tested over nine publicly available datasets, and its performance has been evaluated by comparing it to other frequently used indexes. Our model outperforms all of these measures, as indicated by its higher prediction accuracy.
引用
收藏
页数:15
相关论文
共 69 条
[1]   Friends and neighbors on the Web [J].
Adamic, LA ;
Adar, E .
SOCIAL NETWORKS, 2003, 25 (03) :211-230
[2]   A new similarity measure for link prediction based on local structures in social networks [J].
Aghabozorgi, Farshad ;
Khayyambashi, Mohammad Reza .
PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2018, 501 :12-23
[3]  
Airoldi EM, 2008, J MACH LEARN RES, V9, P1981
[4]   Evolution of the social network of scientific collaborations [J].
Barabási, AL ;
Jeong, H ;
Néda, Z ;
Ravasz, E ;
Schubert, A ;
Vicsek, T .
PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2002, 311 (3-4) :590-614
[5]   The number of followings as an influential factor in rumor spreading [J].
Bodaghi, Amirhosein ;
Goliaei, Sama ;
Salehi, Mostafa .
APPLIED MATHEMATICS AND COMPUTATION, 2019, 357 :167-184
[6]   Hierarchical structure and the prediction of missing links in networks [J].
Clauset, Aaron ;
Moore, Cristopher ;
Newman, M. E. J. .
NATURE, 2008, 453 (7191) :98-101
[7]   Reaction-diffusion processes and metapopulation models in heterogeneous networks [J].
Colizza, Vittoria ;
Pastor-Satorras, Romualdo ;
Vespignani, Alessandro .
NATURE PHYSICS, 2007, 3 (04) :276-282
[8]   Distinguishing humans from computers in the game of go: A complex network approach [J].
Coquide, C. ;
Georgeot, B. ;
Giraud, O. .
EPL, 2017, 119 (04)
[9]  
Dhannuri Svam Prasad, 2019, 2019 6th International Conference on Electrical Engineering, Computer Science and Informatics (EECSI). Proceedings, P410, DOI 10.23919/EECSI48112.2019.8977087
[10]   Temporal Link Prediction: A Survey [J].
Divakaran, Aswathy ;
Mohan, Anuraj .
NEW GENERATION COMPUTING, 2020, 38 (01) :213-258