Wróg mojego wroga – moim przyjacielem?

- autor: tsissput

Większość badań dotyczących sieci społecznościowych koncentruje się na analizie wyłącznie relacji pozytywnych występujących w sieciach. Chociaż związki negatywne, takie jak wrogość czy brak zaufania mają równie istotny wpływ na funkcjonowanie społeczności. Autorzy artykułu „Predicting Positive and Negative Links in Online Social Networks” przyglądają się związkom obu rodzajów w rzeczywistych społecznościach internetowych. Proponują model umożliwiający przewidywanie relacji między dwoma użytkownikami na podstawie ich sąsiedztwa.

Możliwość oceny relacji między użytkownikami byłaby przydatna w systemach rekomendowania przyjaciół. Dzięki temu można by uniknąć sugerowania osób, które pomimo iż dzielą niektóre zainteresowania, czy mają wspólnych znajomych, darzą się antypatią.

Badania zostały przeprowadzone na trzech zbiorach danych, w których znane są wszystkie krawędzie pozytywne oraz negatywne. Pierwszy zbiór powstał na bazie portalu Epinions, gdzie użytkownicy piszą recenzje najróżniejszych produktów. Każdą recenzję można uznać za budzącą zaufanie lub nie, na podstawie tych ocen budowana jest sieć zaufania pomiędzy użytkownikami. Kolejny zbiór danych stanowią użytkownicy portalu Slashdot, którzy w ramach Slashdot zoo mogli oceniać innych użytkowników jako przyjaciół lub wrogów. Analizowane relacje w społeczności portalu Slashdot są semantycznie bardzo zbliżone do sieci zaufania z Epinions. Trzeci zbiór danych pochodzi z Wikipedii, a są nim użytkownicy i ich głosy podczas podejmowania decyzji o przyznaniu danej osobie statusu administratora. Poniższa tabela pokazuje rozmiary analizowanych zbiorów danych. Warto zauważyć, że we wszystkich trzech przypadkach przeważa liczba relacji pozytywnych.

Epinions Slashdot Wikipedia
Użytkownicy 119 217 82 144 7 118
Relacje 841 200 549 202 103 747
% pozytywnych 85% 77,4% 78,7%
% negatywnych 15% 22,6% 21,2%

Zadaniem jakie postawili przed sobą autorzy artykułu jest przewidywanie rodzaju relacji pomiędzy dwoma członkami społeczności, na podstawie znanych relacji w sieci. Do rozwiązania problemu odwołali się do algorytmów uczenia maszynowego.  Wyznaczyli dwie główne klasy cech na podstawie których następnie przewidywali znak relacji pomiędzy dwiema osobami. Pierwsza grupa cech opiera się na ogólnej analizie relacji w jakie wchodzą ze społecznością rozważani użytkownicy. Poszczególne cechy to np. ilość osób mających pozytywną opinię o danym użytkowniku, czy liczba członków społeczności, którym dany użytkownik nie ufa. Z kolei druga klasa cech, ma swoje podłoże w zasadzie psychologii społecznej, mówiącej że, relację między dwoma osobami można zrozumieć poprzez ich związki ze wspólnymi osobami trzecimi. Cechy z tej grupy są liczbami występujących w sieci społecznej relacji pomiędzy analizowanymi osobami za pośrednictwem innego członka. Przykładowo liczba związków, gdzie obie rozważane osoby darzą sympatią jakąś wspólną osobę trzecią. Sumarycznie autorzy wybrali 23 różne cechy do analizy. Do klasyfikacji relacji wykorzystali model regresji logistycznej.

Trafność klasyfikacjiWyniki 10-krotnej walidacji zostały przedstawione na towarzyszących wykresach, odpowiadających kolejno wynikom na zbiorach Epinions, Slashdot oraz Wikipedia. Cztery grupy słupków przedstawiają kolejno sposób predykcji znaku relacji: losowe zgadywanie, uczenie maszynowe w oparciu o cechy dwóch omawianych klas z osobna, a na końcu wykorzystując wszystkie wymienione cechy. Kolor słupka oznacza minimalną liczbę wspólnych znajomych u analizowanych użytkowników; niebieski oznacza co najmniej 25 wspólnych znajomych, zielony – 10, a czerwony nie wprowadza żadnych ograniczeń. W większości przypadków najlepsze wyniki uzyskują cechy z drugiej klasy oraz wykorzystanie wszystkich cech. Warto zauważyć że dla użytkowników połączonych przez większą liczbę osób trzecich predykcja jest o znacznie skuteczniejsza w portalach Epinions oraz Slashdot.

