Axiomatization of the Walk-Based Centrality Measures

Miary centralności są jednym z podstawowych narzędzi analizy sieci. Nadają one każdemu wierzchołkowi wartość, określającą jak jest on istotny. Analiza centralności znajduje wiele zastosowań w szerokiej gamie dziedzin: od nauk społecznych i ekonomii, przez biologię i fizykę, po komunikację i informatykę. Jednak to, co rozumiemy przez istotność wierzchołka, zależy od kontekstu konkretnego zastosowania. W związku z tym oraz stale rosnącą liczbą zaproponowanych miar, wybór odpowiedniej z nich do danej sytuacji jest niezwykle trudny. Różne miary centralności potrafią dać znacząco różne wyniki, problem ten ma więc zasadnicze znaczenie. Niezbędne jest zatem opracowanie teorii, która pozwoli lepiej zrozumieć te miary i pomoże wskazać właściwą z nich do zastosowania w konkretnej sytuacji. Metodą, którą możemy się w tym celu posłużyć, jest aksjomatyzacja. Polega ona na opracowaniu zbioru kilku prostych i intuicyjnych własności, aksjomatów, charakterystycznych dla danej miary centralności. Następnie formalnie udowadniamy, że tylko ta konkretna miara spełnia wszystkie te aksjomaty jednocześnie. W ten sposób otrzymujemy jej intuicyjną charakterystykę i teoretyczne podstawy do jej stosowania. Możemy bowiem stwierdzić czy powinniśmy zastosować miarę centralności w danej sytuacji, decydując czy charakteryzujące ja aksjomaty są pożądane. Aksjomatyczne podejście do analizy miar centralności zyskuje popularność w literaturze ostatnich lat. Charakteryzacje zostały opracowane dla takich centralności, jak centralność bliskości (ang. closeness centrality), miara beta (ang. beta measure), czy centralność łączenia (ang. attachment centrality). Jednak wiele znanych miar nadal nie ma swoich charakteryzacji. Do niedawna centralnością bez aksjomatyzacji był również PageRank – jedna z najpopularniejszych miar centralności. Niniejsza rozprawa wpisuje się w ten nurt i oferuje następujący wkład: Po pierwsze, prezentujemy pierwszą w literaturze aksjomatyczną charakteryzację PageRanka. Po drugie, tworzymy spójne aksjomatyzacje trzech miar centralności: centralności zanikania (ang. decay centrality), PageRanka oraz nowej miary – centralności zanikania błądzenia losowego (ang. random walk decay centrality). Z naszej analizy wynika, że własności centralności zanikania błądzenia losowego w znacznej mierze pokrywają się z własnościami PageRanka, lecz jednocześnie może się ona lepiej sprawdzać w niektórych zastosowaniach. Po trzecie, uogólniamy aksjomatyzację PageRanka, aby stworzyć pierwszy spójny system aksjomatyczny dla czterech podstawowych centralności zwrotnych (ang. feedback centralities).

Centrality measures are one of the fundamental tools of network science. Their role is to assign to every node of a network a value that reflects the importance of this node. Centrality analysis finds numerous applications in the wide variety of fields: from social studies and economics, through biology and physics, to transportation and computer science. However, what it means for a node to be important heavily depends on the context of a particular application. This, along with the ever growing number of proposed measures, makes the choice of a centrality to use a difficult task. Since different centrality measures return very different results, this problem is of utmost importance. Hence, there is a need for research that will provide a better understanding of centrality measures and will help decide upon a centrality measure to use in a specific application. A method that allows for achieving this goal is axiomatization. In this approach, we introduce a set of simple properties, called axioms, that characterize a given centrality measure. Then we formally prove that only this particular measure satisfies all of the axioms at the same time. In this way, we obtain an intuitive characterization of the centrality measure in question and its theoretical foundation. Moreover, by analyzing whether the axioms are desired, we can decide if this measure is well-suited for a particular ap plication at hand. In recent years, the axiomatic approach to centrality measures has been gaining popularity in the literature. Axiomatic characterizations have been created for many centrality measures, such as closeness, beta measure, or attachment. However, for many centrality measures such characterizations are still missing. Until recently, PageRank—one of the most popular centrality measures—was also lacking its axiomatization. Against this background, the main contributions of this thesis are as fol lows: First, we introduce the first in the literature axiomatic characterization of PageRank. Next, we create a coherent axiomatization of three centrality measures: decay centrality, PageRank, and a novel measure—random walk decay centrality. Our analysis shows that while random walk decay cen trality retains a majority of PageRank’s properties, it may be more desirable than PageRank in some settings. Finally, we generalize our axiomatization of PageRank to create a consistent axiom system for four classic feedback centralities: eigenvector and Katz centralities, Seeley index, and PageRank.