## Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

• Skala szarości
• Wysoki kontrast
• Negatyw
• Reset

# Aktualności — Wydarzenia

Games, Mechanisms, and Social Networks

## Closeness centrality via the Condorcet principle

Prelegent: Oskar Skibski

2023-02-02 12:00

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.