Następnie autorzy artykułu porównali model powstały w wyniku uczenia maszynowego z kilkoma znanymi teoriami z zakresu psychologii społecznej. Przedmiotem ich porównań były dwie główne teorie opierające się na analizie relacji między trójkami osób. Pierwsza z nich, teoria równowagi strukturalnej opisuje popularne reguły: „Przyjaciel mojego przyjaciela jest moim przyjacielem” czy „Wróg mojego wroga jest moim przyjacielem”. Teoria ta mówi, że w każdej trójce znających się osób występuje nieparzysta ilość pozytywnych relacji. Drugą analizowaną teorią jest teoria statusu, w której mówimy, że jeśli istnieje pozytywny łuk od osoby u do osoby v, to osoba v ma wyższy status. Jednocześnie negatywny łuk świadczy o niższym statusie wskazywanej osoby, a więc jeśli odwrócimy łuk, odwróci się również znak relacji. Status relacji osób u i v poprzez osobę trzecią w, definiujemy jako suma łuków (u,w) oraz (w,v).

Po porównaniu predykcji obu teorii z modelami wyuczonymi w wyniku eksperymentu, okazało się że dla zbiorów danych Epinions i Slashdot obie teorie charakteryzują się podobnymi rozbieżnościami w stosunku do obliczonego modelu. Natomiast dla zbioru Wikipedia, teoria równowagi strukturalnej nie zgadza się w prawie połowie przypadków z modelem wyuczonym. Prawdopodobnie przyczynia się do tego nieco inny rodzaj relacji w badanych portalach. Na Wikipedii użytkownicy mogą być rzeczywiście bardziej skłonni do udzielenia poparcia, w drodze na stanowisko administratora, osobom które wzbudzają w nich szacunek, mają wyższy status. Do ciekawszych wniosków na temat teorii równowagi można zaliczyć również spostrzeżenie iż reguła „Wróg mojego wroga jest moim przyjacielem” nie zachodzi w żadnej z badanych sieci społecznościowych. Często wręcz mamy sytuację odwrotną – dwie negatywne krawędzie przyciągają trzecią.

Operując na trzech różnych zbiorach danych trudno uniknąć pytania, na ile model nauczony na sieci społeczności jednego z portali można odnieść do sieci istniejących w pozostałych portalach. Jednym słowem, na ile model regresji na analizowanych cechach można zgeneralizować? Poniższa tabela przedstawia wyniki trafności, gdy nauczymy model na jednym zbiorze danych a do ewaluacji wykorzystamy inny zbiór. Model nauczony jest na zbiorze podanym w wierszu, natomiast testowany na zbiorze podanym w kolumnie. W przekątnej macierzy znajdują rezultaty walidacji leave-one-out. Można zauważyć niewielką różnica w trafności klasyfikacji klasyfikatora wyuczonego na testowanym zbiorze w stosunku do klasyfikacji na innym zbiorze. Przykładowo w wyniku walidacji krzyżowej zbiór Slashdot uzyskał trafność 93,51%, natomiast przy wykorzystaniu klasyfikatora nauczonego na innym zbiorze osiąga wyniki nie gorsze niż o 1 punkt procentowy. Dodatkowo pomimo, że na zbiorze Wikipedia w ogólności uzyskiwana jest gorsza trafność, klasyfikator wyuczony na nim osiąga bardzo dobre wyniki na pozostałych zbiorach. Obserwacje te świadczą o dość dużym podobieństwie badanych zbiorów pod względem cech wykorzystanych w uczeniu maszynowym. Można powiedzieć że autorom artykułu udało się uzyskać modele dobrze generalizujące się.

Trafność klasyfikatorów na pozostałych zbiorach

Wspomniane wcześniej teorie równowagi i statusu, mają też swoje uogólnione sformułowania. Rozważając całą sieć społeczności, można powiedzieć że reguła równowagi jest zachowane, jeśli jesteśmy w stanie wyznaczyć dwie grupy, w których występują same pozytywne relacje, a które połączone są samymi negatywnymi relacjami. Z kolei teoria statusu mówi nam że w grafie sieci społecznej będzie istniał pewien ustalony porządek łuków pozytywnych. Autorzy artykułu postanowili sprawdzić na ile te uogólnione zasady są spełnione w analizowanych przez nich zbiorach danych. Dla porównania zbudowali zbiory danych będące losowymi modyfikacjami analizowanych sieci społecznych. Następnie za pomocą prostych heurystyk obliczyli stopień zachowania globalnej teorii równowagi oraz statusu w z rzeczywistych zbiorach oraz zbiorach kontrolnych. Okazało się, że w żadnej z analizowanych sieci nie udało się odnaleźć dwóch zwalczających się frakcji, na które wskazywałaby teoria równowagi. W zbiorach zaburzonych losowymi zmianami osiągano wręcz lepsze rezultaty. Natomiast w przypadku teorii statusu zaszła sytuacja odwrotna – badane sieci społeczne zachowywały uporządkowanie wyraźnie lepiej od swoich losowych mutacji.

Po więcej szczegółów i pominiętych tu dodatkowych spostrzeżeń zachęcam do odwołania się do treści samego artykułu.

84791

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: