Albert-László Barabási and scale free networks

(Notes from a talk given yesterday at the MIT Media Lab Members meeting.)

Albert-László Barabási, a Hungarian scientist, is one of the leading theorists on the properties of networks. As it happens, networks appear in many different branches of science, from sociology to computer science to genetics. It’s hard to pin down what type of scientist Barabási is, as a result: he’s a network scientist.

In that sense, he’s following in the steps of other great Hungarian mathematicians, including Paul ErdÅ‘s and Alfréd Rényi, who conducted early work on understanding networks. In studying complex networks – friendships on Facebook, links between web pages – ErdÅ‘s and Rényi began by building graphs and assuming that nodes were connected randomly. In a network like this, the number of connections each node has is predictable: they’ll order themselves in a poisson distribution with a prominent peak around the average degree. The peak has a steep falloff, which means it’s very hard to find nodes with lots of connections, or to find totally disconnected nodes.

Of course, that’s not how networks in the real world work. In a society where we were organized randomly, we’d each have similarly sized circles of friends. But in real networks, some people are largely disconnected and some are very popular. Barabási studied distribution of links on the early Web, using robots to index web pages. He discovered that the distribution of links between webpages doesn’t form a poisson distribution – instead, it’s a Pareto distribution, a power law – most pages have very few links, while a small number have a massive amound of links. Barabási terms this a “scale free” network, a network in which a small number of highly connected hubs holds the network together.

He invites us to consider the game, “Six Degrees of Kevin Bacon”. It’s not hard to find connections between actors who’ve appeared in the same films together and build chains that connect virtually everyone in Hollywood. (Marilyn Monroe is two degrees away from Kevin Bacon.) The game closely parallels a game mathematicians play, calculating ErdÅ‘s numbers. If you’ve published a paper with ErdÅ‘s, your number is 1, published with an ErdÅ‘s collaborator and your number is 2, and so on. What both ErdÅ‘s numbers and the Kevin Bacon game demonstrate is tha Hollywood and mathematics are both interconnected networks.

What’s bizarre is that similarly structured networks show up far from human interactions. Barabási shows us a network of protein interactions in metabolic networks and tells us that this networks shows a very similar scale free structure, despite the fact that there’s no human intervention in building these networks, and the network is 4 million years old.

One of the breakthroughs in modeling networks is moving away from the assumption that network size is fixed. Instead, networks continually expand – people make new friendships, webpages are created and link to older pages. We can model these networks by adding nodes and then randomly connecting them to a small existing network. Again, that’s not how networks actually work. It’s more likely that the new ties will connect to popular nodes. This idea – preferential attachment – means that networks have a powerful first-mover advantage. It’s likely that the popular nodes will get more popular, and those that are marginal will stay that way.

But this can’t be the only principle at work, otherwise we’d still be searching using AltaVista, and Google would never have arisen. We need to model networks by considering other properties like “fitness”, how desirable it is to link to a given node. Nodes with a higher fitness can overcome the first-mover effect and can always maintain a fraction of available links.

Scale networks have interesting properties when it comes to robustness. You can remove random nodes from networks, and the network will likely stay connected. That’s because the majority of nodes in the network are not highly connected. If you remove links strategically, you can disconnect a scale network easily – you simply target the hubs. Remove links at random in a scale free network and you can remove 99% of the links and stay connected – remove strategically, and you can disconnect a network by eliminating a few hubs.

Barabasi looks at some practical applications of this understanding of human networks. He considers the structure of relationships within a Hungarian corporation that was having management problems. It turns out that the best connected person in the company, the person likely to spread news and gossip through network, is a low-level manager responsible for environmental compliance. Discovering the power of an individual like this can be uncomfortable – do you fire this guy because he’s bringing everyone down? Try to cheer him up? Create someone else who is as deeply connected across the organization?

He brings us back to the Kevin Bacon example: why Kevin Bacon? Is he the best connected node in Hollywood? No, not by a long shot. Mel Blanc, the voice behind Bugs Bunny, has the most films to his credit. The rest of the top 10 in terms of film appearances are largely porn stars. Kevin Bacon doesn’t appear on a list of the most film appearances until number 870 or so. It’s a coincidence, just a clever way of understanding the highly connected network space that is Holywood.