Scott Tiger Tech Blog

Blog technologiczny firmy Scott Tiger S.A.

Analiza sieci społecznościowych

Autor: Piotr Karpiuk o czwartek 9. Sierpień 2012

Poniżej moje notatki z książki Social Network Analysis for Startups, Maksim Tsvetovat i Alexander Kouznetsov, O’Reilly 2011.

Wstęp

Analiza Sieci Społecznościowych (ang. Social Network Analysis, SNA) to studiowanie więzi międzyludzkich w rozumieniu teorii grafów. Nasze relacje definiują kim jesteśmy i jak działamy. Nasza osobowość, wykształcenie, rasa – wszystko to wpływa na wzorce naszych powiązań z innymi ludźmi i zostawia trwałe ślady. Obserwując i studiując te wzorce możemy odpowiedzieć na wiele pytań dotyczących społeczności.

Relacja (ang. relationship) to może być przyjaźń, protekcja, afekt, zaufanie – albo przeciwnie: niechęć, konflikt lub wiele innych rzeczy. Relacje mogą być binarne („Max śledzi Aleksa na Twitterze”) lub skalarne (ang. valued) – np. „Max odpowiedział na 4 tweety Aleksa”. W świecie Twittera siła relacji jest dość łatwa do zmierzenia, ale w bardziej „miękkich” sieciach społecznościowych z pomiarem jakości relacji mogą być duże kłopoty. Użytecznym wskaźnikiem siły powiązania między ludźmi jest częstotliwość komunikacji. Pewne relacje są z natury asymetryczne (np. szef/pracownik), inne (jak śledzenie na Twitterze) mogą przekształcić się w symetryczne. W końcu, relacje mogą łączyć obiekty różnych typów (korporacje zatrudniają ludzi, ludzie posiadają zasoby itp.) – mówimy wtedy o relacjach bimodalnych (ang. bimodal, 2-mode)

Typowe podejście statystyczne zakłada niezależność zdarzeń. W sieciach społecznościowych takie założenie nie musi być prawdziwe – intuicja podpowiada nam przypadki gdy A spotyka B ponieważ oboje znają C. SNA zakłada istnienie potencjalnych zależności pomiędzy każdymi dwiema osobami. Takie założenie czyni tradycyjne podejście statystyczne (regresja, łańcuchy Markowa) trudnymi w zastosowaniu i mało przydatnymi, ale pokażemy nowe metody które lepiej sprawdzają się w interesujących nas przypadkach.

Dziedziną pokrewną do SNA jest Link Analysis (LI). Różnica jest taka, że o ile w SNA mamy ludzi i powiązania między nimi, to LI pozwala na różnego typu wierzchołki i różnego typu powiązania, pozwalając na wyrażenie takich faktów jak np. „A dał $300 dla B aby uzyskać narkotyki dla C„, przy czym słowa wytłuszczone są wierzchołkami (aktorami), a kursywą zapisano krawędzie (akcje).

Historyjka 1. Właściciel zatrudniającej kilkaset osób firmy ACME odszedł na emeryturę, zatrudniając na swoje miejsce osobę z zewnątrz, aby dopilnowała interesu. Nowy CEO zreorganizował firmę zgodnie z regułami sztuki, których uczył się na studiach. Niestety nowy schemat organizacyjny nie sprawdził się w praktyce, ponieważ – jak wykazał konsultant specjalista SNA – sieć społeczna firmy wyglądała zupełnie inaczej niż formalna hierarchia. Okazało się że nowy CEO cieszył się małym zaufaniem, a kluczową rolę odgrywała jedna ze starszych pań sekretarek, pracująca od początku istnienia firmy, a teraz zepchnięta na marginalną funkcję. Została ona przeniesiona do kwatery głównej, powierzono jej funkcję nadzorcy i nauczyciela młodszych pracowników – firma została uratowana. Nieraz gdy opowiadam tę historyjkę studentom lub innemu audytorium, słyszę pytanie: „Jak można zapobiegać powstawaniu nieformalnych powiązań?”. Odpowiedź jest prosta: nie da się.

Historyjka 2. Więzienie Butyrka w Moskwie cieszy się wyjątkowo złą sławą. Władze zabraniają jakichkolwiek kontaktów pomiędzy celami i surowo karają izolatką za naruszenie zakazu. Grube ściany uniemożliwiają komunikację głosową, nie ma też wspólnego miejsca do odbywania spacerów. Okazało się, że nawet w takich okolicznościach rozwinęła się sieć społeczna: niewielkie paczki mieszczące się w kracie, z etykietką nadawcy i odbiorcy, były przesyłane za oknem przy pomocy lin, a także (po zabezpieczeniu torebką foliową) przy użyciu kanalizacji. Opracowano nawet mechanizm rozgłaszania komunikatów: gdy jeden z więźniów okazywał się być konfidentem, rozpowszechniano wiadomość aby daną osobę odpowiednio traktować.

Historyjka 3. Rewolucja w Egipcie w 2011 roku jest często nazywana „Rewolucją Twitterową”, ale to nie jest pierwsze polityczne powstanie w którym media społecznościowe odegrały dużą rolę (wcześniej była Mołdawia w 2009 i powstanie w Iranie) – choć niewątpliwie tutaj efekt był największy. Jak to się stało że media społecznościowe stały się tak potężne? Odpowiedź leży w zdolności mediów społecznościowych do utrzymywania i wzmacniania słabych więzi. Słabe więzi są definiowane jako powiązania społeczne między ludźmi które charakteryzują się małym lub żadnym emocjonalnym aspektem, pewną zgodą co do podstawowych zasad (ale małym ogólnym podobieństwem między ludźmi), niską częstotliwością komunikacji – krótko mówiąc, wymagają przeznaczania niewielkich ilości czasu i energii na pielęgnację. W praktyce okazuje się, że sieć takich luźnych powiązań pozwala przekazywać informacje na bardzo dalekie dystanse, przekraczające granice wyznaczane przez wysokość dochodu czy poglądy. Słabe więzi okazują się niezwykle istotne przy szukaniu pracy. Z drugiej strony, prawdopodobieństwo że słabe wiązanie okaże się użyteczne jest dość małe, podczas gdy koszt pielęgnacji takiego połączenia jest niezerowy – ludzie wydają się podlegać biologicznym granicom w kwestii ilości ludzi z którymi mogą się komunikować, a ten kognitywny limit wynosi ok. 150 (wariancja jest spora) i wydaje się być większy w organizacjach, małych miejscowościach, jednostkach wojskowych itp.

