Stationary distribution of node2vec random walks on household models

원문 초록

The node2vec random walk has proven to be a key tool in network embedding algorithms. These random walks are tuneable, and their transition probabilities depend on the previous visited node and on the triangles containing the current and the previously visited node. Even though these walks are widely used in practice, most mathematical properties of node2vec walks are largely unexplored, including their stationary distribution. We study the node2vec random walk on community-structured household model graphs. We prove an explicit description of the stationary distribution of node2vec walks in terms of the walk parameters. We then show that by tuning the walk parameters, the stationary distribution can interpolate between uniform, size-biased, or the simple random walk stationary distributions, demonstrating the wide range of possible walks. We further explore these effects on some specific graph settings.