- autor: tsissput

Wyszukiwanie najważniejszych osób w sieci na podstawie artykułu „Identifying sets of key players in a social network”

 

Wstęp

Artykuł dotyczy wyszukiwania najważniejszych indywiduów w ramach sieci społecznej. Z uwagi na specyfikę tematu, wpis w przeważającej części przybliża treści wyrażone w dokumencie „Identifying sets of key players in a social network” S.Bogratti’ego.

Głównym założeniem jest fakt, że optymalny wybór kluczowych osób (k kluczowych elementów tworzących zbiór K) zależy od tego, w jakim celu przeprowadza się wyszukiwanie. W zależności od celu, można wyróżnić 2 odmiany problemu – KPP-POS (Key Player Problem / Positive) oraz KPP-NEG (Key Player Problem / Negative).

 

Zdefiniowanie problemu

Problem kluczowych graczy w formie NEG dotyczy stopnia zależności sieci od jej kluczowych elementów. Innymi słowy chodzi o utrzymanie spójności grafu. Istotą jest pomiar ważności zerwanych powiązań – ilościowa miara redukcji spójności sieci, która nastąpiłaby, gdyby usunąć dane węzły. Dla zobrazowania problemu, jako praktyczny przykład można tu podać wybór zbioru z populacji w celu uodpornienia lub przeprowadzenia kwarantanny w toku powstrzymywania rozwoju epidemii. Innym przykładem może być zneutralizowanie (np. aresztowanie) określonych członków środowiska przestępczego w celu największego utrudnienia przeprowadzania zorganizowanych akcji przestępczych.

W drugim sformułowaniu problemu (KPP POS) mówimy raczej o stopniu w jakim kluczowi gracze są połączeni i osadzeni w sieci istniejącej wokół nich. Idąca za tym podejściem intuicja jest następująca: wybieramy mały podzbiór populacji, w celu rozpropagowania na jak największą część populacji odpowiednich zachowań / przekonań – np. wybór osób, które będziemy zachęcać, aby promowały zdrowy tryb życia. We wszystkich wspomnianych sytuacjach szukamy zbioru wierzchołków (indywiduów) grafu (społeczności), które są optymalnie rozstawione, aby szybko rozproszyć informację / nastawienia / zachowania / dobra.

Formalnie problem wyszukiwania kluczowych obiektów można zdefiniować następująco. Dana jest sieć społeczna (w reprezentacji nieskierowanego grafu). Celem jest znalezienie zbioru k wierzchołków takiego, że:

  1. (KPP-Neg) usunięcie wybranego zbioru będzie skutkowało w sieci wynikowej najsłabszą możliwą spójnością
  2. (KPP-Pos) wybrany zbiór jest w jak największym stopniu połączony ze wszystkimi pozostałymi wierzchołkami grafu

Pozostaje jeszcze kwestia kluczowych pojęć – najsłabszej możliwej spójności oraz największego stopnia połączenia. Zostaną one opisane dalej. W uproszczeniu można powiedzieć, że NEG doprowadza do fragmentacji sieci na komponenty lub też prowadzi do takiego wydłużenia odległości między wierzchołkami, aby były one rozpatrywane jako nie połączone ze sobą. Z kolei POS polega na wyszukiwaniu wierzchołków, z których można osiągnąć tak wiele z pozostałych, jak to tylko możliwe przy użyciu bezpośrednich połączeń lub krótkich ścieżek.

Nie jest łatwo wypracować ogólne metody dla każdego z tych problemów z uwagi na różnorodność sformułowania kluczowych pojęć. Niemniej Bogratti podejmuje próbę skonstruowania generycznych rozwiązań wspomnianych problemów.

Na pierwszy rzut oka obydwa problemy wydają się być łatwe do rozwiązania poprzez wybór odpowiednich miar centralności węzłów i wyboru k najbardziej zcentralizowanych. Alternatywnie można skorzystać z podejść znanych z teorii grafów. Napotykamy jednak 2 powody, dla których takie rozwiązania nie spisują się dobrze. Jednym z nich jest kwestia celu. Mianowicie dotyczy to faktu, iż miary centralności nie są zaprojektowane ściśle dla jednego z dwóch problemów (NEG/POS) i stąd nie muszą prowadzić do rozwiązań optymalnych. Drugim istotnym czynnikiem jest kwestia zbioru. Mianowicie obydwa sformułowania problemu dotyczą wyboru zbioru wierzchołków a nie indywiduów, a optymalny zbiór dla dowolnego zadania niekoniecznie składa się z k najbardziej optymalnych obiektów rozważanych indywidualnie.

 

Kwestia celu

Dla problemu NEG najbardziej odpowiednią miarą centralności jest betweenness Freeman’a, która jest miarą sumy proporcji liczby najkrótszych ścieżek od jednego wierzchołka do innego przechodzących przez dany węzeł, do wszystkich wspomnianych najkrótszych ścieżek niekoniecznie przez ten węzeł przechodzących. Wierzchołek z wysokim współczynnikiem tej miary jest na najkrótszej ścieżce między wieloma parami węzłów i jego usunięcie powoduje to, że wiele par węzłów traci połączenie lub przynajmniej ich połączenie jest dłuższe.

Optymalność tego współczynnika dla wyszukiwania wierzchołków, których usunięcie z sieci spowoduje największą redukcję spójności nie jest jednak gwarantowana dla typowych definicji spójności. Wierzchołek 1 grafu z fig.1 charakteryzuje się największą miarą centralności dla każdej standardowej miary włącznie z betweenness. Usunięcie wierzchołka 1 nie skutkuje jednak rozłączeniem sieci. Odległości między wierzchołkami rosną ale jeśli fragmentacja jest celem, to usunięcie wierzchołka 1 jest nieefektywne. Z kolei usunięcie elementu 8 mającego mniejszą centralność (dla wszystkich miar) powoduje rozłączenie grafu – podział na 2 części.

Inspirację można odnaleźć w teorii grafów. Dla przykładu wiele zostało zrobione w kwestii wrażliwości grafów na rozłączenie, co bezpośrednio odpowiada sformułowaniu problemu KPP-NEG.

Przechodząc do wersji POS, jeśli sformułujemy problem jako szukanie wierzchołka, z którego można osiągnąć bezpośrednio najwięcej innych wierzchołków, prosty stopień centralności jest dodatkowo optymalny. Z kolei jeśli podejdziemy do problemu z celem dotarcia do jak największej liczby węzłów w określonej liczbie kroków, najbardziej odpowiednią miarą centralności będzie kolejna z 4 miar centralności szeroko używanych w analizie sieci – closeness centrality. Jest ona zdefiniowana jako suma odległości od danego węzła do wszystkich innych. Dla fig.2 węzeł 4 ma najlepszą wartość tego współczynnika. Jednakże, jeśli interesuje nas dotarcie do największej liczby wierzchołków spośród występujących na ścieżkach o długości <= 2, węzeł 3 będzie lepszym wyborem (da się z niego dotrzeć do 8 wierzchołków a z 4 do 6 elementów).

Kwestia zbioru

Kwestia centralności zbioru dotyczy tego, że wybór k wierzchołków jako zbioru, które razem są optymalnym rozwiązaniem problemów POS i NEG, jest czym innym niż wybór k wierzchołków, które rozpatrywane oddzielnie są optymalne.

Rozważmy problem NEG. Na fig.3 wierzchołki h oraz i są indywidualnie najlepszymi kandydatami do usunięcia w celu podzielenia sieci. Jednakże pozbycie się wierzchołka i po wcześniejszym usunięciu h, nie skutkuje większą fragmentacją (zgodnie ze stosowanymi miarami) niż po usunięciu jedynie wierzchołka i. Z kolei wierzchołek m nie jest indywidualnie tak silny (effective) jak wierzchołek i, w oddzielonych parach wierzchołków, ale usunięcie m oraz h powoduje większą fragmentację niż usunięcie samego m lub h. Powodem, dla którego i oraz h razem nie są tak dobrą parą kandydatów jak h i m, jest to, że i oraz h są nadmiarowe w odniesieniu do ich współpracy – centralność jednego jest po części centralnością drugiego (ich centralności są zależne względem siebie). Stąd łączna centralność zbioru jest mniejsza niż suma centralności wszystkich elementów tego zbioru.

Prawo nadmiarowości ma rację bytu również w problemie POS. Rozważając fig.4 wierzchołki a oraz b są indywidualnie najlepszymi łącznikami. Każdy z nich sąsiaduje z 5 innymi wierzchołkami. Liczność sumy zbiorów sąsiadów dla tych wierzchołków jest równa także 5, czyli wspólnie nie osiągają one więcej sąsiadów niż każdy z osobna. Dla przykładu, gdyby parą były wierzchołki a oraz c (który indywidualnie sąsiaduje jedynie z 3 wierzchołkami), sąsiedztwo grupy {a, c} byłoby maksymalne – obejmowałoby każdy wierzchołek w sieci. Przyczyną osiągania przez {a, c} lepszego wyniku niż {a, b} jest fakt, że a oraz c są mniej podobne do siebie strukturalnie (biorąc pod uwagę strukturę ich połączeń) niż a i b. Takie podobieństwo strukturalne dotyczy stopnia pokrywania się sąsiedztw wierzchołków. Strukturalnie podobne wierzchołki, z definicji są nadmiarowe z uwagi na sąsiedztwo oraz odległości. Różnica polega na tym, że nadmiarowość dla POS rozpatruje się z uwagi na odległość oraz sąsiedztwo, podczas gdy dla NEG biorąc pod uwagę uzupełnianie się (np. linkowanie do tych samych komponentów).

Proponowane rozwiązanie

KPP-NEG – Fragmentacja

Kluczowym pojęciem w tym problemie jest podział grafu. Do rozwiązania tego problemu potrzebna jest zatem bezpośrednia miara podziału grafu. Dysponując taką miarą możemy ocenić każdy zbiór wierzchołków określając jak dobrym rozwiązaniem problemu KPP-Neg jest on. Prawdopodobnie najbardziej oczywistą miarą fragmentacji sieci jest liczba komponentów (zbiorów wierzchołków odizolowanych od innych zbiorów). Np. dla 1 komponentu, sieć nie jest podzielona. Największa fragmentacja występuje, kiedy każdy wierzchołek jest odizolowany od pozostałych (liczba komponentów = liczba wierzchołków). Dla wygody normalizujemy liczbę przez podzielenie przez liczbę wierzchołków.

Problem z tą miarą jest taki, że nie uwzględnia ona rozmiarów komponentów. Dla przykładu – na fig.3 usunięcie węzła m lub i powoduje podział sieci na 2 części. W pierwszym przypadku większość węzłów pozostaje połączona, natomiast w drugiej sytuacji istnieje znacznie więcej par, gdzie nie występuje połączenie między wierzchołkami. To prowadzi do zastosowania innej miary stopnia podziału sieci, która polega na zliczaniu liczby par węzłów, które są rozłączone. W tym celu oblicza się macierz R, w której element r_{ij}=1, jeśli z i można przejść do j, oraz 0 w przeciwnym wypadku. Miara jest zdefiniowana następująco:   F=1-\frac{2 \sum_i \sum_{j<i} r_{ij}}{n(n-1)}

Z kolei problemem związanym z tą miarą jest koszt obliczeń. Dla przyspieszenia można skorzystać z faktów, że węzły wewnątrz komponentów są wzajemnie osiągalne a komponenty grafu mogą być przetwarzane wydajniej. Miara F może być zatem policzona bardziej ekonomicznie przez rozważanie komponentów z uwzględnieniem ich rozmiarów (s_k – rozmiar k-tego komponentu).    F=1-\frac{\sum_k s_k (s_k - 1)}{n(n-1)}

Miara F jest bardzo podobna do współczynnika koncentracji – wskaźnika Herfindahla-Hirschmana, w tym kontekście przyjmującego następującą postać:    H=1-\sum_k (\frac{s_k}{n})^2

Obie miary (F i H) osiągają minimum w 0 (dla 1 komponentu), lecz miara H osiąga wartość maksymalną 1 - \frac{1}{n} kiedy sieć jest maksymalnie podzielona. Normalizując H, przez podzielenie przez jej wartość maksymalną, otrzymujemy miarę F.

Alternatywną miarą jest entropia, która w tym zastosowaniu wygląda następująco:    E=-\sum_k \frac{s_k}{n}\ln \frac{s_k}{n}

Ponownie napotykamy na problem z zakresem wartości (<0;∞>) . Aby sobie z tym poradzić, możemy podzielić wartość miary przez wartość dla sytuacji, gdzie każdy wierzchołek jest odizolowany od pozostałych. Otrzymujemy wówczas następującą miarę:   E=-\frac{ \sum_k \frac{s_k}{n}\ln \frac{s_k}{n} }{ \sum_k \ln \frac{s_k}{n} }

Podczas gdy miara fragmentacji F, oraz entropia E są bardzo satysfakcjonujące w tym zastosowaniu, nie biorą one pod uwagę kształtu komponentów – ich wewnętrznej struktury. Rozważmy sieć składającą się z 2 części, każda rozmiaru 5 będąca kliką (fig.5a). Sieć ta jest postrzegana pod względem podziału tak samo jak sieć składająca się z 2 części 5 elementowych będących „linią” (fig.5b). W tej drugiej sieci odległości są znacznie większe niż w pierwszej. Wiadomo jednak (Granovetter, 1973), że wierzchołki nie muszą być rzeczywiście rozłączone aby być praktycznie rozłączone – jeśli odległości między nimi są wystarczająco długie, wierzchołki są efektywnie oddzielone od siebie.

W dodatku napotykamy jeszcze jeden problem. W niektórych przypadkach wymagany rozmiar zbioru kluczowych elementów jest  tak mały, że nie istnieje zbiór tego rozmiaru rozdzielający graf. Ciągle preferujemy jednak metody oceniania które zbiory są lepsze od innych pod względem możliwości „prawie rozłączenia” wielu par wierzchołków.

Oczywistym rozwiązaniem jest pomiar całkowitej odległości między wszystkimi parami wierzchołków i uwzględnienie go jako miary wirtualnego rozdzielenia. Jednakże działa to tylko w przypadku, gdy graf pozostaje połączony. W przeciwnym przypadku musielibyśmy sumować nieskończone odległości. Praktyczną alternatywą jest oparcie miary o sumę odwrotności odległości. W tym przypadku powstaje wersją miary F, w której wagi to odwrotności odległości. Wartość rij  zostaje zastąpiona przez \frac{1}{d_{ij}}, co oddaje stopień osiągalności wierzchołka j z i, mieszczący się w przedziale <0;1> .      F^D=1-\frac{2\sum_{i>j}\frac{1}{d_{ij}}}{n(n-1)}

Miara F^D jest odpowiada mierze F, gdy wszystkie komponenty są klikami. Kiedy odległości wewnątrz komponentów są większe niż 1, miara bierze pod uwagę względną spójności komponentów. Dla przykładu graf z fig.5b, który jest mniej spójny niż graf na fig.5a ma większą miarę F^D .

KPP-POS: spójność wewnątrz zbioru

Fundamentalnymi pojęciami są w tym wypadku połączenia lub spójność między elementami zbioru kluczowych wierzchołków a pozostałymi elementami grafu. W celu rozwiązania problemu, potrzebna jest bezpośrednia miara liczby połączeń między wybranym zbiorem oraz pozostałą częścią grafu. Dążymy zatem do zdefiniowania funkcji, która oddawałaby spójność między tymi 2 podzbiorami. Na początek zdefiniujmy miarę, w której aij=1 , jeśli wierzchołki i oraz j sąsiadują ze sobą i 0 w przeciwnym przypadku:   C_K=\sum_{i\in K, j\in {V-K}}a_{ij}

To proste podejście ignoruje strukturalną równoważność elementów zbioru, przede wszystkim podwójnie zliczane powiązania do tych samych indywiduów. Zamiast tego chcemy zdefiniować nieco bardziej wyrafinowaną miarę, jak następująca:      C_K=\sum_{j \in {V-K}} \bigcup_{i \in K} a_{ij}

Gdzie operacja sumy mnogościowej jest nieokreśloną dokładnie funkcją agregacji, jak minimum lub maksimum. Dla funkcji max miara reprezentuje liczbę unikalnych wierzchołków spoza zbioru K, do których elementy z K są sąsiednimi. Jest to równoważne stopniowi centralności grupy Everetta i Borgattiego.

Idąc dalej, chcielibyśmy ponownie – tak jak dążyliśmy do tego przy fragmentacji – aby następna miara odpowiednio radziła sobie z odległościami. Przyczyna jest taka sama jak poprzednio – 2 grupy znanego rozmiaru mogą być sąsiadujące z taką samą liczbą wierzchołków, i jednocześnie dla jednej z grup nieosiągalne z niej wierzchołki mogą być odległe o jedno połączenie, a dla innej mogą być bardzo odległe. Prostym podejściem jest miara m-osiągalności, w której zastępujemy sąsiedztwo osiągalnością, tak, że rijm=1  jeśli z i można osiągnąć j, przy scieżce o długości <= m, 0 wpp. Ponownie dla sumy mnogościowej będącej funkcją max, miara m-osiągalności może zostać przedstawiona następująco:     C_K=\sum_{j \in {V-K}} \bigcup_{i \in K} r_{ij}^m

M-osiągalność jest wtedy liczbą unikalnych wierzchołków osiągalnych przez dowolny wierzchołek ze zbioru K, przy odległości <= m połączeń. Zaletą tej miary jest łatwość interpretacji. Wadą z kolei jest to, że zakłada ona, że wszystkie ścieżki o długości <= m, są tak samo ważne, oraz że wszystkie ścieżki o długości >m są nieistotne.

Bardziej wrażliwą miarą jest osiągalność ważona odległościami, czyli suma odwrotności odległości od elementów zbioru K do wszystkich pozostałych wierzchołków, gdzie dla zbioru wierzchołków brana jest minimalna odległość:     C_K=\sum_{j \in {V-K}} \bigcup_{i \in K} \frac{1}{d_{ij}}

Dla jasności interpretacji warto rozważyć wszystkie odległości wewnątrz zbioru elementów kluczowych jako jednakowe i sumować je dla wszystkich wierzchołków. Warto również znormalizować miarę do przedziału <0;1> . Można również uprościć notację przez zdefiniowanie dKj  – minimalnej odległości od dowolnego wierzchołka ze zbioru K, do wierzchołka j, co skutkuje ostateczną postacią miary:     D_R= \frac{\sum_j \frac{1}{d_{K_j}}}{n}

Łatwo można dostrzec, iż formuła ta to ważona proporcja wszystkich wierzchołków osiągalnych z danego zbioru, gdzie wierzchołki są ważone odwrotnie proporcjonalnie do ich minimalnej odległości od zbioru, a tylko wierzchołki o odległości 1 mają pełną wagę. Stąd D_R osiąga max (1) kiedy wszystkie zewnętrzne wierzchołki są sąsiednie do przynajmniej 1 ze zbioru K. Wartość min (0) jest z kolei osiągana, gdy żaden wierzchołek z K nie należy do tego samego komponentu co jakikolwiek wierzchołek spoza K (np. zbiór K jest zupełnie odizolowany).

Wybór zbioru K poprzez optymalizację kombinatoryczną

Podczas gdy prosta heurystyka polegająca na wybieraniu kluczowych k elementów nie zdaje egzaminu, musimy znaleźć inny sposób na skompletowanie zbioru K. Jedno podejście polega na poszukiwaniu modyfikacji wspomnianej heurystyki, która eliminowałaby słabe punkty swojej poprzedniczki. Dla przykładu można zacząć od znalezienia kluczowego wierzchołka i następnie dodawać kolejne najlepsze indywidua, będące najmniej nadmiarowymi w zestawieniu z dotychczas wybranymi. Innym sposobem jest jednoczesny wybór k elementów zbioru K przy pomocy optymalizacji kombinatorycznej. Jest to rozwiązanie sugerowane.

Reprezentując rozwiązanie problemów POS / NEG jako łańcuch S, składający się z zer i jedynek, gdzie 1 oznacza, iż wierzchołek i jest elementem proponowanego zbioru K (0 wpp), łatwo można zastosować algorytmy optymalizacyjne takie jak tabu-search, K-L, simulated annealing, lub algorytmy genetyczne do znalezienia S. Wstępne eksperymenty sugerują, że wszystkie ze wspomnianych typów algorytmów radzą sobie doskonale z KPP. Poniżej zaprezentowano przykładowe rozwiązanie oparte na prostym algorytmie greedy. Jest ono wykonywane wiele razy na losowych zbiorach startowych.

  1. Wybierz k losowych wierzchołków do zbioru K
  2. Dopasuj F używając odpowiedniej metryki
  3. Dla każdego węzła u w zbiorze K i każdego v spoza zbioru K
    1. \Delta F = polepszenie dopasowania po zamianie u z v
    2. Wybierz parę z najlepszym \Delta F
      1. Jeśli \Delta F \leq F zakończ
      2. Wpp zamień u z v (parę z najlepszym \Delta F) i ustaw F = F + \Delta F
      3. Idź do kroku 3.

Przykład

Działanie algorytmów zostanie następnie przedstawione na krótkim przykładzie. Wykorzystany zbiór danych (fig.7) to sieć powiązań pomiędzy znanymi terrorystami. Graf składa się z 74 wierzchołków – podejrzewanych terrorystów. Do celów analizy wykorzystujemy jedynie główny komponent sieci – składający się z 63 indywiduów.

Pierwsze pytanie, jakie należy zadać (KPP-NEG) to: które osoby powinny zostać odizolowane aby maksymalnie poprzerywać sieć? Załóżmy, że możemy unieszkodliwić 3 osoby.

Uruchomienie algorytmu z użyciem miary F, wybiera 3 węzły oznaczone na czerwono (A, B, C). Usunięcie tych wierzchołków skutkuje fragmentacją z wartością miary 0.59 i przerywa graf na 7 komponentów (włącznie z 2 dużymi tworzącymi lewą i prawą połowę grafu).

Drugim pytaniem przed jakim stajemy (KPP-POS) jest: „wiedząc, że chcemy rozproszyć pewną informację, których obiektów powinniśmy użyć aby ta informacja szybko i niezawodnie dotarła do wszystkich wierzchołków?”. Załóżmy, że informacja po przebyciu więcej niż 2 połączeń jest bezużyteczna (zostaje wykryta lub ulega destrukcyjnej modyfikacji). Stąd, szukamy najmniejszego zbioru wierzchołków, z pomocą którego możemy dotrzeć do wszystkich węzłów grafu używając połączeń o długości <= 2. Rozwiązanie znalezione przez algorytm to 3 wierzchołki – zaznaczone na rys.7 jako kwadratowe (A, C, D) – pozwala na dotarcie do wszystkich wierzchołków sieci.

Podsumowanie

W artykule został zdefiniowany problem wyboru kluczowych graczy w dwóch odmianach, wraz z uwzględnieniem kwestii celu oraz zbioru. Zostały także przedstawione rozwiązania oparte na teorii grafów, a także problemy związane z różnymi podejściami. Zaprezentowano także przykład, ukazujący, iż zaproponowane algorytmy radzą sobie bardzo dobrze z tak zdefiniowanymi problemami. Problem kluczowych indywiduów może znaleźć szerokie zastosowania w wielu dziedzinach nowoczesnej nauki.

Autor: 84879

Źródło: Stephen P. Borgatti, „Identifying sets of key players in a social network”

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: