Path Evaluation and Centralities in Weighted Graphs – An Axiomatic Approach

Speaker(s)

Jadwiga Sosnowska

Affiliation

Instytut Informatyki UW

Date

March 15, 2018, 10:15 a.m.

Room

room 4790

Seminar

Seminar Games, Mechanisms, and Social Networks

---

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.

---