

























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。