The same graph, invented twice

Frank Harary built it in 1962 to make a graph as hard to disconnect as possible. Newman and Watts built it in 1999 to make a small world. Under one condition on the parameters, they are the same random graph, and the popular NetworkX versions of both quietly differ from the originals.

An interactive companion to^[1] S. Son, E. J. Choi & S. H. Lee, “Revisiting small-world network models,” J. Korean Phys. Soc. 83, 879–889 (2023). doi:10.1007/s40042-023-00921-8

original model, as published NetworkX implementation randomly placed edge

§2.1–2.2

Harary’s rule: fill the ring, scatter the rest

Given n nodes and m edges, the best possible connectivity is r = ⌊2m/n⌋. Harary builds that graph deterministically from rings and diameters, then places any leftover edges uniformly at random. NetworkX’s hnm_harary_graph keeps the first step but puts the leftovers in fixed positions, so every (n, m) gives exactly one graph.^[2]

The bottom row shows the Newman–Watts graphs^[3] that correspond to the same (n, m) under the mapping of §4: a ring of degree k_init = r, plus shortcuts added with p = 2m/(nr) − 1. The mapping needs r to be even; Newman–Watts reaches m only on average, so the edge count of each draw is shown.

Harary graph, n nodes and exactly m edges

Original Harary (OH)

Leftover edges placed at random

C –L –m –

NetworkX Harary (XH)

Leftover edges placed deterministically

C –L –m –

Corresponding Newman–Watts graph

Original Newman–Watts (ONW)

C –L –m –

NetworkX Newman–Watts (XNW)

C –L –m –

Nodes n

Edges m

deterministic core (rings and diameters) randomly placed edges (OH leftovers, NW shortcuts) XH leftovers in fixed positions

Fig. 2

Randomness buys a much wider range of graphs

Here n = 64 and m runs over every integer from 256 to 2015 (so r goes from 8 to 62), matching the paper and the neural-network search study it critiques. NetworkX gives one point per m; the original rule, drawn ten times per m, fans out across the clustering–path-length plane.

XH: 1,760 graphs

OH: 17,600 graphs

Scroll here to generate.

§3.1–3.3

Two ways to add a shortcut

In the original Newman–Watts model (ONW), each of the n k/2 ring edges triggers, with probability p, a shortcut between a uniformly random pair of nodes. In NetworkX’s newman_watts_strogatz_graph (XNW), the shortcut must start at an endpoint of the ring edge that triggered it, so every node gets a fixed number of attempts. The average degree is the same; its spread is not.

ONW XNW original ring degree k_init

Nodes n

Ring degree k_init

Probability p

Std. dev. of degree, ONW–

Std. dev. of degree, XNW–

Nodes still at k_init (ONW / XNW)–

s = k/(n−1−k)–

§3.4, Figs. 3–4

Clustering turns back up

Unlike Watts–Strogatz rewiring, Newman–Watts keeps adding edges. In a dense ring, shortcuts eventually close triangles faster than they open new triads, so average clustering C dips and then rises. Newman’s textbook approximation^[4] ignores triangles made by shortcuts, and Jo’s correction^[5] adds those closed by a single shortcut but drops the O(p²) terms. The paper’s Eq. (6) counts triangles made by one, two and three shortcuts and catches the upturn. Try k_init = 4 to see it vanish.

Eq. (6) of the paper, for the original Newman–Watts model with n nodes and ring degree k_init:

C_{p} = 3 \frac{\frac{n k_{init}}{4} (\frac{k_{init}}{2} - 1) + (\frac{k_{init}}{2} + 1) \frac{k_{init}}{4} \frac{k_{init} p}{n - 1 - k_{init}} n + \frac{k_{init}^{2} p^{2}}{2} \frac{k_{init}}{n} n + \frac{k_{init}^{2} p^{2}}{2} (1 - \frac{k_{init}}{n}) \frac{k_{init} p}{n - 1 - k_{init}} n}{\frac{1}{2} n k_{init} (k_{init} - 1) + n k_{init}^{2} p + \frac{1}{2} n k_{init}^{2} p^{2}}

Its value at p = 0 is the clustering of the bare ring,

C_{0} = C_{p} |_{p = 0} = \frac{3 (k_{init} - 2)}{4 (k_{init} - 1)}

so the curve plotted below is

\frac{C_{p}}{C_{0}} = \frac{4 (k_{init} - 1)}{k_{init} - 2} \cdot \frac{\frac{n k_{init}}{4} (\frac{k_{init}}{2} - 1) + (\frac{k_{init}}{2} + 1) \frac{k_{init}}{4} \frac{k_{init} p}{n - 1 - k_{init}} n + \frac{k_{init}^{2} p^{2}}{2} \frac{k_{init}}{n} n + \frac{k_{init}^{2} p^{2}}{2} (1 - \frac{k_{init}}{n}) \frac{k_{init} p}{n - 1 - k_{init}} n}{\frac{1}{2} n k_{init} (k_{init} - 1) + n k_{init}^{2} p + \frac{1}{2} n k_{init}^{2} p^{2}}

Reading the numerator from left to right, the four terms count triangles already in the ring, triangles closed by one shortcut, by two shortcuts, and by three shortcuts; the denominator counts connected triples. Keeping only the first numerator term gives Newman’s approximation, Eq. (A1); keeping the first two gives the one-shortcut (Jo-type) curve.

ONW simulation (±1 s.d.) XNW simulation Eq. (6), all terms (Son et al.) Eq. (6), one-shortcut term only (Jo-type) Newman’s approximation, Eq. (A1)

Ring degree k_init, with n = 100

Also plot path length

§4, Fig. 5

The equivalence

Harary’s case 3a with an even r is a ring of degree r plus m − rn/2 edges placed uniformly at random. The original Newman–Watts model is a ring of degree k_init plus, on average, p n k_init/2 edges placed uniformly at random. Match the two:

k_init = r, p = 2m / (n r) − 1

The only difference left is that Newman–Watts hits that edge count on average while Harary hits it exactly. Below, 150 graphs of each kind per point, n = 50.

OH C_m/C₀ OH L_m/L₀ ONW C_p/C₀ ONW L_p/L₀

Harary r = k_init