Home / Curated / Algorithms / KADABRA balanced bidirectional shortest-path sampling

KADABRA balanced bidirectional shortest-path sampling

Algorithms AIMech:KADABRABalancedBidirectionalPathSampling DRAFT

Aliases: KADABRA balanced bidirectional BFS sampler, KADABRA shortest-path sampler

A shortest-path sampling algorithm that expands complete breadth-first-search frontiers from opposite endpoints according to frontier edge volume, then samples a connecting edge and its two path segments with shortest-path-count weights to obtain a uniform shortest path.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 694 native identities; no collision among the proposed record name or aliases. The broad KADABRA identity term matches the enclosing estimator and is explicitly resolved as a subroutine-versus-estimator distinction. Ignored- and hidden-inclusive searches of three full checkouts returned 183,0,0 lines, assessed as the preceding KADABRA record/report, source-reading notes, leads or query strings. Semantic assessment covered 155 AIO and 539 native definitions: all155 AIO and538 prior native rows verified unchanged and the new KADABRA estimator row and full record read. Eleven complete AIO contexts and five full native neighbors assessed. The identity is a conditional uniform shortest-path sampler using full-layer edge-volume balancing and count-weighted connecting edges. It is distinct from the enclosing KADABRA estimator, ABRA pair fractions, exact Brandes dependency accumulation, generic first-meeting bidirectional search and later vertex-wise balancing variants.

Claims & Grounded Evidence

6 Claims

Scope #conditional-path-domain

For a finite simple unweighted directed or undirected graph and distinct specified endpoints s and t, the output is a uniformly sampled shortest s-to-t path when one exists, and an empty result otherwise. This conditional sampler does not itself select the endpoint distribution or estimate centrality. KADABRA’s enclosing estimator uses independent uniform ordered distinct-node pairs, which is an additional sampling layer.

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

Mechanism #balanced-frontier-expansion

Maintain source and target BFS layers, distances and exact shortest-path counts. At each step expand the entire current frontier with smaller incident-edge volume, breaking equal-volume ties by a fixed convention. In directed graphs the source search uses outgoing arcs and the target search uses incoming arcs. Collect all connecting edges encountered in the selected frontier before choosing a path. The balance criterion is edge volume, not merely the number of frontier vertices or the total sizes of the two search trees.

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

Mechanism #count-weighted-cut-and-backtracking

For a source-side meeting edge (v,w), assign weight sigma_sv times sigma_wt. Sample one meeting edge in proportion to this weight, then sample a shortest prefix from s to v and shortest suffix from w to t using path-count-proportional predecessor or successor choices. Their concatenation with the edge is a shortest s-to-t path. The product of cut-edge probability and prefix/suffix probabilities gives each complete shortest path probability 1/sigma_st. Reaching a vertex a second time at the same BFS distance must still contribute to its path count.

supports Source: KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation · Locator: Section 4, PDF p. 7; path-count factorization checked in research/discovery/kadabra-path-boundaries.py. The probability product and equal-distance accumulation are explicit curator interpretation of the source’s counting requirement.

Limitation #finite-uniformity-boundaries

Exact curator enumeration checks every ordered distinct-endpoint pair in all 64 undirected and 4096 directed simple four-node graphs, including disconnected cases. A separate directed branching example has meeting-edge weights 2 and 1, giving three complete paths probability 1/3 each; uniform meeting-edge selection would instead give probabilities 1/4, 1/4 and 1/2. These finite cases illustrate why full-frontier processing and exact counts matter; they do not certify author software or all possible graph implementations.

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

Limitation #complexity-and-model-scope

The sampler retains linear worst-case graph-traversal work; a selected 129-node path requires scanning 254 incident edges in the curator calculation. The source’s sublinear analyses concern specified configuration and rank-one inhomogeneous random-graph models with additional degree-distribution and supercriticality assumptions, not every graph or endpoint pair under every model. Its unit-cost arithmetic assumption also hides the bit cost of potentially exponential shortest-path counts. Weighted edges, approximate counts and a universal square-root runtime are outside this maintained scope.

supports Source: KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation · Locator: Section 4 and Theorem 4, PDF pp. 7–8; Appendix E, pp. 20–24; long-path calculation in research/discovery/kadabra-path-boundaries.py

Limitation #separation-from-centrality-and-later-variants

The sampler is a subroutine distinct from KADABRA’s confidence budgets, bounded adaptive stopping and top-k output. Replacing an exact pair contribution by one sampled path indicator changes the estimator variance even when the mean target is unchanged. The 2016 historical experiments describe the sampler within a particular implementation and graph collection; they are not a general performance guarantee. Other balancing or parallelization variants are outside this record’s scope.

supports Source: KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation · Locator: Abstract and Sections 2, 4 and 6, PDF pp. 1, 4–8 and 9–12; finite indicator-versus-fraction comparison in research/discovery/kadabra-path-boundaries.py. Other algorithms are not included in this maintained identity.

⚠️ Curated Limitations & Negative Results

Exact simple unweighted graph paths and exact counts are assumed. Weighted shortest paths, multiedge conventions, finite-precision sampling and approximate count correction require separate analysis.
The conditional endpoint sampler does not by itself define a centrality estimator or its accuracy, confidence, stopping rule or endpoint population.
Uniformity requires processing the full chosen frontier and count-weighted meeting-edge and segment choices. A generic bidirectional search that returns its first meeting path is not equivalent.
Finite exact calculations and source interpretation are curator checks, not execution or verification of the authors’ implementation. Some random-graph proof displays were read only as extracted text.
No universal runtime improvement, current-software comparison or proof of every reported random-graph bound is asserted. DRAFT remains after author self-review.

Artificial Intelligence Ontology (AIO) Grounding

Explicit AIO Snapshot Assessment: No Match

Rationale: No examined AIO target denotes the conditional uniform shortest-path sampler. In particular, BidirectionalLayer is an RNN wrapper, not a bidirectional graph search.

Search Scope: Compared all 442 pinned AIO and 694 preceding native identities with ignored- and hidden-inclusive searches of three checkouts. A broad KADABRA search term also matches the enclosing estimator, whose complete definition and scope were read to distinguish the subroutine. Semantic assessment covers155 AIO and539 native definitions; eleven complete AIO contexts and five full native neighbors assessed.

Examined AIO Candidate	Rejection Reason
`AIO:Clustering`	Sampling a path does not group vertices into clusters.
`AIO:UnsupervisedClustering`	Uniformly sampling a conditional shortest path does not group vertices into clusters, whether or not labels are available.
`AIO:MathematicalFunction`	The identity is a randomized graph-search and path-sampling procedure, not merely an input-output function.
`AIO:DataPreparation`	The defined output is a sampled shortest path; incidental downstream feature use does not establish a data-preparation identity.
`AIO:GraphLanguageModel`	The conditional graph-path sampler has no language-model objective, training mechanism or learned representation.
`AIO:RankingBias`	A sampled graph path is not a belief about the relevance of highly ranked information.
`AIO:SelectionAndSamplingBias`	A specified uniform conditional path law is an algorithm, not a selection-bias concept.
`AIO:RepresentationBias`	A graph-path sampling procedure is not subgroup representation bias.
`AIO:DeepActiveLearning`	Neither labels nor a deep neural network are acquired or fitted.
`AIO:DataDredgingBias`	Conditional shortest-path sampling does not itself define a data-dredging bias.
`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:43:39Z

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

Source File: data/curated/KADABRABalancedBidirectionalPathSampling.yaml