Sieci społecznościowe takie jak Twitter znacząco zmniejszają koszty utrzymywania dużej liczby słabych więzi (łatwiej aktualizować swój status na Twitterze i przeglądać strumień aktualizacji innych, niż dzwonić do każdego z osobna z pytaniem co słychać). Co więcej, możliwość śledzenia (ang. follow) na Twitterze pozwala na relacje jednostronne i komunikację rozgłoszeniową – Twitter może zmienić zwykłych ludzi w celebrytów, jeśli tylko znajdą się we właściwym czasie na właściwym miejscu – rozważmy przykład skromnego konsultanta IT będącego naocznym świadkiem akcji pojmania Osamy bin Ladena; przed akcją miał kilkuset śledzących jego statusy, po akcji trwającej 15 minut w wyniku nagłośnienia przez media – kilkaset tysięcy, a obecnie ok. stu tysięcy. Wszystkie te powiązania są oczywiście słabe.

W Twitterze tzw. retweet ma miejsce, kiedy użytkownik kopiuje i przesyła wiadomość autorstwa innego użytkownika dalej. Przyjmuje się, że retweet jest dowodem zaufania do nadawcy, więc śledzenia retweetów można użyć do ustalenia kto komu w sieci ufa. Rewolucja nie była skutkiem nawoływań dobrze znanych celebrytów – komunikaty miały źródło i znajdowały odzew w gęstych klastrach wypełnionych zwykłymi ludźmi myślącymi podobnie. Wael Ghonim, pracownik Google odgrywający na Tweeterze jedną z głównych ról w wydarzeniach w Egipcie, miał 80 tys. śledzących, ale każdy jego tweet generował średnio 3200 retweetów. Justin Bieber ma 7,5 mln śledzących go fanów, ale każdy jego tweet pociąga za sobą tylko 300 retweetów.

Teoria grafów

Zdanie „Alice lubi Boba” to tzw. diada, reprezentowana w grafie przez krawędź. W tym rozdziale będzie mowa wyłącznie o grafach w których wierzchołkami będą ludzie, grafy bimodalne i wielomodalne pojawią się odpowiednio w rozdziałach 5 i 6.

Co ciekawe, każda aplikacja społecznościowa przyjmuje nieco inną interpretację relacji „znajomego” w swoim grafie. Trudno więc wymieszać dane Facebooka, Twittera i LiveJournal bez pewnych semantycznych przekształceń.

Socjologowie w ankietach często posługują się tzw. skalą Likerta, dopuszczającą następujące możliwe odpowiedzi:

  1. nie wiem,
  2. zdecydowanie nie lubię,
  3. nie lubię,
  4. ani lubię, ani nie lubię,
  5. lubię,
  6. zdecydowanie lubię.

Niestety, użyteczność takiej skali w sieciach społecznościowych jest ograniczona – ludzie mają tendencję do wybierania odpowiedzi 4,5,6 w ocenie relacji międzyludzkich. Dużo lepsza jest skala Krackhardta, która pyta o częstotliwość komunikacji:

  1. nigdy,
  2. co najmniej raz w roku,
  3. co najmniej raz w miesiącu,
  4. co najmniej raz w tygodniu,
  5. co najmniej raz na dzień,
  6. wielokrotnie w ciągu dnia.

Jeśli kogoś nie lubisz, raczej nie komunikujesz się z nim częściej niż musisz. Poza tym, taka skala może być łatwo weryfikowana np. dzięki stemplom czasowym maili i innych komunikatów.

Gęstość grafu (ang. density) określa stosunek niezerowych komórek do zerowych w macierzy sąsiedztwa. Większość sieci społecznościowych w praktyce ma gęstość rzędu 0.1% lub mniejszą, co czyni reprezentację takiego grafu w postaci macierzy sąsiedztwa mało wydajną pamięciowo.

W bazie danych najłatwiej przedstawić graf w postaci listy krawędzi (ang. edge-list):

      from to value
      A    B  2
      A    D  5
      B    A  2
      D    A  5

Z kolei w pamięci najwygodniejszą strukturą jest lista sąsiedztwa (ang. adjacency list):

      from edges
      A    (B 2),(D 5)
      B    (A 2)
      D    (A 5)

Marszruta (ang. walk) to ciąg sąsiednich wierzchołków. Jest otwarta gdy pierwszy i ostatni wierzchołek są różne. Długość marszruty to liczba zawartych w niej krawędzi. Ścieżka to otwarta prosta (żaden wierzchołek nie jest przekraczany dwukrotnie) marszruta. Zamknięta prosta marszruta to cykl. Formalnie ścieżka może mieć długość 0, a cykl nie.

Algorytm Dijkstry dla danego wierzchołka znajduje ścieżki o najmniejszym koszcie do wszystkich pozostałych wierzchołków, gdzie koszt jest rozumiany jako suma wag krawędzi po drodze. Algorytm można też wykorzystać do obliczenia ścieżki o najmniejszym koszcie między dwoma wybranymi wierzchołkami grafu.

Odległość (ang. distance) w grafie jest abstrakcją marszruty – abstrahujemy od samego marszu poprzestając na ocenie jak daleko od siebie są wierzchołki, co już mówi nam w wielu przypadkach wystarczająco dużo o całym grafie.

Średnica grafu to odległość na jaką są oddalone dwa najodleglejsze wierzchołki grafu.

W grafie społecznościowym mówimy też o zasięgu (ang. reach) wierzchołka i jego autorytecie (ang. influence).

Architektura typowej sieci społecznościowej to gęste sieci lokalne („małe światy”, ang. small world networks) luźno połączone za pośrednictwem osób pełniących rolę łączników (ang. connectors).

Centralność, władza i wąskie gardła

W tym rozdziale poznamy cztery najpopularniejsze metryki, nauczymy się wizualizować je i łączyć.

LiveJournal to platforma blogowa bardzo popularna w Rosji i Europie Wschodniej. Obejmuje obecnie 38 mln blogów, w większości w językach innych niż angielski.

