Archive for Kwiecień, 2012

Kwiecień 24, 2012

Wyszukiwanie wpływowych jednostek w sieciach społecznych

- autor: tsissput

Na przestrzeni ostatnich 10 lat odnotowuje się spory wzrost zainteresowania portalami społecznymi. Liczba aktywnych kont wciąż rośnie, a ludzie spędzają coraz więcej czasu obserwując aktywność swoich znajomych, a także informując ich o swoich przemyśleniach oraz działaniach.  Analiza sieci społecznych najpopularniejszych portalów, jak Facebook czy Twitter, niesie ze sobą wiele możliwości oraz potencjalnych korzyści. Jednym z możliwych kierunków analizy sieci społecznych jest wyszukiwanie wpływowych jednostek. W zależności od konkretnego celu, definicja jednostki wpływowej może być różna.

Analiza powiązań w sieci

W pracy [1] podjęto tematykę analizy sieci reprezentowanej przy pomocy grafu, w którym wierzchołki odpowiadały pojedynczym jednostkom, a krawędzie oznaczały relację między parą jednostek. W tak reprezentowanej sieci, zdefiniowano dwa problemy polegające na znalezieniu zbioru wpływowych jednostek pod kątem pewnych kryteriów. Problem znalezienia zbioru jednostek korzystnych, polega na znalezieniu takiego podzbiór dostępnych jednostek, który umożliwia dostęp do jak największej liczby osób w sieci społecznej. Znaleziony zbiór może następnie posłużyć w celu np. rozsyłania wiadomości w sieci społecznej, bądź promocji dobrych nawyków w społeczeństwie.

Dla odmiany problem znalezienia jednostek niekorzystnych, polega na znalezieniu takiego podzbioru jednostek, których usunięcie z sieci spowoduje, zmniejszenie spójności sieci. W najgorszym wypadku przyczyniając się do wzrostu liczby komponentów w grafie. Problem ten znajduje zastosowanie np. w szeroko pojętych działaniach militarnych oraz walce z organizacjami przestępczymi, gdzie ważne jest skupienie się na neutralizacji takiego zbioru jednostek, który spowoduje paraliż działania całej organizacji.

W przypadku obu problemów kluczowe jest znalezienie możliwie najmniejszego podzbioru jednostek, który spełnia zadane kryteria, w celu minimalizacji kosztów potencjalnych operacji.

Autorzy pracy dowodzą, że popularne miary centralności stosowane w przypadku analizy grafów mogą się nie sprawdzić z uwagi na inną naturę analizowanego problemu, w którym kluczową rolę odgrywa maksymalne zerwanie spójności grafu dla jednostek niekorzystnych, oraz uzyskanie możliwie najkrótszego dostępu dla jednostek spoza wybranego podzbioru, w przypadku jednostek korzystnych. Dodatkowo należy zauważyć, że rozwiązaniem postawionych problemów jest zbiór jednostek, jako całość. Stąd miary centralności skupione na znalezieniu pojedynczego wierzchołka grafu mogą być nie optymalne w przypadku problemu znalezienia zbioru wierzchołków.

W przypadku problemu zbioru jednostek niekorzystnych, autorzy wychodzą od miary F opartej na zliczaniu par wierzchołków rozłącznych (brak ścieżki łączącej).  W celu przyśpieszenia ewentualnych obliczeń, oraz wykorzystując fakt, że wierzchołki znajdujące się w obrębie tego samego komponentu grafu są wzajemnie osiągalne, zliczanie par wierzchołków rozłącznych zastąpiono zliczaniem rozmiaru komponentów, według poniższego wzoru:

sk – rozmiar komponentu k w grafie (liczba wierzchołków w komponencie)

n – liczba wierzchołków w grafie

 

Ponieważ, tak skonstruowana miara uwzględnia jedynie osiągalność par wierzchołków, pomijając wewnętrzną strukturę komponentów, a co za tym idzie rzeczywiste odległości między wierzchołkami została ona udoskonalona poprzez uwzględnienie odwrotnej odległości między wierzchołkami. Dla wierzchołków rozłącznych odległość wynosi nieskończoność, a co za tym idzie odległość odwrotna jest równa 0. Zmodyfikowany miara (DF) wygląda następująco:

