Closeness centrality via the Condorcet principle

Speaker(s)

Oskar Skibski

Affiliation

University of Warsaw

Date

Feb. 2, 2023, noon

Information about the event

zoom meeting

Seminar

Seminar Games, Mechanisms, and Social Networks

---

We provide a characterization of closeness centrality in the class of distance-based centralities. To this end, we introduce a natural property, called majority comparison, that states that out of two adjacent nodes the one closer to more nodes is more central. We prove that any distance-based centrality that satisfy this property gives the same ranking in every graph as closeness centrality. The axiom is inspired by the interpretation of the graph as an election in which nodes are both voters and candidates and their preferences are determined by the distances to the other nodes. Given this, majority comparison states that out of two adjacent nodes the one preferred by more nodes should have higher centrality.

We provide a characterization of closeness centrality in the class of distance-based centralities. To this end, we introduce a natural property, called majority comparison, that states that out of two adjacent nodes the one closer to more nodes is more central. We prove that any distance-based centrality that satisfy this property gives the same ranking in every graph as closeness centrality. The axiom is inspired by the interpretation of the graph as an election in which nodes are both voters and candidates and their preferences are determined by the distances to the other nodes. Given this, majority comparison states that out of two adjacent nodes the one preferred by more nodes should have higher centrality.

---