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

Haji Gul, Feras Al-Obeidat (), Adnan Amin, Fernando Moreira and Kaizhu Huang
Additional contact information
Haji Gul: Center for Excellence in Information Technology, Institute of Management Sciences, Peshawar 25000, Pakistan
Feras Al-Obeidat: College of Technological Innovation, Zayed University, Abu Dhabi 144534, United Arab Emirates
Adnan Amin: Center for Excellence in Information Technology, Institute of Management Sciences, Peshawar 25000, Pakistan
Fernando Moreira: REMIT, IJP, Universidade Portucalense, 4200-072 Porto, Portugal
Kaizhu Huang: Data Science Research Center, Division of Natural and Applied Sciences, Duke Kunshan University Duke Avenue No. 8, Kunshan, Suzhou 215316, China

Mathematics, 2022, vol. 10, issue 22, 1-15

Abstract: 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.

Keywords: complex network analysis; local link prediction methods; link prediction; complex networks; hill climbing (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/22/4265/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/22/4265/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:22:p:4265-:d:972868

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().