icaoberg / Other topics - Introduction to Small-World Networks

Created Sun, 03 May 2026 00:00:00 +0000 Modified Sun, 03 May 2026 09:38:29 -0400

Jupyter Notebook python

Other topics - Introduction to Small-World Networks¶

A small-world network is a graph in which most nodes are not directly connected, yet any two nodes can be reached by a surprisingly short path — combining high clustering with a low average path length. The concept was formalised by Watts & Strogatz (1998).

Key properties:

Average path length L: average shortest-path distance between all node pairs — small (grows as log N).
Clustering coefficient C: probability that two neighbours of a node are also connected — high.
Small-world index σ: C/C_rand divided by L/L_rand — σ > 1 indicates small-world behaviour.

What you'll learn:

Installing and importing NetworkX
Watts–Strogatz, Newman–Watts–Strogatz, and Barabási–Albert models
How rewiring probability shapes the network
Measuring and comparing network metrics
Degree distributions
Community detection
Shortest paths and centrality measures
Real-world network analogues

Installation¶

In [1]:

!pip install networkx matplotlib numpy scipy -q

Imports¶

In [2]:

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.cm as cm
from collections import Counter

print(f'NetworkX version: {nx.__version__}')
plt.style.use('seaborn-v0_8-whitegrid')
SEED = 42

NetworkX version: 3.5

1. The Continuum: Regular → Small-World → Random¶

The Watts–Strogatz model starts from a regular ring lattice and rewires each edge with probability p. As p increases from 0 to 1 the network transitions from fully regular to fully random, passing through a sweet spot with both short paths and high clustering.

In [3]:

n, k = 30, 4
ps = [0.0, 0.05, 0.2, 1.0]
labels = ['Regular\n(p=0)', 'Small-world\n(p=0.05)', 'Small-world\n(p=0.2)', 'Random\n(p=1)']

fig, axes = plt.subplots(1, 4, figsize=(18, 5))
for ax, p, lbl in zip(axes, ps, labels):
    G = nx.watts_strogatz_graph(n, k, p, seed=SEED)
    pos = nx.circular_layout(G)
    nx.draw(G, pos, ax=ax, with_labels=False,
            node_size=180, node_color='steelblue',
            edge_color='gray', alpha=0.85, width=0.8)
    ax.set_title(lbl, fontsize=11)

fig.suptitle('Watts–Strogatz: Regular → Small-World → Random', fontsize=13, y=1.02)
plt.tight_layout()
plt.show()

No description has been provided for this image

2. Watts–Strogatz Model¶

nx.watts_strogatz_graph(n, k, p) — start from a ring where each node is connected to its k nearest neighbours, then rewire each edge with probability p.

In [4]:

n, k, p = 50, 6, 0.1
G_ws = nx.watts_strogatz_graph(n, k, p, seed=SEED)

print(f'Nodes          : {G_ws.number_of_nodes()}')
print(f'Edges          : {G_ws.number_of_edges()}')
print(f'Avg path length: {nx.average_shortest_path_length(G_ws):.4f}')
print(f'Avg clustering : {nx.average_clustering(G_ws):.4f}')
print(f'Density        : {nx.density(G_ws):.4f}')

Nodes          : 50
Edges          : 150
Avg path length: 2.9747
Avg clustering : 0.4578
Density        : 0.1224

In [5]:

pos = nx.spring_layout(G_ws, seed=SEED)
degrees = dict(G_ws.degree())
node_colors = [degrees[n] for n in G_ws.nodes()]

fig, ax = plt.subplots(figsize=(8, 7))
nc = nx.draw_networkx_nodes(G_ws, pos, ax=ax,
    node_color=node_colors, cmap='plasma',
    node_size=250, alpha=0.9)
nx.draw_networkx_edges(G_ws, pos, ax=ax, alpha=0.3, edge_color='gray')
nx.draw_networkx_labels(G_ws, pos, ax=ax, font_size=7)
plt.colorbar(nc, ax=ax, label='Degree')
ax.set_title(f'Watts–Strogatz (n={n}, k={k}, p={p}) — nodes coloured by degree')
ax.axis('off')
plt.tight_layout()
plt.show()

