Link prediction in complex networks based on Significance of Higher-Order Path Index (SHOPI)

Ajay Kumar, Shivansh Mishra, Shashank Sheshar Singh, Kuldeep Singh and Bhaskar Biswas

Physica A: Statistical Mechanics and its Applications, 2020, vol. 545, issue C

Abstract: Finding missing links in an observed network (static) or predicting those links that may appear in the future (dynamic) is the aim of the link prediction (LP) task. LP plays a significant role in network evolution, as shown by several works (Barabasi and Albert,1999; Kleinberg, 2000; Leskovec et al., 2005). However, this problem is still challenging for the authors. Most approaches are based on the topological properties of networks like degree, clustering coefficient, path index, etc. The common neighbor approaches are based on the idea “Friends of a friend are also friends,” i.e., a large number of common friends between two persons (nodes) signifies more similarity between them and more likely to be connected. In the resource allocation process, a large number of connections of common neighbors of two nodes are vulnerable for leaking information (resources) through them. Based on this idea, we proposed a new similarity index SHOPI (Link prediction based on S̄ignificance of H̄igher Ōrder P̄ath Īndex) that tries to constrain the information leak through the common neighbors by penalizing them. Moreover, higher-order paths (as defined by six degrees of separation) are used as discriminating features with penalizing the longer paths available between the seed node pair. The experimental results on twelve real-world network datasets (collected from diverse areas) show that SHOPI outperforms the baseline methods. Moreover, SHOPI is more robust than the existing Katz index and comparable to the local path index (LP). The statistical test shows the significant difference of the proposed method (i.e., SHOPI) with the baseline approaches.

Keywords: Link prediction; Path similarity index; Similarity measures; Complex network (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437119321107
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

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:eee:phsmap:v:545:y:2020:i:c:s0378437119321107

DOI: 10.1016/j.physa.2019.123790

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().