A Note on Computing Betweenness Centrality from the 2-core
<|reference_start|>A Note on Computing Betweenness Centrality from the 2-core: A central task in network analysis is to identify important nodes in a graph. Betweenness centrality (BC) is a popular centrality measure that captures the significance of nodes based on the number of shortest paths each node intersects with. In this note, we derive a recursive formula to compute the betweenness centralities of a graph from the betweenness centralities of its 2-core.Furthermore, we analyze mathematically the significant impact of removing degree-one nodes on the estimation of betweenness centrality within the context of the popular pivot sampling scheme for Single-Source Shortest Path (SSSP) computations, as described in the Brandes-Pich approach and implemented in widely used software such as NetworkX. We demonstrate both theoretically and empirically that removing degree-1 nodes can reduce the sample complexity needed to achieve better accuracy, thereby decreasing the overall runtime.<|reference_end|>
@article{tsourakakis2024a,
    title={A Note on Computing Betweenness Centrality from the 2-core},
    author={Charalampos E. Tsourakakis},
    journal={arXiv preprint arXiv:2408.01157},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.01157},
    primaryClass={cs.SI}
}