Wurde dieses Modell von zufällig gerichteten Graphen untersucht?

Youtube hat kürzlich eine Funktion namens Autoplay hinzugefügt, bei der jedem Clip ein (vermutlich verwandter) Clip zugewiesen wird, der darauf folgt. Dies definiert praktisch ein gerichtetes Diagramm auf dem Satz von Youtube-Clips, wobei jeder Scheitelpunkt einen Grad 1 hat. Der Benutzer beginnt an einem Scheitelpunkt seiner Wahl und macht einen Spaziergang entlang dieses Diagramms.

Das brachte mich zum Nachdenken. Da der Graph endlich ist, bleibt der Benutzer schließlich in einer Schleife stecken. Jede Schleife fungiert als Senke, und jeder Scheitelpunkt führt den Benutzer schließlich zu einer Senke. Dies wirft einige Fragen auf - wie viele Waschbecken gibt es? Wie viele Schritte dauert es, bis der Benutzer die Schleife erreicht? Wie ist die Verteilung der Spülengrößen? Und so weiter.

Hier ist ein Zufallsgraphenmodell, mit dem dieser Prozess modelliert werden kann: Für jeden Scheitelpunkt wählen wir einen einzelnen Nachbarn gleichmäßig zufällig aus und fügen die Kante zum Graphen hinzu. Es könnte interessant sein, die Eigenschaften dieses Modells zu untersuchen und zu sehen, ob sie uns etwas über das Youtube-Netzwerk beibringen können. Haben sich die Leute so etwas schon einmal angesehen?$v$$w$$(v,w)$

Dies mag etwas unerwartet sein, aber ja, dies wurde in mindestens einem bestimmten Kontext untersucht: PRNGs . Ein PRNG kann als gerichteter Graph dargestellt werden, insbesondere als funktionaler Graph (alle Eckpunkte, einzelner Grad) des "aktuellen Werts, nächster Wert". Die meisten PRNGs sind jedoch so konzipiert, dass sie einen einzigen sehr langen Zyklus haben. Es gibt einige Analysen von PRNGs mit mehreren eingebetteten Zyklen. z.B:

• Chaotische Zufallszahlengeneratoren mit zufälligen Zykluslängen / Nebel

Es gibt auch eine Theorie zur Zykluserkennung, z. B. den Tortoise / Hare and Brents-Algorithmus. habe keine anderen Kontexte gefunden, in denen "zufällige" Funktionsgraphen untersucht werden. Beachten Sie, dass Ihre Definition nicht sichergestellt hat, dass Scheitelpunkte verbunden sind. Sie sind sich nicht sicher, ob dies beabsichtigt ist. Es würde eine Theorie darüber geben, wie viele Kanten platziert werden müssten, bevor separate getrennte Graphen verbunden werden. Erdos hat in diesem Bereich Studien mit ungerichteten Graphen nach dem Erdos-Renyi-Modell durchgeführt, das als eine der frühen Entdeckungen von Phasenübergängen in der diskreten Mathematiktheorie bekannt ist. Die von Ihnen beschriebenen zufälligen Funktionsgraphen können als spezielle Version des Erdos Renyi- Modells angesehen werden.

Es ist sehr einfach, etwas über die erwartete Länge zu sagen, bevor Sie in einer Schleife stecken bleiben: wenn ja $n$ Videos wird es (ausgehend von einem zufälligen Video) in Erwartung aufnehmen $\Theta(\sqrt{n})$ Videos, bevor Sie herumschleifen (der tatsächliche Wert ist herum $1.25\sqrt{n}$). Dies ist effektiv das Geburtstagsproblem, da jedes Mal, wenn Sie ein Video zufällig zeichnen.

Da jedes Video in der Kette von $\Theta(\sqrt{n})$ Videos sind wahrscheinlich auch die, zu denen Sie zurückkehren, und die durchschnittliche Länge einer Schleife beträgt ebenfalls $\Theta(\sqrt{n})$ Videos (tatsächlicher Wert $0.625\sqrt{n}$).

Dies gibt die erwartete Länge der Schleife an, in der Sie nach dem Start eines zufälligen Videos enden. Dies bedeutet, dass eine Schleife mit vielen dazu führenden Videos stärker gezählt wird. Wenn Sie stattdessen die erwartete Länge einer Schleife wissen möchten, wenn Sie eine zufällige Schleife auswählen, kann dies als gefunden werden$T(1)$, wo

und $T(n)=\frac{n+1}{2}$. Berechnung der Werte von$T$ experimentell scheint es zu passen $0.625\sqrt{n}$Daher sind beide Arten der Zählung der erwarteten Schleifenlänge gleich.

Die Berechnung der erwarteten Anzahl von Zyklen scheint ein schwierigeres Problem zu sein. Wir beginnen mit dem Zählen der erwarteten Anzahl von Zyklen einer bestimmten Länge. Die wahrscheinlich, dass ein Knoten Teil eines Zyklus der Länge 1 ist, ist$\frac{1}{n}$, also gibt es in Erwartung $1$Länge-1-Zyklen. Die Wahrscheinlichkeit, dass sich ein Knoten in einem Zyklus der Länge 2 befindet, beträgt$\frac{n-1}{n}\frac{1}{n}$, also gibt es in Erwartung $\frac{1}{2}\frac{n-1}{n}$Länge-2 Zyklen. Im Allgemeinen die Anzahl der Längenzyklen$l$ ist $\frac{1}{l}\Pi_{i=1}^{l-1} \frac{n-i}{n}$.

Wir können eine grobe Obergrenze für die Anzahl der Zyklen erhalten, indem wir berücksichtigen $\Sigma_{i=1}^n \frac{1}{i} = H_n$ welches ist $O(\log n)$. Leider scheint die Anzahl der Zyklen nicht zu konvergieren$\log n$ Diese Grenze ist also nicht fest.