Closeness Centrality via the Condorcet Principle
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Distance entropy cartography characterises centrality in complex networks
We introduce distance entropy as a measure of homogeneity in the distribution of path lengths between a given node and its neighbours in a complex network. Distance entropy defines a new centrality measure whose properti…
Graph Neural Networks for Scalable and Transferable Node Centrality Approximation
Graph Neural Networks (GNNs) provide a learning-based framework for approximating graph quantities that are expensive to compute exactly. This paper investigates GNNs for scalable approximation of betweenness and closene…
Compressive Closeness in Networks
Distributed algorithms for network science applications are of great importance due to today's large real-world networks. In such algorithms, a node is allowed only to have local interactions with its immediate neighbors…
Compressive SensingForecasting managerial turnover through e-mail based social network analysis
In this study we propose a method based on e-mail social network analysis to compare the communication behavior of managers who voluntarily quit their job and managers who decide to stay. Collecting 18 months of e-mail, …
Graph Centrality Measures for Boosting Popularity-Based Entity Linking
Many Entity Linking systems use collective graph-based methods to disambiguate the entity mentions within a document. Most of them have focused on graph construction and initial weighting of the candidate entities, less …
Entity Linkinggraph constructionGraph Ranking