Analysis of node2vec random walks on networks
arXiv:2006.04904 · doi:10.1098/rspa.2020.0447
Abstract
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 analyze 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 analyze 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 back-tracking and visiting a neighbor of the previously visited node but do not avoid them completely.
arXiv comment9 figures, 2 tables
References in corpus (19)
- Finding community structure in networks using the eigenvectors of matrices
- Multilayer Networks
- The structure and dynamics of multilayer networks
- Graph Embedding Techniques, Applications, and Performance: A Survey
- Self-similar community structure in organisations
- Community Structure in Jazz
- Diffusion dynamics on multiplex networks
- Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
- Random walks and diffusion on networks
- Memory in network flows and its effects on spreading dynamics and community detection
- Voter Models on Heterogeneous Networks
- Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
- Random Walks: A Review of Algorithms and Applications
- Evolutionary dynamics on degree-heterogeneous graphs
- Non-backtracking random walks mix faster
- Voter model on the two-clique graph
- Non-backtracking random walk
- Analysis of node2vec random walks on networks
- Random Walks on Complex Networks