bipartite-ish

Consider an “almost-bipartite” graph: take $n$ nodes, partition them into two groups with sizes $k$ and $n-k$ respectively; within each group assign each edge the minimum weight $m$; assign edges between the two groups any remaining weight (so as to satisfy stochasticity). The trust matrix for this network looks like this:

$$T = \begin{bmatrix} [m]_{k×k} & ⋆ \\ ⋆ & [m]_{(n-k)×(n-k)} \end{bmatrix}.$$

In other words,

$$xᵢ' = \begin{cases} m ∑ⱼ₌₁ᵏ xⱼ + ∑ⱼ₌ₖ₊₁ⁿ tᵢⱼ xⱼ & j∈\{1,…,k\} \\ ∑ⱼ₌₁ᵏ tᵢⱼ xⱼ + m ∑ⱼ₌ₖ₊₁ⁿ xⱼ & j∈\{k+1,…,n\} \end{cases}.$$

Start with everyone in the first group having opinion $1$ and everyone in the second group having opinion $0$. Observe by induction then that at each step each group shares the same opinion, so let $A=x₁=⋯=xₖ$ and $B=xₖ₊₁=⋯=xₙ$, evolving according to

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

Then note that

$$\begin{aligned} A'-B' &= -(1-mn)(A-B), \\ A'-A &= -(1-mk)(A-B), \\ B'-B &= -(1-m(n-k))(A-B), \end{aligned}$$

so then

$$\begin{aligned} A⁽ᵗ⁺¹⁾-A⁽ᵗ⁾ &= -(1-mk)[-(1-mn)]ᵗ(A⁽⁰⁾-B⁽⁰⁾), \\ B⁽ᵗ⁺¹⁾-B⁽ᵗ⁾ &= -(1-m(n-k))[-(1-mn)]ᵗ(A⁽⁰⁾-B⁽⁰⁾), \\ ∴\qquad Dᵢ &= \frac {A⁽⁰⁾-B⁽⁰⁾} {nm} ⋅ \begin{cases} 1-mk & i∈\{1,…,k\} \\ 1-m(n-k) & i∈\{k+1,…,n\} \end{cases}. \end{aligned}$$

If $k∈\{1,n-1\}$ we recover the star graph, resulting in maximum “worst-case” total convergence distance. Conversely worst-case convergence distance is minimized when $k≈n/2$.

It should be noted that in the small $m$ limit, $Dᵢ∼1/(nm)$, which is same as the upper bound. That is, this graph asymptotically attains the upper bound as well.