Network Theory: Small World, Scale-Free Networks, Clustering

Network Theory: Structure of Interactions

Many complex systems are best described not by equations, but by networks—graphs, where nodes are agents and edges are their interactions. The structure of the network fundamentally determines dynamics: how quickly a disease spreads, how vulnerable a power grid is, how efficiently information propagates.

Key Characteristics of Networks

Graph G = (V, E): V is the set of nodes (vertices), E ⊆ V×V is the set of edges. |V| = n, |E| = m.

Degree of a vertex d(v): number of edges incident to v. Average degree ⟨k⟩ = 2m/n. Degree distribution P(k) = proportion of vertices of degree k—a key characteristic.

Shortest path L(u,v): minimum number of edges between u and v. Average path L̄ = (1/n(n−1)) Σᵤ≠ᵥ L(u,v).

Clustering coefficient Cᵥ: proportion of neighbor pairs of v that are themselves connected by edges: Cᵥ = 2eₙ/(dᵥ(dᵥ−1)), where eₙ is the number of edges among neighbors. Global C̄ = ⟨Cᵥ⟩.

Centrality (betweenness centrality): bᵥ = Σᵤ≠ᵥ σᵤᵥ(v)/σᵤᵥ, where σᵤᵥ is the number of shortest paths from u to v, σᵤᵥ(v) is the number of them passing through v. High betweenness → “broker” role in the network.

Small World Phenomenon (Watts & Strogatz, 1998)

Milgram’s experiment (1967): a letter needs to be delivered to an addressee in Boston through a chain of acquaintances from Omaha, Nebraska. Average chain length: 6 handshakes (number of steps). This is the “six degrees of separation” phenomenon.

Watts-Strogatz model: initial regular lattice (high C, large L) → randomly “rewire” part of the edges (probability p). At p ≈ 0.01: L drops sharply (global “shortcut”), C remains high. Small world: C ≫ C_{random}, L ≈ L_{random}.

Real examples of small world:

• WWW: L ≈ 19 (Barabási, 1999)
• Neural network of C. elegans: L = 2.65, C = 0.28 (vs random graph L = 2.25, C = 0.05)
• Scientific coauthorship: L = 4.79, C = 0.43

Scale-Free Networks (Barabási & Albert, 1999)

Erdős-Rényi random graph: P(k) ~ Poisson—most nodes have degree around ⟨k⟩. Real networks: different! P(k) ~ k^{−γ}—power law. The “tail” of the distribution is far heavier than in Poisson.

Scale-free network: γ ∈ (2, 3) for most real networks. There is no characteristic scale—hence the name. “Hubs”—nodes with very high degree (hub airports, Google, Facebook).

Formation mechanism: preferential attachment. A new node connects to existing nodes with probability proportional to their degree: P(connect to v) = d(v)/Σᵤ d(u). “The rich get richer.” Result: γ = 3.

Real examples: WWW (incoming links: γ ≈ 2.1), citations (γ ≈ 3), airline routes, protein-protein biological networks.

Vulnerability and Robustness of Networks

Robustness to random failures: upon removal of random nodes, scale-free network remains robust—most nodes have low degree, their removal does not destroy connectivity. The giant component remains significant until about 80% of nodes are removed.

Vulnerability to targeted attacks: removal of hubs is catastrophic. Removal of the top 8% of nodes by degree → fragmentation of the network. Example: WWW loses connectivity when “attacked” on Google, Yahoo, Baidu.

Epidemiological implication: in scale-free networks, there is no epidemic threshold (Albert, 2000): SIR model with R₀ > 1 always spreads. Hubs are superspreaders.

Numerical Example: Internet Graph

Graph: 100000 nodes. Random graph (p = 0.0001): C ≈ 0.0001, L ≈ 5.0, max degree ≈ 20. Scale-free (γ ≈ 2.3): C ≈ 0.4, L ≈ 4.2, max degree ≈ 2000. Corresponds to real internet: high clustering + small world + hubs.

Assignment: Use NetworkX (Python). Create three graphs (n=1000 nodes): (1) Random (Erdős–Rényi, p=0.01); (2) Small World (Watts-Strogatz, k=10, p=0.05); (3) Scale-Free (Barabási-Albert, m=5). For each: compute L, C, P(k), betweenness centrality. Visualize degree distribution in log-log scale—which graph has a power law? Simulate SIR epidemic (β=0.1, γ=0.05)—in which graph does it spread faster?