Link prediction by exploiting network formation games in exchangeable graphs

Liqiang Wang, Yafang Wang, Bin Liu, Lirong He, Shijun Liu, Gerard De Melo, Zenglin Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

In social network analysis, we often need to predict new links, given some available evidence. This may, for instance, enable us to study user behavior and infer likely new interactions in the near future. Recently, a family of algorithms based on exchangeable graphs has proven effective for link prediction. The network is modeled as an exchangeable array, whose entries can flexibly be traced back to random function priors (e.g., block models, Gaussian Processes). Unfortunately, the burdensome computational complexity of these methods inhibit their application to even just moderate-scale networks. In this paper, we present a novel online training algorithm based on local Gaussian processes on subgraphs, which successfully overcomes this challenge. Moreover, we address the sparsity problem of links in social networks by presenting an improved algorithm based on network formation games. The network formation games we design also shed light on the ambiguity of missing links - not observed vs. non-existing. We evaluate our method against state-of-the-art algorithms on real-world datasets, demonstrating both the effectiveness and the efficiency of our method.

Original languageEnglish (US)
Title of host publication2017 International Joint Conference on Neural Networks, IJCNN 2017 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages619-626
Number of pages8
ISBN (Electronic)9781509061815
DOIs
StatePublished - Jun 30 2017
Event2017 International Joint Conference on Neural Networks, IJCNN 2017 - Anchorage, United States
Duration: May 14 2017May 19 2017

Publication series

NameProceedings of the International Joint Conference on Neural Networks
Volume2017-May

Other

Other2017 International Joint Conference on Neural Networks, IJCNN 2017
Country/TerritoryUnited States
CityAnchorage
Period5/14/175/19/17

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence

Keywords

  • Exchangeable graphs
  • Graphical model
  • Link prediction
  • Network formation games

Fingerprint

Dive into the research topics of 'Link prediction by exploiting network formation games in exchangeable graphs'. Together they form a unique fingerprint.

Cite this