Second-order random walk-based proximity measures in graph analysis: formulations and algorithms

Yubao Wu, Xiang Zhang, Yuchen Bian, Zhipeng Cai, Xiang Lian, Xueting Liao, Fengpan Zhao

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


Measuring the proximity between different nodes is a fundamental problem in graph analysis. Random walk-based proximity measures have been shown to be effective and widely used. Most existing random walk measures are based on the first-order Markov model, i.e., they assume that the next step of the random surfer only depends on the current node. However, this assumption neither holds in many real-life applications nor captures the clustering structure in the graph. To address the limitation of the existing first-order measures, in this paper, we study the second-order random walk measures, which take the previously visited node into consideration. While the existing first-order measures are built on node-to-node transition probabilities, in the second-order random walk, we need to consider the edge-to-edge transition probabilities. Using incidence matrices, we develop simple and elegant matrix representations for the second-order proximity measures. A desirable property of the developed measures is that they degenerate to their original first-order forms when the effect of the previous step is zero. We further develop Monte Carlo methods to efficiently compute the second-order measures and provide theoretical performance guarantees. Experimental results show that in a variety of applications, the second-order measures can dramatically improve the performance compared to their first-order counterparts.

Original languageEnglish (US)
Pages (from-to)127-152
Number of pages26
JournalVLDB Journal
Issue number1
StatePublished - Feb 1 2018

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Second-order random walk-based proximity measures in graph analysis: formulations and algorithms'. Together they form a unique fingerprint.

Cite this