projekt Homing/2016-1/7, finansowany przez Fundacja na rzecz Nauki Polskiej
ze środków Europejskiego Funduszu Rozwoju Regionalnego
w ramach Programu Operacyjnego Inteligentny Rozwój 2014–2020
realizowany @ MIM Uniwersytet Warszawski, 2016-2018.
Kwota finansowania: 796 260 PLN
Cały świat jaki znamy składa się z sieci: ludzie połączeni są w sieci społeczne, miasta w sieci drogowe, a komórki nerwowe w sieci neuronowe. Coraz większa wiedza o otaczającym nas wszechświecie, duża ilość zebranych danych, a także popularyzacja internetu spowodowały w ostatnich dwóch dekadach olbrzymie zainteresowanie nowymi technikami analizy sieci. W tym projekcie zamierzamy zająć się jednym z fundamentalnych problemów badawczych, jakim jest tzw. analiza centralności, czyli próba odpowiedzenia na pytanie, które wierzchołki odgrywają kluczową rolę w sieci, biorąc pod uwagę jedynie jej strukturę. Naukowcy zaproponowali już wiele miar centralności jednak ich mnogość i brak jasnego rozróżnienia pomiędzy nimi, powoduje, że wybranie odpowiedniej miary dla konkretnego zastosowania jest praktycznie niemożliwe.
Celem projektu jest lepsze zrozumienie miar centralności poprzez stworzenie ich systematycznej klasyfikacji. Klasyfikacja ta będzie opierać się na podejściu aksjomatycznym, czyli zdefiniowaniu danej miary nie za pomocą skomplikowanych wzorów matematycznych, a przy pomocy kilku prostych i zrozumiałych dla każdego cech. Na podstawie klasyfikacji wskażemy istniejącą lub nową miarę pasującą do każdego z trzech zastosowań: identyfikowanie kluczowych przestępców w sieciach kryminalnych, wiarygodnych wierzchołków w Internecie Rzeczy oraz najważniejszych węzłów w sieciach biologicznych.
Skupiamy się na teoriogrowym podejściu do analizy centralności. Mimo że wiele miar centralności zostało zaproponowanych z użyciem tego podejście, wciąż nie wiadomo jak ogólne jest to podejście i co odróżnia niektóre teoriogrowe miary centralności od innych. W tej pracy odpowiadamy na to pytanie przedstawiając pierwszą aksjomatyczną charakteryzację teorio-growych miar centralności. W szczególności pokazujemy, że każda miara centralności może być uzyskana z użyciem podejścia teoriogrowego. Ponadto badamy trzy naturalne klasy teoriogrowych centralności i pokazujemy, że mogą być one scharakteryzowane przez dwie intuicyjne właściwości odnoszące się słynnego pojęcia uczciwości Myersona.
Ta praca jest rozszerzoną wersją pracy z AAAI-17.
Proponujemy nową miarę centralności - Random Walk Decay. Podczas gdy większość centralności w literaturze jest opartych na pojęciu najkrótszych ścieżek, nasza nowa centralność wynika z losowego błądzenia w sieci. Przedstawiamy aksjomatyczną charakteryzację i pokazujemy, że nowa centralność jest blisko związana z PageRankiem. Dokładniej pokazujemy, że zamienienie jednego aksjomatu, Lack of Self-Impact, na inny, Edge Swap, prowadzi do nowej aksjomatyzacji PageRanka. W końcu pokazujemy, że aksjomat Lack of Self-Impact jest pożądany w niektórych sytuacjach i wyjaśniamy czemu niespełnianie aksjomatu Edge Swap może być korzystne i kontrybuować do promowania różnorodności przez miarę centralności.
Badamy problem rozszerzenia klasycznych miar centralności do ważonych grafów. Niestety w istniejących rozszerzeniach ścieżki w grafach sa oceniane jedynie na podstawie ich wag, co w wielu sytuacjach jest ograniczającym i niechcianym założeniem. W związku z tym proponujemy pojęcie funkcji oceny ścieżki, która nadaje ścieżce pomiędzy dwoma wierzchołkami wartość biorąc pod uwagę nie tylko sumę wag na krawędziach, ale także liczbę pośredników. Używając podejścia aksjomatycznego proponujemy trzy klasy funkcji oceny ścieżki. Bazując na tej analizie przedstawiamt pierwszą systematyczną analizę jak klasyczne miary centralności mogą być rozszerzone do ważonych grafów bazując na dowolnej funkcji oceny ścieżki. Jako aplikację używamy nowo zdefiniowanych miar do identyfikacji dobrze połączonych dzielnic w przykładowej sieci transportu miejskiego.
Proponujemy aksjomatykę PageRanka. W tym celu proponujemy pięć prostych alksjomatów - Foreseeability, Outgoing Homogeneity, Monotonicity, Merging, oraz Dummy Node - i pokazujemy, że PageRank jest jedyną miarą centralności która spełnia je wszystkie. Nasze aksjomaty dają nowy wgląd w działanie PageRanka i podkreślają czym różni się on od innych miar centralności.
W tej pracy analizowaliśmy klasę miar centralności zależnych jedynie od odległości do innych wierzchołków w grafie. Do tej klasy zalicza się szereg miar, w szczególności dwie najbardziej podstawowe - miarę stopnia i miarę bliskości oraz ich rozszerzenia - miarę harmoniczną, miarę zasięgu i miarę zanikania. W pracy przedstawiliśmy aksjomatyzację zaproponowanej klasy oraz badaliśmy, jaki wpływ na nią mają aksjomaty znane z literatury. Opierając się na tej analizie, zaproponowaliśmy addytywną podklasę i pewne właściwości, które w połączeniu z aksjomatyczną charakteryzacją całej klasy definiują w sposób unikalny szereg miar centralności znanych z literatury.
Centralności zwrotne (Feedback centralities) są jedną z ważniejszych klas miar centralności. Określają one istotność danego wierzchołka rekursywnie, na podstawie istotności wierzchołków w jego sąsiedztwie. Do tej klasy należy przede wszystkim centralność wektora własnego (Eigenvector Centrality), a także jego modyfikacje, takie jak centralność Katza (Katz Centrality) czy PageRank. Centralności te mają wiele zastosowań w sztucznej inteligencji, między innymi pozycjonowanie stron internetowych albo określanie najbardziej wpływowych użytkowników Twittera. W naszej pracy badamy teoretyczne podstawy, które ze nimi stoją. Mówiąc dokładniej, proponujemy nową aksjomatyzację centralności wektora własnego oraz centralności Katza, opierającą się na sześciu prostych własnościach. Nasze podejście podkreśla podobieństwa i różnice między obiema miarami, co może pomóc w odpowiednim wyborze centralności do danego zastosowania.
W tej pracy koncentrowaliśmy się na pytaniu, jak dużą rolę ogrywa wierzchołek w łączeniu sieci. W literaturze proponowanych jest kilka miar, ale jak pokazano w pracy Skibski et al. (2016) jedynie miara Attachment spełnia szereg aksjomatów naturalnych z punktu widzenia łączenia. Niestety, miara Attachment jest zdefiniowana tylko dla grafów nieważonych, przez co nie można jej zaaplikować do wielu zastosowań, np. sieci kryminalne są zazwyczaj ważone, a wagi niosą dodatkowe informacje o kryminalistach czy terrorystach i połączeniach między nimi. Aby móc analizować takie przypadki, w tej pracy rozszerzyliśmy miarę Attachment na grafy ważone zarówno wierzchołkowo jak i krawędziowo.
Skupiamy się na teoriogrowym podejściu do analizy centralności. Mimo że wiele miar centralności zostało zaproponowanych z użyciem tego podejście, wciąż nie wiadomo co odróżnia te miary od miar klasycznych. W tej pracy odpowiadamy na to pytanie przedstawiając pierwszą aksjomatyczną charakteryzację teorio-growych miar centralności. W szczególności pokazujemy, że każda miara centralności może być uzyskana z użyciem podejścia teoriogrowego i pokazujemy, że dwie naturalne klasy teoriogrowych centralności mogą być scharakteryzowane przez dwie intuicyjne właściwości odnoszące się pojęcia uczciwości Myersona.
