Spectral Analysis of Networks

The eigenvalues and eigenvectors of the graph Laplacian encode deep structural properties of a network. The Fiedler value measures connectivity, the spectral gap controls diffusion speed, and effective resistance quantifies accessibility between locations.

1. The Graph Laplacian

For an undirected graph $G$ with adjacency matrix $\mathbf{A}$ and degree matrix $\mathbf{D} = \text{diag}(k_1, \ldots, k_n)$, the graph Laplacian is:

$$\mathbf{L} = \mathbf{D} - \mathbf{A}$$

Explicitly, its entries are:

$$L_{ij} = \begin{cases} k_i & \text{if } i = j \\ -1 & \text{if } (i,j) \in E \\ 0 & \text{otherwise} \end{cases}$$

Key properties of $\mathbf{L}$:

Positive semi-definite: $\mathbf{x}^T \mathbf{L} \mathbf{x} = \sum_{(i,j) \in E} (x_i - x_j)^2 \geq 0$
Smallest eigenvalue is zero: $\lambda_1 = 0$ with eigenvector $\mathbf{1}$ (the constant vector)
Multiplicity of zero: equals the number of connected components
Row sums are zero: $\mathbf{L}\mathbf{1} = \mathbf{0}$

The normalised Laplacian is sometimes preferred:$\;\mathcal{L} = \mathbf{D}^{-1/2}\mathbf{L}\mathbf{D}^{-1/2} = \mathbf{I} - \mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$, whose eigenvalues lie in $[0, 2]$.

2. The Fiedler Value and Algebraic Connectivity

The eigenvalues of $\mathbf{L}$ are ordered:

$$0 = \lambda_1 \leq \lambda_2 \leq \lambda_3 \leq \cdots \leq \lambda_n$$

The second-smallest eigenvalue $\lambda_2$ is called the Fiedler value or algebraic connectivity. It measures how well-connected the graph is:

$$\lambda_2 = \min_{\mathbf{x} \perp \mathbf{1}} \frac{\mathbf{x}^T \mathbf{L} \mathbf{x}}{\mathbf{x}^T \mathbf{x}} = \min_{\mathbf{x} \perp \mathbf{1}} \frac{\sum_{(i,j) \in E} (x_i - x_j)^2}{\sum_i x_i^2}$$

The corresponding eigenvector $\mathbf{v}_2$ -- the Fiedler vector -- provides the optimal bipartition of the graph. Nodes with positive components of $\mathbf{v}_2$ form one community, negative components form the other. This is the basis of spectral clustering.

Cheeger Inequality

The Fiedler value is related to the isoperimetric number (Cheeger constant) $h(G)$:

$$\frac{\lambda_2}{2} \leq h(G) \leq \sqrt{2\lambda_2 d_{\max}}$$

where $h(G) = \min_{S \subset V, |S| \leq n/2} \frac{|\partial S|}{|S|}$ is the minimum cut ratio. A large $\lambda_2$ means the graph has no bottleneck and is well-connected everywhere.

3. Heat Diffusion on Networks

The heat equation on a graph models diffusion processes (e.g., information spread, traffic congestion propagation):

$$\frac{d\mathbf{u}}{dt} = -\mathbf{L}\mathbf{u}$$

where $\mathbf{u}(t)$ is the vector of node values (temperature, density). The solution uses the spectral decomposition $\mathbf{L} = \mathbf{V}\boldsymbol{\Lambda}\mathbf{V}^T$:

$$\mathbf{u}(t) = e^{-\mathbf{L}t}\mathbf{u}(0) = \sum_{k=1}^{n} e^{-\lambda_k t} (\mathbf{v}_k^T \mathbf{u}(0)) \mathbf{v}_k$$

The $\lambda_1 = 0$ mode is the equilibrium (uniform distribution). The $\lambda_2$ mode decays slowest, so the mixing time scales as:

$$t_{\text{mix}} \sim \frac{1}{\lambda_2}$$

For urban networks, this means that well-connected grids (large $\lambda_2$) equilibrate traffic quickly, while networks with bottlenecks (small $\lambda_2$) have persistent congestion gradients.

4. Effective Resistance as Accessibility

The effective resistance between nodes $i$ and $j$is defined using the pseudoinverse of the Laplacian $\mathbf{L}^+$:

$$R_{\text{eff}}(i, j) = (\mathbf{e}_i - \mathbf{e}_j)^T \mathbf{L}^+ (\mathbf{e}_i - \mathbf{e}_j) = L^+_{ii} + L^+_{jj} - 2L^+_{ij}$$

where $\mathbf{e}_i$ is the $i$-th standard basis vector. In spectral form:

$$R_{\text{eff}}(i, j) = \sum_{k=2}^{n} \frac{(v_k(i) - v_k(j))^2}{\lambda_k}$$

The effective resistance is a true distance metric on the graph. Its urban interpretation: low resistance between two locations means they are well-connected by multiple paths. The total effective resistance (Kirchhoff index) is:

$$K_f(G) = \sum_{i < j} R_{\text{eff}}(i, j) = n \sum_{k=2}^{n} \frac{1}{\lambda_k}$$

5. Python: Laplacian Spectrum and Heat Diffusion

We compare the Laplacian spectra of a grid graph (regular city) and a random graph (irregular city), then simulate heat diffusion on both.

Spectral Analysis: Grid vs Random Graph

Python

script.py118 lines

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx

np.random.seed(42)

# --- Create two graphs ---
# 1. Grid graph (planned city)
n_grid = 10
G_grid = nx.grid_2d_graph(n_grid, n_grid)
G_grid = nx.convert_node_labels_to_integers(G_grid)

# 2. Random graph with same number of nodes and similar edge count
n_nodes = n_grid * n_grid
p_er = 2 * G_grid.number_of_edges() / (n_nodes * (n_nodes - 1))
G_rand = nx.erdos_renyi_graph(n_nodes, p_er, seed=42)
# Ensure connected
while not nx.is_connected(G_rand):
    G_rand = nx.erdos_renyi_graph(n_nodes, p_er * 1.1, seed=np.random.randint(10000))

# --- Compute Laplacian spectra ---
L_grid = nx.laplacian_matrix(G_grid).toarray().astype(float)
L_rand = nx.laplacian_matrix(G_rand).toarray().astype(float)

evals_grid = np.sort(np.linalg.eigvalsh(L_grid))
evals_rand = np.sort(np.linalg.eigvalsh(L_rand))

# Fiedler values
fiedler_grid = evals_grid[1]
fiedler_rand = evals_rand[1]

# --- Heat diffusion simulation ---
# Initial: heat at one corner
u0_grid = np.zeros(n_nodes)
u0_grid[0] = 1.0  # bottom-left corner of grid
u0_rand = np.zeros(n_nodes)
u0_rand[0] = 1.0

# Spectral decomposition
evals_g, evecs_g = np.linalg.eigh(L_grid)
evals_r, evecs_r = np.linalg.eigh(L_rand)

def heat_diffuse(evals, evecs, u0, t):
    coeffs = evecs.T @ u0
    return evecs @ (coeffs * np.exp(-evals * t))

times = [0, 0.5, 2.0, 10.0]

# --- Plot ---
fig, axes = plt.subplots(2, 2, figsize=(14, 11))

# Top left: Eigenvalue distribution comparison
ax = axes[0, 0]
ax.plot(range(len(evals_grid)), evals_grid, 'o-', color='#10b981', markersize=2,
        linewidth=1.5, label=f'Grid ($\\lambda_2$={fiedler_grid:.3f})')
ax.plot(range(len(evals_rand)), evals_rand, 'o-', color='#f59e0b', markersize=2,
        linewidth=1.5, label=f'Random ($\\lambda_2$={fiedler_rand:.3f})')
