mpsic_project_2_random_walks/matma2nowy.ipynb

Spacery losowe po grafach: algorytm wyszukiwania klastrów

Spacery losowe

Spacer losowy można zdefiniować jako serię dyskretnych kroków wykonywanych przez obiekt w pewnym kierunku. Co więcej, kierunek i ruch obiektu w każdym kroku określamy probabilistycznie.

W spacerze losowym przyszłe położenie obiektu jest całkowicie niezależne od bieżącego położenia. Ponadto jest to przykład procesu Markowa. Zaczynając od pewnej pozycji, obiekt może iść w dowolnym kierunku. Każdy krok wykonany przez obiekt w dowolnym kierunku ma przypisane prawdopodobieństwo, dlatego końcowe położenie jest całkowicie niezależne od punktu początkowego.

Przykład jednowymiarowego spaceru losowego zaczynającego się w punkcie 0, po osi liczb całkowitych:

Obiekt w każdym kroku może poruszać się z równym prawdopodobieństwem w dwóch kierunkach: lewo lub prawo. W pierwszym kroku prawdopodobieństwo że obiekt znajdzie się w pozycji -1 lub 1 wynosi 1/2.

W drugim kroku obiekt może znaleźć się na pozycjach -2, 0 i 2. Prawdopodobieństwo że obiekt znajdzie się w położeniu -2 lub 2 jest równe i wynosi 1/4, do punktu 0 obiekt może dotrzeć z punktów -1 i 1 to znaczy że prawdopowdopodobieństwa należy zsumować i wtedy 1/4 + 1/4 = 1/2.

W trzecim kroku obiekt może znaleźć się w pozycjach -3, -1, 1, 3. Prawdopodobieństwo że obiekt znajdzie się w pozycji 3 lub -3 jest równe 3/8, a pozycjach 1 lub -1 jest równe 1/8.

Łatwo zauważyć, że gdy liczba wykonanych kroków jest nieparzysta, to wszystkich możliwych pozycji w jakich może znależć się obiekt również jest nieparzysta liczba. Podobnie w przypadku parzystej liczby wykonanych kroków, ilość możliwych pozycji jest parzysta.

Dwuwymiarowy spacer losowy

Grafy

Grafem nazywamy uporządkowaną kolekcję dwóch zbiorów: zbioru wierzchołków _V oraz zbioru krawędzi E. Zbiór wierzchołków jest dowolnej postaci. Elementami zbioru krawędzi są e ∈ E, które są podzbiorami postaci {v₁, v₂} dla pewnych dwóch wierzchołków v₁, v₂ ∈ V (jeśli graf jest nieskierowany) lub parą uporządkowaną (v₁, v₂) jeśli graf jest skierowany.

Jeżeli (x, y) ∈ E, to wierzchołki x, y nazywamy sąsiadami i oznaczamy x ∼ y. Stopniem wierzchołka x ∈ V nazywamy liczbę jego sąsiadów i oznaczamy deg(x).

Podgrafy

Podgraf danego grafu G to graf powstały przez usunięcie z grafu G pewnej liczby wierzchołków lub krawędzi (z tym zastrzeżeniem, że usuwając pewien wierzchołek usuwamy wszystkie przyległe do niego krawędzie). W szczególności każdy graf jest swoim podgrafem.

Graf spójny

Graf spójny – graf, w którym każdą parę wierzchołków łączy pewna ścieżka. Graf nieposiadający powyższej własności to graf niespójny.

Warunkiem koniecznym, by graf skierowany był spójny, jest spójność jego grafu podstawowego (tego samego grafu bez kierunków na krawędziach).

Wierzchołki krytyczne rozspójniające graf

Wierzchołek krytyczny to taki którego usunięcie sprawi że graf przestaje być grafem spójnym

Wierzchołkiem krytycznym powyższego grafu jest wierzchołek numer 4, usunięcie go spowoduje odłączenie wierzchołka numer 6 od reszty grafu.

