As I’ve noted previously, I’ve been exploring the science of complexity these last few months, trying to get a feel for the different subfields and how it can be applied to various real world issues. One of the areas in the field of Complexity is that of Network Science.
Linked: The New Science of Networks by Albert-Laszlo Barabasi is a useful overview of the field. It’s an easy read that covers a broad amount of the field and is a good layman’s introduction to network theory. He shows that the world around us can be described in terms of Networks, and comments on how they are formed, what forms they take, and how they grow. Note: This is one of my longer reviews, and I left a lot out!
Barabasi starts off with one of the most famous network problems of history: the bridges of Konigsberg. He shows how the problem can be solved using nodes and links, which was discovered by Leonhard Euler. This segues into a discussion of graph theory and its history. Graph theory describes a network as a collection of links and nodes. How to connect these nodes and the relations between them, as well as how the network grows in the first place, is the focus of the book. Hr runs through a history, starting with random networks which although helpful in formulating basic laws, do not really describe real world networks. He describes Stanley Milgram’s famous six degrees experiment and how Barabasi and his team researched it and found similarities in other networks of small worlds, where any node can reach any other node in a small number of jumps no matter how large the network. He also talks about the strength of weak ties.
Clustering – each of us has a small number of close friends – is a key structure in networks and Barabasi talks about these and how a few links between them reduces the length between distant nodes. Still, the nodes are all egalitarian and this is not how it works in real life. Barabasi refers back to Malcolm Gladwell’s book The Tipping Point, talking about connectors and hubs – which means they have more than the average number of links which the egalitarian model doesn’t allow. Hubs are apparent in the Kevin Bacon Game and in airline networks, among others. The distribution follows a Power Law rather than a bell curve. These networks are “scale-free” since there is no average node.
A discussion Of Pareto’s 80 / 20 law and a discussion of “phase transitions” follows, and how understanding them helps us to see how hubs appear in networks. He notes that networks grow and are not static, and that counterintuitively just because a hub is old doesn’t mean it will get the most links – although that does play a role. There is “preferential attachment” – nodes prefer to link to nodes that already have a lot of links. Google today is a perfect example. In other words, the rich get richer…
A basic prediction of scale-free networks is that the first mover will have an advantage in forming the most links. In real life networks, however, this isn’t the case. This is because contrary to the assumption that all links are the same, they instead are all different with different intrinsic properties. This is defined as fitness. More fit nodes will end up with more links. This is complementary to preferential attachment which only examines the number of links. It also shows that the number of links is therefore independent of when the node joins the network.
In an intriguing chapter, Barabasi then turns to the weaknesses of a highly-interconnected network. Most networks in nature are highly interconnected and are also highly robust in that the failure of one component won’t take down the whole network. Barabasi and his team investigated this phenomenon. They found that for these networks, removing a large number of nodes typically had little or no effect on the functioning of the network. This is due to the hubs model – removing nodes randomly eliminates a large number of tiny nodes and not very many hubs, which preserves the integrity of the network since the tiny nodes aren’t very interconnected. However, if the Hubs are specifically AND simultaneously targeted, the network will quickly break apart. This, then is the primary weakness of these networks. they are not vulnerable to accident, but are highly vulnerable to attack. This applies to both man-made and natural networks from the internet to food webs. Cascading failures can happen when the load from a failed node is shifted to other nodes that are unable to handle the load, whereupon they fail and pass it on to yet more nodes that cannot handle the load, and so on. This is what happens during blackouts and rolling power failures and in denial of service attacks on routers. These happen in dynamic networks and still need researched.
Using these findings of network theory, Barabasi discusses the spread of ideas, fads, and viruses, using as examples AIDS, computer viruses, jokes, and hybrid corn. Malcolm Gladwell covers some of this in The Tipping Point. One of the more surprising findings was that the rate of spread does not depend on virulence. The solution is to target the cures to the hubs. In AIDS, this would involve targeting the people who are most likely spreading the virus (those with many partners) as opposed to those who don’t (people with only one or two partners). There are, obviously, ethical questions associated with this course of action. Barabasi also examines the resilience of today’s internet (the physical infrastructure as opposed to the World Wide Web). Instead of being a mesh as it was originally designed inj the 1950s, the Internet is more of a hub and spoke model that has grown organically. This is why the Internet, too, is vulnerable to an attack on Hubs, rather than being perfectly resilient. It also enables “parasitic computing,” where your computer can be “hijacked” and used to perform functions for a computer thousands of miles away – this is done with spam, for example. It can also be used voluntarily, as in SET@Home or research into protein-folding. Another question asked is that as the Internet continues to grow across the planet as it is connected to computers and sensors and cell-phones, will it eventually become self-aware?
One surprising thing about the World Wide Web is how difficult it can be to find information, even though theoretically the amount of information is limitless. Google, surprisingly, indexes less than 25% of all the pages out there! Worse yet, despite the fact that most webpages are separated by an average of nineteen links, due to the architecture of the Web, only 24% of pages can be reached by surfing from one to the other. This is due to the structure of the Web: it is a Directed Network. Barabasi describes this in detail. Also, due to these properties, sections of the web can be partitioned off – providing a tool for control of access. However, the topology of the Web as described here is much more effective than a government at keeping a website hidden! Barabasi notes that the Web is little understood and a great deal more time and attention should be paid to understanding it.
Networks are common, and especially so in biology. Barabasi also discusses how network theory can be applied to business and the economy. He posits that to compete organizations need to go from a tree hierarchy to a web or network instead. They will also participate in ever interconnected webs with suppliers and customers. He shows how members of boards of corporations are ever more interconnected with hubs – 20% of them serve on more than one board. The degree of separation of boards of directors is only three!
In conclusion, Barabasi summarizes: “…though real networks are not as random…as envisioned, chance and randomness do play an important role in their construction. Real networks are not static, as all graph theoretical models were until recently. Instead, growth plays a role in shaping their topology. They are not as centralized as a star network is. Rather, there is a hierarchy of hubs that keep these networks together, a heavily connected node followed by several less connected ones, trailed by dozens of even smaller nodes. ” There is no center, or controller, in the middle of the network that could be removed to destroy the web. They are instead self-organized with emergent behavior. Al-Qaeda is an example of a web organization, which is why the United States military – a hierarchical tree organization – has had trouble battling it. Barabasi suggests that “We must eliminate the need and desire of the nodes to form links to terrorist organizations by offering them a chance to belong to more constructive and meaningful webs.” We can do this by attacking “…the underlying social, economic, and political roots that fuel the network’s growth.” Barabasi sees the future of network theory as understanding complexity and “move beyond structure and topology and start focusing on the dynamics that take place along the links.”