k-hop reachability – opis problemu i analiza rozwiązania

- autor: tsissput
Opracował: Przemysław Grzędzielski 

1 Wstęp

Celem niniejszego wpisu jest przybliżenie czytelnikom problemu k-hop reachability, mającego duże znaczenie w szeregu dziedzin, które można zamodelować przy pomocy sieci (w szczególności w sieciach społecznościowych) oraz analiza rozwiązania tego problemu, zaproponowanego w artykule „K-Reach: Who is in Your Small World”.

 2 Opis problemu i jego znaczenie

 2.1 Sformułowanie problemu

 Dane wejściowe

Niech s (source) i t (target) oznaczają dwa wierchołki w grafie, modelującym sieć. Niech k jest pewną dodatnią liczbą całkowitą.

 Problem

Czy z wierzchołka s da się dojść do wierzchołka t w co najwyżej k krokach? Innymi słowy, czy istnieje ścieżka w grafie skierowanym od wierzchołka s do wierzchołka t o długości co nawyżej k?

 Dane wyjściowe

Jest to problem decyzyjny, więc wynikiem jest odpowiedź TAK lub NIE na postawione pytanie.

 2.2 Związki z innymi problemami grafowymi

Zauważmy, że klasyczny problem osiągalności wierzchołków, polegający na udzieleniu odpowiedzi na pytanie: czy wierzchołek t jest osiągalny z wierzchołka s (czyli, przykładowo – czy Jaś jest w jakiś sposób powiązany z Małgosią?), jest przypadkiem szczególnym przedstawionego problemu, w którym parametr k wynosi nieskończoność.

 2.3 Znaczenie w kontekście sieci społecznościowych

Nietrudno wyobrazić sobie, że problem ten ma potencjalnie duże znaczenie w kontekście sieci społecznościowych. Nierzadko bowiem nie wystarcza nam wiedza o tym, czy dwie osoby są ze sobią powiązane w ogóle (jak zauważają autorzy artykułu – dowolne dwie osoby najprawdopodobniej są w jakiś sposób ze sobą powiązane, biorąc pod uwagę słynne “twierdzenie” o six degrees of separation). Znacznie bardziej przydatna może okazać się wiedza o tym, czy dane dwie osoby są od siebie oddalone o pewną liczbę k, szczególnie w przypadku małych k.

Przykładowo: chcemy, aby szczegółowość informacji o profilu osoby A w portalu społecznościowym widziana przez osobę B zależała od tego, jak “blisko” w grafie znajdują się te osoby. Np. użytkownik A ustawił widoczność swoich danych teleadresowych w taki sposób, aby mieli do nich dostęp znajomi co najwyżej trzeciego stopnia. Kiedy użytkownik B wyświetla profil użytkownika A, potrzebujmy odpowiedzi na pytanie, czy użytkownik B jest “oddalony” od użytkownika A o nie więcej niż trzy.

 3 Przykładowe podejścia, ich wady i zalety

 3.1 Problem z Lady Gagą

Autorzy artykułu “K-Reach: Who is in Your Small World” dokonują istotnego spostrzeżenia: fakt, że wartość k jest mała (mniejsza od 6, bo takie instancje mają sens w kontekście rzeczonych six degrees) nie czyni problemu łatwiejszym. Wydawać by się mogło, że w takim wypadku sprawdziłoby się rozwiązanie naiwne, polegające na przejściu grafu wszerz (Breadth First Search) i sprawdzeniu, czy docelowa osoba zostanie napotkana w odległości nie większej niż k od wierzchołka początkowego. Problemem, który wskazują autorzy, jest obecność tzw. celebrities, czyli osób bardzo popularnych w całej sieci. Twierdzą oni, że w przypadku większości rzeczywistych zapytań na pewnym etapie przeszukiwania grafu napotkamy na celebrytę (nie przepadam za tym neologizmem…), który “zaprowadzi” nas do tak wielkiej liczby wierzchołków, że dalsze przeszukiwanie sieci stanie się zadaniem karkołomnym (przykład: Lady Gaga, która w chwili powstawania niniejszego wpisu ma 60 411 323 fanów na Facebooku – wyobraźmy sobie tę zajętość pamięciową!).

 3.2 DAG – Dlaczego Acykliczny Graf … ?!

Kolejne przytoczone przez autorów podejście opiera się na założeniu, że graf sieciowy jest acyklicznym grafem skierowanym (ang. Directed Acyclic Graph). W przypadku, kiedy tak nie jest (czyli – w rzeczywistości – praktycznie zawsze) zostaje on zredukowany do DAGa poprzez zastąpienie wszystkich silnie spójnych składowych (ang. strongly connected components) pojedynczymi wierzchołkami. Podejście to redukuje zajętość pamięciową i sprawdza się w przypadku pytania, czy połączenie między dwoma wierzchołkami w ogóle istnieje (wiadomo, że jeśli dojdziemy do wierzchołka zastępującego składową silnie spójną, to dojdziemy także do każdego z rzeczywistych wierzchołków ją tworzących). Zawodzi jednakże w przypadku rozważanego problemu k-reachability, ponieważ – jak nietrudno zauważyć – para wierzchołków “osiągalnych” nie musi być “k-osiągalna” (jeśli mogę pokusić się o spolszczenie nazwy naszego problemu).

