# What is the distribution of a “one-step random walk” on a random graph?

I was playing a bit with random graphs and I got a question that I couldn't find in a text book (I am not claiming it is not solved in some textbook by the way).

Let's fix a distribution for the degrees of random graphs and a natural number $N$. Then consider the set of all graphs with $N$ vertices, whose degrees follow the distribution we chose. We choose one graph $g$ from this set uniformly at random.

My question is the following. We choose a node $n_0$ uniformly at random. Then we choose one edge $e$ among of its edges uniformly at random. Then we get the node $n_1$ that this edge connects to. What is the distribution of $n_1$?

Initially I thought that $n_1$ is uniformly distributed, but then I realized that that nodes with high degree have bigger probabilities to connect to $e$.

Is this distribution known?

• It seems like the fact that you're starting with a random graph is irrelevant to the question. Do you just want to know how to compute this distribution given an arbitrary graph? – Misha Lavrov Mar 24 '18 at 2:31
• @MishaLavrov you are right, my question was not clear. I think now I am asking the correct question. – tst Mar 24 '18 at 13:59

## 2 Answers

The set of all graphs with a given degree sequence is an awkward set to consider, and we can't say very much about a uniformly random graph drawn from this set exactly. But if all the degrees are relatively small, then we can get a very good approximation.

Consider the configuration model, which produces a random multigraph with a given degree sequence. Here, we start out by giving each vertex which should have degree $d$ a total of $d$ "half-edges". Then we pick a uniformly random pairing of all the half-edges, and turn every pair of half-edges that got paired together into an edge.

In this model, your question is much easier to answer. Whatever the vertex $n_0$ we choose, if it has degree at least $1$, it has some half-edge going out of it, so our one-step walk takes a half-edge. (It doesn't matter which one.) That half-edge is going to be paired with a uniformly random half-edge, which determines where the one-step walk ends.

Technically, it's a uniformly random half-edge different from the one we started, but assuming that there are lots of vertices it is not a bad approximation to say that it's just a uniformly random half-edge. (If all vertices have degree at least $1$, there are at least $n$ half-edges, so this is an approximation up to a relative error of $\frac1n$ or better.)

Picking a uniformly random half-edge corresponds to picking a random vertex with probability proportional to its degree, so that's the distribution of $n_1$.

This was an approximation for two reasons: first, due to the relative error of $\frac1n$ mentioned above, and second, because the configuration model does not necessarily produce a simple graph. If two half-edges out of the same vertex are paired together, it produces a loop, and if two pairs of half-edges between the same two vertices are paired together, it produces two parallel edges.

If the average squared degree is constant (as a function of $n$), then the expected number of loops is constant; parallel edges are even more rare. In such a setting, there is a pretty good chance of the configuration model giving us a simple graph, and the behavior of a few specific edges doesn't affect this probability too much. So the probability for random graphs following this degree sequence is going to be about the same.

It might be possible to extend my analysis somewhat further. But for an extreme example where this doesn't work out, consider the degree sequence $n-1,1,1,1,\dots,1,1$. There are many multigraphs with this degree sequence, but only one graph: the star. So choosing a uniformly random $n_0$ and then going to its neighbor gives us the vertex with degree $n-1$ with probability $1 - \frac1n$, as opposed to the probability $\frac12$ we'd see in a random multigraph with this degree sequence.

Given a graph with no isolated nodes (what would you do if a node had no neighbors?), fix an order of its nodes and construct the weighted adjacency matrix

$$A_{ij} \equiv \begin{cases}\frac{1}{\deg_i}&\text{if }i\text{ neighbors j}\\0&\text{otherwise}\end{cases}$$

Let $[p_1,\ldots,p_n]^T$ be a vector containing the initial probability of choosing each node.

Then $A\cdot p$ is the probability distribution you're looking for, and I don't believe there's a more expressive formula for this without knowing something about the degrees in your graph.

In general, $$\Pr(x) = \sum_{y\text{ neighbors }x} \frac{p_y}{\deg(y)}.$$

• This is useful, but in the meantime I realized I was not asking the question I meant to ask. Could you please take a look again? – tst Mar 24 '18 at 14:00