dij – odległość między wierzchołkami i oraz j

n – liczba wierzchołków w grafie

 

W ten sposób problem znalezienia zbioru niekorzystnych wierzchołków sprowadza się do znalezienia wierzchołków, których usunięcie spowoduje wzrost miary DF (przyjmującej wartości z przedziału 0-1).

Dla problemu znajdowania zbioru jednostek korzystnych autorzy wyszli również z prostego zbioru zliczając liczbę wierzchołków osiągalnych dla wyznaczonego zbioru jednostek stanowiących rozwiązanie. W celu uniknięcia wielokrotnego zliczania połączeń z tym samym wierzchołkiem wykorzystano operację U, która reprezentuje funkcję max lub min, w zależności od zastosowania. Wzór wygląda następująco:

V – zbiór wierzchołków w grafie

K – zbiór wierzchołków grafu stanowiących rozwiązanie

aij – istnienie ścieżki w grafie między wierzchołkami i oraz j (0 lub 1)

Tak jak w przypadku miary F dla jednostek niekorzystnych, miarę zmodyfikowano w celu uwzględnienia odległości między wierzchołkami. W tym celu zastosowano odwrotną odległość między wierzchołkami:

V – zbiór wierzchołków w grafie

K – zbiór wierzchołków grafu stanowiących rozwiązanie

dij – odległość między wierzchołkami i oraz j

Należy zaznaczyć, że w swoich rozważaniach autorzy brali pod uwagę jedynie sam fakt istnienia połączeń między jednostkami w sieci społecznej, a co za tym idzie analizie poddali jedynie strukturę grafu, nie uwzględniając ewentualnych interakcji zachodzących między wierzchołkami. W odniesieniu do popularnych portali społecznościowych np. Facebooka, oznacza to ograniczenie się do analizy grafu przyjaciół. Przedstawione problemy nie uwzględniały wpływu poszczególnych jednostek na inne jednostki znajdujące w sieci. Poszczególne jednostki mogą mocno oddziaływać na inne, z którymi znajdują się w relacji, a te z kolei mogą propagować to oddziaływanie dalej w głąb sieci. Jednostki silnie oddziaływujące na pozostałe jednostki, uznawane są za wpływowe. We współczesnych sieciach społecznościowych oddziaływanie odbywa się na podstawie różnorakich akcji, jakie udostępniają portale. Takimi akcjami mogą być np. wpis na blogu, komentarz, krótka notka, rekomendacja ogólnie pojętego zasobu (np. strony internetowej, firmy, marki, różnych artykułów), a także zgłoszenie chęci uczestnictwa w różnorodnych wydarzeniach/imprezach.

Wyszukiwanie jednostek wpływowych

Problem znajdowania wpływowych jednostek, został poruszany przez [2]. Autorzy publikacji stworzyli algorytm znajdujący nie tylko jednostki niezwykle wpływowe, ale także liderów grup oraz społeczności istniejących w obrębie serwisów społecznościowych. Liderzy grupy wyróżniają się tym, że ich akcje mają nieustanny wpływ na pewną, niezmienną w czasie, grupę jednostek. Jako punkt wyjścia algorytmu uznaje się sieć powiązań między jednostkami przedstawioną w postaci grafu, oraz chronologicznie uporządkowany dziennik wszystkich akcji podejmowanych przez jednostki. Zaproponowany algorytm bazuje na rozpoznawaniu wzorców w zebranych danych. Punktem wyjścia jest przesuwające się po dzienniku akcji okno czasowe, reprezentujące wszystkie akcje, które zaszły w danym przedziale czasowym. Na podstawie tych akcji oraz danych odnośnie powiązań między jednostkami w zależności od problemu generuje się odpowiednią macierz oddziaływań: 2-wymiarową dla poszukiwania jednostek wpływowych, bądź 3-wymiarową dla poszukiwania liderów społeczności. Podczas całego procesu dziennik jest czytany tylko raz, natomiast analizowane grafy relacji dotyczą jedynie jednostek aktywnych w danym przedziale czasowym. Oba te zabiegi mają za zadanie zmniejszyć koszty obliczeniowe.