Niektóre grafy nie posiadają wierzchołków krytycznych są to na przyklad:

• grafy posiadające cykle (czyli zamkniętą ścieżkę z takim samym ostatnim i pierwszym wierzchołkiem):

• grafy pełne (grafy w których dla każdej pary węzłów istnieje krawędź je łącząca):

Spacer losowy po grafie

Spacer losowy po grafie skierowanym lub nieskierowanym G jest losową sekwencją wierzchołków v1, v2, . . . . , vk takich, że v_i, v_i+1 jest krawędzią w G.

Zakładamy, że A jest macierzą sąsiedztwa grafu G oraz że v_i jest wierzchołkiem.

Macierz sąsiedztwa to macierz definiowana: A = (a_i,j) gdzie a_i,j = { 1 jeśli (v_i, v_j) jest krawędzią w grafie G lub 0 w przeciwnym przypadku }

Liczba spacerów o długości k, które zaczynają się w v_i i kończą w v_j, jest dana przez element z i-tego wiersza i j-tej kolumny w A^k. W szczególności całkowita liczba spacerów o długości k, które zaczynają się w punkcie v_i, jest sumą i-tego wiersza macierzy A^k, tzn. jeśli A^k = (b_i,j), to liczba ta wynosi b_i,1 + b_i,2 + ... + b_i,m. Podobnie, całkowita liczba spacerów o długości k, które kończą się w v_j, jest sumą j-tej kolumny macierzy A^k.

Twierdzenie:

Jeśli A jest macierzą sąsiedztwa grafu lub digrafu G o wierzchołkach {v1, ... . . vn}, to pozycja i, j w A^k jest liczbą przejść o długości k od v_i do v_j.

Dowód na podstawie k:

Widać, że przypadek, gdy k = 1, jest prawdziwy.

Załóżmy zatem, że wynik jest prawdziwy dla dowolnego k > 1. Rozważmy dowolny spacer o długości k + 1 od v_i do v_j . Wówczas na tym przejściu musi istnieć wierzchołek v_l taki, że v_l jest sąsiadujący z v_j. Jeśli usuniemy v_j z tej ścieżki, to pozostała droga jest drogą o długości k od v_i do v_l. Liczba takich spacerów jest określona przez element (i,j) w macierzy A^k. Teraz każdemu takiemu wierzcholkowi v_l odpowiada 1 na pozycji (l, j) w macierzy A. Wynik ten wynika z rozważenia elementu (i, j) w macierzy A^k+1 = A^kA.

Przykład:

Macierz sąsiedztwa dla tego grafu:

Macierz sąsiedztwa podniesiona do szóstej potęgi:

Liczba spacerów o długości 6 jest równa sumie wszystkich elementów macierzy A⁶, czyli 122. Spośród nich liczba tych, które kończą się w v₄ jest równa sumie pozycji z kolumny 4 w A⁶, czyli 19. Zatem prawdopodobieństwo, że spacer losowy o długości 6 zakończy się w punkcie v₄ jest równe 19/122.

Liczba spacerów długości 6, które zaczynają się w punkcie v₁, jest równa sumie wartości pierwszego wiersza A6, czyli 15. Spośród spacerów długości 6, które zaczynają się w punkcie v₁, są 4, które kończą się w punkcie v₅. Zatem prawdopodobieństwo, że spacer losowy o długości 6 zaczynający się w punkcie v₁, zakończy się w punkcie v₅, wynosi 4/15.

Klastrowanie grafów

Klastrowanie jest klasycznym zadaniem eksploracji danych, polegającym na organizowaniu danych wejściowych w grupy (klastry) w taki sposób, że punkty danych w obrębie grupy są bardziej podobne do siebie niż poza nią. Zadanie to różni się od klasyfikacji nadzorowanej, w której przykłady różnych klas są znane a priori i są wykorzystywane do trenowania modelu obliczeniowego w celu przypisania innych obiektów do znanych grup. Celem klasteryzacji jest natomiast znalezienie naturalnych, wewnętrznych podklas w danych, bez zakładania a priori liczby lub rodzaju klastrów.