3. Newman–Watts–Strogatz Model¶

Instead of rewiring edges, the Newman–Watts–Strogatz model adds shortcuts with probability p while keeping all original lattice edges. This preserves connectivity more robustly than WS.

In [6]:

n, k, p = 40, 4, 0.15
G_nws = nx.newman_watts_strogatz_graph(n, k, p, seed=SEED)

print(f'Nodes          : {G_nws.number_of_nodes()}')
print(f'Edges          : {G_nws.number_of_edges()}')
print(f'Avg path length: {nx.average_shortest_path_length(G_nws):.4f}')
print(f'Avg clustering : {nx.average_clustering(G_nws):.4f}')

Nodes          : 40
Edges          : 91
Avg path length: 3.2782
Avg clustering : 0.4538

In [7]:

fig, axes = plt.subplots(1, 2, figsize=(13, 6))

for ax, layout_fn, title in zip(
        axes,
        [nx.circular_layout, nx.spring_layout],
        ['Circular layout', 'Spring layout']):
    pos = layout_fn(G_nws, seed=SEED) if 'spring' in title.lower() else layout_fn(G_nws)
    nx.draw(G_nws, pos, ax=ax, with_labels=False,
            node_size=200, node_color='tomato',
            edge_color='gray', alpha=0.8, width=0.7)
    ax.set_title(f'Newman–Watts–Strogatz — {title}')

plt.tight_layout()
plt.show()

4. Barabási–Albert Scale-Free Model¶

The Barabási–Albert model grows a network by preferential attachment: new nodes attach to existing nodes with probability proportional to their degree, producing a power-law degree distribution and naturally short average path lengths (but low clustering).

In [8]:

n, m = 100, 2
G_ba = nx.barabasi_albert_graph(n, m, seed=SEED)

print(f'Nodes          : {G_ba.number_of_nodes()}')
print(f'Edges          : {G_ba.number_of_edges()}')
print(f'Avg path length: {nx.average_shortest_path_length(G_ba):.4f}')
print(f'Avg clustering : {nx.average_clustering(G_ba):.4f}')
print(f'Max degree     : {max(dict(G_ba.degree()).values())}')

Nodes          : 100
Edges          : 196
Avg path length: 2.8527
Avg clustering : 0.1634
Max degree     : 36

In [9]:

pos = nx.spring_layout(G_ba, seed=SEED)
degrees = dict(G_ba.degree())
sizes = [degrees[n] * 30 for n in G_ba.nodes()]
colors = [degrees[n] for n in G_ba.nodes()]

fig, ax = plt.subplots(figsize=(9, 8))
nc = nx.draw_networkx_nodes(G_ba, pos, ax=ax,
    node_size=sizes, node_color=colors, cmap='hot_r', alpha=0.9)
nx.draw_networkx_edges(G_ba, pos, ax=ax, alpha=0.2, edge_color='gray', width=0.5)
plt.colorbar(nc, ax=ax, label='Degree')
ax.set_title(f'Barabási–Albert (n={n}, m={m}) — hubs highlighted by size & colour')
ax.axis('off')
plt.tight_layout()
plt.show()

5. Metrics vs. Rewiring Probability¶

As p increases in the Watts–Strogatz model, the average path length L drops rapidly while the clustering coefficient C stays high — the hallmark of the small-world regime.

In [10]:

n, k = 100, 6
ps = np.logspace(-3, 0, 50)
Ls, Cs = [], []

for p in ps:
    G = nx.watts_strogatz_graph(n, k, p, seed=SEED)
    Ls.append(nx.average_shortest_path_length(G))
    Cs.append(nx.average_clustering(G))

# Normalise to values at p=0 (regular lattice)
L0, C0 = Ls[0], Cs[0]
Ls_norm = [l / L0 for l in Ls]
Cs_norm = [c / C0 for c in Cs]

fig, ax = plt.subplots(figsize=(8, 5))
ax.semilogx(ps, Ls_norm, 'o-', ms=4, label='L(p) / L(0)  — path length', color='steelblue')
ax.semilogx(ps, Cs_norm, 's-', ms=4, label='C(p) / C(0)  — clustering', color='tomato')
ax.axvspan(0.01, 0.3, alpha=0.08, color='green', label='Small-world regime')
ax.set_xlabel('Rewiring probability p (log scale)')
ax.set_ylabel('Normalised metric')
ax.set_title('L and C vs. rewiring probability (Watts–Strogatz, n=100, k=6)')
ax.legend()
plt.tight_layout()
plt.show()

6. Degree Distributions¶

Regular lattice / WS: narrow, near-Poisson distribution — most nodes have similar degrees.
Barabási–Albert: heavy-tailed power law — a few hubs dominate.
Erdős–Rényi random: Poisson distribution.

In [11]:

n = 500
G_ws2  = nx.watts_strogatz_graph(n, 6, 0.1, seed=SEED)
G_ba2  = nx.barabasi_albert_graph(n, 3, seed=SEED)
G_er   = nx.erdos_renyi_graph(n, 6/n, seed=SEED)

graphs = [('Watts–Strogatz',  G_ws2,  'steelblue'),
          ('Barabási–Albert', G_ba2,  'tomato'),
          ('Erdős–Rényi',     G_er,   'seagreen')]

fig, axes = plt.subplots(1, 3, figsize=(15, 4))
for ax, (title, G, col) in zip(axes, graphs):
    degs = [d for _, d in G.degree()]
    cnt = Counter(degs)
    ax.bar(cnt.keys(), cnt.values(), color=col, alpha=0.8, edgecolor='white')
    ax.set_xlabel('Degree')
    ax.set_ylabel('Count')
    ax.set_title(title)

fig.suptitle('Degree Distributions', fontsize=13)
plt.tight_layout()
plt.show()

7. Power-Law Degree Distribution (log–log)¶

Scale-free networks show a straight line in a log–log degree histogram, indicating P(k) ∝ k⁻ᵞ.

In [12]:

degs = sorted([d for _, d in G_ba2.degree()], reverse=True)
cnt = Counter(degs)
ks = np.array(sorted(cnt.keys()))
pk = np.array([cnt[k] for k in ks], dtype=float)
pk /= pk.sum()

fig, ax = plt.subplots(figsize=(6, 5))
ax.loglog(ks, pk, 'o', ms=5, color='tomato', label='BA degree distribution')

# Fit a line in log-log space
mask = pk > 0
coeffs = np.polyfit(np.log(ks[mask]), np.log(pk[mask]), 1)
fit_y = np.exp(np.polyval(coeffs, np.log(ks)))
ax.loglog(ks, fit_y, '--', color='black', label=f'Fit: γ ≈ {-coeffs[0]:.2f}')

ax.set_xlabel('Degree k')
ax.set_ylabel('P(k)')
ax.set_title('Barabási–Albert — power-law degree distribution')
ax.legend()
plt.tight_layout()
plt.show()

8. Small-World Coefficient σ¶

σ = (C / C_rand) / (L / L_rand)
A network is considered small-world when σ > 1. We compare WS, BA, and ER.

In [13]:

def small_world_sigma(G, nrand=5, seed=0):
    """Ratio of normalised clustering to normalised path length."""
    rng = np.random.default_rng(seed)
    C = nx.average_clustering(G)
    L = nx.average_shortest_path_length(G)
    Cr_list, Lr_list = [], []
    for i in range(nrand):
        R = nx.random_reference(G, niter=5, seed=int(rng.integers(1e6)))
        if nx.is_connected(R):
            Cr_list.append(nx.average_clustering(R))
            Lr_list.append(nx.average_shortest_path_length(R))
    if not Cr_list:
        return float('nan')
    Cr = np.mean(Cr_list)
    Lr = np.mean(Lr_list)
    return (C / Cr) / (L / Lr) if Lr and Cr else float('nan')

for name, G in [('WS (p=0.1)', nx.watts_strogatz_graph(60, 6, 0.1, seed=SEED)),
                ('NWS (p=0.15)', nx.newman_watts_strogatz_graph(60, 6, 0.15, seed=SEED)),
                ('BA (m=2)',  nx.barabasi_albert_graph(60, 2, seed=SEED)),
                ('ER',       nx.erdos_renyi_graph(60, 0.1, seed=SEED))]:
    if nx.is_connected(G):
        s = small_world_sigma(G)
        print(f'{name:18s}  σ = {s:.3f}  {"✓ small-world" if s > 1 else "✗"}')
    else:
        print(f'{name:18s}  (disconnected — skip)')

WS (p=0.1)          σ = 5.410  ✓ small-world
NWS (p=0.15)        σ = 4.782  ✓ small-world
BA (m=2)            σ = 1.190  ✓ small-world
ER                  σ = 0.945  ✗

9. Shortest Paths¶

We visualise all shortest paths from a chosen source node, colouring nodes by their hop distance from the source.

In [14]:

G = nx.watts_strogatz_graph(40, 4, 0.1, seed=SEED)
source = 0
lengths = nx.single_source_shortest_path_length(G, source)
max_dist = max(lengths.values())

pos = nx.spring_layout(G, seed=SEED)
node_colors = [lengths[n] for n in G.nodes()]

fig, ax = plt.subplots(figsize=(8, 7))
nc = nx.draw_networkx_nodes(G, pos, ax=ax,
    node_color=node_colors, cmap='cool',
    node_size=300, alpha=0.9)
nx.draw_networkx_edges(G, pos, ax=ax, alpha=0.3, edge_color='gray')
nx.draw_networkx_labels(G, pos, ax=ax, font_size=7)
plt.colorbar(nc, ax=ax, label=f'Hop distance from node {source}')
ax.set_title(f'Shortest paths from node {source} (max depth {max_dist})')
ax.axis('off')
plt.tight_layout()
plt.show()

10. Centrality Measures¶

Centrality quantifies how important a node is within the network:

Degree centrality: fraction of nodes each node is connected to.
Betweenness centrality: fraction of shortest paths that pass through a node.
Closeness centrality: inverse of the average distance to all other nodes.
Eigenvector centrality: influence based on the centrality of neighbours.

In [15]:

G = nx.watts_strogatz_graph(50, 6, 0.1, seed=SEED)
pos = nx.spring_layout(G, seed=SEED)

centralities = {
    'Degree':      nx.degree_centrality(G),
    'Betweenness': nx.betweenness_centrality(G),
    'Closeness':   nx.closeness_centrality(G),
    'Eigenvector': nx.eigenvector_centrality(G, max_iter=500),
}

fig, axes = plt.subplots(2, 2, figsize=(13, 11))
for ax, (title, cent) in zip(axes.ravel(), centralities.items()):
    vals = [cent[n] for n in G.nodes()]
    nc = nx.draw_networkx_nodes(G, pos, ax=ax,
        node_color=vals, cmap='YlOrRd',
        node_size=[v * 2000 + 80 for v in vals], alpha=0.9)
    nx.draw_networkx_edges(G, pos, ax=ax, alpha=0.25, edge_color='gray', width=0.7)
    plt.colorbar(nc, ax=ax)
    ax.set_title(f'{title} centrality')
    ax.axis('off')

fig.suptitle('Centrality Measures — WS small-world network', fontsize=13)
plt.tight_layout()
plt.show()

11. Community Detection¶

Communities are densely connected subgraphs that are loosely connected to one another. We use the Louvain-style greedy modularity algorithm built into NetworkX.

In [16]:

from networkx.algorithms.community import greedy_modularity_communities

G = nx.watts_strogatz_graph(60, 6, 0.08, seed=SEED)
communities = list(greedy_modularity_communities(G))
print(f'Number of communities: {len(communities)}')
for i, c in enumerate(communities):
    print(f'  Community {i}: {len(c)} nodes')

Number of communities: 4
  Community 0: 19 nodes
  Community 1: 15 nodes
  Community 2: 15 nodes
  Community 3: 11 nodes

In [17]:

pos = nx.spring_layout(G, seed=SEED)
palette = plt.cm.tab10(np.linspace(0, 0.9, len(communities)))

fig, ax = plt.subplots(figsize=(9, 8))
for color, community in zip(palette, communities):
    nx.draw_networkx_nodes(G, pos, nodelist=list(community),
                           node_color=[color], node_size=280,
                           alpha=0.9, ax=ax)
nx.draw_networkx_edges(G, pos, ax=ax, alpha=0.25, edge_color='gray', width=0.6)
nx.draw_networkx_labels(G, pos, ax=ax, font_size=6)
ax.set_title(f'Community Detection — {len(communities)} communities (greedy modularity)')
ax.axis('off')
plt.tight_layout()
plt.show()

12. Local Clustering Coefficient¶

The local clustering coefficient of a node is the fraction of its neighbour pairs that are also connected to each other. Visualising it reveals which nodes sit inside tight cliques vs. act as bridges.

In [18]:

G = nx.watts_strogatz_graph(50, 6, 0.1, seed=SEED)
clust = nx.clustering(G)
pos = nx.circular_layout(G)

fig, axes = plt.subplots(1, 2, figsize=(14, 6))

# Network coloured by clustering
vals = [clust[n] for n in G.nodes()]
nc = nx.draw_networkx_nodes(G, pos, ax=axes[0],
    node_color=vals, cmap='RdYlGn', node_size=280, alpha=0.9)
nx.draw_networkx_edges(G, pos, ax=axes[0], alpha=0.3, edge_color='gray')
plt.colorbar(nc, ax=axes[0], label='Clustering coefficient')
axes[0].set_title('Local clustering (circular layout)')
axes[0].axis('off')

# Distribution
axes[1].hist(vals, bins=20, color='seagreen', edgecolor='white', alpha=0.85)
axes[1].axvline(np.mean(vals), color='red', linestyle='--', label=f'Mean = {np.mean(vals):.3f}')
axes[1].set_xlabel('Local clustering coefficient')
axes[1].set_ylabel('Count')
axes[1].set_title('Distribution of clustering coefficients')
axes[1].legend()

plt.tight_layout()
plt.show()

13. Side-by-Side Network Comparison¶

Comparing four graph types on a common set of metrics.

In [19]:

import pandas as pd

n = 100
test_graphs = {
    'Regular lattice (WS p=0)':  nx.watts_strogatz_graph(n, 6, 0.0, seed=SEED),
    'Small-world (WS p=0.1)':    nx.watts_strogatz_graph(n, 6, 0.1, seed=SEED),
    'Barabási–Albert (m=3)':     nx.barabasi_albert_graph(n, 3, seed=SEED),
    'Erdős–Rényi (p=0.06)':      nx.erdos_renyi_graph(n, 0.06, seed=SEED),
}

rows = []
for name, G in test_graphs.items():
    if not nx.is_connected(G):
        G = G.subgraph(max(nx.connected_components(G), key=len)).copy()
    rows.append({
        'Model': name,
        'Nodes': G.number_of_nodes(),
        'Edges': G.number_of_edges(),
        'Avg path length': round(nx.average_shortest_path_length(G), 3),
        'Avg clustering':  round(nx.average_clustering(G), 3),
        'Density':         round(nx.density(G), 4),
        'Diameter':        nx.diameter(G),
    })

df = pd.DataFrame(rows).set_index('Model')
df

Out[19]:

	Nodes	Edges	Avg path length	Avg clustering	Density	Diameter
Model
Regular lattice (WS p=0)	100	300	8.758	0.600	0.0606	17
Small-world (WS p=0.1)	100	300	3.618	0.443	0.0606	7
Barabási–Albert (m=3)	100	291	2.515	0.187	0.0588	4
Erdős–Rényi (p=0.06)	100	269	2.877	0.054	0.0543	6

14. Real-World Analogue: Zachary's Karate Club¶

Zachary's karate club is a classic social network (34 nodes, 78 edges) built from observations of a university club that later split into two factions. It exhibits small-world properties and is used to benchmark community detection algorithms.

In [20]:

G_kc = nx.karate_club_graph()
print(f'Nodes          : {G_kc.number_of_nodes()}')
print(f'Edges          : {G_kc.number_of_edges()}')
print(f'Avg path length: {nx.average_shortest_path_length(G_kc):.4f}')
print(f'Avg clustering : {nx.average_clustering(G_kc):.4f}')
print(f'Diameter       : {nx.diameter(G_kc)}')

Nodes          : 34
Edges          : 78
Avg path length: 2.4082
Avg clustering : 0.5706
Diameter       : 5

In [21]:

# Official club split (0=Mr. Hi faction, 1=Officer faction)
club_color = ['steelblue' if G_kc.nodes[n]['club'] == 'Mr. Hi' else 'tomato'
               for n in G_kc.nodes()]
bc = nx.betweenness_centrality(G_kc)
sizes = [bc[n] * 3000 + 150 for n in G_kc.nodes()]

pos = nx.spring_layout(G_kc, seed=SEED)
fig, ax = plt.subplots(figsize=(9, 7))
nx.draw_networkx_nodes(G_kc, pos, ax=ax,
    node_color=club_color, node_size=sizes, alpha=0.9)
nx.draw_networkx_edges(G_kc, pos, ax=ax, alpha=0.4, edge_color='gray')
nx.draw_networkx_labels(G_kc, pos, ax=ax, font_size=8)
ax.set_title("Zachary's Karate Club — colour=faction, size=betweenness centrality")
ax.axis('off')

from matplotlib.patches import Patch
ax.legend(handles=[Patch(color='steelblue', label='Mr. Hi'),
                   Patch(color='tomato',    label='Officer')],
          loc='upper left')
plt.tight_layout()
plt.show()

15. Rewiring Progression — Six Snapshots¶

Static snapshot grid showing how the network's visual structure evolves across six rewiring probabilities.

In [22]:

ps_snap = [0.0, 0.02, 0.05, 0.1, 0.3, 1.0]
n, k = 24, 4

fig, axes = plt.subplots(2, 3, figsize=(15, 9))
for ax, p in zip(axes.ravel(), ps_snap):
    G = nx.watts_strogatz_graph(n, k, p, seed=SEED)
    L = nx.average_shortest_path_length(G)
    C = nx.average_clustering(G)
    pos = nx.circular_layout(G)
    nx.draw(G, pos, ax=ax, with_labels=False,
            node_size=200, node_color='mediumpurple',
            edge_color='gray', alpha=0.85, width=0.8)
    ax.set_title(f'p = {p:.2f}\nL={L:.2f}, C={C:.2f}', fontsize=10)

fig.suptitle('Watts–Strogatz rewiring progression', fontsize=13)
plt.tight_layout()
plt.show()

Summary¶

Model	High clustering	Short paths	Power-law degree	Notes
Regular lattice	✓	✗	✗	Baseline; p=0 WS
Watts–Strogatz	✓	✓	✗	Classic small-world
Newman–Watts–Strogatz	✓	✓	✗	Adds shortcuts, preserves lattice
Barabási–Albert	✗	✓	✓	Scale-free / preferential attachment
Erdős–Rényi random	✗	✓	✗	Null model

Further reading:

Watts & Strogatz (1998) — Collective dynamics of 'small-world' networks
Barabási & Albert (1999) — Emergence of scaling in random networks
NetworkX documentation
NetworkX gallery

Licensed under the GNU General Public License v2.0 (GPL-2).
You may redistribute and/or modify this work under the terms of GPL-2.
This work is distributed WITHOUT ANY WARRANTY.
Happy computing.