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.
The Network Science Lens
Graph theory and network science study the same mathematical object, but they often ask different kinds of questions. Graph theory tends to ask what is possible, impossible, optimal, or guaranteed for a graph. Network science starts with a graph measured from the real world and asks what patterns it contains, whether those patterns are surprising, and what mechanisms might have produced them.
Zooming In and Out on the Same Network
A useful way to organize network science is by scale. At the local scale we ask which vertices matter. At the mesoscopic scale we ask how vertices group into communities. At the global scale we ask about overall path lengths, clustering, robustness, and degree distributions.
The Graph Is a Model, Not the World
Before computing any network statistic, decide what a vertex means and what an edge means. A friendship edge, a message edge, a co-presence edge, and a transaction edge can produce very different centralities and communities over the same people. Network science is therefore partly about algorithms and partly about choosing a representation whose measurements answer the question you actually care about.
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.
Four Ways a Vertex Can Matter
Centrality measures are not competing estimates of one hidden quantity called “importance.” They answer different questions. The motifs below deliberately isolate each idea.
Here \(\sigma_{st}\) is the number of shortest paths from \(s\) to \(t\), while \(\sigma_{st}(v)\) counts those that pass through \(v\). The eigenvector equation says a vertex receives score from the scores of its neighbors. For disconnected graphs, ordinary closeness needs care; harmonic closeness, which sums reciprocal finite distances, is often the safer variant.
Memory Aid: Ask What “Important” Means
Degree asks “who knows many?” Betweenness asks “who brokers routes?” Closeness asks “who is near everyone?” Eigenvector asks “who is connected to the well-connected?” The answer can change completely when the question changes.
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.
Key Insight
Two influential and very different community-detection strategies both appear as algorithm deep dives alongside this part: the Girvan-Newman algorithm repeatedly removes the highest-betweenness-centrality edges (the network's "bridges") to progressively split the graph into communities, while the Louvain method instead greedily optimizes modularity directly by moving vertices between candidate communities — a "top-down cutting" strategy versus a "bottom-up assembling" strategy for the same underlying goal.
A Community Is Not the Same as a Connected Component
Two communities may still be connected by several edges. The point is relative density: many connections inside groups, comparatively few connections between them. A connected component asks whether any path exists at all; community detection asks whether the network has meaningful internal organization.
For an undirected, unweighted graph, a common community-quality score is modularity. It rewards within-community edges that are more numerous than a degree-preserving random null model would predict:
The term \(A_{ij}\) records whether the observed edge exists; \(k_i k_j/(2m)\) is the null-model expectation; and \(\delta(c_i,c_j)\) keeps only vertex pairs placed in the same community. Intuitively, modularity asks: “Are these groups more internally connected than their degrees alone would lead us to expect?”
Community Detection Is a Modeling Choice
Real networks do not always contain one objectively correct partition. Communities may overlap, appear at multiple scales, or change over time. Algorithms therefore reveal a useful structural view under a chosen objective; they do not automatically uncover a single ground-truth grouping.
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).
From Lattice to Small World
The surprising part of the Watts-Strogatz model is not that random edges shorten paths. It is that a small number of long-range shortcuts can shorten distances between enormous numbers of vertex pairs while leaving most local neighborhoods almost untouched.
Two statistics capture that combination. The local clustering coefficient of a vertex asks what fraction of its neighbors are connected to one another, while the average path length measures typical shortest-path distance across a connected network:
Here \(T_v\) is the number of edges among the \(k_v\) neighbors of \(v\). A small-world network is therefore not merely a graph with short paths; its signature is the coexistence of short global routes and strong 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.
How a Hub Emerges Without Being Designed
Preferential attachment combines two ingredients: the network grows, and new vertices are more likely to connect to vertices that already have many links. A small early advantage can therefore compound over many arrival steps.
In the idealized Barabási-Albert model, this mechanism produces an asymptotic degree distribution of the form \(P(k)\propto k^{-3}\). That exponent is a property of this particular model, not a universal law for every network with hubs.
Additional Context: “Scale-Free” Is a Hypothesis to Test
Real networks often have highly unequal degree distributions, but that does not automatically prove a clean power law or a Barabási-Albert growth mechanism. Empirical network science distinguishes the observation “there are hubs and a heavy tail” from the stronger statistical claim “the degree distribution follows a power law.” The model is valuable because it explains one mechanism that can create hubs, not because every real network must follow it exactly.
From Network Picture to Evidence
A reliable network-science workflow moves from representation to measurement to comparison. A statistic becomes informative when it is interpreted against a plausible baseline or mechanism, rather than treated as meaningful merely because it can be computed.
Real-World Applications
Identifying Influential Spreaders in Epidemic & Information Networks
Public health researchers use betweenness and eigenvector centrality to identify individuals whose vaccination or isolation would most effectively slow disease spread through a contact network — targeting structurally important "bridge" individuals rather than simply the most socially active ones. The same centrality toolkit, applied to information-sharing networks, helps platforms identify accounts whose removal would most effectively contain the spread of coordinated misinformation campaigns.
Centrality Is a Structural Signal, Not a Causal Guarantee
A high-centrality vertex is structurally prominent under a chosen network model, but the best intervention target also depends on direction, edge weights, timing, behavior, and the process actually spreading on the network. The same person can look central in a static friendship graph and unimportant in a temporal contact graph. This is exactly why the richer representations from Part 24 matter in applied network science.
Part 25 Mental Model
Network science becomes easier to remember when each idea is tied to the specific question it answers.
Degree
Direct reach: who has many immediate neighbors?
Betweenness
Brokerage: who repeatedly sits on shortest routes between other vertices?
Closeness
Access: who can reach the rest of the network in only a few steps?
Eigenvector
Prestige: who is connected to vertices that are themselves well connected?
Community
Mesoscopic structure: look for groups that are dense inside and relatively sparse between. A community is not the same thing as a connected component.
Small World
Local plus global: high neighborhood clustering can coexist with surprisingly short paths across the whole network.
Preferential Attachment
Growth plus feedback: when new vertices favor already-popular vertices, hubs can emerge naturally over time.
Workflow
Interpret carefully: model first, measure second, compare against a meaningful baseline, and only then draw domain conclusions.
Exercises
- Compute degree centrality by hand for every vertex in a small 6-vertex graph, and identify the vertex with the highest degree centrality.
- 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).
- 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.
- 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.
Next in the Series
In Part 26: Graph Machine Learning & Knowledge Graphs, we'll explore graph neural networks and how modern AI systems represent and reason over relational data.