On the expressiveness and structural properties of centrality measures
Loading...
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Centrality measures are used as analytical tools to understand graph-based data in various contexts. They are particularly useful for detecting important agents in disease spreading, influential individuals in social networks, or political decisionmakers. This is primarily due to the diversity of measures and their potential for exploitation in theoretical analyses. However, there exists a gap in the understanding of centrality from a foundational perspective. In this thesis, we provide an in-depth study of centrality measures from two different angles. Firstly, we examine how centralities behave over trees. Due to the simple structure of trees, it is easier to analyze each centrality measure in a restricted setting. We introduce the rooting tree property and propose a framework of potential functions to characterize rooting measures. In the last two Chapters, we present a novel study of the family of subgraph-based centralities (SBMs), which serve as a general framework for developing new measures. To define an SBM, we select a set of important subgraphs relevant to a specific application. The most important vertices are then determined based on the number of important subgraphs surrounding them. Initially, we investigate the absolute and ranking expressiveness of SBMs, answering the question of when an arbitrary centrality measure can be defined as an SBM. This, in turn, allows us to compare commonly used centralities within the scope of SBMs. Finally, we conduct an experimental study of important subgraph-based measures, as well as commonly used measures, using statistical scores such as Pearson correlation, ranking distances, and similarities to identify evidence of closely related measures.
Description
Tesis (Doctor in Engineering Sciences)--Pontificia Universidad Católica de Chile, 2024
Tesis (Doctor of Philosophy)--Pontificia Universidad Católica de Chile, 2024
Tesis (Doctor of Philosophy)--Pontificia Universidad Católica de Chile, 2024
Keywords
Centrality measures, Network science, Graph data bases