Anzahl unterschiedlicher Knoten in einer zufälligen Wanderung

22

Die Pendelzeit in einem zusammenhängenden Graphen ist definiert als die erwartete Anzahl von Schritten in einem zufälligen Gang, der bei i beginnt , bevor der Knoten j besucht und dann der Knoten i wieder erreicht wird. Es ist im Grunde die Summe der beiden Schlagzeiten H ( i , j ) und H ( j , i ) .G=(V,E)ijiH(i,j)H(j,i)

Gibt es etwas, das der Pendelzeit ähnlich ist (nicht genau dasselbe), aber in Bezug auf Knoten definiert ist? Mit anderen Worten, was ist die erwartete Anzahl unterschiedlicher Knoten, die ein zufälliger Spaziergang von bis zu meiner Rückkehr von i besuchen wird?ii

Update (30. September 2012): Es gibt eine Reihe verwandter Arbeiten zur Anzahl der verschiedenen Orte, die von einem zufälligen Wanderer auf einem Gitter besucht wurden (dh ). Siehe zum Beispiel: http://jmp.aip.org/resource/1/jmapaq/v4/i9/p1191_s1?isAuthorized=noZn

Hat jemand schon mal was dazu gelesen?

Fabrizio Silvestri
quelle
Was ist das Problem mit dem folgenden Argument? Eine zufällige Bewegung in einem Graphen kann durch eine Markov-Kette beschrieben werden, bei der die Zustände die Knoten sind. Ebenso kann man den gleichen Weg durch eine Markov-Kette darstellen, wobei die Zustände die Kanten sein können. (Jede Kante enthält auch die aktuell besuchten Knoteninformationen.) Sobald eine Markov-Kette erhalten wurde, können Sie eine beliebige Definition / ein beliebiges Ergebnis von Markov-Ketten verwenden.
Abuzer Yakaryilmaz
Danke für den Kommentar. Ich habe eigentlich vergessen, verschiedene Knoten zu sagen . Ich werde die Frage jetzt ändern.
Fabrizio Silvestri
Vielleicht habe ich es verpasst (tut mir leid, wenn ja), aber wie lautet die URL zum SE-Beitrag?
Ich habe den SE-Beitrag entfernt ... Es ist verboten, die gleiche Frage an zwei verschiedenen Stellen zu posten.
Fabrizio Silvestri
es kommt auf die jeweilige Grafik an, oder? Können Sie etwas skizzieren, das über ähnliche Probleme bekannt ist?
VZN

Antworten:

4

Anhand der Fragen und Antworten in den Kommentaren scheinen Sie daran interessiert zu sein, etwas zu untersuchen, das als Stapelabstand in dieser Reihe von Folien definiert ist: Zur mathematischen Modellierung von Caches

Definieren Sie den Stapelabstand einer Referenz als die Anzahl der eindeutigen Blockadressen zwischen der aktuellen Referenz und der vorherigen Referenz auf dieselbe Blocknummer.

Es hat einige empirische Analysen über Benchmarks. es heißt im Allgemeinen, dass es "keine bekannte Messung der Lokalität" von Cache-Anforderungen gibt, und schlägt dann die Stapelentfernung als eine solche Maßnahme vor. Es bezieht sich nicht auf die Zufallsgraphentheorie, obwohl Sie in Ihren Kommentaren einen solchen Zusammenhang skizzieren. (Es scheint, als könnte die Stapelentfernung mit dem Mischen der Markov-Kette zusammenhängen ?)

Es scheint, dass Sie daran interessiert sind, die Cache-Leistung oder Optimierungsalgorithmen zu modellieren, indem Sie Cache-Anforderungen als Knoten eines Diagramms und die Kanten als Übergänge zwischen benachbarten Anforderungen betrachten. Ich habe noch keine Artikel gesehen, die die Struktur dieses Graphen untersuchen. Aufgrund des Erfolgs von Caches in der Praxis und der in den obigen Folien als räumlich und zeitlich bezeichneten Lokalität scheint es sich nachweislich nicht um einen rein zufälligen Graphen zu handeln . dh eine Art "Clustering", wie Joe in seiner Antwort skizziert.

(Vielleicht hat es eine kleine Weltstruktur ?, die in realen Daten allgegenwärtig ist.)

