Networks and Simulation — Tutorial Six

Supplementary Notes: Consensus Dynamics

These notes are intended as pre-tutorial reading that focus on the ideas most directly relevant to the tutorial exercises, and in particular on the connections between the Laplacian, the dynamics, and the network structure you have been studying throughout the course.

1. Why Consensus Dynamics?

Networks are not just static objects — they host dynamic processes. One of the simplest and most instructive of these is consensus dynamics, a model for how interacting agents collectively reach agreement. Think of sensors in a distributed network averaging their measurements, or individuals in a social network adjusting their opinions toward those of their neighbours. In each case, a purely local rule — each agent adjusts based only on its immediate contacts — produces a global outcome: the whole system converges to a shared value.

This interplay between local rules and global outcomes is a recurring theme in network science. Consensus dynamics is a simple example of it, and its analysis reveals that the path to consensus — how fast it happens, whether it separates into stages, which nodes lead and which follow — is entirely determined by the spectral structure of a matrix called the graph Laplacian. You have not encountered this matrix in previous tutorials, but it is built from the adjacency matrix A you already know well, and its introduction is one of the main goals of this tutorial. The Laplacian turns out to be the natural operator for any process defined by differences between neighbouring nodes.

2. Introducing the Graph Laplacian

Before analysing the dynamics, we need to introduce a new matrix: the graph Laplacian. It is constructed from two matrices you already know.

The first is the adjacency matrix A, where $A_{ij} = 1$ if there is an edge between nodes $i$ and $j$, and $0$ otherwise.

The second is the degree matrix D: a diagonal matrix whose $i$-th diagonal entry is the degree $k_i = \sum_j A_{ij}$ of node $i$, and all off-diagonal entries are zero:

\[\mathbf{D} = \begin{pmatrix} k_1 & 0 & \cdots & 0 \\ 0 & k_2 & \cdots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & k_n \end{pmatrix}\]

The combinatorial graph Laplacian is defined as:

\[\mathbf{L} = \mathbf{D} - \mathbf{A}\]

Written out entry by entry, this gives:

\[L_{ij} = \begin{cases} k_i & \text{if } i = j \\ -1 & \text{if } i \neq j \text{ and } (i,j) \text{ is an edge} \\ 0 & \text{otherwise} \end{cases}\]

The Laplacian has several important properties that will be useful throughout the tutorial. First, every row sums to zero: $\sum_j L_{ij} = k_i - k_i = 0$. This means L always has at least one zero eigenvalue, with the constant vector $\mathbf{1}$ as its eigenvector. Second, for an undirected graph, L is symmetric and positive semi-definite — all its eigenvalues are real and non-negative. Third, the number of zero eigenvalues equals the number of connected components: a connected graph has exactly one zero eigenvalue.

Why not just use A? The adjacency matrix A encodes where edges go. The Laplacian L encodes differences across edges — for any vector x, the quantity

\[(\mathbf{L}\mathbf{x})_i = \sum_j A_{ij}(x_i - x_j)\]

measures the total disagreement between node $i$ and its neighbours. Any process defined by local differences — how much node $i$ differs from its neighbours — is naturally described by the Laplacian, not the adjacency matrix.

3. From the Coordinate Form to the Laplacian

The continuous-time consensus dynamics for a node i is:

\[\dot{x}_i = \sum_j A_{ij}(x_j - x_i)\]

Each node moves toward a weighted average of its neighbours’ states. If a neighbour has a higher value, node i increases; if lower, it decreases. The rate of change is zero if i already agrees with all its neighbours. This is a local rule: the sum runs only over nodes j adjacent to i (since $A_{ij} = 0$ for non-neighbours).

To write this in matrix form, expand the sum:

\[\dot{x}_i = \sum_j A_{ij} x_j - \sum_j A_{ij} x_i = (\mathbf{A}\mathbf{x})_i - k_i x_i\]

where $k_i = \sum_j A_{ij}$ is the degree of node i. In matrix form this is $\dot{\mathbf{x}} = \mathbf{A}\mathbf{x} - \mathbf{D}\mathbf{x} = -(\mathbf{D} - \mathbf{A})\mathbf{x}$, which is exactly:

\[\dot{\mathbf{x}} = -\mathbf{L}\mathbf{x}\]

This derivation makes clear why the Laplacian, and not the adjacency matrix alone, governs the dynamics. The consensus update is a difference operation — each node responds to the gap between itself and its neighbours — so the Laplacian, which encodes exactly those differences, is the natural operator.

To see what happens with A alone: the system $\dot{\mathbf{x}} = \mathbf{A}\mathbf{x}$ would have nodes increasing whenever their neighbours have high values, with no stabilising force from the degree term. This leads to exponential growth rather than convergence.

4. Convergence to the Mean: Local Rules, Global Outcomes

The formal solution to $\dot{\mathbf{x}} = -\mathbf{L}\mathbf{x}$ is:

\[\mathbf{x}(t) = e^{-\mathbf{L}t} \mathbf{x}(0)\]

To understand the long-time behaviour, use the spectral decomposition of L. For an undirected connected graph, L has n real, non-negative eigenvalues $0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ with corresponding orthonormal eigenvectors $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$. The first eigenvalue is always $\lambda_1 = 0$ with eigenvector $\mathbf{v}_1 = \mathbf{1}/\sqrt{n}$ (the uniform vector).

Expanding the initial condition in this eigenbasis:

\[\mathbf{x}(t) = \sum_{k=1}^{n} e^{-\lambda_k t} (\mathbf{v}_k^\top \mathbf{x}(0)) \mathbf{v}_k\]

The $k = 1$ term does not decay (since $\lambda_1 = 0$):

\[e^{-\lambda_1 t} (\mathbf{v}_1^\top \mathbf{x}(0)) \mathbf{v}_1 = \frac{\mathbf{1}^\top \mathbf{x}(0)}{n} \cdot \mathbf{1} = \bar{x} \cdot \mathbf{1}\]

where $\bar{x}$ is the mean of the initial conditions. All terms with $k \geq 2$ decay exponentially to zero. Therefore, as $t \to \infty$, every node converges to $\bar{x}$: the system reaches global consensus at the mean of the initial conditions.

Two things are worth noting. First, the mean is conserved: the total $\sum_i x_i(t)$ is constant, since $\frac{d}{dt}\mathbf{1}^\top \mathbf{x} = -\mathbf{1}^\top \mathbf{L} \mathbf{x} = 0$ (because $\mathbf{L}^\top \mathbf{1} = \mathbf{0}$). The system redistributes but does not create or destroy the total “opinion”. Second, convergence requires the network to be connected: if the network has multiple components, each component converges to its own local mean independently, since there is no path for information to travel between components.

5. The Spectral View: Convergence Rate and the Fiedler Value

The second term to vanish in the spectral expansion — the slowest-decaying non-trivial mode — decays at rate $\lambda_2$, the second-smallest eigenvalue of L. This means the characteristic timescale for reaching consensus is:

\[t^* \approx \frac{1}{\lambda_2}\]

The eigenvalue $\lambda_2$ is called the Fiedler value or the algebraic connectivity of the graph. A large Fiedler value means the network is highly connected and consensus is reached quickly; a small Fiedler value means the network has a bottleneck (a sparse cut) through which information flows slowly, and consensus is slow.

This gives a spectral interpretation of network connectivity that goes beyond simple edge counts. Two networks with the same number of edges can have very different Fiedler values — a ring has a very small Fiedler value (long path to carry information across), while a random graph with the same number of edges will have a much larger one.

The Fiedler vector (the eigenvector $\mathbf{v}_2$ corresponding to $\lambda_2$) also has a structural interpretation: its entries roughly partition the network into two halves, identifying the primary “cut” in the network. This is the basis for spectral bisection, a classical method for graph partitioning, and closely related to spectral clustering.

6. Timescale Separation in Modular Networks

For a network with C well-separated communities, the eigenvalue spectrum of L has a characteristic structure: the smallest C eigenvalues are small and clustered near zero (separated from the rest by a spectral gap), while the remaining $n - C$ eigenvalues are larger. This structure produces a striking dynamical phenomenon: timescale separation.

