Closeness Centrality via the Condorcet Principle
This work addresses theoretical foundations in network analysis for researchers in graph theory and centrality measures, but it is incremental as it builds on existing concepts without broad practical applications.
The paper tackles the problem of relating Closeness centrality to the Condorcet principle in graph theory, showing that Closeness centrality and its random-walk version are the only classic centrality measures that are Condorcet consistent on trees, and that Closeness centrality uniquely satisfies the Condorcet Comparison property for adjacent nodes in general graphs.
We uncover a new relation between Closeness centrality and the Condorcet principle. We define a Condorcet winner in a graph as a node that compared to any other node is closer to more nodes. In other words, if we assume that nodes vote on a closer candidate, a Condorcet winner would win a two-candidate election against any other node in a plurality vote. We show that Closeness centrality and its random-walk version, Random-Walk Closeness centrality, are the only classic centrality measures that are Condorcet consistent on trees, i.e., if a Condorcet winner exists, they rank it first. While they are not Condorcet consistent in general graphs, we show that Closeness centrality satisfies the Condorcet Comparison property that states that out of two adjacent nodes, the one preferred by more nodes has higher centrality. We show that Closeness centrality is the only regular distance-based centrality with such a property.