Liczba różnych węzłów w przypadkowym spacerze

Czas dojazdu na połączonym wykresie definiuje się jako oczekiwaną liczbę kroków w losowym marszu rozpoczynającym się od , przed odwiedzeniem węzła a następnie ponownie osiągnięciem węzła . Jest to w zasadzie suma dwóch czasów uderzenia i .i j i H ( i , j ) H ( j , i $G=(V,E)$$i$$j$$i$$H(i,j)$$H(j,i)$

Czy jest coś podobnego do czasu dojazdu (nie dokładnie tego samego), ale zdefiniowanego w kategoriach węzłów? Innymi słowy, jaka jest oczekiwana liczba różnych węzłów przypadkowego spaceru rozpoczynającego się o wracającego o odwiedzę?$i$$i$

Aktualizacja (30 września 2012 r.): Istnieje szereg powiązanych prac nad liczbą różnych witryn odwiedzanych przez przypadkowego spacerowicza w sieci (tj. ). Na przykład patrz: http://jmp.aip.org/resource/1/jmapaq/v4/i9/p1191_s1?isAuthorized=no$\mathbb{Z}^n$

Czy ktoś kiedykolwiek coś o tym czytał?

od pytania i odpowiedzi z tobą w komentarzach, wydaje się, że jesteś zainteresowany badaniem czegoś zdefiniowanego jako odległość stosu w tym zestawie slajdów, Na matematycznym modelowaniu pamięci podręcznej

zdefiniuj odległość stosu odniesienia jako liczbę unikalnych adresów bloków między bieżącym odniesieniem a poprzednim odniesieniem do tego samego numeru bloku.

zawiera pewne analizy empiryczne za pomocą testów porównawczych. mówi ogólnie, że „nie jest znany pomiar lokalizacji” żądań pamięci podręcznej, a następnie proponuje taką odległość stosu. nie odnosi się to do teorii losowych grafów, chociaż szkicujesz takie powiązanie w swoich komentarzach. (wydaje się, że odległość stosu może być związana z mieszaniem łańcucha markowa ?)

Wygląda na to, że jesteś zainteresowany modelowaniem wydajności lub algorytmów optymalizacji pamięci podręcznej, biorąc pod uwagę żądania pamięci podręcznej jako węzły wykresu, a krawędzie jako przejścia między sąsiednimi żądaniami. nie widziałem artykułów analizujących strukturę tego wykresu. wydaje się, że okazuje się, że nie jest to wykres czysto losowy w rzeczywistych zastosowaniach ze względu na sukces pamięci podręcznych w praktyce oraz tak zwaną lokalizację przestrzenną i czasową na powyższych slajdach. tj. pewnego rodzaju „grupowanie”, gdy Joe kreśli w swojej odpowiedzi.

(może ma małą strukturę światową ? co jest dość wszechobecne w rzeczywistych danych)

Komentarz: Niedawno uczestniczyłem w rozmowie Bruce'a Reeda zatytułowanym Catching a Drunk Miscreant , która była wspólną pracą z Natashą Komorov i Peterem Winklerem. Jeśli możesz uzyskać wyniki tej pracy, być może pomoże Ci to w pewnym kierunku.

Ogólnie rzecz biorąc, dowodzą górnej granicy liczby kroków, których gliniarz potrzebuje na ogólnym wykresie, aby złapać złodzieja, gdy wiemy, że złodziej porusza się losowo wzdłuż krawędzi.

To nie jest właściwa odpowiedź na twoje pytanie, ale jest trochę za długa na komentarz.

Ilość, której szukasz, będzie się różnić w zależności od wykresu i będzie zależeć od początkowej strony walkera. Oczekiwana liczba odrębnych węzłów pośrednich będzie silnie zależeć od klastrowania na wykresie, i oczekiwałbym, że oczekiwana liczba różnych węzłów pośrednich będzie skorelowana ze współczynnikiem klastrowania .

Klaster jest w zasadzie podzbiorem wierzchołków, które mają dużą liczbę krawędzi, dzięki czemu każdy wierzchołek jest połączony z dużą częścią pozostałych wierzchołków w obrębie klastra. Gdy piechur wchodzi do klastra, prawdopodobnie pozostanie w tym regionie przez dużą liczbę przeskoków, być może wielokrotnie odwiedzając każdy węzeł. Rzeczywiście, stosowanie losowych spacerów w ten sposób jest jedną z technik obliczeniowych stosowanych do identyfikacji klastrów na dużych wykresach. Zatem dla spacerowicza rozpoczynającego się w gromadzie oczekiwana liczba wyraźnych pośrednich wierzchołków będzie prawdopodobnie skalowana wraz z rozmiarem gromady i średnim prawdopodobieństwem opuszczenia gromady.

$N$$\frac{1}{N}$$N+1$

Średni stopień wierzchołków na wykresie również będzie odgrywał ważną rolę, chociaż jest to związane z grupowaniem. Powodem tego jest to, że gdy piechur wskakuje na wierzchołek o stopniu 1, musi przeskoczyć z powrotem do poprzedniego wierzchołka na następnym skoku. Nawet gdy stopień wynosi 2, istnieje tylko jedna ścieżka, po której można podążać na wykresie, chociaż można ją pokonywać w obu kierunkach przy każdym przeskoku. Z drugiej strony, w przypadku wykresów o stopniu wyższym niż 2 liczba ścieżek może eksplodować, co sprawia, że ​​bardzo mało prawdopodobne jest powrót do początkowej strony, nawet jeśli najkrótsza ścieżka między nimi jest niewielka.

Dlatego można oczekiwać, że liczba odrębnych pośrednich wierzchołków będzie wysoka dla wykresów, które oba mają średni stopień znacznie powyżej 2, a także nie mają znaczącego skupienia, takiego jak drzewa.

Oczywiście te komentarze nie mają już miejsca w przypadku losowych spacerów kwantowych, ale myślę, że zależy ci tylko na klasycznym przypadku.