Fast approximation of betweenness centrality through sampling

DOI10.1007/s10618-015-0423-0zbMath1411.91458OpenAlexW1029409534WikidataQ60113138 ScholiaQ60113138MaRDI QIDQ1741154

Matteo Riondato, Evgenios M. Kornaropoulos

Publication date: 3 May 2019

Published in: Data Mining and Knowledge Discovery (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10618-015-0423-0

zbMATH Keywords

samplingVC-dimensionapproximation algorithmssocial network analysisbetweenness centrality

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (17)

A multi-stage hierarchical clustering algorithm based on centroid of tree and cut edge constraint ⋮ Compressive sensing of high betweenness centrality nodes in networks ⋮ Improving the Betweenness Centrality of a Node by Adding Links ⋮ Dynamic Merging of Frontiers for Accelerating the Evaluation of Betweenness Centrality ⋮ Towards classifying the polynomial-time solvability of temporal betweenness centrality ⋮ A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs ⋮ Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality ⋮ Estimating the clustering coefficient using sample complexity analysis ⋮ Finding groups with maximum betweenness centrality via integer programming with random path sampling ⋮ An Adaptive Version of Brandes' Algorithm for Betweenness Centrality ⋮ KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation ⋮ Fast approximation of betweenness centrality through sampling ⋮ Optimizing node infiltrations in complex networks by a local search based heuristic ⋮ Percolation centrality via Rademacher Complexity ⋮ Approximating Betweenness Centrality in Fully Dynamic Networks ⋮ Incorporating auxiliary information in betweenness measure for input-output networks ⋮ Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs

Uses Software

• igraph
• NetworKit

Cites Work

• Unnamed Item
• Unnamed Item
• Relative \((p,\varepsilon )\)-approximations in geometry
• The VC-dimension of set systems defined by graphs
• Fast approximation of betweenness centrality through sampling
• A faster algorithm for betweenness centrality*
• VC-Dimension and Shortest Path Algorithms
• Emergence of Scaling in Random Networks
• Fully-Dynamic Approximation of Betweenness Centrality
• Routing betweenness centrality
• Shape Fitting on Point Sets with Probability Distributions
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Fast Approximation of Centrality
• Neural Network Learning
• Approximating Betweenness Centrality in Large Evolving Networks
• Better Approximation of Betweenness Centrality
• Fast and Simple Approximation of the Diameter and Radius of a Graph
• Probability Inequalities for Sums of Bounded Random Variables
• Approximating Betweenness Centrality
• Probability and Computing
• Understanding Machine Learning
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Network Analysis
• CENTRALITY ESTIMATION IN LARGE NETWORKS
• Networks
• Improved bounds on the sample complexity of learning

This page was built for publication: Fast approximation of betweenness centrality through sampling