Brandes–Fleischer grounded current-flow closeness computation
Algorithms AIMech:BrandesFleischerGroundedCurrentFlowCloseness DRAFT
Aliases: Brandes-Fleischer grounded resistance-sum closeness algorithm
An exact network-analysis algorithm that accumulates effective-resistance sums from successive columns of an embedded grounded-Laplacian inverse and returns their reciprocals; the inspected Algorithm 2 omits the n-1 normalization used in the same chapter’s closeness definition.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 690 native identities; no normalized match. Ignored- and hidden-inclusive searches of three full checkouts returned 203,0,0 lines, read as the Newman and current-flow records/reports and prior chapter leads or query strings. Semantic assessment covered 147 AIO and 524 native definitions: all 147 AIO and 523 prior native rows verified unchanged and one newly selected native row read. Nine complete AIO contexts and five full native neighbors were assessed. Algorithm2 accumulates columns of a grounded inverse and reciprocates effective-resistance sums. It is distinct from the current-flow score alone, exact or sampled betweenness, shortest-path closeness sampling and the chapter’s separate L-plus-J information-centrality construction. The explicit output follows the algorithm’s inverse-sum convention, with Definition3’s n-1 multiplier separately identified.
Claims & Grounded Evidence
6 Claims
Scope
#domain-and-resistance
The maintained domain is a connected simple undirected graph with n>=3 and positive edge conductances. Ground one vertex and embed the inverse of the reduced weighted Laplacian in C with a zero ground row and column. Effective resistance between v and w is R_vw=C_vv+C_ww-2C_vw, the potential drop for unit current from v to w. It is positive for distinct vertices and independent of the chosen ground.
Mechanism
#column-accumulation
Initialize q(v)=0. For each inverse column indexed by v and every vertex w, add C_vv-2C_wv to q(v) and C_vv to q(w), including w=v. After all columns, q(v)=n C_vv-2 sum_w C_wv+trace(C)=sum_w R_vw. Algorithm 2 returns 1/q(v). Including the diagonal terms in both updates cancels them; the ground column is zero. Column order does not change the exact final sum.
Limitation
#normalization-discrepancy
The source defines n_C=n-1 and uses n_C divided by the resistance sum in Definition 3, but its proof and Algorithm 2 omit that factor. This record preserves the explicit Algorithm 2 output 1/sum_w R_vw; multiplying it by n-1 yields the stated normalized definition. On the unit triangle, these values are 3/4 and 3/2 respectively. No unqualified numerical identity with every convention called information centrality is asserted.
Scope
#computation-and-numerics
With a dense reduced inverse, forming and accumulating all n columns costs O(n^2) beyond inversion and uses O(n^2+m) storage. The source also describes obtaining columns as needed from reduced linear solves, allowing the column accumulator to avoid storing the whole inverse. Numerical solve time, accuracy and preconditioner storage require implementation-specific assumptions; the chapter’s rough conjugate-gradient and condition-number discussion is not an unconditional exact floating-point guarantee.
Limitation
#distance-and-weight-boundaries
This uses effective resistance rather than shortest-path length in general. On a tree, effective resistance equals the unique-path sum of reciprocal conductances, so matched-normalization closeness values agree. On a unit triangle, inverse resistance-sum closeness is 3/4 but inverse shortest-path-sum closeness is 1/2. Multiplying all conductances by a positive factor multiplies this closeness by the same factor. These finite graph examples and scaling consequences do not make the score dimensionless or bounded by one.
Limitation
#method-and-evidence-scope
Algorithm 2 computes reciprocal resistance sums; it is distinct from the chapter’s exact and sampled betweenness algorithms and from the earlier information-centrality construction using an inverse of L plus the all-ones matrix. The inspected chapter supplies a mathematical mechanism; its Appendix A experiment concerns betweenness. No empirical closeness speedup, replicated author implementation, causal interpretation or learned predictive performance is asserted.
⚠️ Curated Limitations & Negative Results
- Connected simple undirected positive-conductance graphs with n>=3 only. Disconnected components, singleton cases, signed conductances and directed networks require other definitions.
- Algorithm 2 and Definition 3 differ by n-1 in the inspected source. The maintained output follows the explicit algorithm, and the alternative normalized quantity is labeled separately. Information-centrality naming is not an unqualified normalization identity.
- The chapter’s literal cycle equation for currents is inconsistent with its Ohm law for unequal conductances. The maintained construction uses the explicit weighted Laplacian and potential drops; no corrected source edition is claimed.
- Dense inverses and streaming numerical solves have different storage and precision requirements. Finite rational graphs verify selected equalities and scaling, not general floating-point stability or the performance of historical software.
- All twelve chapter pages and references were read, with method equations and Figure 1 visually inspected. No author code, raw data or closeness benchmark was run. This structural score does not establish causality or trained-model performance. DRAFT remains.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No examined AIO target denotes this reciprocal-resistance-sum column algorithm. Matrix operations, distance-like quantities and possible downstream feature use do not alone identify it with a general function, clustering task or preprocessing method.
Search Scope: Compared all 442 pinned AIO and 690 preceding native identities with ignored- and hidden-inclusive checkout searches. Semantic context covers 147 AIO and 524 native definitions, with prior rows verified unchanged and the new Newman row read. Nine complete AIO contexts and five complete native neighbors were 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 is a particular grounded-inverse column algorithm, not solely a general 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 electrical-network computation has no language-model input/output or training mechanism. |
AIO:RankingBias
|
A structural graph score is not the belief that high-ranked information is necessarily relevant. |
AIO:SelectionAndSamplingBias
|
This exact column-accumulation method is not a sampling-selection 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. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
brandesfleischer2005
|
Ulrik Brandes, Daniel Fleischer
|
primary paper
full_text
|
ID: doi:10.1007/978-3-540-31856-9_44
sha256:92063e95b544…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-14T05:42:14Z
Updated: 2026-10-14T05:42:14Z