Losowy model surfowania

Model losowego przeglądania to model grafu opisujący prawdopodobieństwo, że przypadkowy użytkownik odwiedzi stronę internetową . Model próbuje przewidzieć prawdopodobieństwo, że przypadkowy internauta trafi na stronę, klikając link lub bezpośrednio wchodząc na stronę, na przykład bezpośrednio wpisując adres URL witryny w pasku adresu. Z tego powodu przyjmuje się założenie, że wszyscy użytkownicy surfujący po Internecie w końcu przestaną korzystać z linków na rzecz całkowitego przejścia na inną stronę. Model jest podobny do łańcucha Markowa , gdzie stany łańcucha to strony internetowe, na które trafia użytkownik, a przejścia to równie prawdopodobne łącza między tymi stronami.

Opis

Użytkownik porusza się po Internecie na dwa podstawowe sposoby; użytkownik może uzyskać bezpośredni dostęp do witryny, wprowadzając adres URL witryny lub klikając zakładkę , lub użytkownik może skorzystać z szeregu hiperłączy, aby przejść do żądanej strony. Model losowego internauty zakłada, że ​​link, który użytkownik wybierze jako następny, jest wybierany losowo. Model zakłada również, że liczba kolejnych linków nie jest nieskończona – użytkownik w pewnym momencie straci zainteresowanie i opuści dotychczasową witrynę do zupełnie nowej.

Model losowego internauty jest przedstawiony jako seria węzłów wskazujących strony internetowe, do których użytkownicy mogą uzyskać dostęp w sposób losowy. Nowy węzeł jest dodawany do wykresu po opublikowaniu nowej witryny internetowej. Ruch wokół węzłów wykresu jest modelowany poprzez losowy wybór węzła początkowego, a następnie wykonanie krótkiego i losowego przechodzenia przez węzły lub błądzenie losowe . To przechodzenie jest analogiczne do użytkownika uzyskującego dostęp do strony internetowej, a następnie podążającego za hiperłączem ${\ displaystyle t}$ tyle razy, aż użytkownik opuści stronę lub całkowicie przejdzie do innej witryny. Połączenia z innymi węzłami na tym grafie powstają, gdy na stronie umieszczane są linki wychodzące.

Definicje wykresów

W modelu losowego przeglądania wykresy internetowe są przedstawiane jako sekwencja grafów skierowanych tak, że $wykres$$, \ ldots}$${t}}$$displaystyle$ ma $krawędzie$ i . Proces definiowania wykresów jest sparametryzowany z prawdopodobieństwem $,$ niech ${\ displaystyle q = 1-p}$ .

$\ displaystyle G_ {t}}$ pojedynczo, tworząc połączenia z istniejącym wykresem $sol$ . W niektórych modelach połączenia reprezentują krawędzie skierowane, aw innych połączenia reprezentują krawędzie niekierowane. $się$ od pojedynczego $węzła$ mają pętle . ${\ Displaystyle v_ {t}}$ oznacza wierzchołek dodany w ${\ Displaystyle t ^ {th}}$$.$ , a oznacza całkowitą liczbę wierzchołków

Model 1. (chodnik 1-stopniowy z pętlą)

$displaystyle$ czasie wierzchołek tworzy połączenia przez ${$$\ displaystyle k}$ iteracje następujących kroków: t ${$

1. Wybierz istniejący węzeł $równomiernie$ losowo z ${\ Displaystyle \ {v_ {0}, v_ {1}, \ ldots, v_ {t-$
2. Z prawdopodobieństwem pozostań w ${$$\ displaystyle v}$ ; z prawdopodobieństwem ${\ displaystyle 1-p}$ idź 1 krok do przypadkowego sąsiada ${\ displaystyle v}$
3. $Dodaj$ krawędź z do bieżącego węzła

$skierowanych$ kierowane z istniejącego wykresu. Krawędzie są nieskierowane w odpowiednich grafach nieskierowanych.

Model 2. (Spacery losowe z rzutami monetą)

$displaystyle$ czasie wierzchołek tworzy połączenia przez ${$$\ displaystyle k}$ iteracje następujących kroków: t ${$

1. Wybierz istniejący węzeł $z$ losowo $\}}$
2. Rzuć monetą uprzedzeń ${\ displaystyle p}$
3. Jeśli moneta wypadnie orzeł, dodaj krawędź od $węzła$ i zatrzymaj się
4. Jeśli moneta wypadnie reszka, przejdź do losowego sąsiada bieżącego węzła i wróć do kroku 2

$skierowanych$ kierowane z istniejącego wykresu. Krawędzie są nieskierowane w odpowiednich grafach nieskierowanych.

Ograniczenia

Istnieją pewne zastrzeżenia do standardowego modelu losowego internauty, z których jednym jest to, że model ignoruje zawartość stron wybieranych przez użytkowników – ponieważ model zakłada, że ​​linki są wybierane losowo. Ponieważ użytkownicy zwykle mają na uwadze cel podczas surfowania w Internecie, zawartość witryn, do których prowadzą łącza, jest czynnikiem decydującym o tym, czy użytkownik kliknie łącze.

Aplikacja

Znormalizowana centralność wektora własnego w połączeniu z założeniem losowego modelu surfera o przypadkowych skokach stworzyło podstawę algorytmu Google PageRank .

Zobacz też

• Awrim Blum
• PageRank
• Wykres sieciowy

Linki zewnętrzne

• Studium przypadku przypadkowych internautów
• Data Mining and Analysis: Fundamental Concepts and Algorithms można bezpłatnie pobrać do użytku osobistego tutaj
• Badania firmy Microsoft dotyczące PageRank i modelu losowego surfera
• Artykuł o tym, jak wyszukiwarka Google implementuje PageRank w celu znajdowania trafnych wyników wyszukiwania