Estimation and update of betweenness centrality with progressive algorithm and shortest paths approximation.

ABSTRACT: Betweenness centrality is one of the key measures of the node importance in a network. However, it is computationally intractable to calculate the exact betweenness centrality of nodes in large-scale networks. To solve this problem, we present an efficient CBCA (Centroids based Betweenness Centrality Approximation) algorithm based on progressive sampling and shortest paths approximation. Our algorithm firstly approximates the shortest paths by generating the network centroids according to the adjacency information entropy of the nodes; then constructs an efficient error estimator using the Monte Carlo Empirical Rademacher averages to determine the sample size which can achieve a balance with accuracy; finally, we present a novel centroid updating strategy based on network density and clust

SUBMITTER: Xiang N 

PROVIDER: S-EPMC10564764 | biostudies-literature | 2023 Oct

REPOSITORIES: biostudies-literature