Supervised link prediction using random walks

Yuechang Liu, Hanghang Tong, Lei Xie, Yong Tang

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

Abstract

Network structure has become increasingly popular in bigdata representation over the last few years. As a result, network based analysis techniques are applied to networks containing millions of nodes. Link prediction helps people to uncover the missing or unknown links between nodes in networks, which is an essential task in network analysis. Random walk based methods have shown outstanding performance in such task. However, the primary bottleneck for such methods is adapting to networks with different structure and dynamics, and scaling to the network magnitude. Inspired by Random Walk with Restart (RWR), a promising approach for link prediction, this paper proposes a set of path based features and a supervised learning technique, called Supervised Random Walk with Restart (SRWR) to identify missing links. We show that by using these features, a classifier can successfully order the potential links by their closeness to the query node. A new type of heterogeneous network, called Generalized Bi-relation Netowrk (GBN), is defined in this paper, upon which the novel structural features are introduced. Finally experiments are performed on a disease-chemical-gene interaction network, whose result shows SRWR significantly outperforms standard RWR algorithm in terms of the Area Under ROC Curve (AUC) gained and better than or equal to the best algorithms in the field of gene prioritization.

Original languageEnglish (US)
Title of host publicationSocial Media Processing - 4th National Conference, SMP 2015, Proceedings
EditorsMaosong Sun, Xichun Zhang, Zhenyu Wang, Xuanjing Huang
PublisherSpringer-Verlag Berlin Heidelberg
Pages107-118
Number of pages12
ISBN (Print)9789811000799
DOIs
StatePublished - Jan 1 2015
Externally publishedYes
Event4th National Conference on Social Media Processing, SMP 2015 - Guangzhou, China
Duration: Nov 16 2015Nov 17 2015

Publication series

NameCommunications in Computer and Information Science
Volume568
ISSN (Print)1865-0929

Conference

Conference4th National Conference on Social Media Processing, SMP 2015
CountryChina
CityGuangzhou
Period11/16/1511/17/15

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Supervised link prediction using random walks'. Together they form a unique fingerprint.

  • Cite this

    Liu, Y., Tong, H., Xie, L., & Tang, Y. (2015). Supervised link prediction using random walks. In M. Sun, X. Zhang, Z. Wang, & X. Huang (Eds.), Social Media Processing - 4th National Conference, SMP 2015, Proceedings (pp. 107-118). (Communications in Computer and Information Science; Vol. 568). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-981-10-0080-5_10