W przypadku grafów, klastrowanie to proces grupowania węzłów grafu w klastry, uwzględniający strukturę krawędziową grafu w taki sposób, aby w każdym klastrze występowało kilka krawędzi, a niewiele pomiędzy klastrami. Klastrowanie grafu ma na celu podzielenie węzłów grafu na rozłączne grupy.

Łancuch markova

Na danym grafie G = (V, E) definiujemy prosty spacer losowy. Jest to łańcuch Markowa na przestrzeni stanów V z macierzą przejścia

$P(x, y) = \frac{1}{deg(x)}$ jeżeli y ∼ x

$P(x, y) = 0$ w przeciwnym razie

Gdy łańcuch znajduje się w wierzchołku x, to wybiera losowo (jednostajnie) jednego z jego sąsiadów i przechodzi do niego.

Spacery losowe są podstawą algorytmu MCL. Poruszając się losowo od węzła do węzła, istnieje większe prawdopodobieństwo poruszania się wewnątrz klastru, niż przecinania klastrów. Dzieje się tak, ponieważ z definicji klastry są wewnętrznie gęste, a są oddzielone rzadkimi regionami. W grupowaniu grafów gęstość i rzadkość definiuje się jako proporcję szczelin krawędziowych, które mają w sobie krawędzie. Przeprowadzając spacery losowe, mamy większą szansę na znalezienie trendu gromadzenia się wierzchołków i definicji klastrów w grafie. Spacery losowe w grafie są obliczane za pomocą łańcuchów Markowa.

Proces Markowa – ciąg zdarzeń, w którym prawdopodobieństwo każdego zdarzenia zależy jedynie od wyniku poprzedniego. W ujęciu matematycznym, procesy Markowa to takie procesy stochastyczne, które spełniają własność Markowa.

$P(X_{n+1} = x|X_{n}=x_n,\ldots X_{1}=x_{1}) = P(X_{n+1}=x | X_{n}=x_n)$

Oznacza to, że zmienna w ciągu (X_n) ''pamięta'' tylko swój stan z poprzedniego kroku i wyłącznie od niego zależy.

Podgrafy silnie ze sobą powiązane

Najprościej będzie to zaobserować na przykładzie:

Jak widać a powyższym obrazku silnie ze sobą powiążane podgrafy to po prostu podgrafy których wierzchołki posiadają między sobą znacznie więcej krawędzi niż z pozostałymi wierzchołkami grafu.

W przypadku grafów skierowanych, podgraf silnie powiązany to podgraf z którym z każdego wierzchołka można osiągnąć inny wierzchołek, jak na poniższym obrazku:

Zastosowanie spacerów losowych w klastrowaniu grafów.

Spacery losowe na grafach nadają się do klastrowania ponieważ istnieje znacznie większeprawdopodobieństwo że poruszając się losowo zostaniemy w obrębie danego klastru. klastry są wewnątrz gęste a wyjścia z klastru są rzadkie. Do klastrowania można wykorzystać algorytm MCL(Markov Cluster Algorithm)

1. Obliczamy dla każdej pary wezłów u i v prawdopodobieństwo rozpoczęcia od węzła u i zakończenia w węźle v po przejściu k kroków.
2. Otrzymaną macierz normalizujemy do wartości z przedziału 0-1
3. Mnożymy macierz k razy przez siebie
4. Wzmacniamy obserwacje z punktu 3 stosując inflacje z parametrem r ma to wpływ na ziarnistość klastrów

5. Kroki 3 i 4 powtarzamy do momeentu gdy sumy w kolumnach będą równe
6. Z otrzymanej macierzy odczytujemy klastry np: {1}, {3}, {2,4}