Krótkie spojrzenie na problem prognozowania połączeń w sieciach społecznościowych z wykorzystaniem miar opartych na modelu grafowym

- autor: tsissput

Wprowadzenie:

Podczas nazywanej przez Samuela Smitha Wiekiem Sieci, pierwszej epoki trzeciego tysiąclecia, zaobserwować można było niezwykły wzrost skupienia życia społecznego, politycznego, a nawet ekonomicznego wokół sieci tworzonych w Internecie. Ewolucja ta stopniowo doprowadziła do wzrostu zainteresowania tematem sieci społecznościowych, aż w końcu sprawiła, iż dla wielu ludzi stały się one nieodłącznym punktem życia, ułatwiającym komunikację na masową skalę.

Sieć społecznościowa w ogólności definiuje jednostki oraz połączenia realizowane między nimi poprzez współzależności, takie jak: przyjaźń, wspólne interesy, współpraca, zainteresowania, wiedza, czy przekonania. Jako naturalny przykład sieci społecznościowej przedstawić można grupę naukowców prowadzących badania w danej dziedzinie, gdzie połączenia pomiędzy dwoma osobami występują w przypadku, gdy prowadziły one wspólne badania lub były współautorami prac naukowych.

Warto pamiętać, iż wbrew przekonaniu wielu osób, sieci społecznościowe to nie tylko popularne serwisy typu: Facebook, Twitter, czy LinkedIn, ale również portale takie jak: Wikipedia, Slashdot, czy Epinions, które to, ze względu na możliwość nawiązywania zarówno pozytywnych, jak i negatywnych połączeń, wynikających chociażby z odmiennych przekonań czy niezgodności opinii, określane są jako „Signed Social Network”. Jako inny przykład sieci społecznościowej przytoczyć można strukturę  sieci web, a dokładniej zestaw linków pomiędzy stronami domowymi.

Link-prediction:

Rozwój sieci społecznościowych następuje niezwykle dynamicznie, a ich wzrost oraz topologia zmieniają się w znaczący sposób w niewielkich odstępach czasu. Jakkolwiek niewykonalnym jest prognozowanie nowych jednostek pojawiających się w sieci, istnieje możliwość przewidywania połączeń pomiędzy już istniejącymi indywidualnościami.

Formalnie definiując problem, można stwierdzić, iż mając obraz sieci w chwili t, poszukiwane są z jak największym prawdopodobieństwem jednostki, pomiędzy którymi powstaną powiązania w sieci w przedziale czasowym t do t’.

Rozwiązanie problemu prognozowania połączeń oparte jest na cechach obiektu oraz istniejących już połączeniach, dlatego też najczęściej podczas przewidywania połączeń wykorzystywane są różnego rodzaju miary podobieństwa, a samo zagadnienie zajmuje szeroki obszar zainteresowań w zakresie eksploracji danych, w którym to wiele zadań przetwarzania danych wykorzystuje relacje pomiędzy obiektami. Upraszczając, zadanie prognozowania połączeń zdefiniowane może zostać jako binarny problem klasyfikacji.

Ze względu na wspomniany już dynamiczny rozwój sieci, a także na ich niejednokrotne stosunkowo duże rozrzucenie, osiągnięcie wysokiej precyzji oceny staje się dużym wyzwaniem. Możliwość zastosowania problemu również w innych dziedzinach, takich jak: bibliografie, biologia molekularna, systemy rekomendacyjne, czy policyjne śledztwa, determinuje jednakże powstawanie oraz rozwój wielu algorytmów umożliwiających przewidywanie połączeń.

Matematyczny opis problemu:

Jednym z najpowszechniejszych, a jednocześnie jednym z najwcześniej powstałych, modeli wykorzystywanych w prognozowaniu połączeń w sieciach społecznościowych jest model oparty na teorii grafów, stosowany również w badaniach prowadzonych przez Davida Libena-Nowella oraz Jona Kleinberga, amerykańskich naukowców znanych z prowadzonych badań nad algorytmami wykorzystywanymi w sieci.

Wykorzystując teorię grafów, sieć społecznościowa przyrównana może zostać do grafu postaci G=<V,E >, w którym każda krawędź e=u,v∈E  reprezentuje połączenie pomiędzy wierzchołkami u  oraz v , mające miejsce w danej jednostce czasowej t . Wierzchołki natomiast odpowiadają poszczególnym jednostkom sieci. Model ten jest grafem nieskierowanym, wobec czego zaobserwować można tożsamość pomiędzy zbiorami u,v  oraz v,u .

W modelu grafowym problem prognozowania połączeń sprowadza się do oszacowania prawdopodobieństwa z jakim do grafu, w zadanym przedziale czasowym (t,t’) , zostaną dodane odpowiednie krawędzie.

Wielokrotne związki pomiędzy wierzchołkami u i v opisane mogą być jako krawędzie równoległe, oznaczone różnymi znacznikami czasowymi.

