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.
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ć:
- Oblicz pośredniość dla wszystkich krawędzi w grafie
- Usuń krawędź z najwyższą pośredniością
- Oblicz ponownie pośredniość w grafie – uwzględniając usunięcie krawędzi
- 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.
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.
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
tsiss@PUT 