Averaging whenever you meet: the opportunistic protocol #
Becchetti, Clementi, Manurangsi, Natale, Pasquale, Raghavendra, Trevisan, Average whenever you
meet: opportunistic protocols for community detection, ESA 2018, arXiv:1703.05045 (numbering of
arXiv v3). In every round one edge of a finite graph is activated, chosen uniformly and
independently at random. A node activated for the first time draws a uniform value ±1, and the
two endpoints of the active edge replace their values by their average (Algorithm 1,
Averaging(δ) with δ = 1/2).
A uniformly random edge is drawn as a uniformly random dart (oriented edge): every edge carries
exactly two darts (the core's Dynamics.avg_edgeRound_edge). The rounds are i.i.d. uniform
darts, so expectations over T rounds are Dynamics.expList G.Dart T. As in the paper
(principle of deferred decisions, Section 3), the first-activation coins are drawn in advance as
a uniform vector σ : V → ℤˣ, independent of the edges; oppRun_getD shows that the protocol
then runs the averaging process avgRun started at x⁽⁰⁾ = σ.
The real vector x⁽⁰⁾ ∈ {-1, 1}ⁿ of the initial signs σ.
Equations
- Averaging.Opportunistic.signVec σ v = ↑↑(σ v)
Instances For
One round of Averaging(1/2) (Algorithm 1) on the active edge {d.fst, d.snd}: both
endpoints take the average of their two values; the other values are unchanged.
Equations
Instances For
The state x⁽ᵗ⁾ = W_t ⋯ W_1 x⁽⁰⁾ after the rounds l, the first round first.
Equations
Instances For
One round of the opportunistic protocol. A node holds none until its first activation; an
endpoint that still holds none uses its coin σ, then both endpoints average.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The opportunistic protocol after the rounds l, starting with no node activated.
Equations
- Averaging.Opportunistic.oppRun G σ l = List.foldl (Averaging.Opportunistic.oppStep G σ) (fun (x : V) => none) l
Instances For
One round preserves the sum of the values.
Deferred decisions (Section 3): the opportunistic protocol runs the averaging process from the
initial vector x⁽⁰⁾ = σ, a node not activated yet holding its future coin σ v.
Every round preserves the sum of the values (𝟙ᵀ W_t = 𝟙ᵀ).