project Homing/2016-1/7, funded by Foundation for Polish Science, Poland
implemented @ MIM University of Warsaw, 2016-2018.
projekt Homing/2016-1/7, finansowany przez Fundacja na rzecz Nauki Polskiej
realizowany @ MIM Uniwersytet Warszawski, 2016-2018.
The whole world as we know it consists of networks: people are connected in social networks, cities in road networks, neurons in neural networks. The increasing knowledge about the universe around us, a large amount of collected data, as well as the popularization of the Internet have caused in the past two decades enormous interest in new techniques of network analysis. In this project we will address one of the fundamental research problem, which is centrality analysis, i.e., an attempt to answer the question which vertices play a key role in the network, taking into account only the network structure. Scientists have already proposed a number of centrality measures but their multiplicity and lack of a clear distinction between them makes selecting the appropriate measures for a particular application virtually impossible.
The goal of the project is to better understand the centrality measures through the creation of their systematic classification. This classification will be based on the axiomatic approach, i.e., defining the measures not with complicated mathematical formulas, but using a few simple and understandable for everyone properties. Based on the classification we will identify existing or a new measure suitable to each of the three applications: identifying key terrorists in criminal networks, reliable vertices in the Internet of Things, and the most important nodes in biological networks.
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.
University of Oxford, UK
University of WarsawUniwersytet Warszawski, PL
We focus on the game-theoretic approach to centrality analysis. While various centrality indices have been recently proposed based on this approach, it is still unknown how general is the game-theoretic approach to centrality and what distinguishes some game-theoretic centralities from others. In this article, we attempt to answer this question by providing the first axiomatic characterization of game-theoretic centralities. Specifically, we show that every possible centrality measure can be obtained following the game-theoretic approach. Furthermore, we study three natural classes of game-theoretic centrality, and prove that they can be characterized by certain intuitive properties pertaining to Myerson’s well-known notion of Fairness.
This is an extended version of our AAAI-17 paper.
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.
We propose a new centrality measure, called the Random Walk Decay centrality. While most centralities in the literature are based on the notion of shortest paths, this new centrality measure stems from the random walk on the network. We provide an axiomatic characterization and show that the new centrality is closely related to PageRank. More in detail, we show that replacing only one axiom, called Lack of Self-Impact, with another one, called Edge Swap, results in the new axiomatization of PageRank. Finally, we argue that Lack of Self-Impact is desirable in various settings and explain why violating Edge Swap may be beneficial and may contribute to promoting diversity in the centrality measure.
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.
We study the problem of extending the classic centrality measures to weighted graphs. Unfortunately, in the existing extensions, paths in the graph are evaluated solely based on their weights, which is a restrictive and undesirable assumption for a variety of settings. Given this, we define a notion of the path evaluation function that assesses a path between two nodes by looking not only on the sum of edge weights, but also on the number of intermediaries. Using an axiomatic approach, we propose three classes of path evaluation functions. Building upon this analysis, we present the first systematic study how classic centrality measures can be extended to weighted graphs while taking into account an arbitrary path evaluation function. As an application, we use the newly-defined measures to identify the most well-linked districts in a sample public transport network.
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.
We propose an axiomatization of PageRank. Specifically, we introduce five simple axioms – Foreseeability, Outgoing Homogeneity, Monotonicity, Merging, and Dummy Node – and show that PageRank is the only centrality measure that satisfies all of them. Our axioms give a new conceptual and theoretical underpinnings of PageRank and show how it differs from other centralities.
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.
We study the class of distance-based centralities that consists of centrality measures that depend solely on distances to other nodes in the graph. This class encompasses a number of centrality measures, including the classical Degree and Closeness Centralities, as well as their extensions: the Harmonic, Reach and Decay Centralities. We axiomatize the class of distance-based centralities and study what conditions are imposed by the axioms proposed in the literature. Building upon our analysis, we propose the class of additive distance-based centralities and pin-point properties which combined with the axiomatic characterization of the whole class uniquely characterize a number of centralities from the literature.
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.
Feedback centralities are one of the key classes of centrality measures. They assess the importance of a vertex recursively, based on the importance of its neighbours. Feedback centralities includes the Eigenvector Centrality, as well as its variants, such as the Katz Centrality or the PageRank, and are used in various AI applications, such as ranking the importance of websites on the Internet and most influential users in the Twitter social network. In this paper, we study the theoretical underpinning of the feedback centralities. Specifically, we propose a novel axiomatization of the Eigenvector Centrality and the Katz Centrality based on six simple requirements. Our approach highlights the similarities and differences between both centralities which may help in choosing the right centrality for a specific application.
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.
We concentrate on the question how central are nodes in terms of connecting the network. While a few dedicated centrality measures have been proposed, previously Skibski et al. (2016) showed that the Attachment Centrality is the only one that satisfies certain natural axioms desirable for connectivity. Unfortunately, the Attachment Centrality is defined only for unweighted graphs which makes this measure ill-fitted for various applications. For instance, covert networks are typically weighted, where the weights carry additional intelligence available about criminals or terrorists and the links between them. To analyse such settings, in this paper we extend the Attachment Centrality to node-weighted and edge-weighted graphs.
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.
We focus on the game-theoretic approach to centrality analysis. While various centrality indices have been proposed based on this approach, it is still unknown what distinguishes this family of indices from the more classical ones. In this paper, we answer this question by providing the first axiomatic characterization of game-theoretic centralities. Specifically, we show that every centrality can be obtained following the game-theoretic approach, and show that two natural classes of game-theoretic centrality can be characterized by two intuitive properties pertaining to Myerson's notion of Fairness.
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.
