project Homing/2016-1/7, funded by Foundation for Polish Science, Poland
from the European Regional Development Fund
under the Smart Growth Operational Program 2014-2020
implemented @ MIM University of Warsaw, 2016-2018.
Amount of funding: 796 260 PLN
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.
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.
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.
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.
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.
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.
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.
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.
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.
