An Ensemble Approach to Link Prediction

Liang Duan, Shuai Ma, Charu Aggarwal, T. Ma, J. Huai

Research output: Contribution to journalArticlepeer-review

Abstract

A network with n nodes contains O(n2) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Further, even though link prediction is closely related to missing value estimation problems, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity on large networks. Hence, most known link prediction methods are designed for evaluating the link propensity on a specified subset of links, rather than on the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this article, we propose an ensemble enabled approach to scaling up link prediction, by decomposing traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with latent factor models, which can be effectively implemented on networks of modest size. By incorporating with the characteristics of link prediction, the ensemble approach further reduces the sizes of subproblems without sacrificing its prediction accuracy. The ensemble enabled approach has several advantages in terms of performance, and our experimental results demonstrate the effectiveness and scalability of our approach.
Original languageEnglish
Pages (from-to)2402-2416
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume29
Issue number11
Early online date21 Jul 2017
DOIs
Publication statusPublished - 1 Nov 2017

Keywords

  • computational complexity
  • network theory (graphs)
  • O
  • ensemble enabled approach
  • entire networks
  • known link prediction methods
  • link propensity
  • modest size
  • prediction accuracy
  • traditional link prediction problems
  • Algorithm design and analysis
  • Collaboration
  • Estimation
  • Prediction algorithms
  • Predictive models
  • Social network services
  • Link prediction
  • NMF
  • big data
  • ensembles
  • social networks

Fingerprint

Dive into the research topics of 'An Ensemble Approach to Link Prediction'. Together they form a unique fingerprint.

Cite this