References for "second order" random walk on graphs (used in "node2vec" paper)?

Question

The "word2vec" family of methods provided a great breakthrough in natural language processing. The methods assign to each word a vector in $R^{n}$, such that the "similar" words are assigned vectors close to one another in the space. Later on the concept has been generalized to graph research in machine-learning, where "nearby in some sense" nodes of a graph are assigned "nearby" vectors in $R^{n}$.

"Deepwalk" and "node2vec" are the most popular ones, both of them define "nearby nodes" as nodes co-occuring in some random walks many times.

The "node2vec" considers unusual type of random walk - they call it "biased second order random walk" (the comments are given below).

Question: Have this (or similar) random walks been considered in mathematical literature ? What is known/unknown about them ?

"Biased second order random walk".

That random walk is defined with the help of two parameters p,q - positive real numbers. Random walk is "second order" that means it remembers the previous node (denoted s1). Now assume the current node is "w" . We split nearby nodes in THREE categories:

1. s1 - just the previous node

2. the nodes which are neigbours of BOTH - current node w and previous node s1

3. the other neigbours of current node w, not falling in categories above.

Now we give weights 1/p, 1, 1/q for these categories, so first we sample category according to these weight, and latter choose node uniformly in category.

http://web.stanford.edu/class/cs224w/slides/07-noderepr.pdf

Answer 1

This is nothing but an ordinary Markov chain whose state space is the set of oriented edges of the graph with the transition probabilities determined by the configuration of two adjacent oriented edges (more precisely, whether the distance between the endpoints is 0, 1, or 2). What do you want to know about this chain?