Discriminating Power of Centrality Measures

Abstract

The calculation of centrality measures is common practice in the study of networks, as they attempt to quantify the importance of individual vertices, edges, or other components. Different centralities attempt to measure importance in different ways. In this paper, we examine a conjecture posed by E. Estrada regarding the ability of several measures to distinguish the vertices of networks. Estrada conjectured that if all vertices of a graph have the same subgraph centrality, then all vertices must also have the same degree, eigenvector, closeness, and betweenness centralities. We provide a counterexample for the latter two centrality measures and propose a revised conjecture.

Working paper; comments welcome. 10 pages, 9 figures

References in corpus (3)

• Communicability in complex networks
• The Physics of Communicability in Complex Networks
• On walk-regular graphs and graphs with symmetric hitting times

Cited by in corpus (3)

• About the Discriminant Power of the Subgraph Centrality and Other Centrality Measures About the Discriminant Power of the Subgraph Centrality and Other Centrality Measures(Working paper)
• Vertex distinction with subgraph centrality: a proof of Estrada's conjecture and some generalizations
• New results and open problems on subgraph centrality