  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.
