Zufallspfade

Ein Zufallspfad ist ein Pfad in einem Netzwerk oder Graphen mit zufälligem Verlauf. Dabei wird von einem zufälligen Knoten begonnen und in jedem Schritt eine zufällige Kante zur Fortsetzung des Pfades ausgewählt. 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. Zufallspfade sind unter anderem Gegenstand der Netzwerktheorie und Graphentheorie.

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.

  Andreas Schnederle vor 7248 Tagen