Centrality - Wikipedia
graph-theorynetwork-analysiscentralitysocial-networks
Abstraction: Taxonomy and definitions of node importance measures in graphs
Key points:
- Major types: degree (immediate connections), closeness (avg shortest path), betweenness (fraction of shortest paths through node), eigenvector (score from neighbors' scores)
- PageRank and Katz centrality are eigenvector centrality variants; PageRank uses left eigenvector with degree scaling
- Betweenness and closeness both require all-pairs shortest paths: O(V³) Floyd-Warshall or O(VE) Brandes' algorithm
- Radial vs. medial and volume vs. length classification (Borgatti & Everett 2006) shows most measures are radial-volume
- Percolation centrality extends betweenness to dynamic spreading/contagion scenarios with node states
- Centrality rankings only identify the most important node reliably; generalization to remaining nodes may be meaningless on heterogeneous networks
Connections: Graph Centrality · Network Analysis · Pagerank · Eigenvector Centrality