Solving Consensus Dynamics in Networks Using Mathematical and Computational Method

A network of agents that can only see their immediate neighbours is asked to agree on a single number. Nobody has a global view, there is no leader, and the only thing each agent can do is move a little towards the people it can hear. Whether that is enough — and how long it takes — turns out not to be a question about the agents at all. It is a question about the shape of the network.

This project works that claim out concretely. Each network is written down as three matrices, the consensus rule is written as one differential equation, and the equation is integrated numerically on graphs ranging from four nodes to a hundred. What emerges is that a single number extracted from the network’s structure — the second-smallest eigenvalue of its Laplacian — predicts both whether agreement happens and how quickly.

§Research question

How do network topology, connection strength and the pattern of information flow determine the speed and stability with which a set of interacting agents reaches consensus?

§Theoretical background

A network of $n$ agents is an undirected, unweighted graph. Its adjacency matrix $A$ records who can hear whom,

$$A_{ij} = \begin{cases} 1 & \text{if } i \text{ and } j \text{ are connected},\\ 0 & \text{otherwise},\end{cases}$$

and the degree matrix $D$ is the diagonal matrix of connection counts, $D_{ii} = \sum_j A_{ij}$. The object that does the real work is their difference, the graph Laplacian

$$L = D - A .$$

Each agent holds a state $x_i(t)$ and repeatedly moves towards its neighbours by the sum of its disagreements with them,

$$\dot{x}_i = \sum_{j \in N(i)} (x_j - x_i),$$

which for the whole system collapses into a single linear equation,

$$\frac{\dd \mathbf{x}}{\dd t} = -L\,\mathbf{x}.$$

Because every row of $L$ sums to zero, the all-ones vector $\mathbf{1}$ is always an eigenvector with eigenvalue $0$: a state in which everyone already agrees never changes. The rest of the spectrum decides what happens on the way there. $L$ is symmetric and positive semidefinite, so its eigenvalues are real and non-negative,

$$0 = \lambda_1 \le \lambda_2 \le \cdots \le \lambda_n ,$$

and the multiplicity of $0$ counts the connected components of the graph. The second-smallest, $\lambda_2$, is Fiedler’s algebraic connectivity. It is strictly positive exactly when the graph is connected, and it sets the slowest rate at which disagreement decays.

§Methodology

Network construction. Networks were written as undirected graphs with each node an agent and each edge a communication link, and were varied systematically from sparse to dense. The worked example is a six-node graph given by the edge list

$$s = [\,1\;1\;2\;2\;3\;2\;4\;4\;5\,], \qquad t = [\,2\;3\;3\;4\;5\;5\;5\;6\;6\,],$$

that is, the nine edges $(1,2), (1,3), (2,3), (2,4), (3,5), (2,5), (4,5), (4,6), (5,6)$.

Matrix formulation. For every structure, $A$, $D$ and $L = D - A$ were constructed explicitly. For the six-node graph above the degree sequence is $(2, 4, 3, 3, 4, 2)$, giving

$$L = \begin{pmatrix} \;\;2 & -1 & -1 & \;\;0 & \;\;0 & \;\;0\\ -1 & \;\;4 & -1 & -1 & -1 & \;\;0\\ -1 & -1 & \;\;3 & \;\;0 & -1 & \;\;0\\ \;\;0 & -1 & \;\;0 & \;\;3 & -1 & -1\\ \;\;0 & -1 & -1 & -1 & \;\;4 & -1\\ \;\;0 & \;\;0 & \;\;0 & -1 & -1 & \;\;2 \end{pmatrix}.$$

The four-node case analysed in detail is the subgraph induced on nodes $1$–$4$, with edges $(1,2), (1,3), (2,3), (2,4)$, degree sequence $(2, 3, 2, 1)$ and

$$L_4 = \begin{pmatrix} \;\;2 & -1 & -1 & \;\;0\\ -1 & \;\;3 & -1 & -1\\ -1 & -1 & \;\;2 & \;\;0\\ \;\;0 & -1 & \;\;0 & \;\;1 \end{pmatrix}.$$

Numerical implementation. The consensus equation was integrated in Python with networkx, numpy and matplotlib, using the explicit Euler method,

$$\mathbf{x}_{k+1} = \mathbf{x}_k - \Delta t\, L\, \mathbf{x}_k ,$$

with $\Delta t = 0.1$ over $50$ steps, from assorted initial states. Graphs were drawn with force-directed layouts; node trajectories were plotted against time; and the Laplacian spectrum was examined with attention to $\lambda_2$.

Cases simulated. A four-node graph; a sparse six-node chain $1$–$2$–$3$–$4$–$5$ with node $6$ attached to nothing; the nine-edge six-node graph above; the complete graph $K_6$; and sparse networks of $30$ and $100$ nodes.

4 nodesSparse, one isolated6 nodes, 9 edgesComplete graph

Graph

Node states, 50 Euler steps at dt = 0.1

Edges

4

λ₂ (connectivity)

1.000

Components

1

Spread after 50 steps

1.0e-2

Replay the integrationThe worked example: nodes 1–4 of the six-node graph, with the edges among them.

§Results and observations

Connected graphs reach agreement; disconnected ones do not. In every connected case the node states converged to a common value. In the sparse case the chain $1$–$2$–$3$–$4$–$5$ converged while node $6$, having no neighbours, stayed at its initial value for all time — its row of $L$ is identically zero, so the dynamics never touch it.

Density accelerates convergence. The complete graph settled fastest and most smoothly; the nine-edge graph next; the chain slowest. Convergence in the moderately connected networks increased with algebraic connectivity, and across every topology tested the manuscript reports convergence speed tracking $\lambda_2$.

Scale slows it down. The $30$- and $100$-node sparse networks still converged, but more slowly and with more variation than the small or dense cases.

The table below gathers the spectra of the graphs whose matrices the manuscript writes out, computed from those matrices:

Graph	Edges	$\lambda_2$	Zero eigenvalues	Behaviour reported
Chain of 5, node 6 isolated	4	0	2	Chain agrees, node 6 never moves
Four-node subgraph	4	1.000	1	Converges
Six nodes, nine edges	9	1.186	1	Converges, faster
Complete graph $K_6$	15	6.000	1	Converges fastest

The disconnected case is the clean one. Its Laplacian has two zero eigenvalues rather than one, so $\lambda_2 = 0$ — and $\lambda_2 = 0$ is precisely the algebraic statement that the graph falls into more than one piece. The isolated node is not a numerical nuisance; it is the spectrum reporting a fact about the topology.

§Challenges and limitations

• The model is the simplest one available: undirected, unweighted, static graphs, with identical agents, no delay, no noise and no external input. Real social and infrastructural networks are directed, weighted and time-varying.
• Convergence rate is governed by $\lambda_2$, but the apparent speed in a plot also depends on how far apart the initial states were. The cases shown use different initial vectors as well as different graphs, so visual comparisons between plots conflate the two.
• Explicit Euler is only conditionally stable, requiring $\Delta t < 2/\lambda_n$. It holds comfortably for every graph above — $K_6$ is the tightest at $\Delta t < 1/3$ — but it is a constraint the method inherits, not a property of consensus.
• The manuscript’s applied claims about social media, public-health messaging and smart grids are motivation drawn from the literature, not results of these simulations. Nothing here was tested against real network data.
• The $30$- and $100$-node networks are described qualitatively; their edge lists and initial states are not recorded in the manuscript, so those two results cannot be reproduced from it as written.