Back
pdf
Journal article

Uncovering missing links with cold ends

  • Zhu, Yu-Xiao Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China
  • Lü, Linyuan Institution of Information Economy, HangZhou Normal University, China - Department of Physics, University of Fribourg, Switzerland
  • Zhang, Qian-Ming Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China
  • Zhou, Tao Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China - Beijing Computational Science Research Center, China
Show more…
    09.06.2012
Published in:
  • Physica A: Statistical Mechanics and its Applications. - 2012, vol. 139, no. 22, p. 5769–5778
Complex networks
Link prediction
Cold ends
Sampling methods
English To evaluate the performance of prediction of missing links, the known data are randomly divided into two parts, the training set and the probe set. We argue that this straightforward and standard method may lead to terrible bias, since in real biological and information networks, missing links are more likely to be links connecting low-degree nodes. We therefore study how to uncover missing links with low-degree nodes, namely links in the probe set are of lower degree products than a random sampling. Experimental analysis on ten local similarity indices and four disparate real networks reveals a surprising result that the Leicht–Holme–Newman index [E.A. Leicht, P. Holme, M.E.J. Newman, Vertex similarity in networks, Phys. Rev. E 73 (2006) 026120] performs the best, although it was known to be one of the worst indices if the probe set is a random sampling of all links. We further propose an parameter-dependent index, which considerably improves the prediction accuracy. Finally, we show the relevance of the proposed index to three real sampling methods: acquaintance sampling, random-walk sampling and path-based sampling.
Faculty
Faculté des sciences et de médecine
Department
Département de Physique
Language
  • English
Classification
Physics
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/302696
Statistics
Document views: 21 File downloads:
  • lu_uml.pdf: 37