complete graphs

Assume we have a directed weighted network on $n$ nodes that is complete including self-loops; that is, every edge has strictly positive weight. This means that the trust matrix $𝑻$ has strictly positive entries.

definition

Denote the minimum entry of $𝑻$

$$m ≔ \min_{i,j∈\{1,…,n\}} tᵢⱼ.$$

Note that row-stochasticity of $𝑻$ implies $m≤1/n$.

definition

For each time $t$, define the maximum and minimum opinion values $U⁽ᵗ⁾=\max_{i∈\{1,…,n\}}xᵢ⁽ᵗ⁾$ and $L⁽ᵗ⁾=\min_{i∈\{1,…,n\}}xᵢ⁽ᵗ⁾$.

claimconvergence distance bound for complete graphs

Under these conditions, total convergence distance is bounded by

$$D ≤ \frac {1-m} {nm} (U⁽⁰⁾-L⁽⁰⁾).$$

Furthermore, this bound is tight—meaning, for each $n∈ℕ$ and $m∈(0,1/n]$ there exists a network and initial state resulting in $D=(1-m)/(nm)$.

For the next two lemmas, to ease readability we omit $^{(t)}$ denoting values at time $t$, and use primes $'$ instead of $^{(t+1)}$ to denote values at time $t+1$.

lemmaupper-lower

$$U'-L'≤(1-nm)(U-L).$$

proof

Let $u,l∈\{1,…,n\}$ be the indices of the nodes that respectively attain the maximum/minimum values at time $t+1$; that is, $U'=xᵤ'=∑ⱼ₌₁ⁿ tᵤⱼ xⱼ$ and $L'=xₗ'=∑ⱼ₌₁ⁿ tₗⱼ xⱼ$. Then observe by row-stochasticity that

$$\begin{aligned} U' &= U + ∑ⱼ₌₁ⁿ \underbrace{tᵤⱼ}_{≥m} \underbrace{(xⱼ-U)}_{≤0} &&≤ U + m ∑ⱼ₌₁ⁿ (xⱼ-U), \\ L' &= L + ∑ⱼ₌₁ⁿ \underbrace{tₗⱼ}_{≥m} \underbrace{(xⱼ-L)}_{≥0} &&≥ L + m ∑ⱼ₌₁ⁿ (xⱼ-L), \end{aligned}$$

from which it follows that $U'-L'≤(1-nm) (U-L)$.

lemmahalf-step

$$\max\{U'-L,U-L'\}≤(1-m)(U-L).$$

proof

Same as before, start by observing that

$$\begin{aligned} U' &≤ U + m ∑ⱼ₌₁ⁿ (xⱼ-U), \\ L' &≥ L + m ∑ⱼ₌₁ⁿ (xⱼ-L). \end{aligned}$$

• In the expression for $U'$, note that at least one term in the sum attains the minimum value $xⱼ=L$, so discarding/ignoring all other terms (all of which are non-positive) we have $U'≤U+m(L-U)$. Then $U'-L'≤(1-m)(U-L)$.

• Likewise, in the expression for $L'$ at least one term in the sum attains $xⱼ=U$; discard other terms (all of which are non-negative) to obtain $L'≥L+m(U-L)$ and so $U-L'≤(1-m)(U-L)$ as well.

---

Now we prove the actual bound. Fix any node $i$. Observe that on each step

$$L'-U ≤ dᵢ = xᵢ'-xᵢ ≤ U'-L$$

and so

$$\lvert dᵢ\rvert≤\max\{U'-L,U-L'\}≤(1-m)(U-L)$$

by the half-step lemma.

Meanwhile, the upper-lower lemma implies that $U⁽ᵗ⁾-L⁽ᵗ⁾≤(1-nm)ᵗ(U⁽⁰⁾-L⁽⁰⁾)$, so we have

$$\begin{aligned} Dᵢ &= ∑ₜ₌₀^∞ \lvert dᵢ⁽ᵗ⁾ \rvert \\ &≤ (1-m) ∑ₜ₌₀^∞ (U⁽ᵗ⁾-L⁽ᵗ⁾) \\ &≤ (1-m) \left(∑ₜ₌₀^∞ (1-nm)ᵗ\right) (U⁽⁰⁾-L⁽⁰⁾) \\ &≤ \frac {1-m} {nm} (U⁽⁰⁾-L⁽⁰⁾) \end{aligned}$$

by the geometric series formula.

---

Next, we construct an example to show that this bound is tight. Fix $n∈ℕ$ and $m∈(0,1/n]$, and consider

$$𝑻 = \begin{bmatrix} m & 1-(n-1) m & m & … & m \\ 1-(n-1) m & m & m & … & m \\ 1-(n-1) m & m & m & … & m \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1-(n-1) m & m & m & … & m \end{bmatrix}$$

with initial condition

$$𝒙(0) = \begin{bmatrix} 1 \\ 0 \\ ⋮ \\ 0 \end{bmatrix}.$$

Note then that at each time-step $x₂=⋯=xₙ$, so to simplify calculations let $A=x₁$ and $B=x₂=⋯=xₙ$. Then $A,B$ evolve as follows:

$$\begin{aligned} A' &= m A + (1-m) B, \\ B' &= [1-(n-1)m] A + (n-1)m B. \end{aligned}$$

Observe that

$$\begin{aligned} A'-B' &= -(1-nm) (A-B), \\ A'-A &= -(1-m) (A-B), \end{aligned}$$

so in particular

$$\begin{aligned} A⁽ᵗ⁾-B⁽ᵗ⁾ &= [-(1-nm)]ᵗ (A⁽⁰⁾-B⁽⁰⁾), \\ d₁⁽ᵗ⁾ = A⁽ᵗ⁺¹⁾-A⁽ᵗ⁾ &= -(1-m) (A⁽ᵗ⁾-B⁽ᵗ⁾) \\ &= -(1-m) [-(1-nm)]ᵗ (A⁽⁰⁾-B⁽⁰⁾). \end{aligned}$$

Then, by the geometric series formula

$$D₁ = ∑ₜ₌₀^∞ \lvert d₁⁽ᵗ⁾\rvert = \frac {1-m} {nm} (A⁽⁰⁾-B⁽⁰⁾).$$

---

If we take the network defined above and discard all edges of weight $m$, we’re left with a star graph, with node $1$ in the center and all other agents on the spokes. So we could generalize this a little—a star graph is a special instance of bipartite graphs (also, core-periphery? hub-and-spoke?).

• What about generalizations of this shape of graph?