Średnia długość ścieżek st (prostych) na skierowanym wykresie

Biorąc pod uwagę fakt, że wyliczenie ścieżki - jest problemem # P-zupełnym, czy mogłyby istnieć wydajne metody obliczające (lub przynajmniej przybliżające) średnią długość ścieżki - bez ich wyliczania? ~~Co jeśli ścieżki mogą ponownie odwiedzać wierzchołki?~~ $s$ $t$ $s$ $t$

Pomocne mogą być również odpowiednie wyniki na specjalnych wykresach.

— Liuyu
źródło

Jeśli dozwolone jest ponowne odwiedzanie wierzchołków przez ścieżki, wówczas nie prosta ścieżka sugeruje, że nie ma średniej długości, ponieważ długość będzie miała tendencję do nieskończoności.

s - t

$s-t$

— Shaull

@Shaull, masz rację. Myślałem o czasie uderzenia przypadkowego spaceru od do . Ale średnia długość ma tendencję do nieskończoności bez dalszych ograniczeń.

s

$s$

t

$t$

— liuyu

wydaje się to bardzo zaawansowane, zalecamy migrację do cstheory

— dniu

Jeśli dobrze rozumiem, to pytanie może zainteresować Cię w przypadku specjalnego wykresu.

— Juho,

wygląda na to, że może to być związane z maksymalnym przepływem sieci? zwróć również uwagę na małe wykresy świata i różne inne wykresy z pewną symetrią, będzie dążyć do średniej długości ścieżki . dość naturalnym algorytmem może być losowe próbkowanie najkrótszych ścieżek - i spojrzenie na odchylenie standardowe wyników.

s

$s$

t

$t$

— dniu

obliczanie / szacowanie / przybliżanie średniej długości ścieżki zostało zbadane dla niektórych modeli grafów losowych, w tym modelu Erdosa-Renyi i sieci wolnych w skali Barabasi-Alberta, a także małych wykresów światowych Strogatz, które mogą być odpowiednie jako przybliżenia dla twoich wykresów. [byłoby lepiej, gdybyś mógł zawęzić / uszczegółowić niektóre cechy charakterystyczne / wykresów, które studiujesz.]

— vzn
źródło

Dzięki za komentarz i referencje. Z tym problemem wpadłem, próbując modelować obciążenie systemu przetwarzania zapytań za pomocą grafu probabilistycznego. Model graficzny ma pewne unikalne właściwości, które pozwalają mi sądzić, że może istnieć przybliżenie średniej długości ścieżek - . Jak zasugerowano w twoim komentarzu, losowe próbkowanie daje przybliżenie. Problem polega na tym, że nie podaje ona gwarantowanej górnej granicy aproksymacji, z wyjątkiem długości najdłuższej ścieżki - . Co gorsza, obliczenie samej najdłuższej ścieżki - jest problemem NP-zupełnym.

s

$s$

t

$t$

s

$s$

t

$t$

s

$s$

t

$t$

— liuyu,