The Story of Networks

Networks, spurred on by digital technology, have become such an important part of our lives so quickly, that much of  the bigger story has been lost.  The result has been a lot of unneeded confusion.

We tweet, update our status on Facebook and talk constantly on our mobile phones.  We prospect for business, find jobs, friends, lovers and even spouses through a complex web of relationships that we’ve really just begun to really understand.

That is the story of networks. It’s a fascinating tale with many twists and turns that reach across centuries.  Moreover, it’s an important one.  As networks become a larger part of our lives and businesses, we need to understand them better than we do now.

The Beginning: Seven Bridges of Königsberg

It all starts in Königsberg, now Kaliningrad, a small strip of Russian territory sandwiched between Poland and Lithuania.  In the 18th century, the philosopher Immanuel Kant, lived there and was famous for taking walks so regularly that it was said that people could set their clocks by him.

Most likely, on these walks, he would encounter one of its seven famous bridges.

When Kant was still a young boy, the bridges had become the center of a popular riddle:  Is it possible to walk across all seven bridges without crossing the same one twice?  It was an enigma that defied an easy solution until it caught the eye of the Leonhard Euler, the greatest mathematician of that age.

To solve the Königsberg bridge problem, Euler developed a new type of mathematics called graph theory.  He designated the four land masses that the bridges connected as nodes and the bridges themselves as links.

From there it was fairly easy to see that the only way someone could walk across all the bridges only once would be if there were an even number of bridges.  It was a nice trick, but at the time, nobody realized how important Euler’s invention of graph theory would become.

Random Networks

One of the people who got interested in graphs was this funny looking guy, Paul Erdős.

Erdős was famous for showing up at mathematicians doors and announcing “my brain is open” (meaning that he was ready to collaborate).  He did this so often, that mathematicians often rank themselves by their Erdős number, or how many links away they are from collaborating with him.

What Erdős realized is that if networks develop randomly, they are highly efficient.  Even with a lot of nodes, you need relatively few links.  Moreover, the larger the network, the less links you need, proportionately, to connect everything together.

The Milgram Small World Experiment: 6 Degrees of Separation

In 1967, the psychologist Stanley Milgram randomly selected people living in Wichita, Kansas and Omaha, Nebraska and asked them to get a letter to a stockbroker in Boston they had never met.  This became known as the small world experiment.

The subjects were given no information except the man’s name and occupation and were only allowed to send the package to people they knew on a first name basis.  Amazingly, the letters got there in about six steps on average.  Just six relationships separated people across an entire continent!

(More modern e-mail experiments have confirmed most of Milgram’s findings).

Just as Erdős predicted, even in the huge network of people comprising the entire USA, it took an amazingly small amount of links to connect them all.  There seemed to be mysterious forces at work that bind disparate parts into a coherent whole.

The Strength of Weak Ties

Mark Granovetter, a sociologist, was aware of Milgram’s work and decided to study the matter further.  In the late 1960’s and Early 1970’s, he began studying how people found jobs in communities around Boston.

He soon found that successful job searches revolved around a strange combination of acquaintance and chance.  Granovetter found that over 80% of the people in his study who found a job through a contact did not have a close relationship with that person.

Our friends have a lot more friends than we do, so we’ll often find what we’re looking for through the friends of our friends (besides, we share so much of our experiences with those close to us that they tend to have the same information we do).  Granovetter called this phenomenon, The Strength of Weak Ties (pdf).

Syncing Behavior

In the late 90’s, a graduate student named Duncan Watts started thinking seriously about networks in conjunction with the work his PhD advisor, Steven Strogatz, was doing on the strange way that certain things, such as heart pacemaker cells and Malaysian fireflies, can sync their behavior as if they were one giant organism.

How do they do it?  Is there a leader?  In what manner does the information travel across thousands or even millions of entities?

It occurred to Watts that the situation was eerily similar to the six degrees phenomenon uncovered by Milgram.  Just like with pacemaker cells and fireflies, information seems to have an ability to travel across large populations very quickly.  Watts was determined to figure out how it happened.

Spacemen vs. Cavemen

Watts started with a thought experiment inspired by two Isaac Asimov novels: one about spacemen and another about cavemen. The spacemen communicated remotely so that the people they knew didn’t know each other, while the cavemen lived in isolated groups and knew everybody their friends knew.

He decided to build a mathematical model that would describe both situations and every possibility in between.

Armed with mathematical representations for both his “spacemen and his “cavemen” he could experiment with different types of networks.

Small World Networks

What he found was startling. In his model, as communities connect to each other, the social distance between people increases – up to a point – and then immediately comes crashing down.

Although surprising, the pattern was familiar.  Similar “instantaneous phase transitions” have been long known in physics, specifically in Bose-Einstein Statistics.  Moreover, he found that in almost all cases, the same result appeared. It took a small amount of random links to shorten social distance dramatically, but an enormous amount to lose the cohesiveness of communities.

In other words, globally connected networks with strong local cohesion are not only possible, they are the equilibrium case – you just needed a relatively small number of Granovetter’s “weak ties” mixed in to make the whole thing work.

He called the result a “Small World Network” after Milgram’s famous experiment.

The Fitness Model

Almost as soon as Watts and Strogatz came out with their paper Albert-László Barabási recognized its importance to the work he was doing on how networks evolve.  He, along with his student, Reka Albert, realized that networks grow and that as they do, the nodes with the most links get the bulk of new links.  They called this effect preferential attachment.

The Barabási-Albert Model had an important consequence.  As networks evolve, they form hubs that dominate the network, along with massive amounts of smaller nodes which link to the hubs.  Moreover, they found the structure of networks form power laws, the same mathematical structure made famous by Chris Anderson’s book, The Long Tail.

Later, Barabási further embellished on both Watts’ work and his own B-A model by capitalizing on the similarities that the Watts-Strogatz model had with the Bose-Einstein equation.  Along with preferential attachment, he substituted “fitness” for the original Bose-Einstein variables and found that there was a perfect fit with network data.

This became his Fitness Model of Networks. (For more on the implications of this, see my post on the Justin Bieber phenomenon).

The Future of Networks

Probably the biggest difference between the modern network theory of Watts and Barabasi and what came before is how universal both the methods and implications are.  They didn’t need to invent new math like Euler, nor does their work apply to only specific situations like Erdős.

Instead, they used basic tools like power laws and Bose-Einstein statistics to find commonalities among a variety of phenomena like the Internet, nervous systems, ecological systems and a whole lot of other stuff.  It is this universality which makes networks so important and useful.

While much of the publicity is focused on online social networks such as Facebook and Twitter, the really exciting stuff is happening elsewhere.  Network theory is being applied to medicine, innovation and marketing theory as well as a host of other areas.  To get an idea of where the future lies, watch this great Nicholas Christakis TED talk.

Whatever your field of endeavor, the story of networks is bound to play a part.

– Greg