[Solved]: Has this model of random directed graphs been studied?

Problem Detail: 

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?

Asked By : Zur Luria

Answered By : vzn

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44563

3.2K people like this

 Download Related Notes/Documents