# QuickCent: a fast and frugal heuristic for harmonic centrality estimation on scale-free networks

arXiv: https://arxiv.org/abs/2303.00927 · HTML: https://mlsanity.com/paper/2303.00927/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 78 references that are in the map.
- First posted on arXiv 2 Mar 2023.

## Builds on (most cited first, 9 of 9)

- [Scale-free networks are rare](https://mlsanity.com/paper/1801.03400/) (2018)
- [Axioms for Centrality](https://mlsanity.com/paper/1308.2140/) (2013)
- [Scale-free Networks Well Done](https://mlsanity.com/paper/1811.02071/) (2018)
- [Computing All-Pairs Shortest Paths by Leveraging Low Treewidth](https://mlsanity.com/paper/1401.4609/) (2014)
- [Predicting User Roles in Social Networks using Transfer Learning with Feature Transformation](https://mlsanity.com/paper/1611.02941/) (2016)
- [Computing Classic Closeness Centrality, at Scale](https://mlsanity.com/paper/1409.0035/) (2014)
- [Exactly scale-free scale-free networks](https://mlsanity.com/paper/1309.0961/) (2013)
- [On a minimum distance procedure for threshold selection in tail analysis](https://mlsanity.com/paper/1811.06433/) (2018)
- [Finding Early Adopters of Innovation in Social Network](https://mlsanity.com/paper/2210.13907/) (2022)

## Abstract (arXiv)

We present a simple and quick method to approximate network centrality indexes. Our approach, called QuickCent, is inspired by so-called fast and frugal heuristics, which are heuristics initially proposed to model some human decision and inference processes. The centrality index that we estimate is the harmonic centrality, which is a measure based on shortest-path distances, so infeasible to compute on large networks. We compare QuickCent with known machine learning algorithms on synthetic data generated with preferential attachment, and some empirical networks. Our experiments show that QuickCent is able to make estimates that are competitive in accuracy with the best alternative methods tested, either on synthetic scale-free networks or empirical networks. QuickCent has the feature of achieving low error variance estimates, even with a small training set. Moreover, QuickCent is comparable in efficiency -- accuracy and time cost -- to those produced by more complex methods. We discuss and provide some insight into how QuickCent exploits the fact that in some networks, such as those generated by preferential attachment, local density measures such as the in-degree, can be a proxy for the size of the network region to which a node has access, opening up the possibility of approximating centrality indices based on size such as the harmonic centrality. Our initial results show that simple heuristics and biologically inspired computational methods are a promising line of research in the context of network measure estimations.