Similarity index based on local paths for link prediction of complex networks

Linyuan Lü, Ci-Hang Jin, and Tao Zhou
Phys. Rev. E 80, 046122 – Published 26 October 2009

Abstract

Predictions of missing links of incomplete networks, such as protein-protein interaction networks or very likely but not yet existent links in evolutionary networks like friendship networks in web society, can be considered as a guideline for further experiments or valuable information for web users. In this paper, we present a local path index to estimate the likelihood of the existence of a link between two nodes. We propose a network model with controllable density and noise strength in generating links, as well as collect data of six real networks. Extensive numerical simulations on both modeled networks and real networks demonstrated the high effectiveness and efficiency of the local path index compared with two well-known and widely used indices: the common neighbors and the Katz index. Indeed, the local path index provides competitively accurate predictions as the Katz index while requires much less CPU time and memory space than the Katz index, which is therefore a strong candidate for potential practical applications in data mining of huge-size networks.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Received 21 May 2009

DOI:https://doi.org/10.1103/PhysRevE.80.046122

©2009 American Physical Society

Authors & Affiliations

Linyuan Lü1, Ci-Hang Jin1, and Tao Zhou1,2,*

  • 1Department of Physics, University of Fribourg, Chemin du Musee 3, Fribourg 1700, Switzerland
  • 2Department of Modern Physics, University of Science and Technology of China, Hefei 230026, People’s Republic of China

  • *zhutou@ustc.edu

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 80, Iss. 4 — October 2009

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×