vzn
quelle
Schöner Fang. In der Tat hat es eine kleine Weltstruktur. In der Tat, in der Anwendung, die ich im Auge habe, folgt die Gradverteilung einem Potenzgesetz. Nun, das kann helfen ... Trotzdem haben wir keinen guten Weg gefunden :)
Fabrizio Silvestri
Danke. Welchen Caching-Parameter möchten Sie optimieren? scheint es wahrscheinlich, dass es irgendwie direkt mit dem Potenzgesetz-Exponenten korreliert ...? vermuten, dass einfache Monte-Carlo-Ansätze zeigen könnten, dass die
Stapelentfernung
αα=1,<1,>1
Es scheint, als wäre die Stapelentfernung nicht direkt in der Graphentheorie untersucht worden, aber es ist ein weites Feld. Beachten Sie, dass das Watt / Strogatz- Modell gut für Monte-Carlo-Ansätze geeignet ist, die kleine Weltgraphen erzeugen. Auch zufällige Spaziergänge auf einem Graphen von Lovasz sind eine gute Übersicht über die Theorie der Spaziergänge auf zufälligen Graphen.
VZN
4

Ein Kommentar: Ich habe kürzlich an einem Vortrag von Bruce Reed mit dem Titel Catching a Drunk Miscreant teilgenommen , der eine gemeinsame Arbeit mit Natasha Komorov und Peter Winkler war. Wenn Sie sich über die Ergebnisse dieser Arbeit informieren können, hilft Ihnen das möglicherweise in eine Richtung.

Im Allgemeinen beweisen sie eine Obergrenze für die Anzahl der Schritte, die ein Cop in einem allgemeinen Graphen benötigt, um einen Räuber fangen zu können, wenn wir wissen, dass sich der Räuber willkürlich entlang der Ränder bewegt.

Pål GD
quelle
Gibt es eine Möglichkeit, einen Entwurf oder eine Kopie der Folien zu haben?
Fabrizio Silvestri
2
Es tut mir leid, dass ich nicht mehr zu geben habe, aber vielleicht ist dieser MO-Thread eine Hilfe: Polizisten und betrunkene Räuber .
Pål GD
Danke Pål ... Ich schaue mir das vom MO-Thread verlinkte Papier an.
Fabrizio Silvestri
3

Dies ist keine richtige Antwort auf Ihre Frage, aber für einen Kommentar etwas zu lang.

Die Menge, nach der Sie suchen, variiert von Diagramm zu Diagramm und hängt von der ursprünglichen Position des Gehers ab. Die erwartete Anzahl unterschiedlicher Zwischenknoten hängt stark von der Clusterbildung im Diagramm ab, und ich würde erwarten, dass die erwartete Anzahl unterschiedlicher Zwischenknoten mit dem Clusterbildungskoeffizienten korreliert .

Ein Cluster ist im Grunde eine Untergruppe von Scheitelpunkten, die eine große Anzahl von Kanten gemeinsam haben, so dass jeder Scheitelpunkt mit einem großen Bruchteil der anderen Scheitelpunkte innerhalb des Clusters verbunden ist. Wenn ein Walker einen Cluster betritt, bleibt er wahrscheinlich für eine große Anzahl von Hops in dieser Region und besucht möglicherweise jeden Knoten mehrmals. In der Tat ist die Verwendung von Zufallsläufen auf diese Weise eine der Berechnungstechniken, die zum Identifizieren von Clustern in großen Graphen verwendet werden. Somit wird für einen Wanderer, der in einem Cluster startet, die erwartete Anzahl unterschiedlicher Zwischenscheitelpunkte wahrscheinlich mit der Größe des Clusters und der durchschnittlichen Wahrscheinlichkeit, den Cluster zu verlassen, skaliert.

N1NN+1

Der durchschnittliche Grad der Eckpunkte innerhalb des Diagramms spielt ebenfalls eine wichtige Rolle, obwohl dies mit der Clusterbildung zusammenhängt. Der Grund dafür ist, dass der Wanderer, wenn er auf einen Scheitelpunkt mit Grad 1 springt, beim nächsten Sprung zum vorherigen Scheitelpunkt zurückspringen muss. Selbst wenn der Grad 2 ist, gibt es nur einen Pfad, der durch den Graphen geführt werden kann, obwohl er bei jedem Sprung in beide Richtungen durchlaufen werden kann. Auf der anderen Seite kann bei Graphen mit einem Grad über 2 die Anzahl der Pfade explodieren, was es äußerst unwahrscheinlich macht, zur ursprünglichen Stelle zurückzukehren, selbst wenn der kürzeste Pfad dazwischen klein ist.

Daher würde man erwarten, dass die Anzahl der unterschiedlichen Zwischenscheitelpunkte für Diagramme hoch ist, die beide einen Durchschnittsgrad von deutlich über 2 aufweisen und auch keine signifikante Häufung aufweisen, wie z. B. Bäume.

Natürlich gelten diese Kommentare nicht mehr für Quanten-Random-Walks, aber ich denke, Sie interessieren sich nur für den klassischen Fall.

Joe Fitzsimons
quelle