Path Evaluation and Centralities in Weighted Graphs - An Axiomatic Approach

Path Evaluation and Centralities in Weighted Graphs - An Axiomatic Approach

Jadwiga Sosnowska, Oskar Skibski

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 3856-3862. https://doi.org/10.24963/ijcai.2018/536

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.
Keywords:
Multidisciplinary Topics and Applications: Social Sciences
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems