Diffusion Speed of the Node2vec Random Walk on Networks

Random walks on networks, which are usually formulated as first-order Markov processes, are a prevailing tool for constructing various stochastic algorithms to obtain information from network data. The node2vec algorithm [1] provides a flexible biased random walk framework for graph machine learning, which can be applied to tasks such as node classification and link prediction. The behavior of node2vec in these applications is contingent on two parameters that control how a random walker explores the entire network. Here, we examine properties of the node2vec random walk both theoretically and numerically. The node2vec random walk can be formulated as a second-order Markov chain, which can be reduced to a first-order Markov chain using the so-called memory network formalism. We exploit this correspondence to write down the transition probability matrix in the state space of directed edges, and then analyze the stationary probability, relaxation speed in terms of the spectral gap of the transition probability matrix, and coalescence time [2]. In particular, we show that node2vec random walk accelerates diffusion when walkers are configured to avoid back-tracking (by making the value of parameter α small) and also avoid visiting neighbors of the previously visited node (by making the value of parameter β small) to a certain degree. We have observed this tendency consistently for different diffusion speed measures (i.e., spectral gap and coalescence time) and across different empirical and model networks (see Fig. 1 for two examples). Finally, we discuss the application of the node2vec random walk to analyses of epidemic processes on networks.

Συνεδρία: 
Authors: 
Lingqi Meng and Naoki Masuda
Room: 
6
Date: 
Tuesday, December 8, 2020 - 17:45 to 18:00

Partners

Twitter

Facebook

Contact

For information please contact :
ccs2020conf@gmail.com