Archive for ‘Graph algorithms’

Listopad 22, 2014

Nowa jakość w odkrywaniu społeczności w grafach

- autor: tsissput

Wstęp

Jako, że wiele systemów i zjawisk we współczesnym (i nie tylko) świecie przyjmuje postać sieci lub zbiorów wierzchołków połączonych ze sobą  niezwykle interesujące są różne właściwości przez nie prezentowane oraz możliwość ich automatycznego odnajdywania.

Przykłady sieci:

– sieci społecznościowe

– sieci znajomości

– sieci współpracowników

– sieci technologiczne

– sieci biologiczne (takie jak na przykład układ nerwowy)

Większość z ostatnich prac na ten temat skupiała się na wielu statystycznych wskaźnikach, które owe sieci dzielą między sobą.

Są to przede wszystkim:

– efekt małego świata

– prawo potęgowe stopni wierzchołków

– klastrowanie

– skłonność tworzenia małych społeczności

Klastrowanie przedstawia bardzo ciekawą własność sieci społecznościowych oznaczającą, że dwójka znajomych jednej osoby ma znacznie większe prawdopodobieństwo znania się wzajemnie niż dwie losowo wybrane osoby z populacji.

C=3x liczba trójkątów w grafie/liczba połączonych trójek.

Prawdopodobieństwo wystąpienia takiego zdarzenia jest określone przez C. W Grafie pełnym wynosi 1, a w sieciach naturalnych zazwyczaj waha się od 0,1 do 0,5.

Skłonność tworzenia małych społeczności oznacza tendencję tworzenia się zbiorów wierzchołków stosunkowo gęsto połączonych, które są luźno połączone pomiędzy sobą. Ta własność jest bez wątpienia mocno sprzężona z klastrowaniem, jednakże z punktu widzenia analizy danych stanowi osobne wyzwanie.

Tradycyjna metoda

Hierarchiczny algorytm klastrowania wykrywania społeczności zakłada obliczenie wagi (bliskości) dla każdej pary Wij. Następnie bierzemy n wierzchołków bez połączeń pomiędzy nimi i dodajemy połączenia pomiędzy parami w kolejności malejących wag. W rezultacie otrzymujemy zagłębione zbiory coraz większych komponentów. Niestety proponowane wagi bliskości tak jak inne rozwiązania hierarchicznego algorytmu klastrowania mają wiele wad, między innymi pozostawianie pojedynczych wierzchołków (z małymi wagami) poza społecznościami.

drzewo

Przekład drzewa klastrów

Pośredniość Wierzchołków

Panowie Newman i Girvan zaproponowali zmianę podejścia do wykrywania społeczności: zamiast poszukiwać wierzchołków, które są najbardziej centralne dla społeczności, postanowili poszukać tych,  które są najmniej centralne – które leżą najbardziej pomiędzy społecznościami. Graf wynikowy jest konstruowany przez stopniowe usuwanie wierzchołków z oryginalnego grafu zamiast, jak poprzednio dodawanie najsilniejszych.

Zaproponowano uogólnienie pośredniości Freemana na krawędzie – krawędź otrzymuje pośredniość w podobny sposób jak wierzchołki – jak sumę najkrótszych ścieżek przebiegających przez nią.

Proponowany algorytm ma następującą postać:

  1. Oblicz pośredniość dla wszystkich krawędzi w grafie
  2. Usuń krawędź z najwyższą pośredniością
  3. Oblicz ponownie pośredniość w grafie – uwzględniając usunięcie krawędzi
  4. Wracaj do kroku 2, aż żadne krawędzie nie pozostaną w grafie.

Złożoność algorytmu:

Do obliczenia pośredniości wykorzystywany jest algorytm Newmana działający w czasie O(mn). Musi zostać powtórzony m razy (dla każdej usuwanej krawędzi), tak więc ostateczna złożoność wynosi O(m^2 n).

Przy optymalizowaniu czasu działania może pojawić się pokusa nie obliczania ponownie pośredniości, jednakże taka strategia okaże się błędna dla dwóch społeczności połączonych więcej niż jedną krawędzią – mamy gwarancję, że tylko jedna z nich będzie miała wysoką miarę pośredniości od samego początku.

Testowanie metody:

Metoda została przetestowana na różnych sieciach. Wygenerowanych komputerowo, przez co zapewniających określone właściwości, jak i sieciach występujących naturalnie. Dla wszystkich w tych sieci znana była struktura połączeń społeczności. Wyniki działania algorytmu były zadowalające – algorytm poprawnie rozpoznawał połączenia.

Grafy generowane komputerowo

