Stationary distribution of node2vec random walks on household models
This provides theoretical insights for network embedding algorithms, though it is incremental as it builds on existing node2vec methods.
The paper tackles the problem of understanding the stationary distribution of node2vec random walks on community-structured household model graphs, proving an explicit description of this distribution in terms of walk parameters and showing it can interpolate between uniform, size-biased, or simple random walk distributions.
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.