Supervised link prediction using random walks

Yuechang Liu, Hanghang Tong, Lei Xie, Yong Tang

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

2 Scopus citations


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
Number of pages12
ISBN (Print)9789811000799
StatePublished - 2015
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
ISSN (Print)1865-0929


Other4th National Conference on Social Media Processing, SMP 2015

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


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

Cite this