Do powyższych spostrzeżeń dorzuciłbym jeszcze jedno, zasadnicze – w praktyce sieć społecznościową rzadko możemy w ogóle zamodelować w postaci grafu skierowanego, najczęściej bowiem “znajomość” między dwoma osobami jest relacją symetryczną, czyż nie?

 3.3 Najkrótsze ścieżki

Innym rozważanym podejściem jest stosowanie indeksów przeznaczonych do przetwarzania zapytań o najkrótsze ścieżki pomiędzy wierzchołkami w grafie. Użycie takiego indeksu, który danego wierzchołka s powie nam szybko (czyt. O(1)), jaka jest jego odległość od wierzchołka t, byłoby trywialne. Problemy, które wskazują autorzy, jest koszt przetwarzania zapytań o odległości między wierzchołkami oraz fakt, że indeksy takie przeważnie są tworzone dla grafów nieskierowanych.

Moim zdaniem, podstawowym mankamentem, który należałoby tutaj podkreślić, jest duża zajętość pamięciowa takiego indeksu oraz złożoność samego procesu tworzenia. Stworzenie macierzy najkrótszych odległości między wierzchołkami wymaga bowiem po prostu przejścia grafu w kolejności BFS (jeśli łuki mają jednakowe wagi, oczywiście). Jeśli natomiast łuki mają różne wagi, najkrótsze odległości między wierzchołkami na niewiele nam się przydadzą.

 4 Algorytm k-Reach

 4.1 Pokrycie wierzchołkowe

Zaproponowany algorytm konstruuje indeks, który pozwala na sprawdzenie, czy dane dwa wierzchołki leżą w odległości co najwyżej k. Do stworzenia indeksu wykorzystywane jest tzw. pokrycie wierzchołkowe grafu:

Pokrycie wierzchołkowe to taki podzbiór wierzchołków grafu G(V,E), że dowolna krawędź w tym grafie jest incydentna z co najmniej jednym wierzchołkiem tego podzbioru

Minimalne pokrycie wierzchołkowe to najmniejszy możliwy podzbiór wierzchołków grafu, który jest jego pokryciem wierzchołkowym

Problem znalezienia minimalnego pokrycia wierzchołkowego grafu jest NP-trudny. Istnieje jednak algorytm, który znajduje jego przybliżenie w czasie wielomianowym: 2-approximate minimum vertex cover.

Jego przebieg jest następujący (E oznacza zbiór krawędzi w grafie G, V zbiór wierzchołków w grafie G, S jest wynikowym zbiorem):

 S = <empty set>()
while (E is not empty){
(u,v) = randomly_select_edge_from_E
// add u and v to result set
S += u
S += v
// remove every edge that is incident to u or v
for every e : (e incident to u or v) {
E -= e
}
// remove u and v from the vertices
V -= u
V-=v
}
// S is the result
return S

Zauważmy, że dla każdej krawędzi (u,v), którą dodajemy do zbioru S, co najmniej jeden z pary wierzchołków musi należeć do minimalnego pokrycia wierzchołkowego (oznaczmy je jako C). W przeciwnym razie C nie spełniałoby definicji pokrycia wierzchołkowego (tzn. krawędź (u,v) nie byłaby incydentna z żadnym z wierzchołków należących do C). O skonstruowanym oszacowaniu możemy więc powiedzieć, że jego liczność jest co najwyżej dwa razy większa od liczności minimalnego pokrycia wierzchołkowego: |S| <=2*|C|.

 4.2 indeks k-Reach

Indeks k-Reach zakłada, że dane są:

• graf G(V,E)

• S – pokrycie wierzchołkowe grafu G

• parametr k

Indeks jest grafem I=(V_i, E_i, w_i) zdefiniowanym następująco:

• V_i = S

• E_i jest zbiorem krawędzi (u,v) należących do S takich, że v jest k-osiągalny z u (isReachable(u,v,k) == true)

• w_i to funkcja wagowa, która każdej krawędzi e=(u,v) ze zbioru E_i przyporządkowuje wagę (zauważmy, że isReachable(u,v,k-2) impikuje, że isReachable(u,v,k-1), co z kolei implikuje isReachable(u,v,k):

 – if (isReachable(u,v,k-2)) { w_i(e) = k-2;}
 – else if (isReachable(u,v,k-1)) { w_i(e) = k-1; }
 – else if (isReachable(u,v,k)) { w_i(e) = k;}

Procedura konstrukcji indeksu k-Reach jest następująca: dla każdego wierzchołka u w pokryciu S wyznaczamy zbiór S_k(u), zawierający wierzchołki znajdujące się w odległości nie większej niż k od niego, wykonując przejście BFS po grafie G). Pseudokod znajduje się poniżej:

