Back
pdf
Journal article

+ 1 other files

Toward link predictability of complex networks

  • Lü, Linyuan Alibaba Research Center for Complexity Sciences, Alibaba Business College, Hangzhou Normal University, Hangzhou, China
  • Pan, Liming Alibaba Research Center for Complexity Sciences, Alibaba Business College, Hangzhou Normal University, Hangzhou, China - CompleX Lab, Web Sciences Center, University of Electronic Science and Technology of China, Chengdu, China
  • Zhou, Tao CompleX Lab, Web Sciences Center, University of Electronic Science and Technology of China, Chengdu, China - Big Data Research Center, University of Electronic Science and Technology of China, Chengdu, China
  • Zhang, Yi-Cheng Alibaba Research Center for Complexity Sciences, Alibaba Business College, Hangzhou Normal University, Hangzhou, China - Department of Physics, University of Fribourg, Switzerland
  • Stanley, H. Eugene Alibaba Research Center for Complexity Sciences, Alibaba Business College, Hangzhou Normal University, Hangzhou, China - Department of Physics and Center for Polymer Studies, Boston University, Boston, USA
    24.02.2015
Published in:
  • Proceedings of the National Academy of Sciences. - 2015, vol. 112, no. 8, p. 2325–2330
Link prediction
Complex networks
Structural perturbation
Predictability
English The organization of real networks usually embodies both regularities and irregularities, and, in principle, the former can be modeled. The extent to which the formation of a network can be explained coincides with our ability to predict missing links. To understand network organization, we should be able to estimate link predictability. We assume that the regularity of a network is reflected in the consistency of structural features before and after a random removal of a small set of links. Based on the perturbation of the adjacency matrix, we propose a universal structural consistency index that is free of prior knowledge of network organization. Extensive experiments on disparate real-world networks demonstrate that (i) structural consistency is a good estimation of link predictability and (ii) a derivative algorithm outperforms state-of-the-art link prediction methods in both accuracy and robustness. This analysis has further applications in evaluating link prediction algorithms and monitoring sudden changes in evolving network mechanisms. It will provide unique fundamental insights into the above-mentioned academic research fields, and will foster the development of advanced information filtering technologies of interest to information technology practitioners.
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/304332
Other files
Supplementary material
Supplementary material
Statistics
Document views: 136 File downloads:
  • pdf: 226
  • Supplementary material: 141