The Small World Hypothesis
17:25 Share

The other day I was trying to think, who is the most distant person from me? Not geographically, more in terms of a social network. I thought about it for a while. The best answer I came up with was Kim Jong-un.

Not a personal friend, not a friend of a friend, but I mean, let's imagine a science fiction premise. I've come back from the future, I have to get him a message to save the world. Could I get that message through? I mean, I don't have his phone number, email address, but I've worked on some government R&D projects. I know a few low-profile politicians. Maybe one of those people knows someone in the State Department.

One of those people knows a UN negotiator, and one of them knows some humanitarian mission person who's been in North Korea. It's common in our culture to say there's just six steps between any two people, even from me to Kim Jong-un.

It isn't a conspiracy theory. It's a mathematical truth. And it's called the Small World Hypothesis. It asserts that almost everyone on Earth is only a few connections away from someone else. And if you've been following this season at all, you've probably heard Asaf maybe on numerous occasions mention how random networks look totally different from real-world networks.

Okay, but what if I need mock data or simulated data? Maybe I need test cases to see about the scalability of some graph project I'm working on. A random graph is not going to do the trick. Today's episode is going to be a tiny bit of a history lesson, but mostly the exploration of three different models. The Erdos-Renyi model, Watts-Strogatz model, and the Barabasi-Albert model. You're listening to Data Skeptic, Graphs and Network.

The podcast exploring how the graph data structure has an impact in science, industry, and elsewhere. So let's begin with this deceptively simple question. What does a random graph look like? Set aside that we already know it doesn't necessarily look like a real-world network. That's not an obvious insight. And if we rewind to the late 1950s, Hungarian mathematicians Paul Erdos and Alfred Rényi set out to answer this question.

Erdos is a particularly famous guy known for publishing on a wide array of topics with a wide array of contributors. There's even this notion of your Erdos number. If you're a co-publisher with him, you have, I think, a 1, maybe it's a 0. If you've published with someone who published with him, you've got one more than that, and so on and so forth. Quite an interesting network in and of itself. But anyway, that's separate.

Their idea back at this time in the 50s was kind of bold for the time. People knew about graphs, they'd studied them for a long time of course, but one of the key insights here was asking the question, what if we studied the entire space of all possible graphs? Good idea, how do we do that? Well their approach was treating connections as random events. So they came up with a model I'm going to describe for how you generate a random graph.

You've got however many nodes in your network, then you go through each possible pairing and you flip a coin. Heads they connect, tails they don't. This was the first formal model of a random network. And it's mathematically tractable, you gotta give it that. So even if we know it didn't match reality, this Erdos-Renyi model for the first time put randomness and networks in the same conversation.

That opens up an entirely new set of questions. For example, how many links does it take, adding them randomly, before the entire network becomes fully connected? What's the chance that some given nodes end up isolated? And when, I guess on average, does that massive cluster, what we now call the giant connected component, when does that typically emerge seemingly out of nowhere?

And these weren't just academic curiosities. Epidemiologists were interested in this. Maybe they could estimate things about how viruses spread. Computer scientists interested in networking saw how they could apply this. And there's a link to physics because mathematicians could finally talk about phase transitions in network structure. That moment when the system flips from one behavior to another just by nudging a single parameter.

So a promising model, computable, easy to understand, easy to work with. That coin toss could just as well be a probability weighted one way or the other.

But when scientists tried to apply the Erdos-Renyi model to real-world systems, like social networks and transportation grids, it missed the mark. What it failed to capture was something crucial, and that's the structure of the network. Real-world networks are full of tight communities, little groups where everyone's connected to everyone else. Those clusters always seem to appear.

But they also have shortcuts. Once in a while there's a long-range connection that dramatically shrinks the number of steps between two very distant points. Erdos-Renyi does give few short paths, but very little clustering. And that's not what we see in the real world. So the problem became clear. How do you build random networks that are less distinguishable from real-world ones? Or another way of putting it, under what generative process can we make graphs randomly that bear the properties we're looking for?

In this case, there are generally short paths and there's a high degree of clustering. Believe it or not, it's not until about 1998 when, as far as I can tell, the next leap forward happens. And that's with the Watts-Strogatz model. So Duncan Watts and Steve Strogatz published a paper that quietly changed everything.

Their insight was simple but powerful. You start with a highly clustered network, like a ring lattice. That's one in which each node is connected to its nearest neighbors. That's how we initialize a network. Then we rewire a small fraction of those edges at random. Not all of them, just a few.

Following this simple procedure, what they found was kind of stunning. Even with just a tiny number of random shortcuts, the average path length between nodes dropped dramatically, while that high clustering that they started with stayed intact. In other words, they built a bridge between two extremes. They created the order of regular networks, and they maintained that short path that we saw in both the previous model and in real-world networks.

So this Watt-Strogatz model is a step forward, at least if your goal is to generate random networks that are true to life, high clustering, short paths. But if we can say this method unseeded the first one, it begs the question, what might be even better than Watt-Strogatz? Or put another way, in what areas does it leave room for improvement?

So it's a nice model, it's a parametric model. You can control how many k nearest neighbors one connects to at the initialization and random factors about when edges are randomly redirected. If you ran clustering algorithms, it would find clusters. But the area that most fell short was its unevenness.

Real-world networks are messy. The Watt-Strogettes network still felt a little regular. You know, in the real world, let's take a social network for example. Some people have hundreds of connections, while others have just a couple. Some nodes are hubs, linking everywhere. Others are buried deep in little sub-networks you'd never visit very often on a random walk. And Watt-Strogettes doesn't account for that.

In their model, every node starts out with the same number of connections, even if you put a little bit of like Gaussian noise on that. It's still too uniform, too egalitarian really. Real-world networks exhibit those power laws we've talked about so often. There should be a few nodes that get most of the links. That doesn't mean Watt-Strogatz isn't useful. It certainly showed how just a few long-range connections can make a network feel small.

So this leads us to the third model we're going to cover today, the Barabasi-Albert model. Their insight was that instead of rewiring the network as the previous two approaches did, they were going to grow the network over time. So start from, well, I guess an empty graph, add a node, not possible to add any edges right away, so then you add a second node. And the key insight was that new nodes would prefer to connect to already well-connected nodes.

So, as you can imagine, just by chance, as you add nodes, at some point some density will occur. Maybe if you've added ten nodes, there's one in particular that five of the ten, well, I guess nine other nodes connect to it. That would mean it's probabilistically more likely that a future node would connect to this already popular one. The result of this approach, you get scale-free networks with lots of small nodes but a few massive hubs.

So we talked about three straightforward models, let's leave theory behind now and talk more about empirical evidence for the small world hypothesis. Identity theft is no joke. With data breaches up 72% just last year, protecting your personal information has never been more important. But here's the thing, it's not just about a strong password anymore. Data brokers are collecting and selling your information right now, making you vulnerable to scams and identity theft.

That's why I'm excited to tell you about Incogni. They specialize in automatically removing your personal data from these data broker sites. Think about it. Instead of spending countless hours trying to track down where your information is being sold, Incogni does it all for you. They work with hundreds of data brokers, sending removal requests and handling any pushback.

And with their family and friends plan, you can provide your loved ones with protection too. It's like having a personal privacy team working 24/7. For your exclusive 60% off offer on an annual Incogni plan, use our code DATASKEPTIC at checkout. That's one word, DATASKEPTIC. Or visit incogni.com/dataskeptic. I-N-C-O-G-N-I, Incogni. Let's leave theory behind now.

and talk more about empirical evidence for the small world hypothesis. It's one thing to model a small world on paper. It's enough to prove that we actually live in one. So we're going to rewind a couple decades. Again, the earliest and most iconic attempt to prove this theory came in 1967, when psychologist Stanley Milgram tried to measure the connectedness of American society using the U.S. Postal Service. Milgram had a pretty simple idea. You give a letter to a random person in the Midwest.

You ask them to forward it through personal contacts only to a target person in Boston. So don't just send it to anyone. Don't send it to the person directly, unless you know them. Instead think, all right, do I know anybody in Boston? Could I send it there? Or maybe you know somebody who lives in Ohio but went to school in Boston. If that's the best you got, send it to that person and ask them to forward it on. I think we all know the outcome, but at the onset, I guess it was possible these letters could get lost in the mail. Just backtrack.

bouncing around the country never hitting their target. But what Milgram found was that the average number of links, that is forwarded attempts, what Milgram found was that on average it took six attempts, six forwards, six links in that chain to get the letter from that random Midwesterner to the specific target in Boston. Thus ingrained in our culture this notion six degrees of separation, later popularized by the Kevin Bacon game.