Na potrzeby testów przygotowano duży zestaw grafów składających się ze 128 wierzchołków. Każdy graf był podzielony na cztery społeczności (po 32 wierzchołki). Krawędzie były umieszczane w grafie losowo z prawdopodobieństwem Pin pomiędzy wierzchołkami z tej samej społeczności oraz Pout dla wierzchołków pomiędzy społecznościami. Oczywiście Pin>Pout, a ich stosunkiem możemy sterować gęstością połączeń w społeczności. Sumaryczne prawdopodobieństwo było ustalone tak, aby stopień wierzchołków był średnio równy 16.

Algorytm sprawdza się dobrze dla Zout (połączenia poza społeczność) jest mniejsze od 6 (a tym samym Zout większe od 10) klasyfikując ponad 90% wierzchołków prawidłowo. Dla Zout większe niż 6 jakość klasyfikacji drastycznie spada, co jest logiczne, gdyż liczba połączeń wewnątrz społeczności zbliża się do tej z poza społeczności, co sprawia, że podział na społeczności jest mocno niejasny. Wyniki tego algorytmu zdecydowanie przewyższają wyniki jakościowe hierarchicznego algorytmy klastrowania.

zinzout

Porównanie wyników nowego algorytmu vs. algorytmu hierarchicznego klastrowania. Kółka – nowy algorytm, kwadraty – algorytm hierarchicznego klastrowania

Sztuczne a prawdziwe środowisko

W oczywisty sposób testowanie algorytmu na sztucznych sieciach jest wygodne, gdyż możemy kontrolować ilość i rodzaj połączeń, tworząc tym samym bardzo jednoznaczne sieci, jednakże prawdziwie użyteczny algorytm może okazać się tylko na naturalnie występujących sieciach, dlatego panowie Girvan i Newman wykorzystali kilka przykładów z życia codziennego (i badań), aby sprawdzić jakość wykrywania połączeń w społecznościach.

Badanie klubu karate Zachary (Zachary’s Karate Club Study)

Zachary  obserwował 34 członków klubu karate przez okres 2 lat. Podczas obserwacji administrator i trener klubu pokłócili się, w wyniku czego trener odszedł z klubu i założył swój własny zabierając ze sobą około połowy obecnych członków. Zachary konstruował sieć znajomości pomiędzy członkami klubu używając różnych miar do zobrazowania przyjaźni pomiędzy jednostkami. Na potrzeby testu algorytmu wykorzystana zostanie zwykła, nieważona wersja grafu przyjaźni. Algorytm wyodrębnił dwie społeczności zaczynając od węzła 1 i 34 (odpowiednio trener i administrator klubu), które prawie idealnie odzwierciedlały realny podział klubu po odejściu trenera.

karate

Podział klubu karate na społeczności względem trenera i administratora

Hierarchiczny algorytm klastrowania, dla porównania również z sukcesem wyodrębnił osobne społeczności, jednakże korelacja pomiędzy właściwym rozpadem klubu a efektem działania tego algorytmu była znacznie mniejsza.

Football amerykański (College Football)

Następnie algorytm został przetestowany na drużynach futbolu amerykańskiego. Wierzchołki reprezentowały zespoły a krawędzie regularne gry pomiędzy zespołami w sezonie 2000′. Struktura społeczności jest znana, gdyż zespoły połączone są w konferencje zawierające po 8-12 zespołów każda i gry są częstsze wśród członków jednej konferencji.[W sezonie 2000′ średnio 7 gier wewnątrz i 4 gry poza konferencją dla zespołu]

Algorytm poprawie klasyfikował większość przypadków. Błędy pojawiły się tam, gdzie drużyny grały podobną ilość meczów przeciwko drużyną z własnej konferencji i obcej. [Niektóre były podzielone]

Taki wynik jest spodziewany – jest to sytuacja podobna do tej, kiedy w grafach wygenerowanych komputerowo Zin zbliżało się do Zout i bez dodatkowych informacji nie dało się odróżnić społeczności.

Wnioski i komentarze

Metoda wydaje się być ciekawa i bardzo efektywna zarówno dla odkrywania znanych struktur (opisane powyżej) jak  i nieznanych pomagających zrozumieć pewne zjawiska (odsyłam do oryginału).

Pewnym problemem może być wydajność. Czas działania O(m^2 n) jest problematyczny dla bardzo dużych grafów i należałoby znaleźć pewne usprawnienia. Błędy popełniane przez algorytm całkowicie mieszczą się w wynikach oczekiwanych, gdyż obserwując zjawiska jedynie przez krótki okres czasu i nie posiadając dodatkowej wiedzy my jako ludzie również nie bylibyśmy w stanie wyodrębnić pewnych społeczności – tych w którymi algorytm miał problem.

Po usprawnieniach wydajnościowych algorytm może okazać się bardzo użyteczny dla odkrywania społeczności.

Bibliografia

Girvan, Newman Community structure in social and
biological networks Cornell University, University of Michigan 2001

Krzysztof Lewiński

98436

Listopad 10, 2013

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