N.E. Friedkin zdefiniował pojęcie horyzontu obserwacyjnego (ang. horizon of observability), które mówi że dość dobrze znamy ok. 70% swoich znajomych, ale nasza wiedza o sieci dalszych powiązań spada gwałtownie. Znamy tylko 30% znajomych znajomych i praktycznie żadnych znajomych znajomych znajomych. Dlatego też, w miarę pełne otoczenie interesującej nas osoby obejmuje zaledwie 3 poziomy powiązań.

Centralność

Pierwsze podejście do analizy sieci społecznościowych to pomiar władzy (ang. power), autorytetu (ang. influence) i innych indywidualnych cech pojedynczych osób, w oparciu o ich wzorce powiązań z innymi. Tym niemniej, nie ma całkowitej zgody badaczy w kwesti tego co tak naprawdę znaczą pojęcia władzy czy autorytetu, ani jakie wzorce powiązań im odpowiadają. To zależy chociażby od semantyki powiązań pomiędzy ludźmi. Tutaj zrobimy sobie wycieczkę po metodach pomiaru tych dwóch pojęć (w żargonie określanych mianem „centralności”) i przedyskutujemy ich zalety i użyteczność.

Celebryci

Każda społeczność ma swoich „celebrytów” w rodzaju Paris Hilton czy Lady Gaga. Jest ich zwykle bardzo mało i cieszą się popularnością o rzędy wielkości większą od przeciętnych osób. Centralność stopnia (ang. degree centrality) opiera się na pojęciu stopnia wierzchołka grafu, czyli liczby krawędzi które posiada dany wierzchołek.

BTW: Scott Adams, twórca Dilberta, stwierdził że władza jaką ma osoba w organizacji jest odwrotnie proporcjonalna do liczby kluczy jakie ma w swoim breloczku. Woźny ma klucze do każdego pomieszczenia, ale żadnej władzy. Z kolei CEO nie potrzebuje żadnego klucza, bo wszyscy otwierają przed nim drzwi. Ale wtedy, oczywiście, przybywa Wszechmocny Woźny (ang. Almighty Janitor):

Gdybym kiedykolwiek został prezesem firmy, moją pierwszą decyzją biznesową byłaby promocja woźnego na stanowisko executive vice president. Wezwałbym go do swojego biura i powiedział:
– No dobrze, Janie, chcę żebyś mi powiedział o tym co się dzieje w firmie. Może drinka zanim zaczniemy? Chyba mam tu gdzieś butelkę Szkockiej
– Najniższa szuflada pańskiego biurka, tuż za pańskim pudełkiem cygar El Puffo, które – pozwolę sobie dodać – są wyśmienite.

Jeśli z grafu sieci społecznościowej usuniemy wszystkie wierzchołki o stopniu mniejszym niż – powiedzmy – 10, to otrzymamy rdzeń sieci. W przypadku LiveJournal jest tylko jeden rdzeń, ale typowym wynikiem dla sieci społecznościowych jest wiele rdzeni luźno ze sobą połączonych. Każdy z tych rdzeni może tworzyć własną subkulturę, mieć żargon, celebrytów itp. Więcej o wielordzeniowych sieciach w kolejnym rozdziale.

Plotkarze

Przyjmijmy sobie dwie kolejne definicje: ego odnosi się do głównego wierzchołka wokół którego koncentruje się nasze zainteresowanie, podczas gdy pojęcie alter odnosi się do do wszystkich pozostałych wierzchołków połączonych z ego.

Zdolność ego do odbierania i wysyłania informacji zależy od jego odległości od reszty sieci. Pojęcie horyzontu obserwacyjnego daje do zrozumienia że ego nie ma bezpośredniego wglądu w to co się dzieje dalej niż 3 poziomy. Zdolność do przenoszenia informacji z jednego krańca sieci do drugiego (tj. plotkowanie) jest ważnym krokiem w stronę tworzenia się wspólnej wizji świata, niezależnie od tego czy ma to związek z czyimś wyglądem na przyjęciu, czy tworzeniem się ruchu politycznego. Krótko mówiąc, odległość od innych definiuje rolę osoby w sieci. To spostrzeżenie leży u podstaw kolejnej metryki, tj. centralności bliskości (ang. closeness centrality).

Wyliczenie wartości metryki jest drogie obliczeniowo:

  1. Przy użyciu algorytmu Dijkstry oblicz najkrótsze ścieżki między każdymi dwoma wierzchołkami grafu.
  2. Dla każdego wierzchołka:
    1. oblicz średni dystans do pozostałych wierzchołków,
    2. podziel przez maksymalny dystans,
    3. centralność bliskości = 1 / średni dystans.

Wynik jest liczbą z przedziału 0 do 1, gdzie wyższe wartości oznaczają mniejszy średni dystans. Jeśli porównać tą metrykę z poprzednią, można zauważyć że najwyższe wartości otrzymują zwykle raczej inne osoby niż wcześniej. Na serwisie LiveJournal, o ile wcześniej na szczycie znajdowali się popularni pisarze i profesjonalni blogerzy, o tyle tutaj mamy do czynienia ze zwykłymi ludźmi którzy poświęcają dużo czasu na blogowanie i komentowanie postów innych osób. Także rozkład plotkarstwa jest zauważalnie inny niż bycia celebrytą – przypomina bardziej krzywą Gaussa.

Wąskie gardła i mosty

Osoba która znajduje się w wąskim gardle łączącym dwie różne podsieci społeczne niewątpliwie posiada pewną władzę (i jest narażona na stres). Jeden z autorów książki na przykład jest doktorem nauk komputerowych, ale jednocześnie rozwija swoje zainteresowania jako wzięty koncertujący muzyk jazzowy i rockowy.

Algorytm wyliczający kolejny rodzaj miary: betweenness centrality jest następujący:

  1. Przy użyciu algorytmu Dijkstry oblicz najkrótsze ścieżki między każdymi dwoma wierzchołkami grafu.
  2. Dla każdego wierzchołka X w sieci oblicz liczbę najkrótszych ścieżek na których znajduje się X.
  3. Znormalizuj wynik aby otrzymać wynik z zakresu od 0 do 1.

