Zufallspfad

Ein Zufallspfad ist ein Pfad in einem Netzwerk oder einem Graphen mit zufälligem Verlauf. Dabei wird an einem zufälligen Knoten begonnen und in jedem Schritt eine zufällige Kante zur Fortsetzung des Pfades ausgewählt. Zufallspfade sind u. a. Gegenstand der Netzwerk- und der Graphentheorie.

Die Analyse von Zufallspfaden kann statistische Aussagen über die Struktur eines Netzwerkes liefern. Beispielsweise kann davon ausgegangen werden, dass bei einem Zufallspfad im World Wide Web, bei dem einzelne Webseiten die Knoten und Hyperlinks die Kanten darstellen, Seiten mit einem höheren PageRank mit einer größeren Wahrscheinlichkeit besucht werden.

Ein ähnliches Verfahren wie Zufallspfade bilden Random Walks, die nicht in Graphen, sondern beispielsweise in mathematischen Räumen in Verbindung mit einem Zufallszahlengenerator betrachtet werden können. Dabei wird von einem Startpunkt (in der Regel dem Nullpunkt) ausgegangen und die aktuelle Position im Raum um einen in jedem Schritt zufällig erzeugten Wert verändert.

Anwendung

Zufallspfade können dazu eingesetzt werden, um Informationen über die gesamte Struktur eines Graphen zu gewinnen, ohne alle Knoten und Kanten betrachten zu müssen.

So werden Zufallspfade in der Webometrie dazu eingesetzt, um Aussagen über die Struktur des Internets zu gewinnen und um das Verhalten von Websurfern zu simulieren. Allerdings ist fraglich, ob jeder Link auf einer Webseite mit der gleichen Wahrscheinlichkeit angeklickt wird. Auch die Qualität von Suchmaschinen kann untersucht werden. Ein Problem bei der Erzeugung von Zufallspfaden im Internet besteht darin, eine wirklich zufällig ausgewählte Startseite zu finden.

Zufallspfade können auch aus Sicht der Graphentheorie und Statistik betrachtet werden, um die Beziehungen zwischen speziellen Strukturen von Graphen und Zufallspfaden in diesen Graphen zu klären. Zufallspfade wurden auch eingesetzt, um den Einfluss von Erwartungshaltungen oder übernatürlichen Kräften auf wissenschaftliche Experimente zu untersuchen.

In der Mathematik können Zufallspfade u. a. zur Berechnung von Integralen eingesetzt werden und sind Gegenstand statistischer Untersuchungen (siehe Monte-Carlo-Simulation und Metropolisalgorithmus).

Siehe auch

• Zufallsgraph

Literatur

• Monika R. Henzinger, Allan Heydon, Michael Mitzenmacher, Marc Najork: Measuring index quality using random walks on the Web. In: Proceeding of the eighth international conference on World Wide Web, May 1999, S. 1291–1303
• Henzinger, Heydon, Mitzenmacher, Najork: On near-uniform URL sampling. In: Proceedings of the 9th International World Wide Web Conference, Mai 2000, Computer Networks, 33 (1–6), S. 295–308.
• http://www.princeton.edu/~pear/
• Siddhartha Chib und Edward Greenberg: Understanding the Metropolis–Hastings Algorithm. In: American Statistician, 49, 327–335, 1995