Model grafowy jest modelem uniwersalnym, co implikuje możliwość przeprowadzenia na nim popularnych metod klasyfikacji, wykorzystując przykładowo naiwny klasyfikator Bayesa, sieci neuronowe, SVM, czy też metodę k-najbliższych sąsiadów. Celem wykonania klasyfikacji należy jednak wcześniej dokonać odpowiedniego wyboru zestawu cech, na których to koncentrują się wspomniane algorytmy.

Miary prognozowania:

Algorytmy grafowe głównie skupiają się na obliczeniach związanych z miarą podobieństwa opartą na sąsiedztwie wierzchołków lub zestawie połączeń pomiędzy dwoma wierzchołkami. Jakkolwiek niewątpliwą zaletą przetwarzania tego typu jest ogólność miary, możliwość jej zastosowania dla różnych przypadków, a także brak konieczności posiadania wiedzy dziedzinowej, w przypadku dużych sieci może pojawić się problem związany z dużymi kosztami obliczeniowymi.

Node Based Topological Patterns:

W przypadku algorytmów opartych na analizie sąsiedztwa wierzchołków, istnieje wiele metod wyznaczania wagi połączenia pomiędzy wierzchołkami, oznaczanej jako score(x,y) . Niezależnie od wykorzystanego sposobu, przyjęta została nomenklatura, w której zbiór sąsiadów wierzchołka x  w grafie oznaczony jest przy pomocy symbolu Γ(x) . Miary oparte są na idei zakładającej, że prawdopodobieństwo powstania połączenia pomiędzy dwoma wierzchołkami jest tym większe, im większa jest część wspólna pomiędzy ich zbiorami sąsiadów. Przekładając powyższe na problem analizy sieci, można powiedzieć, że szansa współpracy pomiędzy dwoma autorami rośnie wraz z liczbą wspólnych publikacji pomiędzy ich znajomymi.

  • Common neighbors:

Miara oparta bezpośrednio na liczbie wspólnych sąsiadów pomiędzy dwoma wierzchołkami. Generalizując, jeśli wierzchołek x jest połączony z wierzchołkiem y , a wierzchołek y  jest połączony w wierzchołkiem z , istnieje wysokie prawdopodobieństwo wystąpienia w przyszłości połączenia pomiędzy wierzchołkiem x oraz z .

  • Jaccard coefficient:

Podejście bazujące na metodzie common neighbors, wprowadzając do niej czynnik normalizacyjny. W związku z powyższym, w przypadku większej liczby wspólnych znajomych, prawdopodobieństwo wystąpienia połączenia powinno rosnąć. Zgodnie jednak z badaniami Libena-Nowella, wydajność współczynnika Jacarda jest znacznie gorsza niż miary common neighbors.

  • Adamic/Adar:

Miara wykorzystująca współczynnik wagowy, przypisywany w przypadku wystąpienia połączenia z wierzchołkami charakteryzującymi się  małym stopniem.

  • Preferential attachment:

Metoda mająca swoje podwaliny w założeniu, że prawdopodobieństwo powstania nowego połączeniu jest proporcjonalne do korelacji zbiorów sąsiadów dla wierzchołków x oraz y, co oznacza, że im większy jest zbiór sąsiadów wierzchołka x , tym większa szansa, że nowa krawędź będzie wychodzić z tego wierzchołka.

Path based Topological Patterns:

Path based Topological Patterns to metody oparte na wyznaczaniu zbioru najkrótszych ścieżek pomiędzy dwoma wierzchołkami na podstawie zestawu wszystkich ścieżek łączących te wierzchołki.

  • Shortest Path Distance:

Metoda opierająca się na twierdzeniu, że im krótsza ścieżka dzieli dwa wierzchołki, tym wyższe jest prawdopodobieństwo wystąpienia połączenia pomiędzy nimi.

  • Katz:

Miara sumująca bezpośrednio zestaw ścieżek łączących dwa wierzchołki, przypisując odpowiednią wagę ścieżkom w zależności od ich długości.

  • Hitting time:

Metoda oparta na losowym iteracyjnym przejściu od wierzchołka x  do y . Miara Hitting time (Hx,y)  odpowiada czasowi wykonania przejścia, czyli liczbie niezbędnych do wykonania kroków. Im krótszy czas przejścia, tym wyższe jest prawdopodobieństwo wystąpienia połączenia pomiędzy dwoma wierzchołkami.

  • Rooted PageRank:

Jak odkrył Chung Zhao, algorytm PageRank wykorzystywany do tworzenia rankingów stron internetowych, jest nieodłącznie związany z metodą Hitting time, co sprawia, iż algorytm ten, poddany pewnym modyfikacjom, może również być używany w problemie przewidywania połączeń. W takim przypadku podobieństwo dwóch wierzchołków opierane jest na prawdopodobieństwie losowego powrotu od wierzchołka y do wierzchołka x.

  • SimRank:

