Has this model of random directed graphs been studied?

Question

Youtube recently added a feature called autoplay, where each clip is assigned a (presumably related) clip that follows it. This, in effect, defines a directed graph on the set of youtube clips, where each vertex has outdegree 1. The user starts at a vertex of his choice and takes a walk along this graph.

This got me thinking. Since the graph is finite, the user will eventually get stuck in a loop. Each loop acts as a sink, and each vertex will eventually lead the user to some sink. This raises some questions - how many sinks are there? How many steps does it take before the user reaches the loop? What is the distribution of the sink sizes? And so on.

Here is a random graph model that can be used to model this process: For each vertex $v$ we choose a single neighbor $w$ uniformly at random and add the edge $(v,w)$ to the graph. It might be interesting to investigate the properties of this model and to see if they can teach us anything about the Youtube network. Have people looked at this type of thing before?

Answer 1

this may be a bit unexpected but yes, this has been studied in at least one particular context: PRNGs. a PRNG can be visualized as a directed graph, specifically a functional graph (all vertices, single outdegree) of "current value, next value". however most PRNGs are designed to have a single very long cycle. there is some analysis of PRNGs with multiple embedded cycles. eg:

• Chaotic Random Number Generators with Random Cycle Lengths / Fog

there is also some theory on cycle detection eg the Tortoise/ Hare and Brents algorithm. did not find other contexts where "random" functional graphs are studied. note your definition did not ensure that vertices are connected, not sure if that is what you intended. there would be some theory about how many edges would have to be placed before separate disconnected graphs become connected. Erdos did studies in this area with undirected graphs on Erdos-Renyi model and its famous as being one of the early discoveries of phase transitions in discrete math theory. the random functional graphs you describe could be regarded as a specialized version of Erdos Renyi model.

Answer 2

It is very easy to say something about the expected length before you get stuck in a loop: if there are $n$ videos, it will (starting from a random video) take in expectation $\Theta(\sqrt{n})$ videos before you loop around (the actual value is around $1.25\sqrt{n}$). This is effectively the birthday problem, since each time you draw a video at random.

Since each video in the chain of $\Theta(\sqrt{n})$ videos is equally likely to be the one you loop back to, the average length of a loop is also $\Theta(\sqrt{n})$ videos (actual value $0.625\sqrt{n}$).

This gives the expected length of the loop you end up in after starting from a random video. This means that a loop with many videos leading to it is counted more strongly. If instead you want to know the expected length of a loop if you pick a random loop, this may be found as $T(1)$, where

$$T(i)=\frac{n-i}{n}T(i+1)+\frac{i}{n}\frac{i+1}{2}$$

and $T(n)=\frac{n+1}{2}$. Computing the values of $T$ experimentally it seems to match up with $0.625\sqrt{n}$, so both ways of counting the expected loop length are the same.

Computing the expected number of cycles seems to be a harder problem. We start by counting the expected number of cycles of a given length. The probably that a node is part of a length-1 cycle is $\frac{1}{n}$, so there are in expectation $1$ length-1 cycles. The probability that a node is in a length-2 cycle is $\frac{n-1}{n}\frac{1}{n}$, so there are in expectation $\frac{1}{2}\frac{n-1}{n}$ length-2 cycles. In general, the number of cycles of length $l$ is $\frac{1}{l}\Pi_{i=1}^{l-1} \frac{n-i}{n}$.

We can obtain a crude upper bound on the number of cycles by considering $\Sigma_{i=1}^n \frac{1}{i} = H_n$ which is $O(\log n)$. Unfortunately the number of cycles doesn't seem to converge to $\log n$ so this bound is not tight.