overview

definitionDeGroot model

Fix a weighted directed network (allowing self-edges) with $n$ nodes; denote by $tᵢⱼ$ the weight on the edge $i→j$ (taking $tᵢⱼ=0$ to mean that there is no edge $i→j$). For each node, we assume that the weights of its outgoing edges are non-negative and sum to $1$.

Define an iterative process ranging over time-steps $t∈\{0,1,2,…\}$. To each node $i∈\{1,…,n\}$ we assign an opinion value $xᵢ⁽ᵗ⁾∈[0,1]$, evolving according to the rule

$$xᵢ⁽ᵗ⁺¹⁾ = ∑ⱼ₌₁ⁿ tᵢⱼ xⱼ⁽ᵗ⁾.$$

We call $𝒙=(xᵢ)ᵢ₌₁ⁿ$ the (opinion) state vector and the matrix with entries $𝑻=(tᵢⱼ)_{i,j=1}^n$ (a.k.a. the network’s (weighted) adjacency matrix) the trust matrix of the network. The assumption that each node’s outgoing edge weights sum to $1$ is equivalent to the assumption that $𝑻$ is row-stochastic, i.e. that each row of $𝑻$ sums to $1$. In matrix form the iteration rule is just

$$𝒙⁽ᵗ⁺¹⁾ = 𝑻 𝒙⁽ᵗ⁾.$$

Among other things, we’re interested in measuring how quickly opinions converge (assuming they do) under this process. This is a vague task—how do we measure convergence “rate”? There are many reasonable answers to this question. One “obvious” approach is to measure the number of time/iteration-steps for opinions to (approximately) stabilize. We will take a different approach instead, by measuring how much “total distance” each node’s opinion travels back-and-forth before settling on its limit value.

One interesting feature of this measure is its time-independence; that is, this measure of convergence rate doesn’t actually (directly) depend on the number of iteration steps, only the iteration values. (Does this mean that this measure is somehow a better measure of inherent/underlying structure? I don’t know, maybe.)

(This notion of convergence is an attempt to generalize the notion of consensus time for voter models; see Redner, page 276.)

definitionconvergence distance

For each time $t$, define the (opinion state) displacement $𝒅⁽ᵗ⁾≔𝒅⁽ᵗ⁺¹⁾-𝒅⁽ᵗ⁾$ and the distance as the (entry-wise) absolute value, denoted $\lvert 𝒅⁽ᵗ⁾\rvert$.

We are ultimately interested in the total convergence distance

$$\begin{aligned} D &≔ ∑ₜ₌₀^∞ \left\lvert 𝒅⁽ᵗ⁾ \right\rvert \\ &= ∑ₜ₌₀^∞ \left\lvert 𝒙⁽ᵗ⁺¹⁾-𝒙⁽ᵗ⁾ \right\rvert \\ &= ∑ₜ₌₀^∞ \left\lvert 𝑻ᵗ⁺¹ 𝒙⁽⁰⁾-𝑻ᵗ 𝒙⁽⁰⁾ \right\rvert \\ &= ∑ₜ₌₀^∞ \left\lvert 𝑻ᵗ(𝑻-𝑰) 𝒙⁽⁰⁾ \right\rvert. \end{aligned}$$

Note that this depends on the initial opinion state $𝒙⁽⁰⁾$. (For example, if the initial state is already full consensus then $D=0$.)

question

• Assuming opinion states converge, does that imply that the total convergence distance must be finite?
• Can we find quantitative bounds on the total convergence distance, depending on network structures/properties?
• How does total convergence distance behave for random networks?