ax.set_xlabel('Eigenvalue index k', fontsize=12, color='white')
ax.set_ylabel('$\\lambda_k$', fontsize=12, color='white')
ax.set_title('Laplacian Spectrum', fontsize=13, color='white')
ax.legend(fontsize=10, facecolor='#1e293b', edgecolor='#10b981', labelcolor='white')
ax.tick_params(colors='white')
ax.grid(True, alpha=0.2)

# Top right: Spectral density (histogram of eigenvalues)
ax = axes[0, 1]
ax.hist(evals_grid[1:], bins=30, density=True, alpha=0.6, color='#10b981', edgecolor='#064e3b', label='Grid')
ax.hist(evals_rand[1:], bins=30, density=True, alpha=0.6, color='#f59e0b', edgecolor='#92400e', label='Random')
ax.set_xlabel('$\\lambda$', fontsize=12, color='white')
ax.set_ylabel('Spectral density', fontsize=12, color='white')
ax.set_title('Spectral Density Distribution', fontsize=13, color='white')
ax.legend(fontsize=10, facecolor='#1e293b', edgecolor='#10b981', labelcolor='white')
ax.tick_params(colors='white')
ax.grid(True, alpha=0.2)

# Bottom left: Heat diffusion on grid
ax = axes[1, 0]
pos_grid = {i: (i % n_grid, i // n_grid) for i in range(n_nodes)}
for i, t in enumerate(times):
    u_t = heat_diffuse(evals_g, evecs_g, u0_grid, t)
    total = np.sum(u_t)
    ax.plot(sorted(u_t, reverse=True), color=['#94a3b8', '#06b6d4', '#10b981', '#f59e0b'][i],
            linewidth=2, label=f't = {t}')
ax.set_xlabel('Node (sorted by temperature)', fontsize=12, color='white')
ax.set_ylabel('Temperature u(t)', fontsize=12, color='white')
ax.set_title('Heat Diffusion on Grid', fontsize=13, color='white')
ax.legend(fontsize=10, facecolor='#1e293b', edgecolor='#10b981', labelcolor='white')
ax.tick_params(colors='white')
ax.grid(True, alpha=0.2)

# Bottom right: Heat diffusion on random graph
ax = axes[1, 1]
for i, t in enumerate(times):
    u_t = heat_diffuse(evals_r, evecs_r, u0_rand, t)
    ax.plot(sorted(u_t, reverse=True), color=['#94a3b8', '#06b6d4', '#10b981', '#f59e0b'][i],
            linewidth=2, label=f't = {t}')
ax.set_xlabel('Node (sorted by temperature)', fontsize=12, color='white')
ax.set_ylabel('Temperature u(t)', fontsize=12, color='white')
ax.set_title('Heat Diffusion on Random Graph', fontsize=13, color='white')
ax.legend(fontsize=10, facecolor='#1e293b', edgecolor='#10b981', labelcolor='white')
ax.tick_params(colors='white')
ax.grid(True, alpha=0.2)

fig.patch.set_facecolor('#0f172a')
for ax_row in axes:
    for ax in ax_row:
        ax.set_facecolor('#0f172a')
plt.tight_layout()
plt.savefig('output.png', dpi=130, bbox_inches='tight', facecolor='#0f172a')
plt.show()

# Kirchhoff index
Kf_grid = n_nodes * np.sum(1.0 / evals_grid[1:])
Kf_rand = n_nodes * np.sum(1.0 / evals_rand[1:])
print(f"Grid: Fiedler value = {fiedler_grid:.4f}, Kirchhoff index = {Kf_grid:.1f}")
print(f"Random: Fiedler value = {fiedler_rand:.4f}, Kirchhoff index = {Kf_rand:.1f}")
print(f"Grid mixing time ~ 1/lambda_2 = {1/fiedler_grid:.1f}")
print(f"Random mixing time ~ 1/lambda_2 = {1/fiedler_rand:.1f}")

Click Run to execute the Python code

Code will be executed with Python 3 on the server

← Street Networks Percolation Threshold →