Eq. (1) — δ_{s,t}(s) = 1 and δ_{s,t}(v) = Σ_{u∈Pred_{s,t}(v)} δ_{s,t}(u)·R(s,u,v,t)
ProvedRoutingBC.Chaining.pairwise_dependency_recursionbetweenness-centralityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrouting
Let be a loop-free routing scheme on a finite node set (nonnegative, total forwarding probability one at every non-target node, silent target); the decisions may depend on the source. Fix and let be the set of immediate predecessors of on the way to . Then
This recursion computes all pairwise dependencies of a pair by one pass over a topological order of the routing DAG, which is Algorithm 1 of the paper.
Formalization Note. The page writes the second line of (1) without ""; at the first line applies instead (the right side of the second line is there, by loop-freeness). Both lines are stated without source-obliviousness.
Preamble
import Mathlib import Definitions.Def_RoutingBC_Chaining_Routing
Formal statement
namespace RoutingBC.Chaining
theorem pairwise_dependency_recursion {V : Type*} [Fintype V] [DecidableEq V]
(R : V → V → V → V → ℝ) (hR : IsRoutingScheme R) (s t : V) :
delta R s t s = 1 ∧
∀ v, v ≠ s →
delta R s t v =
∑ u ∈ Finset.univ.filter (fun u => 0 < R s u v t), delta R s t u * R s u v t := by sorry
end RoutingBC.Chaining
Source
Dolev, Elovici, Puzis, Routing Betweenness Centrality, BGU CS Tech. Rep. #2009-09 (Aug. 2009), Section 4.1, Eq. (1), p. 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.