Documentation

Averaging.OpportunisticModel

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⁽⁰⁾ = σ.

def Averaging.Opportunistic.signVec {V : Type u_1} (σ : V → ℤˣ) :
V → ℝ

The real vector x⁽⁰⁾ ∈ {-1, 1}ⁿ of the initial signs σ.

Equations
Instances For
    noncomputable def Averaging.Opportunistic.edgeAvg {V : Type u_1} [DecidableEq V] (G : SimpleGraph V) (x : V → ℝ) (d : G.Dart) :
    V → ℝ

    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
      noncomputable def Averaging.Opportunistic.avgRun {V : Type u_1} [DecidableEq V] (G : SimpleGraph V) (x : V → ℝ) (l : List G.Dart) :
      V → ℝ

      The state x⁽ᵗ⁾ = W_t ⋯ W_1 x⁽⁰⁾ after the rounds l, the first round first.

      Equations
      Instances For
        noncomputable def Averaging.Opportunistic.oppStep {V : Type u_1} [DecidableEq V] (G : SimpleGraph V) (σ : V → ℤˣ) (s : V → Option ℝ) (d : G.Dart) :
        V → Option ℝ

        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
          noncomputable def Averaging.Opportunistic.oppRun {V : Type u_1} [DecidableEq V] (G : SimpleGraph V) (σ : V → ℤˣ) (l : List G.Dart) :
          V → Option ℝ

          The opportunistic protocol after the rounds l, starting with no node activated.

          Equations
          Instances For
            theorem Averaging.Opportunistic.oppStep_isSome {V : Type u_1} [DecidableEq V] (G : SimpleGraph V) (σ : V → ℤˣ) (s : V → Option ℝ) (d : G.Dart) (v : V) :
            (oppStep G σ s d v).isSome = true ↔ (v = d.toProd.1 ∨ v = d.toProd.2) ∨ (s v).isSome = true
            theorem Averaging.Opportunistic.foldl_oppStep_isSome {V : Type u_1} [DecidableEq V] (G : SimpleGraph V) (σ : V → ℤˣ) (l : List G.Dart) (s : V → Option ℝ) (v : V) :
            (List.foldl (oppStep G σ) s l v).isSome = true ↔ (s v).isSome = true ∨ ∃ d ∈ l, v = d.toProd.1 ∨ v = d.toProd.2
            theorem Averaging.Opportunistic.foldl_oppStep_getD {V : Type u_1} [DecidableEq V] (G : SimpleGraph V) (σ : V → ℤˣ) (l : List G.Dart) (s : V → Option ℝ) (x : V → ℝ) (h : ∀ (w : V), (s w).getD (signVec σ w) = x w) (v : V) :
            (List.foldl (oppStep G σ) s l v).getD (signVec σ v) = List.foldl (edgeAvg G) x l v
            theorem Averaging.Opportunistic.sum_edgeAvg {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (x : V → ℝ) (d : G.Dart) :
            ∑ v : V, edgeAvg G x d v = ∑ v : V, x v

            One round preserves the sum of the values.

            theorem Averaging.Opportunistic.oppRun_isSome_iff {V : Type u_1} [DecidableEq V] (G : SimpleGraph V) (σ : V → ℤˣ) (l : List G.Dart) (v : V) :
            (oppRun G σ l v).isSome = true ↔ ∃ d ∈ l, v = d.toProd.1 ∨ v = d.toProd.2

            A node holds a value exactly when it has been an endpoint of an active edge.

            theorem Averaging.Opportunistic.oppRun_getD {V : Type u_1} [DecidableEq V] (G : SimpleGraph V) (σ : V → ℤˣ) (l : List G.Dart) (v : V) :
            (oppRun G σ l v).getD (signVec σ v) = avgRun G (signVec σ) l v

            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.

            theorem Averaging.Opportunistic.sum_avgRun {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (x : V → ℝ) (l : List G.Dart) :
            ∑ v : V, avgRun G x l v = ∑ v : V, x v

            Every round preserves the sum of the values (𝟙ᵀ W_t = 𝟙ᵀ).