Im większa władza wierzchołka wynikająca z położenia w wąskim gardle, tym większa wartość wyniku.

Na ogół prawdą jest, że w każdej większej społeczności istnieje „elita” osób osiągających najwyższe wyniki w dwóch lub nawet wszystkich trzech omówionych do tej pory metrykach. Takie osoby są oczywiście łakomym kąskiem dla ludzi zajmujących się np. marketingiem.

No dobrze, a jak należy interpretować kombinacje wartości różnych metryk?

Metryka Niska stopnia Niska bliskości Niska betweenness
Wysoka stopnia Ego jest zawarte w klastrze daleko od reszty sieci Połączenia ego są redundantne – świat przemija obok
Wysoka bliskości Kluczowy gracz związany z innymi ważnymi/aktywnymi Ego jest w gęstym, aktywnym klastrze w centrum zdarzeń – z wieloma innymi osobami

Szare eminencje

Don Corleone, fikcyjny mafioso z powieści Ojciec chrzestny, nie miał zbyt wielu silnych relacji. Był mrukiem, ale mimo to mógł składać oferty którym nie można było odmówić. Corleone otaczał się synami i zaufanymi capo, którzy z kolei zajmowali się codziennymi sprawami rodziny. Gdybyśmy zaaplikowali nasze metryki do omawianej osoby, okazałby się człowiekiem praktycznie niewidocznym w sieci – co zresztą jest kluczowe dla organizacji jaką stworzył. Pozycja Don Corleone ma władzę; znając dobrze połączonych ludzi, może wykorzystywać tą informację aby realizować swoje plany pozostając w cieniu.

Skoro w sieciach społecznościowych istnieją szare eminencje, musi być jakaś metryka żeby je wykryć! Philip Bonacich zaproponował żeby zamiast liczyć liczbę „znajomych” ego, lepiej mierzyć liczbę znajomych jego znajomych (ci, którzy znają właściwe osoby są bardziej prawdopodobnymi kandydatami na szare eminencje niż ci, którzy nie są tak dobrze podłączeni w sieci). Taka metryka nosi miano centralności wektora własnego (ang. eigenvector centrality) i jest poniekąd rekurencyjną wersją centralności stopnia.

Algorytm z grubsza wygląda tak:

  1. przypisz wartość 1 do każdego węzła (v_i = 1 dla każdego i),
  2. przelicz wartość każdego wierzchołka jako sumę ważoną centralności wszystkich wierzchołków w otoczeniu wierzchołka: v_i = suma po j (x_i_j * v_j),
  3. znormalizuj v dzieląc każdą wartość przez wartość największą,
  4. powtarzaj kroki 2 i 3 aż wartość v przestanie się zmieniać.

Aktor który ma wysoką wartość centralności wektora własnego, jest podłączony do wielu aktorów podłączonych do wielu aktorów. Niestety, mamy problem z wydajnością obliczeń: każda iteracja algorytmu to koszt rzędu liczba wierzchołków * średni stopień, iteracji może być kilkaset – wniosek: ta metryka jest nierealna w naprawdę dużych sieciach. Osoba, która ma małą wartość metryki stopnia, wysoką betweenness i wektora własnego, łączy dwie gęste sieci, nie będąc aktywnym członkiem żadnej z nich.

