Part 25: Network Science

A Bit of History

Psychologist Stanley Milgram's 1967 "small world" experiment asked ordinary Americans to route a letter to a stranger using only acquaintance chains — the letters that arrived took a median of about six intermediaries, popularizing the phrase "six degrees of separation" decades before anyone had the mathematics to explain why. That explanation arrived in 1998, when Duncan Watts and Steven Strogatz published "Collective Dynamics of 'Small-World' Networks," formalizing exactly what structural property makes short paths so common in real networks. A year later, Albert-László Barabási and Réka Albert published "Emergence of Scaling in Random Networks" (1999), explaining why real-world networks are dominated by a few extremely well-connected "hubs" rather than the uniform degree distribution the Erdős–Rényi model (Part 20) predicts. Centrality measures themselves were systematically formalized earlier, largely through Linton Freeman's influential 1977-1979 papers unifying degree, betweenness, and closeness centrality into one coherent framework.

Centrality Measures

"How important is this vertex?" has no single answer — different centrality measures capture genuinely different notions of importance:

• Degree centrality: simply the vertex's degree — how many direct connections it has.
• Betweenness centrality: the fraction of shortest paths between all other vertex pairs that pass through this vertex — capturing "bridge" or "broker" importance, independent of raw connection count.
• Closeness centrality: the inverse of the sum of shortest-path distances to every other vertex — capturing how quickly this vertex can reach the rest of the network.
• Eigenvector centrality: a vertex is important if it connects to other important vertices — precisely the same self-referential eigenvector idea underlying PageRank from a previous deep dive.

Community Detection

Community detection asks: can a network's vertices be partitioned into tightly-connected groups, with comparatively few edges between groups? This is closely related to, but distinct from, the global minimum cut problem (Stoer-Wagner/Karger's deep dives) — community detection typically seeks many well-separated groups simultaneously, optimizing a global quality measure called modularity (comparing actual within-group edge density against what random chance would predict), rather than finding a single optimal 2-way split.

Small-World Networks

The Watts-Strogatz model starts from a regular ring lattice (every vertex connected to its \(k\) nearest neighbors) and randomly "rewires" a small fraction of edges to arbitrary distant vertices. This tiny amount of randomness has an outsized effect: it dramatically shrinks the network's average shortest-path length (creating "shortcuts" across the whole structure) while barely disturbing the high local clustering the original ring lattice had — precisely the combination (high clustering and short average path length) observed in real social networks, and precisely what a purely random Erdős–Rényi graph fails to reproduce (it has short paths, but essentially no local clustering).

Scale-Free Networks

The Barabási-Albert model grows a network one vertex at a time, with each new vertex connecting preferentially to already well-connected existing vertices — a "rich get richer" mechanism called preferential attachment. This produces a power-law degree distribution (a small number of extremely high-degree "hub" vertices, and a long tail of low-degree vertices) rather than the roughly uniform degree distribution an Erdős–Rényi random graph produces — matching empirical observations of the actual web graph, airline route networks, and citation networks far more closely than uniform-degree random models ever could.

Real-World Applications

Exercises

1. Compute degree centrality by hand for every vertex in a small 6-vertex graph, and identify the vertex with the highest degree centrality.
2. Explain in your own words why a vertex can have low degree centrality but high betweenness centrality, giving a concrete example (hint: think of a single "bridge" vertex connecting two otherwise-separate dense clusters).
3. Describe the Watts-Strogatz rewiring process, and explain why rewiring even a small fraction of edges dramatically shrinks average path length while preserving local clustering.
4. Challenge: Research why the Barabási-Albert model's "rich get richer" preferential attachment mechanism produces a power-law degree distribution, connecting this to the model's growth-over-time construction.

Conclusion & Next Steps

Network science turns graph theory's abstract machinery toward empirical questions: what do real-world networks actually look like, and why do they consistently share certain structural signatures? Having studied networks as objects of empirical study, the series now turns to graphs as objects of machine learning — teaching computers to learn from graph-structured data directly.