Definition - Zufallsweg-basierte Ähnlichkeit

• Generalisierungen:
  • Ähnlichkeitsmaß
• Involvierte Definitionen:
  • Graph
  • Random Walk
  • Knoten
• Veranstaltung: DM
• Referenz: @valdes2024 (p. 41)

⠀

Definition: Zufallsweg-basierte Ähnlichkeit

Als Zufallsweg-basierte Ähnlichkeit zwischen zwei Knoten eines ungerichteten Graphen bezeichnen wir ein Maß für die Ähnlichkeit dieser Knoten, das auf der Wahrscheinlichkeit basiert, durch einen Random Walk auf dem Graphen von einem Knoten zum anderen zu gelangen.

Je häufiger ein zufälliger Weg zwischen und auftritt, desto ähnlicher sind die Knoten.

Für den Random Walk gilt:

• Die Wahrscheinlichkeit, einer Kante zu folgen ist proportional zu dem Gewicht der Kante.
• In jedem Schritt besteht mit konstanter Wahrscheinlichkeit die Möglichkeit zu dem Startpunkt (also oder ) zurückzukehren.