Podobny problem, dotyczący wyszukiwania jednostek wpływowych, poruszony został w [3]. Autorzy skupiają się na znalezieniu grupy wpływowych blogerów w obrębie pojedynczego blogu. Zwracają przy tym uwagę, że pojęcie wpływowy nie znaczy to samo, co aktywny. Wpływowi blogerzy mogą publikować wpisy rzadko, lecz istotnie oddziaływać nimi na akcje podejmowane przez czytelników. Z drugiej strony najaktywniejsi blogerzy wcale nie muszą należeć do grona tych najbardziej wpływowych. Duża aktywność może wynikać np. z publikowania dużej ilości mało znaczących informacji. Blogerzy są uznawani za wpływowych, jeśli publikują wpływowe wpisy. W celu rozpoznania wpływowych wpisów, autorzy proponują zastosowanie czterech wielkości:

  • Rozpoznanie – liczba linków do danego wpisu, znajdujących się w pozostałych wpisach w obrębie danego blogu. Większa liczba linków wewnątrz blogu, oznacza większy wpływ danego wpisu.
  • Aktywność – liczba komentarzy dotyczących danego wpisu. Większa liczba komentarzy oznacza większe zainteresowanie wpisem.
  • Innowacyjność – liczba linków zawartych we wpisie kierujących do innych postów na blogu. Duża liczba linków w poście oznacza jego małą innowacyjność i odnoszenie się do zagadnień już poruszanych, co wpływa na mniejsze zainteresowanie wpisem.
  • Elokwencja – mierzona jako rozmiar wpisu. Czytelniczy preferują czytać ciekawe wpisy. Badania dowodzą, że wpisy dłuższe zawierają zazwyczaj zagadnienia bardziej istotne dla odbiorców oraz przedstawione w ciekawszy sposób.

Tak określone wskaźniki służą następnie do zbudowaniu skierowanego grafu modelującego wpływ poszczególnych postów. Wierzchołki w grafie reprezentują poszczególne wpisy, natomiast łuki definiowane są na podstawie rozpoznania oraz aktywności, czyli linków między wpisami. Ocena końcowa wpisu pod kątem jego wpływu wyznaczana jest na podstawie dwóch pozostałych wskaźników, aktywności i elokwencji, oraz przepływów w grafie dla danego blogu.

Podumowanie

Biorąc pod uwagę nieustannie rosnącą popularność serwisów społecznościowych, można śmiało stwierdzić, że analiza wirtualnych społeczności może z biegiem czasu nabrać coraz większego znaczenia. Analizie może być poddana nie tylko struktura sieci, ale także interakcje zachodzące między jej członkami. Sieci społecznościowe rozrastają się z dnia na dzień, nie tylko pod katem liczby użytkowników, ale przede wszystkim pod kątem dostępnych danych. Jednym z potencjalnych problemów, z jakim przychodzi się mierzyć podczas badań, jest rozmiar danych, który wymusza stosowanie naprawdę efektywnych heurystyk. Z drugiej strony, na pewno nie można narzekać na brak dostępnych danych.

Literatura

[1] Borgatti and Stephen. Identifying sets of key players in a social network. Computational & Mathematical Organization Theory, 12(1):21–34, April 2006. [link]

[2] Amit Goyal, Francesco Bonchi, and Laks V. S. Lakshmanan. Discovering leaders from community actions. In Proc. of the 17th ACM conference on Information and knowledge management, CIKM ’08, pages 499–508, New York, NY, USA, 2008. ACM. [link]

[3] Nitin Agarwal, Huan Liu, Lei Tang, and Philip S. Yu. Identifying the influential bloggers in a community. In Proc. of the international conference on Web search and web data mining, WSDM ’08, pages 207–218, New York, NY, USA, 2008. ACM. [link]