Now in truth, Milgram's study is interesting but somewhat problematic. It had a very small sample size and it did have a lot of drop chains, that is letters that never reach their target. You could argue there was a geographic bias and everything I know about the Milgram prison experiment leads me to be skeptical of it, so I don't know what that says about this work. Alright, so what other evidence have we got? Fast forward closer to the present.

Let's go to 2003 when sociologist Peter Dodds and his colleagues at Columbia University decided to revisit Milgrim's idea, but this time do it with email.

Instead of a physical letter, participants were asked to forward messages electronically. And again, using only their real-world contacts. In the DODS experiment, there were 18 different designated target individuals in 13 countries. So they weren't random people, they were spread across different professions, continents, and even social circles. So DODS got about 60,000 people to take part. And once again, something rather remarkable emerged. The arithmetic mean, that's the regular average,

The number of steps needed to reach the target was 5.5. That's slightly less than six digital handshakes to cross oceans, languages, and social boundaries. Very similar to Milgram's experiment, but more data, more rigor, and crucially at a global scale this time. It was the strongest evidence yet for the small world effect, and that it wasn't just some American quirk. It seems to be a universal structural property of human networks all around the world.

Next insight I could dig up comes in 2011 with the Backstrom et al. study. So it's 2011 and social networks have blown up. Facebook claims to have 721 million active users and over 69 billion friendship links. Arguably, this is probably the most comprehensive social network dataset ever assembled. So researchers at Facebook led by Lars Backstrom will able to ask some really profound questions.

Just how many steps really do separate any two users on earth? They analyzed that entire Facebook graph. 721 million active users. Man, I wish I could talk to them about the engineering behind that. That could not have been easy. What did they find? The average distance between two users wasn't 6. It wasn't 5.5. It was 4.72.

So the phrase six degrees of separation wasn't just true, it was out of date. What's going on here? Is the world shrinking? Are we getting more connected? Or maybe we're just measuring things better now. We have a digital data set that we didn't have before. It's probably all of the above. Milgrams and Dodd replied on human judgment. Who do you think is closer to the target? Facebook had the actual network. All right, so where does this leave us?

We have some methods for generating random graphs. The Barabasi-Albert one seems to be the most consistent with real-world data. We have empirical evidence to believe the small world hypothesis is true. Okay, what do we do with that? If you accept we live in a small world, it raises a whole new set of questions. Short paths and tight clusters don't just describe a network. They shape how that network behaves.

In a small world structure, a rumor or a meme, maybe even a call to action can spread with incredible speed. It doesn't necessarily need a big marketing push, it just needs the right shortcut. The same goes for viruses, biological or digital. Small world networks make it easy for pathogens to jump from one cluster to another, bypassing the barriers geography or social distance usually provide. There are also some serious implications for, I guess, core computer science.

When you study algorithms, you typically discuss the worst case runtime, Big O analysis. I know there's a lot of good work in average case analysis as well, but it happens to be the case that algorithms like breadth-first search and Dijkstra's algorithm are going to run more efficiently when the average path lengths are short. And even problems that are normally considered intractable, NP-hard problems, some of them can behave differently when run on small world data sets.

There's interesting things to be done studying not just the worst case, but the typical case. You know, from theory to what actually happens. Now, outside of classical algorithms, small world structures impact complexity. So let's now invoke the spirit of Karl Popper and ask the key question: How might one falsify this hypothesis? What data could invalidate the small world hypothesis?

One way would be to show that in a real-world network, people are not connected by short paths. That in actuality, average distances are large. That most nodes are isolated or live in structural dead zones. I don't know, maybe with like spiders it's that way? Aren't they reclusive? Maybe there's some weird animal whose social network bears that structure, but not one that I know of. Another route would be to disprove the clustering side.

show that real-world networks don't actually form tight communities. But again, across domains, whether social, biological, or technological, always seems to be you see dense local groupings. All this brings us to just one deep truth: the small world hypothesis may not be a law, but it's a pattern. And like any good pattern, its power isn't in being universally true, it's in being true often enough to shape the way we think.

Isn't it both curious and wonderful that these emergent properties happen just by scaling up this one wonderful data structure? So the small world hypothesis is one hypothesis that truly stands up to the scrutiny of the skeptical eye.