Pergunta

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?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top