Podejście oparte na definicji, iż pomiędzy dwoma wierzchołkami jest szansa na powstanie połączenia, jeśli są one związane z podobnymi sąsiadami.

Higher-level approaches:

Algorytmy „Meta-approaches” mogą być używane w połączeniu z każdą z metod przedstawionych powyżej.

  • Low-rank approximation:

Low-rank approximation jest problemem minimalizacji, gdzie funkcja kosztu mierzy dopasowanie pomiędzy grafem zadanym, a grafem otrzymanym w wyniku wybrania podzbioru grafu, najlepiej aproksymującego model wyjściowy. Ranking może być tworzony z wykorzystaniem metod takich jak miara Katz, czy metoda wspólnych sąsiadów.

  • Unseen bigrams:

Problem prognozowania połączeń zbliżony jest do problemu estymowania częstotliwości w tak zwanych „unseen bigrams”. Zgodnie z tą metodą, miara poprawnej estymacji wystąpienia połączenia dla wierzchołków x,y może zostać zwiększona poprzez wykorzystanie miary dla wierzchołków z,y, wiedząc, że wierzchołek x jest podobny do wierzchołka z. Miara wyznaczona może być poprzez dowolną z metod zaprezentowanych powyżej.

  • Clustering :

Jakość wykonywanych estymacji poprawiana może być poprzez usunięcie mniej istotnych krawędzi z wykorzystaniem procedury grupowania, a następnie uruchomienie metod predykcji na „wyczyszczonych” podgrafach.

Porównanie

Konfrontując w swoich badaniach działanie przedstawionych powyżej metod, Jon Kleinberg i Dawid Liben-Nowell, zbadali podobieństwo otrzymywanych przy ich pomocy wyników. Rezultat zaprezentowany został w tabeli 1.

Tabela 1

Analizując przedstawione dane, zaobserwować można podobieństwo pomiędzy estymacją dokonywaną przy pomocy metod Katz, Adamic/Adar oraz Low-Rank. Podobnie, analogie widoczne są również w działaniu miar Rooted PageRank, SimRank oraz Jaccard. Podejściem dającym rezultaty zdecydowanie odbiegające od pozostałych jest metoda Hitting time.
Niezależnie jednak od zastosowanej metody, należy zwrócić uwagę na fakt, iż wykonane estymacje cechuje dość niski poziom poprawności, co widoczne jest na podstawie danych zawartych w tabeli 2.

Tabela 2

Konkluzje
Opisane powyżej przybliżenia pozwalają skupić się na różnych miarach podobieństwa opartych na topologii grafu. W większości przypadków, zadanie prognozowania połączeń sprowadza się jedynie do problemu istnienia połączenia. Zadanie to może stać się jednak bazą do rozwiązania pozostałych problemów, związanych ze znaczeniem połączeń, ich siłą oraz liczbą.
Zważając na fakt popularności oraz dynamiczności wzrostu sieci społecznościowych, zrozumienie mechanizmu, zgodnie z którym następuje ich rozwój, jest niezwykle istotne i może przynieść wiele korzyści. Przykładowo w serwisach społecznościowych typu Facebook, czy Twitter, przewidywanie połączeń wykorzystywane jest w celu polepszenia systemu sugerowania nawiązywania kontaktów. Odchodząc od popularnych portali, problem prognozowania połączeń może zostać wykorzystany również do automatycznego kreowania linków, budowania systemów rekomendacyjnych, uzupełniania i tworzenia bibliografii, jako pomoc dla badaczy w poszukiwaniu ekspertów oraz dokumentacji związanych z danym obszarem zainteresowań, a nawet do identyfikowania grup przestępczych. Niezwykle ciekawym zastosowaniem przewidywania połączeń może być zastosowanie go w ramach realizacji projektów grupowych, gdzie organizacje mogą posłużyć się odpowiednimi metodami formując bardziej efektywne grupy.
Jakkolwiek zaprezentowane miary cechuje niska trafność przewidywania, z powodzeniem mogą one zostać wykorzystane w bardziej zaawansowanych algorytmach klasyfikacji.

Źródła:
http://www.cs.cornell.edu/home/kleinber/link-pred.pdf
http://www.cs.rpi.edu/~zaki/PaperDir/SNDA11.pdf

Opracowała: Joanna Skotarczyk

David Liben-Nowell, & Jon Kleinberg (2003). The Link Prediction Problem for Social Networks Journal of the American society for information science and technology DOI: 10.1002/asi.20591

Reklamy

One Comment to “Krótkie spojrzenie na problem prognozowania połączeń w sieciach społecznościowych z wykorzystaniem miar opartych na modelu grafowym”

  1. Ciekawy artykuł:) Poszukując grafów, połączeń między stronami natknąłem się także na: http://www.lome.pl/2011/07/gephi-1-narysuj-graf-spoleczny-i-pokoloruj-kregi-znajomych/ i na stronę: http://www.wordstream.com/blog/ws/2011/02/23/visualizing-link-flow Może się przydać:)

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: