Eq. (16) — δ̃_{s,t}((s_1,…,s_k)) = δ_{s,t}(s_1)·δ_{s_1,t}(s_2)⋯δ_{s_{k−1},t}(s_k)
ProvedRoutingBC.Chaining.sequence_dependency_productbetweenness-centralityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrouting
Under the hypotheses of Lemma 1 (a loop-free, source-oblivious routing scheme on a finite node set, total forwarding probability one at every non-target node, a silent target), let and let with . Then the sequence dependency is a product of pairwise dependencies on single nodes:
This is what lets the RBC of a sequence be evaluated from precomputed pairwise dependencies of single nodes.
Formalization Note. The page prints the second factor as ; the intended factor is , as the Figure 4 caption () and Lemma 1 confirm, and the corrected product is stated. The product runs over the consecutive pairs of (empty for ). No distinctness of the is assumed.
Preamble
import Mathlib import Definitions.Def_RoutingBC_Chaining_Routing
Formal statement
namespace RoutingBC.Chaining
theorem sequence_dependency_product {V : Type*} [Fintype V] [DecidableEq V]
(R : V → V → V → V → ℝ) (hR : IsRoutingScheme R) (hobl : IsSourceOblivious R)
(s t : V) (hst : s ≠ t) (s₁ : V) (rest : List V) :
seqDelta R s t (s₁ :: rest) =
delta R s t s₁ * (((s₁ :: rest).zip rest).map (fun ab => delta R ab.1 t ab.2)).prod := by sorry
end RoutingBC.Chaining
Source
Dolev, Elovici, Puzis, Routing Betweenness Centrality, BGU CS Tech. Rep. #2009-09 (Aug. 2009), Section 5.2, Eq. (16), p. 15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.