Home / Curated / Algorithms / Brandes betweenness centrality computation

Brandes betweenness centrality computation

Algorithms AIMech:BrandesBetweennessCentrality DRAFT

Aliases: Brandes algorithm

An exact graph algorithm for computing shortest-path vertex betweenness that combines single-source shortest-path counting with reverse-distance accumulation of dependencies, avoiding explicit summation of every source-target-vertex contribution.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 684 native identities; no normalized match. Ignored- and hidden-inclusive searches of three checkouts returned 56,0,0 lines; all 13 unique payloads were read and were prior citation/query/pending-lead context. The semantic search selected 128 AIO and 470 native definitions; all 128 AIO and 469 previous native rows were verified unchanged and the new PageRank definition read. Nine complete AIO node/edge/generated-record contexts and full GN, definition-filtered GN, PageRank and HITS records were assessed. This identity is the algorithm for computing vertex shortest-path betweenness by per-source dependency accumulation. It is not the older betweenness measure itself, stress centrality, PageRank, HITS or an iterative edge-removal community detector. Its role here is a reusable network-analysis primitive relevant to structural graph features and the inspected web/text-network applications; this does not assert that every graph algorithm is a learned AI model.

Claims & Grounded Evidence

7 Claims

Scope #scoped-path-domain

The explicit formulation here uses a finite connected simple undirected graph with positive edge lengths, or unit lengths for an unweighted graph. A vertex receives the fraction of each pair’s shortest paths on which it is an internal vertex; endpoints do not contribute. The scores stated here use unordered vertex pairs without size normalization. The paper also discusses directed and more general graph inputs; their implementation conventions are not silently added to this scoped formulation.

supports Source: A Faster Algorithm for Betweenness Centrality · Locator: Section 2, PDF/printed pp. 3–4; undirected halving on p. 9; Algorithm 1, p. 10

Mechanism #shortest-path-counts

For each source s, compute distances, shortest-path counts sigma_s(v) and predecessor lists. Initialize sigma_s(s)=1 and add counts from every shortest-path predecessor, including ties. Breadth-first traversal applies to unit lengths; Dijkstra traversal applies to positive lengths. Strictly positive lengths place predecessors at smaller distances and make the predecessor structure acyclic.

supports Source: A Faster Algorithm for Betweenness Centrality · Locator: Section 3, PDF/printed pp. 5–6, predecessor definition and Lemma 3; Algorithm 1, p. 10

Mechanism #dependency-accumulation

Process vertices in non-increasing distance from s. For each successor w for which v is a shortest-path predecessor, add [sigma_s(v)/sigma_s(w)] times [1+delta_s(w)] to delta_s(v). Add each non-source vertex’s dependency to its total across sources. Divide the resulting totals by two for the selected undirected convention, because both orientations of each pair were visited. This division is distinct from any optional normalization for network size.

supports Source: A Faster Algorithm for Betweenness Centrality · Locator: Section 4, PDF/printed pp. 6–10; Theorem 6, proof, Corollary 7 and Algorithm 1

Limitation #fractional-and-weighted-boundaries

Fractions of shortest paths are not raw counts of paths and do not count every walk. In a constructed four-cycle, each vertex has unordered betweenness 1/2 but stress count 1. In a triangle with edge lengths 0–1=1, 1–2=1 and 0–2=2, vertex 1 has betweenness 1/2 because direct and two-edge routes tie. Raising the last length to 3 gives that vertex score 1; treating all three edges as unit length gives 0. Thus interpreting a strength or similarity weight as a path length requires an explicit modeling choice.

supports Source: A Faster Algorithm for Betweenness Centrality · Locator: Sections 2–3, PDF/printed pp. 3–6; exact curator examples in research/discovery/brandes-betweenness-boundaries.py

Scope #complexity-scope

The paper gives O(n+m) storage, O(nm) time for unweighted graphs and O(nm+n-squared log n) time for positive-weight graphs. These are the stated arithmetic-operation bounds under its connected-graph assumptions, with a Fibonacci-heap shortest-path bound for the weighted case. They do not establish arbitrary-precision bit complexity, a universal wall-clock speedup or the same bound for every priority-queue implementation.

supports Source: A Faster Algorithm for Betweenness Centrality · Locator: Section 3, PDF/printed p. 6, Fibonacci-heap qualification; Section 4, p. 9, Corollary 7 and Theorem 8

Scope #method-and-application-boundary

The contribution accelerates computation of an existing shortest-path centrality measure. It produces structural vertex scores without fitting a predictive model, assigning community labels or defining a causal influence measure. The primary text discusses social, web and word-network analysis. PageRank and HITS use different link-propagation objectives; repeatedly deleting high-betweenness edges to form communities is a surrounding procedure, not this vertex-score computation.

supports Source: A Faster Algorithm for Betweenness Centrality · Locator: Introduction, PDF/printed pp. 1–2; Sections 2 and 4, pp. 3–4,9–10; applications pp. 12–13

Limitation #evaluation-limits

The empirical evidence concerns historical LEDA implementations, specified hardware, random graphs and particular network-analysis examples. The random-graph experiments vary density or fix average degree; reported application speed comparisons include different machines and software contexts. These observations do not establish held-out prediction accuracy, modern hardware performance, calibrated social importance or correctness of an unseen implementation.

supports Source: A Faster Algorithm for Betweenness Centrality · Locator: Section 5, PDF/printed pp. 9,11–13; Figures 3–4 and footnotes 3–4

⚠️ Curated Limitations & Negative Results

The maintained mechanism is scoped to connected simple undirected positive-length graphs. The paper mentions directed graphs, loops and multiple edges, but this record does not infer every convention needed for those cases, disconnected inputs or endpoint-inclusive variants.
Positive lengths and exact shortest-path comparisons are material assumptions. Zero or negative lengths and numerical tie handling need separate analysis; the stated DAG argument must not be extended to them automatically.
The existing betweenness measure, sampled approximations, variants and community-detection pipelines remain distinct identities or source leads. No model-training behavior or AIO acceptance is implied.
The rendered proof prose on PDF page 8 uses sigma(s,v)/sigma(s,w), consistently with Theorem 6 and Algorithm 1. An earlier preliminary discovery note had misread that fraction; issue #340 corrects the note rather than attributing an error to the paper.
The curator calculator uses independent path enumeration on five small constructed graphs. It does not reproduce author code, original datasets, historical runtimes or general asymptotic proofs.
All primary text, references, mathematical displays and figures were inspected. No author software, separate journal-layout copy, training, paid service or data upload was used. This record remains DRAFT after author self-review.

Artificial Intelligence Ontology (AIO) Grounding

Explicit AIO Snapshot Assessment: No Match

Rationale: No inspected AIO target adequately denotes this centrality-computation algorithm. A downstream clustering or feature-engineering use does not make the algorithm identical to those tasks, and a mathematical expression for its output does not identify its computational procedure.

Search Scope: Compared all 442 pinned AIO and 684 preceding native identities and searched three checkouts including ignored and hidden files. The semantic search selected 128 AIO and 470 native definitions; prior selected rows were verified unchanged and the new PageRank definition read. Nine complete AIO node/edge/generated-record contexts and four full native neighboring records were assessed.

Examined AIO Candidate	Rejection Reason
`AIO:Clustering`	Vertex centrality scores do not group objects into clusters.
`AIO:UnsupervisedClustering`	No unlabeled-object grouping or cluster assignment is defined by this computation.
`AIO:HierarchicalClustering`	The algorithm does not construct a cluster hierarchy; a downstream divisive community procedure is distinct.
`AIO:MathematicalFunction`	The betweenness index is mathematically a function, but this record denotes a particular traversal and accumulation algorithm for computing it. The generic function class does not identify that computational method.
`AIO:DataPreparation`	The specified output is a network centrality statistic, not a procedure defined to clean or organize machine-learning data. Possible use as a feature is insufficient for this mapping.
`AIO:GraphLanguageModel`	Graph traversal and path counting do not define a language model.
`AIO:RankingBias`	The algorithm computes a structural statistic rather than a belief that a top-ranked result is most relevant.
`AIO:DimensionalityReduction`	The method is not a learned embedding or an algorithm intended to preserve high-dimensional data geometry.
`AIO:PrincipalComponentAnalysis`	Shortest-path dependency accumulation does not compute centered covariance principal components.

Evidence Sources & Primary Literature

1 Source

Source ID	Publication / Document	Type / Access	Reference & Checksum
`brandes2001`	A Faster Algorithm for Betweenness Centrality Ulrik Brandes	primary paper full_text	ID: doi:10.1080/0022250X.2001.9990249 sha256:a4af39425ef8…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-14T03:53:06Z

Updated: 2026-10-14T03:53:06Z

Source File: data/curated/BrandesBetweennessCentrality.yaml