TY - JOUR

T1 - Analysis of node2vec random walks on networks

T2 - Node2vec random walks on networks

AU - Meng, Lingqi

AU - Masuda, Naoki

N1 - Funding Information:
Data accessibility. The empirical network datasets are open resources and available at [21–26]. The Python codes used in the present study are available on Github [47]. Authors’ contributions. N.M. conceived and designed the research; L.M. and N.M. carried out the mathematical analysis; L.M. performed the computational experiment; L.M. and N.M. wrote the paper. Both authors gave final approval for publication and agree to be held accountable for the work performed therein. Competing interests. We declare we have no competing interests. Funding. N.M. acknowledges the support provided through AFOSR European Office grant no. FA9550-19-1-7024.
Funding Information:
N.M. acknowledges the support provided through AFOSR European Officegrant no. FA9550-19-1-7024.
Publisher Copyright:
© 2020 The Author(s).

PY - 2020

Y1 - 2020

N2 - Random walks have been proven to be useful for constructing various algorithms to gain information on networks. Algorithm node2vec employs biased random walks to realize embeddings of nodes into low-dimensional spaces, which can then be used for tasks such as multi-label classification and link prediction. The performance of the node2vec algorithm in these applications is considered to depend on properties of random walks that the algorithm uses. In the present study, we theoretically and numerically analyse random walks used by the node2vec. Those random walks are second-order Markov chains. We exploit the mapping of its transition rule to a transition probability matrix among directed edges to analyse the stationary probability, relaxation times in terms of the spectral gap of the transition probability matrix, and coalescence time. In particular, we show that node2vec random walk accelerates diffusion when walkers are designed to avoid both backtracking and visiting a neighbour of the previously visited node but do not avoid them completely.

AB - Random walks have been proven to be useful for constructing various algorithms to gain information on networks. Algorithm node2vec employs biased random walks to realize embeddings of nodes into low-dimensional spaces, which can then be used for tasks such as multi-label classification and link prediction. The performance of the node2vec algorithm in these applications is considered to depend on properties of random walks that the algorithm uses. In the present study, we theoretically and numerically analyse random walks used by the node2vec. Those random walks are second-order Markov chains. We exploit the mapping of its transition rule to a transition probability matrix among directed edges to analyse the stationary probability, relaxation times in terms of the spectral gap of the transition probability matrix, and coalescence time. In particular, we show that node2vec random walk accelerates diffusion when walkers are designed to avoid both backtracking and visiting a neighbour of the previously visited node but do not avoid them completely.

KW - coalescence time

KW - community structure

KW - diffusion

KW - relaxation time

KW - ring network

KW - second-order Markov chain

UR - http://www.scopus.com/inward/record.url?scp=85097943925&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85097943925&partnerID=8YFLogxK

U2 - 10.1098/rspa.2020.0447

DO - 10.1098/rspa.2020.0447

M3 - Article

AN - SCOPUS:85097943925

SN - 1364-5021

VL - 476

JO - Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences

JF - Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences

IS - 2243

M1 - 0447

ER -