Home / Curated / Algorithms / KADABRA adaptive betweenness approximation

KADABRA adaptive betweenness approximation

Algorithms AIMech:KADABRAAdaptiveBetweenness DRAFT

Aliases: KADABRA, KADABRA all-node adaptive betweenness approximation

An adaptive sampling algorithm for static-graph betweenness that averages internal-node indicators of uniformly sampled shortest paths and stops when node-specific confidence radii meet an additive tolerance or a predetermined sample horizon is reached.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 693 native identities; no normalized match. Ignored- and hidden-inclusive searches of three full checkouts returned 59,0,0 lines, all read as existing KADABRA leads, source-reading notes or query strings. Semantic assessment covered 155 AIO and 538 native definitions: the prior 154 AIO and 536 native rows were verified unchanged, with BidirectionalLayer, ABRA-s-fix and Apriori additions read. Eleven complete AIO contexts and seven full native neighbors were assessed. The maintained identity is the all-node adaptive stopping procedure for sampled shortest-path indicators, using a fixed sample horizon and node-specific confidence radii. It differs from fixed-size RK path sampling, progressive or fixed ABRA pair fractions, exact dependency accumulation, electrical-flow methods, and the path-sampling subroutine alone. Top-k output and the pilot-budget optimization heuristic require separate scope assessment.

Claims & Grounded Evidence

6 Claims

Scope #domain-and-estimand

The maintained scope is a finite simple static unweighted directed or undirected graph with n>=3, additive tolerance lambda and failure budget delta in (0,1), and exact shortest-path counting and sampling. Independently sample each ordered pair of distinct endpoints uniformly from n(n-1) possibilities, then select one of its shortest paths uniformly. An unreachable pair contributes an empty path. For each node, average the indicators that it lies internally on the sampled path; endpoints and unreachable pairs contribute zero. The target is shortest-path betweenness normalized by n(n-1).

supports Source: KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation · Locator: Section 2, PDF pp. 4–6; Section 4, p. 7; Appendix A notation, p. 15

Mechanism #balanced-path-sampling

The path sampler expands an entire BFS frontier from the side with smaller incident-edge volume. For directed graphs, the source search follows outgoing arcs and the target search follows incoming arcs. At the first connecting frontier, finish collecting the meeting edges. Choose meeting edge (v,w) with weight sigma_sv times sigma_wt, then backtrack prefix and suffix using their shortest-path counts. Choosing the first meeting edge, or choosing meeting edges uniformly despite unequal counts, need not sample complete shortest paths uniformly.

supports Source: KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation · Locator: Section 4, PDF p. 7; curator path-law calculations in research/discovery/kadabra-path-boundaries.py

Mechanism #fixed-horizon-and-tail-budgets

Before the main sample stream, fix a positive integer horizon Omega whose fixed-time all-node additive-error failure probability is at most delta/2. Also fix positive lower and upper node budgets whose total is at most delta/2; uniform budgets delta/(4n) satisfy this requirement. Pilot-dependent budgets require a separate pilot and an independent main stream, conditioning on the pilot choices. A conservative curator alternative to the source’s graph-dependent horizon is ceil(ln(4n/delta)/(2 lambda^2)), from its two-sided Hoeffding bound and a union bound. This alternative is explicitly not the paper’s optimized RK horizon or experimental configuration.

supports Source: KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation · Locator: Section 2 and Remark 1, PDF pp. 5–6; Sections 3 and Appendix C, pp. 6–7 and 17–19; independent pilot described in Appendix D, pp. 19–20; curator Hoeffding cap derived from p. 5

Mechanism #confidence-radii-and-stopping

At positive sample count tau<=Omega, use the sample mean h for each node. For its lower budget let L=ln(1/delta_L) and f=(L/tau)[1/3-Omega/tau+sqrt((1/3-Omega/tau)^2+2h Omega/L)]. For the upper budget let U=ln(1/delta_U) and g=(U/tau)[1/3+Omega/tau+sqrt((1/3+Omega/tau)^2+2h Omega/U)]. Stop when both radii are at most lambda for every node, or when tau reaches Omega, and return the sample means. Increment tau once per path draw, including an empty path, and normalize counters before using these formulas. The source’s bounded stopping-time analysis, combined with the fixed-time cap, supports a simultaneous additive-error statement under these assumptions; fixed-time concentration alone does not justify plugging in an arbitrary random stopping time.

supports Source: KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation · Locator: Algorithm 1 and Section 3, PDF pp. 6–7; Theorem 2, p. 5; Appendix C, Theorem 9 and Equations 5–6, pp. 17–19

Limitation #boundary-and-transcription-limits

The record describes positive-time means, not a literal execution of the printed pseudocode: Algorithm 1 displays raw counters where the confidence formulas need means and initializes tau=0. At true and estimated score zero, f=0, so the printed inclusive lower-tail failure event includes equality with probability one; closed-interval coverage instead treats only strict outside errors as failures. Integer horizon rounding and the log(VD-2) small-diameter boundary also need explicit handling. Curator checks on a zero-score triangle with delta=0.1, lambda=0.05, uniform tail budgets and the conservative cap give Omega=958 and an early stopping count of 462. This finite example is not a certification of every printed proof or numerical implementation.

supports Source: KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation · Locator: Algorithm 1, PDF p. 6; horizon expression, p. 5; Theorem 9 and proof, pp. 17–19; explicit curator calculation in research/discovery/kadabra-path-boundaries.py

Limitation #identity-and-evaluation-limits

This algorithm samples one path indicator per pair rather than ABRA’s exact pair fraction. Both can target the same normalized score while having different variances: a curator four-node diamond example gives mean 1/12, indicator variance 11/144 and pair-fraction variance 5/144 for a selected node. Fixed-size unbiasedness does not imply unbiasedness of the stopped mean. Historical C++/gcc 5.3.1 experiments on directed and undirected networks compare against RK and the earlier 2016 ABRA implementation; they do not establish superiority over revised 2018 ABRA or current software. General graph runtimes, exact top-k ordering, dynamic updates and heuristic pilot optimization are outside this record’s guarantee.

supports Source: KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation · Locator: Sections 2–6, PDF pp. 4–12; Appendix D and Appendix F, pp. 19–20 and 25–37; finite variance comparison in research/discovery/kadabra-path-boundaries.py

⚠️ Curated Limitations & Negative Results

The confidence interpretation requires iid uniform pair/path draws, a certified deterministic horizon, budgets fixed independently of the main stream, and conservative numerical evaluation. It is not an unlimited-time or adaptive-adversary guarantee.
No stopped-mean unbiasedness, relative-error bound, exact unique ranking, weighted BFS extension or dynamic-graph guarantee is asserted.
The source’s pilot allocation heuristic has zero-estimate and transcription boundaries that require a separate implementation assessment. Uniform fixed budgets suffice for the maintained core scope.
The source has printed equality, counter-normalization and proof-notation issues. The record preserves these caveats and does not certify literal pseudocode, every proof display or author software.
The conservative Hoeffding horizon and finite path-law/variance examples are labeled curator mathematics, not reported author experiments. The graph-dependent RK horizon requires its own valid diameter, constant and rounding choices.
The 2016 source’s conditional random-graph and historical performance claims are not universal speedups. The extended version has a printed-date versus arXiv-version-date difference, and no later journal-byte equivalence is asserted. DRAFT remains.

Artificial Intelligence Ontology (AIO) Grounding

Explicit AIO Snapshot Assessment: No Match

Rationale: No examined AIO target denotes the bounded stopped shortest-path estimator. Its concentration argument and bidirectional graph traversal do not make it a neural layer, bias concept, clustering task, language model or data preparation identity.

Search Scope: Compared all 442 pinned AIO and 693 preceding native identities with ignored- and hidden-inclusive searches of three checkouts. Semantic assessment covers155 AIO and538 native definitions: prior154/536 rows verified unchanged, one new AIO and two new native definitions read. Eleven complete AIO contexts and seven full native neighbors assessed.

Examined AIO Candidate	Rejection Reason
`AIO:Clustering`	A centrality vector assigns scores without grouping vertices into clusters.
`AIO:UnsupervisedClustering`	Absence of labels does not turn structural score computation into clustering.
`AIO:MathematicalFunction`	The identity includes a specific random sampling and bounded stopping procedure, not only an input-output function.
`AIO:DataPreparation`	Computing network prominence is the defined result; incidental downstream feature use does not establish a preprocessing identity.
`AIO:GraphLanguageModel`	The static graph sampling and concentration method has no language-model objective or training mechanism.
`AIO:RankingBias`	A structural graph score is not the belief that high-ranked information is necessarily relevant.
`AIO:SelectionAndSamplingBias`	Uniform pair sampling and its confidence bound define an algorithm, not selection or sampling bias.
`AIO:RepresentationBias`	A graph centrality computation is not subgroup representation bias.
`AIO:DeepActiveLearning`	Neither labels nor a deep neural network are acquired or fitted.
`AIO:DataDredgingBias`	A bounded stopping-time confidence construction is not itself a data-dredging bias concept.
`AIO:BidirectionalLayer`	This AIO class wraps recurrent neural networks; forward and reverse graph searches do not instantiate that layer.

Evidence Sources & Primary Literature

2 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`borassinatal2016esa`	KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation Michele Borassi, Emanuele Natale	primary paper full_text	ID: doi:10.4230/LIPIcs.ESA.2016.20 sha256:c73bb488b2ad…
`borassinatal2016v4`	KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation Michele Borassi, Emanuele Natale	primary paper full_text	sha256:6e42bfafd925…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-14T06:40:41Z

Updated: 2026-10-14T07:01:29Z

Source File: data/curated/KADABRAAdaptiveBetweenness.yaml