Ś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.

algorithms complexity-theory graphs approximation enumeration 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

Odpowiedzi:

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,