Klout Score (http://klout.com) jest metryką wyliczaną na podstawie całej Twojej aktywności w mediach społecznościowych. Jest to jednak zasadniczo metryka stopnia, faworyzująca celebrytów. Nie uwzględnia wąskich gardeł, czy gęstych klastrów rozdzielonych od siebie poprzez używany język. Lady Gaga może i jest wpływowa w kręgach popkultury, ale czy również wśród francuskich naukowców? Aplikacja niezróżnicowanej metryki do bardzo szerokiej sieci społecznościowej daje wyniki trudne do interpretacji w specyficznych kontekstach.

PageRank

Zauważmy, że koncepcja PageRank w wyszukiwarce Google’a wywraca świat do góry nogami. Tutaj centralność zamiast „promieniować z” wierzchołka i być jedną z jego własności, jest wnioskowana na podstawie przychodzących linków. PageRank został pierwotnie stworzony na potrzeby indeksowania stron w Internecie, ale równie dobrze może być użyty do sieci społecznościowych, o ile tylko mamy do czynienia z grafem skierowanym (krawędź ma kierunek), jak w Twitterze. Wartość PageRank waha się od 0 do 1 i oznacza prawdopodobieństwo że osoba chodząca po sieci trafi na konkretną stronę. PageRank 0.5 strony X oznacza prawdopodobieństwo 50%, że osoba klikająca na losowym linku zostanie przekierowana na stronę X.

PageRank jest procesem iteracyjnym – w dowolnym momencie można otrzymać wynik, ale im więcej damy mu czasu, tym lepsza jest jakość tego wyniku – aż do osiągnięcia punktu stabilizacji (konwergencji). W tym sensie PageRank jest podobny do metryki wektora własnego, ale algorytm skaluje się znacznie lepiej do wielkich sieci zmieniających się w czasie.

Co tak naprawdę mierzy PageRank w sieciach społecznościowych? Coś w rodzaju przepływu zaufania (ang. flow of trust). O ile jego wyliczenia mają charakter lokalny (brane są pod uwagę tylko sąsiednie wierzchołki), jego iteracyjna natura pozwala na propagację globalnego wpływu na całą sieć – zupełnie jak w świecie rzeczywistym.

Narzędzia SNA potrafią wyliczyć PageRank dla wierzchołków sieci społecznościowych.

Czego metryki nie mówią?

Nie mówią, jak (ani dlaczego) wizjoner jest otaczany przez nowicjuszy, jakie siły popychają ludzi do wyboru stron w debatach, ani jakie siły scalają sieć lub ją rozrywają. Aby się tego dowiedzieć, musimy zajrzeć głębiej. W kolejnym rozdziale przyjrzymy się triadom, niewątpliwie najmniejszym grupom ludzi zdolnym tworzyć „społeczność”. Z tych triad utworzymy większe kliki i klastry, nauczymy się odnajdywać je w rzeczywistych danych, a także zobaczymy dokąd nas to zaprowadzi.

Kliki, klastry i komponenty

Podgraf to podzbiór wierzchołków sieci i wszystkich krawędzi które łączą te wierzchołki. Z kolei komponenty to fragmenty sieci odłączone od innych.

Sieć ego to podgraf wycentrowany na określonym wierzchołku, o głębokości 3; na serwisach takich jak Facebook czy LinkedIn, to po prostu „twoja sieć” do poziomu „znajomi znajomych znajomych”. Rozmiar sieci ego określa bogactwo informacji do której osoba ma dostęp.

Współczynnik klastrowania (ang. clustering coefficient) mierzy odsetek znajomych którzy są znajomymi między sobą (tj. jaką ilość wzajemnego zaufania ludzie mają do siebie). Ta metryka może być aplikowana do całej sieci, ale z uwagi na różną gęstość i wiele rdzeni taki współczynnik jest trudny do interpretacji. W sieciach ego interpretacja jest prosta: gęste sieci ego z dużą ilością wzajemnego zaufania mają wysoką wartość współczynnika. Sieć ego celebryty będzie miała niską wartość.

Triadą nazywamy graf składający się z trzech wierzchołków. W przypadku grafów nieskierowanych mamy 4 rodzaje triad, a dla grafów skierowanych jest ich 16 i w literaturze mają one swoje nazwy, jak pokazuje rysunek:

Strukturalna dziura, struktura pośrednictwa, zakazana triada – to trzy określenia takiej triady w której B zna A i C, ale A i C się nie znają. Czasem lepiej żeby się nie znały, jak w przypadku gdy A i C są kochankami B, albo A i C są bankami, a B wykorzystuje różnice w oprocentowaniu lokat i pożyczek żeby żyć dostatnio. Ron Burt pokazał w swoich studiach, że biznesmeni utrzymujący wiele strukturalnych dziur mają większe szanse na sukces na wolnym rynku.

Spis triad (ang. triad census) to proces w którym dla każdego wierzchołka sieci wyliczamy wystąpienia każdego rodzaju triad, aby w ten sposób ustalić rolę wierzchołka w strukturze sieci. Przykładowo, wierzchołek z wieloma wystąpieniami 4, 7 i 11 jest źródłem informacji i prawdopodobnym liderem grupy. Przydatne jest również porównanie liczby triad każdego typu w całym grafie, np. hierarchie zawierają wiele strukturalnych dziur, a struktury egalitarne będą miały więcej triad zamkniętych.

W powszechnym rozumieniu kliką (ang. clicque) nazywamy spójną grupę silnie powiązanych ludzi (i jednocześnie luźniej powiązanych z otoczeniem). Formalnie definiujemy klikę jako maksymalnie kompletny podgraf danego grafu, tj. grupę ludzi gdzie każdy jest bezpośrednio połączony z każdym. Ludzie w klice wypracowują konsensus, inaczej klika się rozpada – w praktyce często występują konflikty między klikami. W rzeczy samej posiadanie wspólnego wroga silnie jednoczy klikę.

Mając jakoś zdefiniowaną metrykę odległości między dowolnymi dwoma wierzchołkami, możemy zapuścić algorytm hierarchicznego klastrowania (ang. hierarchical clustering) aby połączyć blisko związane ze sobą wierzchołki w grupy.

  1. Na początku, każdy wierzchołek stanowi osobny klaster.
  2. Używając metryki odległości, znajdujemy dwa klastry najmniej odległe od siebie i łączymy je w jeden klaster.
  3. Przeliczamy metryki odległości, traktując nowy klaster jako nowy wierzchołek.
  4. Powtarzamy kroki 2 i 3, aż wszystkie wierzchołki sieci zostaną połączone w jeden wielki klaster.
  5. Wybierz użyteczny próg klastrowania pomiędzy najniższym a najwyższym poziomem algorytmu – to wymaga udziału człowieka-analityka, i niestety nie może zostać zautomatyzowane.

Sieci bimodalne

Zajmijmy się sieciami z dwoma rodzajami wierzchołków. Mogą to być np. ludzie i organizacje, ludzie i lubiane przez nich strony w Internecie itp.

Rozważmy przypadek sieci, gdzie mamy ludzi (wierzchołki A-H) i tematy które ich interesują (1-3). W poniższym rysunku jest to graf na górze.

W dolnej części rysunku mamy dwa grafy afiliacji. Są to grafy 1-modalne (każdy z wierzchołkami jednego typu): pierwszy to graf ludzi gdzie połączenia są wyznaczone przez wspólne zainteresowania, a drugi to graf zainteresowań gdzie połączenia są wyznaczone przez współprzynależność ludzi do nich. Aby utworzyć te sieci, wystarczy po prostu policzyć współprzynależność każdej pary osób do tych samych zainteresowań – lub, odpowiednio, ile jest osób współprzynależących do każdej pary tematów. Co ciekawe, jeśli graf przedstawimy jako macierz sąsiedztwa A, to macierz sąsiedztwa grafu afiliacji otrzymamy wykonując mnożenie macierzy: A i A transponowanego.

Zauważmy, że mając graf afiliacji ludzi utworzony z grafu ludzi i ich zainteresowań, możemy użyć metody hierarchicznego klastrowania do wyznaczenia ludzi o podobnych zainteresowaniach, np. po to aby zaproponować znajomości każdemu z użytkowników naszego portalu społecznościowego.

W praktyce, oczywiście, mamy często do czynienia z sieciami wielomodalnymi (z wierzchołkami wielu typów). Technikę mnożenia macierzy możemy łatwo rozszerzyć na dowolny sieciowy model danych. Możemy sobie np. wyobrazić graf przedsiębiorstwa, gdzie mamy pracowników, ich umiejętności, zasoby i zadania do wykonania. Taki graf możemy rozbić na szereg grafów bimodalnych, jak w poniższej tabeli (dwuliterowa nazwa to nazwa macierzy sąsiedztwa grafu):

People Skills Resources Tables
People PP: Kto zna kogo? PS: Kto się na czym zna? PR: Kto ma jakie zasoby? PT: Kto co robi?
Skills SS: Jakie umiejętności występują razem? SR: Jakie umiejętności są wymagane dla zasobów? ST: Jakie umiejętności są potrzebne do wykonania zadania?
Resources RR: Jakie zasoby występują razem? RT: Jakie zasoby są potrzebne do wykonania zadania?
Task TT: Jaka jest kolejność wykonywania zadań?

Każda z macierzy to po prostu tabela, gdzie zapisujemy np. czy Joe potrafi pracować na tokarce, albo czy Joe ma dostęp do metalu. Teraz możemy się zabawić: mnożymy macierze i otrzymujemy nowe grafy. Zauważmy że możemy mnożyć całe ciągi macierzy przeprowadzając dalekosiężne wnioskowania, np.:

  • PP * PP = PP: Nowa sieć odpowiada na pytanie: „kim są przyjaciele przyjaciół?”
  • PT * PTt = PT * TP = PP: co oznacza: „kto pracuje razem, i nad iloma zadaniami?”
  • PT * TT = PT: Dla każdej osoby, jakie zadania są na jej krytycznej ścieżce?
  • TT * TT = TT: Niezależne zadania
  • PT * TT * TP = PP: Jacy ludzie są na ścieżce krytycznej każdej osoby?
  • PT * TT * TT’ * TP = PP: Kto pracuje razem nad równoległymi zadaniami?

Zanim zaczniesz używać nowej wiedzy w praktyce, weź pod uwagę jedno zastrzeżenie: nie ma biznesu, choćby nie wiem jak dobrze funkcjonującego, dla którego moglibyśmy ustalić kompletny obraz modelu biznesowego i sieci społecznej. Jeśli zaprojektujesz sobie idealną sieć przedsiębiorstwa, to prawie na pewno będzie ona obchodzona przez nieformalne związki między ludźmi.

Wirusowe rozprzestrzenianie się informacji

Wielu ludzi chciałoby wiedzieć co powoduje że niektóre filmy, portale, nowinki itp. wirusowo rozprzestrzeniają się po sieci stając się elementem kultury i czyniąc autorów sławnymi (a czasem nawet bogatymi). Nie mamy gotowej recepty, ale w tym rozdziale spróbujemy zrozumieć co napędza rozprzestrzenianie się informacji i jak Twoje decyzje mogą wpłynąć na przyjęcie produktu przez społeczność.

Jakościowe przejście pomiędzy „nieciekawe” a „musisz to zobaczyć” jest widoczne na wykresie w postaci punktu przegięcia, znanego jako masa krytyczna. O ile przed nim mem rozprzestrzeniał się liniowo, od tej pory popularność rośnie wykładniczo aż do punktu nasycenia, gdy prawie każdy już to widział. Potem popularność produktu słabnie. Oczywiście w jednej sieci nasz mem może osiągnąć punkt nasycenia, podczas gdy w innej nie osiągnie nawet masy krytycznej. Tym niemniej, ponieważ społeczności są mniej lub bardziej luźno połączone, mem ma szanse przeskoczyć z jednej sieci do drugiej.

Jeden z pierwszych serwisów społecznościowych: SixDegrees, uruchomiony w 1997 roku, miał służyć do komunikacji między znajomymi w USA i nawiązywania kontaktów z ludźmi określonych specjalności: najlepszymi prawnikami, lekarzami, hydraulikami itp. Niestety, witryna mimo że świetnie zaprojektowana (jak na owe czasy) oraz dobrze rozreklamowana w mediach tradycyjnych w całym kraju i w internecie, nigdy nie osiągnęła masy krytycznej. Powstała 5 lat za wcześnie, gdy naprawdę niewielu hydraulików korzystało z Internetu lub w ogóle myślało o tym, a gęstość połączeń między ludźmi w ówczesnym Internecie była mała.

Gdy Facebook wystartował w 2003 roku, był ograniczony do małej gęstej społeczności studentów Harwardu, gdzie szybko osiągnął masę krytyczną. W ciągu 4 godzin od uruchomienia witryna przyciągnęła 450 gości, czyli ok. 6% studentów. Zapamiętaj tą liczbę 6%; ona jest ważna. Z czasem na portal zaglądało już 50% studentów uczelni, i zaczął obsługiwać najpierw pozostałe uczelnie Ligi Bluszczowej, a wkrótce potem wszystkie uniwersytety w USA. Zwróćmy uwagę na różnice między SixDegrees a FB: Facebook najpierw osiągnął punkt nasycenia w małej społeczności zanim się rozprzestrzenił na inne społeczności. W ten sposób masa krytyczna nie słabła a nowi użytkownicy portalu dołączali do społeczności składającej się z rówieśników z innych szkół. Dla wielu założycieli startupów to jest nieintuicyjne – chcieliby od razu rozpowszechnić swój produkt na maksymalnym polu.

Jest jeszcze jeden aspekt do rozważenia w kontekście problemu masy krytycznej – chodzi o koszt wzięcia udziału w zabawie. Ten koszt zawsze jest – nie tylko w postaci pieniędzy (jak w przypadku mody na iPhone’y), ale choćby w postaci czasu spędzonego na FB zamiast w kinie. Ten koszt niestety utrudnia osiągnięcie etapu masy krytycznej.

W naszych eksperymentach odkryliśmy, że przejście ze wzrostu liniowego rozprzestrzeniania się memu do wzrostu wykładniczego następuje w okolicy momentu w którym ok. 7-9% docelowej społeczności zaakceptuje mem (wykonało retweet w Twitterze, zapisało się na witrynę itp.) – wówczas reszta ludzi dołączy szybko w wirusowym tempie.

Ilościowa analiza sieci społecznościowych nie pozwala odpowiedzieć na pytanie co czyni komunikat szczególnie interesującym dla odbiorców. Z doświadczenia można powiedzieć, że „Content is King” (treść jest najważniejsza), i choć pojawiło się wiele reguł typu „witryna powinna być tak skonstruowana aby użytkownik mógł maksymalnie 6-ma kliknięciami myszki dostać się do potrzebnych informacji, a najważniejsze informacje powinny być wyświetlane na górze strony tak aby nie trzeba było przewijać ekranu”, to w sytuacji gdy treść jest wciągająca reguły te tracą znaczenie – ludzie będą klikać i przewijać jeśli tylko dojdą do wniosku że im się to opłaca.

Jak informacja kształtuje sieć (i vice versa)?

Zjawisko homofilii oznacza spontaniczne (czy też: nieprzypadkowe) tworzenie powiązań pomiędzy wierzchołkami w jakiś sposób podobnymi do siebie. Wyróżnić możemy dwa typy zjawiska: homofilia statusu (ang. status homophily) dotyczy tworzenia powiązań między ludźmi wywodzącymi się z podobnej klasy społecznej, mającymi podobny majątek i status; z kolei homofilia wartości (ang. value homophily) dotyczy kojarzenia ludzi na podstawie wspólnych poglądów i zainteresowań, niezależnie od statusu społecznego. Amerykańska kultura jest wyraźnie bardziej podatna na homofilię wartości, ale w wielu innych społeczeństwach status społeczny precyzyjnie wyznacza zbiór ludzi z którymi można się kontaktować. Homofilia wartości króluje też w Internecie, gdzie „nikt nie wie, że jesteś psem”.

Oprócz homofilii, drugą siłą wpływającą na tworzenie połączeń jest ciekawość (ang. curiosity), która łączy ludzi niezbyt do siebie podobnych, ale też nie na tyle różnych, by nie można było znaleźć wspólnego tematu do rozmowy.

W rezultacie, wykres prawdopodobieństwa nawiązania znajomości w zależności od podobieństwa pomiędzy ludźmi przyjmuje zabawny kształt z dwiema górkami. Wysokość i dokładne położenie „górki ciekawości” jest różna u różnych ludzi w zależności od tego czy szukają nowości czy raczej unikają ich (co zapewne jest uwarunkowane genetycznie, a wyraża się obecnością receptorów dopaminy D1 w naszych mózgach).

W latach 70-tych Mark Granovetter przeprowadził studia wśród pracowników fizycznych w Południowym Bostonie. Większość z nich to byli irlandzcy emigranci pracujący na budowach. Tego rodzaju praca była w tamtych czasach bardzo niepewna i niestabilna, i przez cały czas duża część środowiska pozostawała bez pracy szukając jej. Głównym miejscem spotkań tych ludzi był lokalny pub, gdzie większość ludzi dobrze się znała. Granovetter ze zdumieniem stwierdził że tylko w 30% przypadków osoby szukające pracy dowiadywały się o nowych miejscach od swoich kolegów z pubu. W większości przypadków, informacja o pracy pochodziła od dalszych znajomości i kuzynów. Badacz wyciągnął wnioski, że bezpośrednie znajomości nie są dobrymi źródłami nowych informacji, z kolei znajomi słabo połączeni mogą znajdować się w zupełnie innym miejscu (w znaczeniu dostępu do informacji).

W dalszej części rozdziału są symulacje sieci, gdzie badamy jak w kolejnych iteracjach rozchodzi się informacja i jak zmieniają się poglądy ludzi, przy założeniu że każdego cechuje pewna wartość „współczynnika łatwowierności”. Sprawdzamy też, jaki wpływ na sieć ma pojawienie się propagandzistów/ewangelistów o mocno ukształtowanych poglądach.

Zbieranie danych społecznościowych

Email

Skrzynka emaili korporacyjnych przechowuje mnóstwo danych sieci społecznościowej. Email ma nagłówki from i to, może mieć załączniki. Fakt że jedna osoba wysłała drugiej dokument Worda/Excela sugeruje że dwie osoby pracują razem lub że jedna jest nadrzędna względem drugiej. Samo wyszukiwanie słów „żart”, „śmieszne” i „YouTube” może odsłonić drogi rozchodzenia się memów (i tym samym nieformalne powiązania między ludźmi). Wiele korporacji ma prawo analizować logi swoich serwerów pocztowych. Najlepiej znanym publicznie dostępnym zbiorem danych tego typu jest archiwum emaili firmy Enron, zawierający dane 150 pracowników firmy, opublikowany przez Federal Energy Regulatory Commission podczas śledztwa (423 MB po spakowaniu).

Serwisy społecznościowe

Twitter

Zasadniczo wszystko, co zostanie powiedziane na Twitterze, jest traktowane jako dane publiczne. Twitter oferuje darmowy dostęp do strumienia ok. 1% swojego całego ruchu. W 2011 roku było to 1,2 mln komunikatów dziennie, przy założeniu że jeden komunikat ma 1KB oznacza to 1,5GB dziennie.

Tweety można tagować, przy czym robi się to w dość intrygujący sposób, po prostu wyróżniając określone słowa w treści poprzedzając je znakiem # – są to tzw. hashtags. Tagując, przypisujemy tweeta do określonego tematu/kategorii i dzięki temu można będzie łatwo znaleźć wszystkie wiadomości na ten temat. Dzięki tagom twitterowy mechanizm trending topics jest w stanie ustalić jakie tematy są najpopularniejsze w danym momencie – pojawiają się w prawej kolumnie profilu; można wybrać kraj z którego tagi nas interesują, ale niestety nie ma jeszcze Polski do wyboru. Oczywiście netykieta nakazuje nie nadużywać hashtagów (zaleca się używać nie więcej niż 3 w jednym tweecie) i używać tylko takich hashtagów, które mają związek z treścią tweeta.

Jeśli dwa tagi w występują razem w więcej niż paru tweetach, można z tego wnioskować że są semantycznie powiązane, np. oba tagi #earthquake i #NYC występują w ponad 100 tweetach, co sugeruje że w Nowym Jorku było trzęsienie ziemi (owszem, 23.VIII.2011).

Ponieważ tweety mają stempel czasowy i często są geokodowane, możemy prześledzić jak informacja rozchodzi się geograficznie. Publiczne repozytorium danych zebranych z dnia trzęsienia ziemi na Wschodnim Wybrzeżu USA są dostępne w internecie.

Facebook

Od czasu gdy na FB pojawiły się mechanizmy ochrony danych, łatwo jest wyciągnąć z niego dane tylko dwojakiego rodzaju: prywatne sieci ego i strony publiczne.

Dane grafowe w realnym świecie

Istnieją próby stworzenia bazy danych (nierelacyjnej) nadającej się do przechowywania strumieni aktywności różnych sieci społecznościowych: http://activitystrea.ms. Typowym formatem transferu danych oferowanym przez API współczesnych mediach społecznościowych jest XML i JSON, przy czym ten drugi z czasem staje się wyraźnie preferowany.

Sporym problemem jest często modyfikowany format generowanych danych (dodawane nowe funkcjonalności do serwisu, aktualizacja standardów).

Większość interaktywnych narzędzi analitycznych wymaga, aby cały graf znajdował się w pamięci komputera. Dla przykładu, pythonowa biblioteka NetworkX po załadowaniu grafu 1000 wierzchołków ze średnim współczynnikiem połączeń 0.8 (czyli 800 tys. krawędzi) zużywa 100 MB pamięci, a 2000 wierzchołków (prawie 2 mln krawędzi) już 500 MB.

Najbardziej znanym, obecnym na rynku od 20 lat, komercyjnym systemem SNA dla Windows jest napisany w Turbo Pascalu UCINET, nazywany „Excelem SNA”

Mały graf: plik

Lista krawędzi

Lista krawędzi ma zalety takie, że jest łatwa do odczytania w arkuszu kalkulacyjnym, jak również łatwo może być otrzymana jako wynik zapytania SQL.

Format zapisu grafu ma tu postać:

[from_id] [to_id] [data1] [data2] ... [dataN]
foo bar 1 2

Gdzie from_id oraz to_id to nazwy wierzchołków lub ich ID, a dataX to lista dowolnych wartości przypisanych do krawędzi. W pliku nie powinno być nazw kolumn, użytkownik decyduje co oznaczają kolumny z danymi.

.net

Pajek (utworzony w Uniwersytecie Lubljańskim na Słowacji, „pajek” znaczy „pająk”) to tekstowy format (*.net) zapisu grafów, lingua franca w tym zakresie. Graf społeczny zapisany w tym formacie może zostać odczytany przez praktycznie dowolne oprogramowanie SNA.

*Vertices 3
1 "Node1" 0.0 0.0 0.0 ic Green bc Brown
2 "Node2" 0.0 0.0 0.0 ic Green bc Brown
3 "Node3" 0.0 0.0 0.0 ic Green bc Brown
*Arcs
1 2 3 c Green
2 3 5 c Black
*Edges
1 3 4 c Green

Plik jest podzielony na sekcje, nazwa każdej z nich jest poprzedzona gwiazdką.

*Vertices
Przechowuje wierzchołki. Zaraz za nazwą nagłówka powinna być liczba wierzchołków, a format każdego wiersza jest następujący: ID wierzchołka, nazwa w cudzysłowach, współrzędne w przestrzeni (0.0 oznacza brak), kolor pierwszego planu i kolor tła.
*Arcs i *Edges
Pierwsza sekcja to krawędzie skierowane, druga – nieskierowane. Kolejne wartości oznaczają odpowiednio: from_id, to_id, weight, color.

GML, GraphML

GML (ang. Graph Modeling Language) oraz GraphML to dwie aplikacje XMLa. GraphML jest bardziej wyrazisty pozwalając na grafy hierarchiczne, multigrafy i inne przypadki specjalne, ale na potrzeby SNA obydwa formaty można traktować jako równoważne.

<?xml version="1.0" encoding="UTF-8"?>
<graphml>
  <key id="d0" for="node" attr.name="color" attr.type="string">yellow</key>
  <key id="d1" for="edge" attr.name="weight" attr.type="double"/>
  <graph id="G" edgedefault="undirected">
    <node id="n0">
      <data key="d0">green</data>
    </node>
    <node id="n1"/>
    <node id="n2">
      <data key="d0">blue</data>
    </node>
    <node id="n3">
      <data key="d0">red</data>
    </node>
    .... more node definitions....
    <edge id="e0" source="n0" target="n2">
      <data key="d1">1.0</data>
    </edge>
    <edge id="e1" source="n0" target="n1">
      <data key="d1">1.0</data>
    </edge>
    <edge id="e2" source="n1" target="n3"/>
    .... more edges ....
  </graph>
</graphml>

Średni graf: relacyjna baza danych

Wyliczanie grafu afiliacji może wyglądać tak:

select
foo.from_node as fromID , bar.from_node as toID, count(*) as weight
from
(select * from edges where ......) as foo,
(select * from edges where ......) as bar
where
foo.to_node = bar.to_node and
foo.from_node<>bar.from_node
group by foo.from_node, bar.from_node

Przy czym istotne są tu indeksy na edges.from_node i edges.to_node, które mogą przyspieszyć operację nawet o rząd wielkości.

Gigantyczny graf: Big Data

NoSQL

NoSQLowe bazy danych cechują:

  • brak (na ogół) języka zapytań,
  • brak struktury lub luźno zarysowana struktura (dane backupem),
  • łatwe skalowanie poprzez dodanie sprzętu (skalowanie poziome).
BigTable
Implementacja Google’a dla sieci PC-tów, do przechowywania stron WWW całego Internetu
HBase
Opensource’owy (Apache) klon BigTable
Hadoop
Nie baza danych, ale framework do rozproszonego przetwarzania i składowania danych; jeden ze standardów w chmurach obliczeniowych. Hadoop udostępnia system plików (HDFS), automatycznie rozdystrybuowuje podzadania do wierzchołków, kontroluje wykonanie i pozwala na monitoring przy użyciu interfejsu webowego. Amazon S3 może być udostępniany jako system plików Hadoopa.
MongoDB
Ważny, skalowalny, wydajny magazyn dokumentów z indeksami, zapytaniami itp. Używa dokumentów JSON z dynamicznymi schematami.
CouchDB
Inna baza danych dokumentów, prosta w instalacji i zarządzaniu, wspiera styl indeksowania MapReduce
Neo4j
grafowa baza danych w Javie
Hive
SQLowa baza danych operująca na plikach tekstowych w różnych formatach; Hive działa w ten sposób, że przekształca zapytanie SQL na zadania MapReduce i prezentuje wyniki z powrotem w formie SQL
Share and Enjoy:
  • del.icio.us
  • Facebook
  • Google Bookmarks
  • Śledzik
  • Blip
  • Blogger.com
  • Gadu-Gadu Live
  • LinkedIn
  • MySpace
  • Wykop

Zostaw komentarz

XHTML: Możesz użyć następujących tagów: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>