Obciążony spacer losowy na wykresie

W naukach o sieciach obciążone błądzenie losowe po wykresie to proces ścieżki czasowej, w którym ewoluująca zmienna przeskakuje ze swojego obecnego stanu do jednego z różnych potencjalnych nowych stanów; w przeciwieństwie do czystego spaceru losowego , prawdopodobieństwa potencjalnych nowych stanów są nierówne.

Obciążone błądzenie losowe po grafie zapewnia podejście do analizy strukturalnej grafów nieskierowanych w celu wyodrębnienia ich symetrii, gdy sieć jest zbyt złożona lub gdy nie jest wystarczająco duża, aby można ją było analizować metodami statystycznymi . Koncepcja obciążonych błądzenia losowego na wykresie przyciągnęła uwagę wielu badaczy i firm zajmujących się danymi w ciągu ostatniej dekady, zwłaszcza w sieciach transportowych i społecznościowych .

Model

Napisano wiele różnych reprezentacji obciążonych błądzenia losowego na wykresach w oparciu o konkretny cel analizy. Typowa reprezentacja mechanizmu dla grafów nieskierowanych jest następująca:

Na $nieskierowanym$ wykresie chodzik robi krok od bieżącego $i.}$ do $displaystyle i$ Zakładając, że każdy węzeł ma atrybut $}$ prawdopodobieństwo przeskoczenia z węzła do ${\$ jest określone przez:

${\ Displaystyle T_ {ij} ^ {\ alfa} = {\ Frac {\ alfa _ {i} A_ {ij}} {$

gdzie $reprezentuje$${\ Displaystyle i.}$ krawędzi od $_$

$.$ rzeczywistości kroki chodzika są obciążone współczynnikiem, który może się różnić w zależności od węzła

$zależności$ od sieci atrybut różnie interpretować. Może to być sugerowane jako atrakcyjność osoby w sieci społecznościowej , może to być centralność pomiędzy lub nawet może być wyjaśnione jako wewnętrzna cecha węzła. W przypadku uczciwego spaceru losowego na wykresie $.$ jeden dla wszystkich węzłów

W przypadku najkrótszych ścieżek spacery losowe $.$$całkowita$ liczba najkrótszych ścieżek między wszystkimi parami węzłów, które przechodzą W rzeczywistości chodzik preferuje węzły o większej centralności pomiędzy , która jest zdefiniowana poniżej:

${\ Displaystyle C (i) = {\ tfrac {{\ tekst {Całkowita liczba najkrótszych ścieżek przez}} i} {\ text {Całkowita liczba najkrótsze ścieżki}}}}$

Na podstawie powyższego równania czas powrotu do węzła w błądzeniu obciążonym jest określony wzorem:

${\ Displaystyle r_ {i} = {\ Frac {1} {C (i)}}}$

Aplikacje

Istnieje wiele aplikacji wykorzystujących tendencyjne błądzenie losowe po wykresach. Takie aplikacje obejmują kontrolę rozprzestrzeniania się, reklamę produktów w sieciach społecznościowych , wyjaśnianie rozproszenia i redystrybucji populacji zwierząt i mikroorganizmów, wykrywanie społeczności, sieci bezprzewodowe i wyszukiwarki.

Zobacz też

• Centralność pomiędzy
• Struktura społeczności
• Dywergencja Kullbacka – Leiblera
• łańcuch Markowa
• Błądzenie losowe z maksymalną entropią
• Centralna bliskość losowego spaceru
• Analiza sieci społecznościowych
• Problem komiwojażera

Linki zewnętrzne

• Gábor Simonyi, „Entropia wykresu: ankieta” . W optymalizacji kombinatorycznej (red. W. Cook, L. Lovász i P. Seymour). Providence, RI: Amer. Matematyka Soc., s. 399–441, 1995.
• Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Trédan, „Ocena jakości topologii sieci poprzez losowe spacery” w Gadi Taubenfeld (red.) Obliczenia rozproszone