Bavarian: Betweenness Centrality Approximation with Variance-Aware Rademacher Averages
Bavarian: Betweenness Centrality Approximation with Variance-Aware Rademacher Averages
复制标题
DOI：
10.1145/3447548.3467354
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Cyrus Cousins;Chloe Wohlgemuth;Matteo Riondato
中科院分区：
文献类型：
--
作者：
Cyrus Cousins;Chloe Wohlgemuth;Matteo Riondato
我们提出了巴伐利亚，这是一个基于抽样的算法的集合，用于近似图中所有顶点的中间性中心性（BC）。我们的算法使用Monte-Carlo经验Rademacher平均（MCERAS）（MCERAS），这是一种统计学习理论的概念，可以有效地计算出估计值与确切值的最大偏差的紧密界限。由于使用方差感知概率的尾巴界限，MCERA提供的依赖样品依赖性近似保证比最高的状态要强得多。 MCERA的灵活性使我们能够引入一个统一的框架，该框架可以与BC的现有基于采样的估计量进行实例化，从而可以进行公平的比较，从而与最初引入的样本复杂性结果脱钩。此外，我们证明了新型样品复杂性结果表明，对于所有估计量，足以获得所需近似保证的样本量取决于图形的顶点直径，这是一个易于结合的特征数量。我们还显示了对其他中心度度量（例如渗透中心性）的进行性采样算法和扩展。我们对巴伐利亚的广泛实验评估表明，MCERA对最先进的最新技术的改善，它使我们能够评估不同估计器提供的样本量和准确性保证之间的不同权衡。
We present Bavarian, a collection of sampling-based algorithms for approximating the Betweenness Centrality (BC) of all vertices in a graph. Our algorithms use Monte-Carlo Empirical Rademacher Averages (MCERAs), a concept from statistical learning theory, to efficiently compute tight bounds on the maximum deviation of the estimates from the exact values. The MCERAs provide a sample-dependent approximation guarantee much stronger than the state of the art, thanks to its use of variance-aware probabilistic tail bounds. The flexibility of the MCERA allows us to introduce a unifying framework that can be instantiated with existing sampling-based estimators of BC, thus allowing a fair comparison between them, decoupled from the sample-complexity results with which they were originally introduced. Additionally, we prove novel sample-complexity results showing that, for all estimators, the sample size sufficient to achieve a desired approximation guarantee depends on the vertex-diameter of the graph, an easy-to-bound characteristic quantity. We also show progressive-sampling algorithms and extensions to other centrality measures, such as percolation centrality. Our extensive experimental evaluation of Bavarian shows the improvement over the state-of-the art made possible by the MCERA, and it allows us to assess the different trade-offs between sample size and accuracy guarantee offered by the different estimators.