KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation

DOI10.1145/3284359OpenAlexW2344526012WikidataQ124937204 ScholiaQ124937204MaRDI QIDQ4629536

Michele Borassi, Emanuele Natale

Publication date: 27 March 2019

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.08553

zbMATH Keywords

samplingnetwork analysisshortest path algorithmgraph miningbetweenness centrality

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (3)

Deterministic performance guarantees for bidirectional BFS on real-world networks ⋮ Finding groups with maximum betweenness centrality via integer programming with random path sampling ⋮ Incorporating auxiliary information in betweenness measure for input-output networks

Uses Software

• KADABRA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper and lower bounds for the \(q\)-entropy of network models with application to network model selection
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Which problems have strongly exponential complexity?
• Fast approximation of betweenness centrality through sampling
• Query size estimation by adaptive sampling
• A note on the complexity of computing the number of reachable vertices in a digraph
• A faster algorithm for betweenness centrality*
• Random Graphs and Complex Networks
• Alternative Route Graphs in Road Networks
• Fully-Dynamic Approximation of Betweenness Centrality
• Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
• Routing betweenness centrality
• Adaptive Sampling for k-Means Clustering
• An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
• Dynamic Merging of Frontiers for Accelerating the Evaluation of Betweenness Centrality
• Fast Approximation of Centrality
• Computing Top-k Closeness Centrality Faster in Unweighted Graphs
• The phase transition in inhomogeneous random graphs
• The diameter of sparse random graphs
• Approximating Betweenness Centrality
• On a conditionally Poissonian graph process
• Network Analysis
• CENTRALITY ESTIMATION IN LARGE NETWORKS
• Networks

This page was built for publication: KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation