Analysis of node2vec random walks on networks.

Area of Science:

• Network science
• Computer science
• Algorithm analysis

Background:

• Random walks are fundamental to network analysis algorithms.
• Node2vec uses biased random walks for network node embeddings, crucial for classification and link prediction.
• The efficiency of node2vec is linked to the properties of its underlying random walks.

Purpose of the Study:

• To theoretically and numerically analyze the random walks employed by the node2vec algorithm.
• To understand how specific random walk properties influence network embedding performance.

Main Methods:

• Modeling node2vec random walks as second-order Markov chains.
• Mapping transition rules to a transition probability matrix for directed edges.
• Analyzing stationary probability, spectral gap, and coalescence time.

Main Results:

• Demonstrated that node2vec random walks are second-order Markov chains.
• Showed that avoiding backtracking and previously visited neighbors accelerates diffusion.
• Identified specific conditions under which diffusion is accelerated.

Conclusions:

• The analysis provides theoretical and numerical insights into node2vec's random walk mechanism.
• Optimizing random walk strategies, like controlled avoidance of revisiting nodes, can enhance network embedding quality.
• Findings contribute to a deeper understanding of random walk dynamics in network algorithms.