S = 2-approximate_vertex_cover(G)
V_i = S
for each u in S {
S_k(u) = BFS(graph=G,upper_bound=k)
for each v in S_k(u) {
E_i += (u,v)
compute weight w_i for (u,v)
}
}
return I=(V_i,E_i,w_i)

 4.3 Przetwarzanie zapytań przy użyciu indeksu k-Reach

Zakładając, że dla danego parametru k skonstruowano indeks k-Reach (a także, uprzednio, pokrycie wierzchołkowe S), odpowiedź na pytanie: czy wierzchołek t jest oddalony od wierzchołka s o co najwyżej k, jest stosunkowo prosta. Istotne jest spostrzeżenie, że możemy tu mieć do czynienia z czterema przypadkami. Logika algorytmu jest prosta:

 Przypadek 1: s i t należą do S

Najprostszy przypadek. Jeśli zarówno s i t należą do pokrycia wierzchołkowego S, to isReachable(u,v,k) zachodzi wtedy i tylko wtedy, gdy krawędź (s,t) znajduje się w zbiorze krawędzi E_i naszego indeksu.

 Przypadek 2: s należy do S, t nie należy do S

Skoro t nie należy do pokrycia wierzchołkowego S, to wiadomo, że wszystkie jego poprzedniki należą do S (wynika to z definicji pokrycia wierzchołkowego). Wiadomo też, że jeden z tych poprzedników (o ile takie w ogóle istnieją) musi być (k-1)-osiągalny z wierzchołka s (wówczas docelowe t będzie k-osiągalne z wierzchołka s).

Przypadek 3: s nie należy do S, t należy do S

Sytuacja analogiczna do powyższej. Skoro s nie należy do pokrycia wierzchołkowego S, to wiadomo, że wszystkie jego następniki muszą należeć do S. Wiadomo też, że z co najmniej jednego z tych następników wierzchołek docelowy t jest (k-1)-osiągalny (wówczas jest on k-osiągalny z początkowego s).

 Przypadek 4: s, t nie należą do S

Rozumowanie podobne jak poprzednio. Wiemy, że wszystkie następniki s oraz wszystkie poprzedniki t należą do S. Sprawdzamy więc, czy istnieje taka para (u,v), że u jest następnikiem s, v jest poprzednikiem t oraz zachodzi isReachable(u,v,k-2). Jeśli taka para istnieje, to wiemy, że t jest osiągalny z s.

 4.4 Analiza złożoności

Warto zwrócić uwagę na złożoności obliczeniowe poszczególnych kroków prezentowanego algorytmu. Muszę przyznać, że wyjaśnienia podane przez autorów (dotyczy to w szczególności kroku nr 2) wydają mi się niekompletne, a co za tym idzie – niezrozumiałe.

 4.4.1 Tworzenie indeksu k-Reach

• Wyznaczanie pokrycia wierzchołkowego S: O(m+n)

• Tworzenie skierowanego, ważonego grafu I=(V_i, E_i, w_i): całkowita liczba wykonywanych kroków jest równa sumie kroków wymaganych do stworzenia zbiorów S_k dla każdego wierzchołka u (czyli zbiorów wierzchołków k-osiągalnych z u) – pamiętajmy, że w tym celu przechodzimy graf w porządku BFS dla każdego wierzchołka u (z maksymalnym zasięgiem k)

 4.4.2 Przetwarzanie zapytania dla danych s,t

Niech inDegree(u,G) i outDegree(u,G) oznaczają, odpowiednio, stopień wejściowy i stopień wyjściowy wierzchołka u w grafie G.

• Sprawdzenie, czy wierzchołek należy do V_i: O( 1 )

• Sprawdzenie, czy krawędź (u,v) należy do E_i i odczytanie jej wagi: O( log outDegree(u,I) ) lub O( log inDegree(v,I) ) przy założeniu, że graf jest przechowywany w formie listy sąsiedztwa (ang. adjacency list)

Na tej podstawie autorzy podają następujące złożoności przetwarzania poszczególnych przypadków zapytań wyróżnionych w algorytmie:

• Przypadek 1: O( log outDegree(s,I) )

• Przypadek 2: O( outDegree(s,I)+inDegree(t,G) )

• Przypadek 3: O( outDegree(s,G)+inDegree(t,I) )

• Przypadek 4: O(  sum_by_u_in_outNeighbours(s,G): (outDegree(u,I)+inDegree(t,G)) )

Uważam, że analizie złośoności obliczeniowej należałoby w artykule poświęcić nieco więcej miejsca. Co o nich sądzicie?

 5 Bibliografia

K-Reach: Who is in Your Small World”, 1 VIII 2012; James Cheng, Zechao Shang, Hong Cheng, Haixun Wang, Jeffrey X. Yu

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s

%d blogerów lubi to: