Anomalie w „sieciach ego”

- autor: tsissput

Anomalia to zjawisko rzadkie, odstępujące od normy, czyli najczęściej ciekawe i warte uwagi. Wiele problemów analizy struktur sieciowych w naturalny sposób sprowadza się właśnie do ich wykrywania. Jako przykład może posłużyć detekcja intruzów w sieciach komputerowych, którzy generują niestandardowe wydarzenia podczas spamowania czy skanowania portów. W sieciach telefonicznych anomalią będzie z kolei zachowanie telemarketerów dzwoniących do setek klientów.

Można z dużą dozą prawdopodobieństwa spodziewać się, że anomalie o podobnym charakterze powinny występować w większości sieci interakcji społecznych. Intuicja podpowiada nam, że w sieciach społecznościowych odbiegającymi od normy zjawiskami będą skrajności, takie jak „kolekcjonowanie” znajomych albo po prostu ich brak. Czy faktycznie tak jest? Czy istnieją modele opisujące nasze relacje z innymi ludźmi, które pozwoliłyby określić, czy jesteśmy gdzieś na środku krzywej Gaussa, czy może przeciwnie – poza trzecią sigmą? Odpowiedzieć na to pytanie pomaga nam praca „OddBall: Spotting Anomalies in Weighted Graphs” trójki autorów z Carnegie Mellon University w Pittsburghu. Metodą naukową znaleziono w niej kilka praw statystycznych, które wydają się rządzić intensywnością i strukturą naszych społecznych działań. Idąc za ciosem, naukowcy wykorzystali je do zbudowania algorytmu wskazującego interesujące miejsca sieci interakcji. Przyjrzyjmy się tokowi ich postępowania.

Wykrywanie anomalii to jeden z problemów dziedziny uczenia maszynowego, nic więc dziwnego, że przedmiotem naszego zainteresowania będą przypadki opisane zestawem cech. Co może być takim przypadkiem w grafie? W pracy autorzy skupili się na pojedynczych węzłach wraz z ich sąsiedztwem, czyli tak zwanych „sieciach ego”. Każdy węzeł otrzymuje w ten sposób zestaw wartości determinowanych przez połączenia z sąsiadami i pomiędzy sąsiadami. Jako ciekawostkę można podać, że „sieć ego” jest szczególnym przypadkiem sąsiedztwa k-tego stopnia, które definiujemy jako podgraf indukowany przez węzły położone w odległości nie większej niż k od wybranego centrum. Można by pomyśleć, że tak mały podgraf to bardzo ograniczający wybór, jednak eksperymenty pokazały, że dalsi znajomi niczego ciekawego o nas samych już nie mówią, co więcej – zwiększają złożoność algorytmu wieńczącego omawiany artykuł.

Podejście zastosowane w pracy polegało na znalezieniu powtarzających się w „sieciach ego” wzorców, a następnie szukaniu od nich odstępstw. Na schemacie przedstawiono te, które pojawiały się w badanych grafach najczęściej. Można tam zauważyć struktury przypominające gwiazdę, klikę oraz sieć z wyraźnie dominującymi krawędziami. Wyjaśnienia wymaga anomalia typu „heavy vicinity”, która polega na stosunkowo wysokiej sumie wag krawędzi przy danej liczbie sąsiadów. Pojawia się ona np. w sieci telekomunikacyjnej, gdy wadliwe urządzenie wymusza ponawianie połączeń.

Jednym z podstawowych problemów uczenia maszynowego jest selekcja cech. Aby możliwe było przetwarzanie ogromnych grafów, ich ekstrakcja powinna być szybka, a samych cech nie powinno być zbyt wiele. Zgodnie z tymi założeniami wybrano tylko 4 wartości numeryczne charakteryzujące sąsiedztwo:

  • N: liczba sąsiadów centralnego węzła
  • E: liczba krawędzi w całej „sieci ego”
  • W: całkowita waga „sieci ego”
  • a: największa wartość własna ważonej macierzy sąsiedztwa „sieci ego”

Nieco tajemnicza jest tylko ostatnia cecha. Można ją interpretować jako miarę tego, czy w sieci istnieją najważniejsze krawędzie i mało ważna reszta, której odrzucenie nie spowoduje dużej utraty informacji.

Mając tak skompresowany opis węzłów, można przystąpić do wykrywania anomalii. Najprostsze algorytmy starają się modelować próbki wielowymiarowym rozkładem Gaussa, a następnie porównują szacowaną gęstość prawdopodobieństwa z wartością progową. Jak się okazuje, sieć społecznościowa jest bardziej skomplikowana i wymaga lepszego pomysłu. Autorzy proponują więc aby przetestować pary cech pod kątem korelacji pomiędzy nimi. W ten sposób znaleziono 3 ciekawe zależności:

  • E jest proporcjonalne do N^x, 1 <= x <= 2
  • W jest proporcjonalne do E^y, y >= 1
  • a jest proporcjonalne do W^z, 0.5 <= z <= 1

W uproszczeniu wykrycie anomalii sprowadza się potem np. do obliczenia przewidywanej wartości liczby krawędzi na podstawie liczby sąsiadów i porównaniu z rzeczywistą wartością w „sieci ego”. Metoda ta posiada jednak wadę, gdyż nie wychwyci węzłów podlegających prawu statystycznemu, ale mimo to różniących się od reszty. Przykładem może być osoba z bardzo dużą liczbą znajomych, którzy często znają się nawzajem, nie tworząc struktury gwiazdy. Rozwiązanie problemu znaleziono w zastosowaniu tzw. metod gęstościowych. Na koniec miary uzyskane z obu algorytmów zagregowano do jednej wartości.

Eksperymenty przeprowadzono na dużych zbiorach danych reprezentujących linki pomiędzy postami w określonym zbiorze blogów, korespondencję pracowników koncernu Enron, komunikację routerów BGP, autorów i ich publikacje na konferencjach naukowych, darczyńców i komitety wyborcze oraz komitety wyborcze i kandydatów. Warto omówić najciekawsze przypadki znalezione przez autorów pracy.

Analiza pierwszej korelacji dla danych z Enronu jako największe anomalie wskazuje CEO oraz dyrektora firmy. Ich wyjątkowość polega na małej liczbie wymienionych wiadomości pomiędzy kontaktami tych osób, co odpowiada „sieciom ego” przypominającym gwiazdę. Myślę, że można by spróbować wyjaśnić taką strukturę połączeń koniecznością koordynacji działań niezależnych grup wewnątrz firmy przez kadrę kierowniczą oraz częstym kierowaniem kopii emaili do przełożonych. Ocenę sytuacji utrudnia fakt, że algorytm OddBall przeszukuje grafy nieskierowane, zatem nie wiemy nic o kierunku interakcji. Dla zbioru danych Postnet jako anomalię wykryto post autora zamieszczającego często linkujące do siebie nawzajem wpisy na wielu blogach, tworząc w ten sposób dużą strukturę podobną do kliki.

Zależność pomiędzy całkowitą wagą „sieci ego” a jej liczbą krawędzi pozwoliła wykryć anomalie w danych dotyczących kandydatów, komitetów wyborczych i ich darczyńców. Wyróżniono takie sytuacje jak wyjątkowo wysoka lub niska kwota dofinansowania przypadająca na kandydata. W oko rzucają się również komitety, które przekazały pojedynczą kwotę oraz kandydaci będący pojedynczymi beneficjentami komitetów. Analizując finansowanie komitetów można również znaleźć węzeł o dużym dofinansowaniu pochodzącym od jednej osoby oraz węzeł z podejrzanie niskim wpływem, co wyjaśniono częstymi zwrotami dotacji.

Wykrywanie anomalii to zagadnienie trudne, nawet gdy obserwujemy dane jednowymiarowe. Potrzeba dużej ilość informacji aby dobrze rozstrzygnąć o rzadkości zjawiska i uniknąć fałszywych alarmów. Gwałtowny rozwój serwisów społecznościowych, większa liczba połączeń telefonicznych oraz operacji bankowych rozwiązują ten problem i pozwalają zastosować metody detekcji anomalii w nowych kontekstach. W wielu sytuacjach pozwoli to odkryć i zareagować na sytuacje niepożądane, jak oszustwa finansowe czy awarie urządzeń. Analiza danych pokazała również, że wykrywanie anomalii może być użyteczną metodą dla szukającego interesujących zjawisk politologa lub socjologa. Jak widać, poruszona tematyka pojawia się w wielu zastosowaniach, więc jeśli szukamy nieregularności w dowolnej sieci połączeń, to może właśnie algorytm OddBall będzie dobrym narzędziem do rozwiązania tego problemu.

Autor: Michał Frankiewicz

Bibliografia

Leman Akoglu, Mary McGlohon, & Christos Faloutsos (2010). OddBall: Spotting anomalies in weighted graphs Advances in Knowledge Discovery and Data Mining, 6119
DOI: 10.1007/978-3-642-13672-6_40

Reklamy

2 komentarze to “Anomalie w „sieciach ego””

  1. Bardzo ciekawa notka. Uzupełniłem ją o właściwe formatowanie bibliografii, więc powinna się za chwilę pojawić na researchblogging.com (potrzebna jest chwila żeby serwis zaindeksował tę notkę)

  2. Udało się, choć nie było łatwo… Notatka pojawiła się w ResearchBlogging.com, najprościej jest poszukać blogu TSISS lub zmienić język czytanych blogów na „Polish”.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d blogerów lubi to: