Stationary distribution of node2vec random walks on household models

Random walks on graphs have captivated researchers for decades. Beyond their theoretical appeal, random walks serve as a fundamental technique in developing algorithms that extract insights from network data. Examples include community detection, node ranking, dimension reduction, and sampling [8, 6, 21]. Traditionally, many studies have focused on simple random walks, where the walker transitions to a uniformly chosen neighbor at each step. However, several more complex types of random walks have proven to be useful in algorithms related to community detection and learning on networks [12, 1]. For example, the non-backtracking random walk, where nodes are not allowed to walk on the edge they followed in the last step, has proven fundamental to community detection on the stochastic block model [18]. Unlike simple random walks, which induce a Markov chain on the nodes, such random walks form a second-order stochastic process, as they depend on one past state. While second-order processes are more complex to analyze, such walks mix faster [1], and have shown better concentration properties in spectral methods [15]. A second, more recently proposed second-order random walk is the node2vec random walk [12], which contains one parameter that controls the non-backtracking properties of the walker, and a second parameter that controls the likelihood of exploring nodes further from the current node as compared to staying in a close neighborhood.