To see why, consider the spectral expansion again. The modes corresponding to the C small eigenvalues are slow to decay; the modes corresponding to larger eigenvalues decay quickly. In a modular network:

Fast modes (large eigenvalues): correspond to within-community fluctuations. Nodes within the same community rapidly equilibrate with each other, because they are densely connected. This happens on a timescale of approximately $1/\lambda_{C+1}$.
Slow modes (small eigenvalues): correspond to between-community dynamics. Once local consensus is reached within each community, the communities themselves slowly converge to a common value through the sparse cross-community edges. This happens on a timescale of approximately $1/\lambda_C$.

The result is a two-stage convergence: first, rapid local consensus within communities (nodes coloured by community membership converge to their community mean); then, slow global consensus as communities reach agreement with each other. In a semi-log time plot, this appears as a clear compression of trajectories at time $t^* \approx 1/\lambda_C$, followed by a second compression at a later time.

The size of the spectral gap — the difference between $\lambda_{C+1}$ and $\lambda_C$ — controls the degree of separation between the two stages. A large gap (strong community structure) produces a clear, long plateau between the two stages. A small gap (weak community structure) produces a barely visible separation, just as spectral clustering becomes unreliable when the gap is small.

This connection is not accidental. The slow modes of consensus dynamics and the eigenvectors used by spectral clustering are the same objects — the Fiedler vector and its neighbours in the spectrum. Watching consensus dynamics evolve on a modular network is, in a sense, watching spectral clustering unfold in time.

7. Directed Networks

Consensus dynamics on directed networks is considerably more complex. The key issue is that the Laplacian of a directed graph is no longer symmetric: the in-degree and out-degree of a node may differ, and the matrix $\mathbf{L} = \mathbf{D}^{\text{in}} - \mathbf{A}$ (or $\mathbf{D}^{\text{out}} - \mathbf{A}$, depending on convention), where $\mathbf{D}^{\text{in}}$ and $\mathbf{D}^{\text{out}}$ are the diagonal matrices of in-degrees and out-degrees respectively, is no longer guaranteed to have real eigenvalues or orthogonal eigenvectors.

More fundamentally, the conservation of the mean no longer holds in general. In a directed network, influence flows asymmetrically: if node i influences node j but not vice versa, the dynamics no longer conserves the total “opinion.” The system can still converge — under certain conditions on the graph’s strong connectivity and its associated random walk — but it converges to a weighted mean determined by the stationary distribution of the random walk on the directed graph, not the simple arithmetic mean. This stationary distribution is essentially the in-degree-weighted mean (related to PageRank), so nodes with many incoming edges have greater influence on the final consensus value.

A common practical approach when applying consensus dynamics to a directed network is to symmetrize the adjacency matrix (replacing $A_{ij}$ with $(A_{ij} + A_{ji})/2$) to obtain an undirected network on which the standard analysis applies. This is a modelling choice with real consequences, since it treats all edges as bidirectional; whether this is appropriate depends on the application.

8. Practical Notes

Numerical integration. The ODE $\dot{\mathbf{x}} = -\mathbf{L}\mathbf{x}$ can be integrated using scipy.integrate.solve_ivp with the system matrix constructed from the Laplacian. For small networks, the matrix exponential scipy.linalg.expm(-L * t) can be used directly for exact solutions at specific times. For large networks, constructing and exponentiating the full dense Laplacian is expensive; sparse solvers or explicit time-stepping are more practical.

Logarithmic time axis. Because the dynamics operates on multiple timescales — fast within-community equilibration and slow cross-community consensus — a linear time axis will either compress the early dynamics or fail to show the late-time convergence. A logarithmic time axis is essential for visualising both stages simultaneously.

SBM parameters. For 5 communities of 60 nodes, a within-community probability of $p_{\text{in}} = 0.15$ and between-community probability of $p_{\text{out}} = 0.01$ produces clear block structure while remaining sparse. Vary these to explore the transition between clear and weak community structure.

References

Lambiotte, R., & Schaub, M. T. (2021). Modularity and dynamics on complex networks. Cambridge University Press. https://doi.org/10.1017/9781108774116