imported>Leonry: Umformulierung

2024-06-16T12:28:23Z

Umformulierung

Neue Seite

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

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

Ein ähnliches Verfahren wie Zufallspfade bilden [[Irrfahrt (Stochastik)|Irrfahrten]], die nicht in Graphen, sondern beispielsweise in [[Raum (Mathematik)|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 [[Internet]]s 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 [[Suchmaschine]]n 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 [[Integralrechnung|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: ''[http://www9.org/w9cdrom/88/88.html 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: [[The American Statistician]] 49 (1995), S. 327–335.

[[Kategorie:Graphentheorie]]
[[Kategorie:Stochastischer Prozess]]

Zufallspfad - Versionsgeschichte

imported>Leonry: Umformulierung