How to choose the most appropriate centrality measure? A decision tree approach
arXiv:2003.01052 · doi:10.1109/TSMC.2024.3510633
Abstract
Centrality metrics play a crucial role in network analysis, while the choice of specific measures significantly influences the accuracy of conclusions as each measure represents a unique concept of node importance. Among over 400 proposed indices, selecting the most suitable ones for specific applications remains a challenge. Existing approaches -- model-based, data-driven, and axiomatic -- have limitations, requiring association with models, training datasets, or restrictive axioms for each specific application. To address this, we introduce the culling method, which relies on the expert concept of centrality behavior on simple graphs. The culling method involves forming a set of candidate measures, generating a list of as small graphs as possible needed to distinguish the measures from each other, constructing a decision-tree survey, and identifying the measure consistent with the expert's concept. We apply this approach to a diverse set of 40 centralities, including novel kernel-based indices, and combine it with the axiomatic approach. Remarkably, only 13 small 1-trees are sufficient to separate all 40 measures, even for pairs of closely related ones. By adopting simple ordinal axioms like Self-consistency or Bridge axiom, the set of measures can be drastically reduced making the culling survey short. Applying the culling method provides insightful findings on some centrality indices, such as PageRank, Bridging, and dissimilarity-based Eigencentrality measures, among others. The proposed approach offers a cost-effective solution in terms of labor and time, complementing existing methods for measure selection, and providing deeper insights into the underlying mechanisms of centrality measures.
arXiv comment12 pages, 2 tables, 1 algorithm, 8 figures. Presentation has been improved
References in corpus (16)
- Subgraph Centrality in Complex Networks
- Vital nodes identification in complex networks
- Harmony in the Small-World
- Consistency and differences between centrality measures across distinct classes of networks
- A Survey on Centrality Metrics and Their Implications in Network Resilience
- The Key Player Problem in Complex Oscillator Networks and Electric Power Grids: Resistance Centralities Identify Local Vulnerabilities
- Using Node Centrality and Optimal Control to Maximize Information Diffusion in Social Networks
- A Class of Graph-Geodetic Distances Generalizing the Shortest-Path and the Resistance Distances
- The Walk Distances in Graphs
- A general centrality framework based on node navigability
- The Forest Metrics for Graph Vertices
- Similarities on Graphs: Kernels versus Proximity Measures
- Measuring centrality by a generalization of degree
- Studying new classes of graph metrics
- The graph bottleneck identity
- Selection of Centrality Measures Using Self-Consistency and Bridge Axioms