Averaging whenever you meet: clustered regular graphs and the first-moment criteria #
An (n, d, b)-clustered regular graph (Definition 2.2 of arXiv:1703.05045, v3) is d-regular with
two communities Vโ, Vโ of size n/2, every node having exactly b neighbours in the other
community. Then the cut vector ฯ = ๐_{Vโ} - ๐_{Vโ} is an eigenvector of the normalized Laplacian
๐ = L/d with eigenvalue ฮปโ = 2b/d, and of Wฬ = I - ๐/n with eigenvalue 1 - ฮปโ/n
(Section 4.1). The state splits as x = x_โฅ + y + z (equation (7)) along ๐, along ฯ, and
orthogonally to both.
The third eigenvalue ฮปโ of ๐ enters only through the bound zแต๐z โฅ ฮปโ โzโยฒ for z โ ๐, ฯ
(ThirdEigenvalueLB). With these, the first-moment decomposition (Lemma B.1) is exact, the set of
bad nodes of Definition B.1 is empty, and Lemmas B.3 (monotonicity) and B.4 (sign) hold for every
node: this is Theorem 3.1 on clustered regular graphs.
Definition 2.2: G is an (n, d, b)-clustered regular graph with communities Vโ and
Vโ = Vโแถ, where n is the number of nodes: |Vโ| = |Vโ| = n/2, every node has degree d,
every node has exactly b neighbours in the other community, and 0 < b, 2b < d < n.
- regular : G.IsRegularOfDegree d
Instances For
The cut vector ฯ = ๐_{Vโ} - ๐_{Vโ}.
Instances For
x_โฅ = Qโ x, the projection of x on the constant vectors: every entry is the average
ฮฑโ = โจx, ๐โฉ/n of x.
Equations
- Averaging.Opportunistic.projOne x xโ = Dynamics.avg x
Instances For
y = Qโ x, the projection of x on the cut vector: (โจx, ฯโฉ/n) ฯ.
Equations
- Averaging.Opportunistic.projCut Vโ x v = (Dynamics.avg fun (w : V) => Averaging.Opportunistic.cutVec Vโ w * x w) * Averaging.Opportunistic.cutVec Vโ v
Instances For
z = Q_{3โฏn} x = x - x_โฅ - y, the projection of x orthogonally to ๐ and ฯ.
Equations
- Averaging.Opportunistic.projRest Vโ x v = x v - Averaging.Opportunistic.projOne x v - Averaging.Opportunistic.projCut Vโ x v
Instances For
ฮปโ โฅ lam3 for a d-regular graph with cut vector ฯ: the Rayleigh quotient of the
normalized Laplacian ๐ = L/d is at least lam3 on the vectors orthogonal to ๐ and ฯ. For a
clustered regular graph with ฮปโ > 2b/d (so that ฯ spans the second eigenspace), the largest
such lam3 is the third eigenvalue ฮปโ of ๐.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Auxiliary lemmas #
Wฬ maps the orthogonal complement of ๐ and ฯ to itself.
The Rayleigh bounds of Wฬ: at most ฮปฬโ = 1 - ฮปโ/n on the complement of ๐, ฯ, and at
least -ฮปฬโ everywhere.
One step of the contraction of Lemma B.1, by polarization.
The iterated contraction of Lemma B.1.
The cut vector as a vector of units.
Instances For
Main statements #
Section 4.1: on an (n, d, b)-clustered regular graph, Wฬ ฯ = (1 - ฮปโ/n) ฯ with
ฮปโ = 2b/d.
Equation (12) with ฮด = 1/2: the expected component along ฯ decays geometrically,
E[yโฝแตโพ] = (1 - ฮปโ/n)แต yโฝโฐโพ.
Lemma B.1 (main decomposition) on a clustered regular graph:
E[xโฝแตโพ | xโฝโฐโพ = x] = x_โฅ + (1 - ฮปโ/n)แต y + eโฝแตโพ with eโฝแตโพ = Wฬแต z.
The bound of Lemma B.1 on eโฝแตโพ: on the vectors orthogonal to ๐ and ฯ, Wฬแต contracts the
norm by ฮปฬโแต, where ฮปฬโ = 1 - ฮปโ/n is the third eigenvalue of Wฬ.
Lemma B.3 (monotonicity property) on a clustered regular graph, where no node is bad: for an
initial vector x โ {-1, 1}โฟ with ฮฑโ = โจx, ฯโฉ/n โ 0 and every round t with
t โฅ 3 log n / log (ฮปฬโ/ฮปฬโ) (that is, nยณ ฮปฬโแต โค ฮปฬโแต, where ฮปฬโ = 1 - ฮปโ/n and
ฮปฬโ = 1 - ฮปโ/n), the expected value of every node u moves in the direction given by its
community: sgn(E[xโฝแตโปยนโพ_u] - E[xโฝแตโพ_u]) = sgn(ฮฑโ ฯ_u).
Lemma B.4 (sign property) on a clustered regular graph, where no node is bad: for an initial
vector x โ {-1, 1}โฟ with averages ฮฑโ = โจx, ๐โฉ/n and ฮฑโ = โจx, ฯโฉ/n, and every round t in the
window log (n/|ฮฑโ|) / log (1/ฮปฬโ) โค t (that is, n ฮปฬโแต โค |ฮฑโ|) and 2|ฮฑโ| < |ฮฑโ| ฮปฬโแต, the
sign of the expected value of every node u is sgn(ฮฑโ ฯ_u).