Albert-Laszlo Barabasi’s Linked: A Summary, Part I

Some call it the circle of life and others call it cosmic consciousness. No matter what anybody calls it, we all acknowledge the same universal truth, that we are all connected, even if we do not know exactly how.  In his book Linked, author Albert-Laszlo Barabasi explores the how.

Barabasi states that his book has a simple aim: to get us to think networks – they are present everywhere and we just need an eye for them he says (7). Linked is supposed to help us develop this eye, but be forewarned: this book is not an easy read. Barabasi is a physicist, and despite trying hard to make this book user-friendly, the subject matter just doesn’t lend itself to the task.

The first chapter, the Introduction, opens with Barabasi linking a twenty-first century teenage computer hacker named MafiaBoy to the first century Apostle Paul, and asserting that both were masters of the network. From his bedroom, the teen hacker orchestrated a distributed denial of service attack (DDoS) that was able to crash the websites of some of the biggest names in e-commerce back in the year 2000. Nearly 2,000 years before the, then, biggest denial of service attack on the Internet, a reformed persecutor of Christians had a conversion experience and afterward walked nearly 10,000 miles, over twelve years, spreading the message and faith of a man whom he’d never met.

From this reach of an opening, we jump to the book’s first scientific concept – reductionism. Barabasi writes that reductionism tells us that to comprehend nature, we first must decipher its components, assuming that once we understand the parts it will be easy to understand the whole (6). He then tells us a secret: we’ve been doing it wrong.

Barabasi believes that reductionism, which according to him was the driving force behind much of the twentieth century’s scientific research, is the wrong approach and has resulted in us taking apart the universe and having no idea how to put it back together. He goes on to say that after spending trillions of research dollars to disassemble nature in the last century, we are just now acknowledging that we have no clue how to continue except to take it apart further (6) because putting it back together turned out to be harder than scientists thought it would be.

So, why would it be harder to reassemble the universe than take it apart? Barabasi answers that question with one word – complexity. He writes that nature is not a well-designed puzzle with only one way to put it back together and that in complex systems the components can fit in so many different ways that it would take us billions of years to try all the combinations (6). Well, then, how did nature do it? According to the author, nature exploits the laws of self-organization whose roots, he writes, are still largely a mystery.

In chapter two, Barabasi introduces the reader to the random universe. He tells us way too much minutiae about Leonhard Euler, who in 1736 introduced the idea of graphs and unintentionally created a branch of mathematics known as graph theory, which today is the basis for our thinking about networks.

We then learn about Paul Erdos and Alfred Renyi, who together in 1959 introduced the random network theory model. Random network theory says that nodes in a network connect to each other randomly and, according to Barabasi, has dominated scientific thinking about networks since being introduced in 1959 (23).

Chapter three of Linked introduces us to something we have all probably heard of, just not like this: the six degrees of separation. Although it would not be given its catchy title until more than sixty years later, the concept was first introduced in 1929 by Hungarian writer Frigyes Karinthy in his short story “Lancszemek” (PDF) or, in English, “Chains” (26), which also made it the first time the concept was ever published. A character in the story bet the other people that he was with that they could name any person on earth and through at most five acquaintances, one of which he knew personally, he could link himself to the chosen one, and does so.

In 1967, Harvard professor Stanley Milgram rediscovered Karinthy’s concept and turned it into a much celebrated and groundbreaking study of our interconnectivity (27). The actual term “six degrees of separation” was not coined until John Guare‘s 1991 stage play of the same title (29).

Chapter four opens by introducing us to Mark Granovetter and his paper The Strength of Weak Ties (PDF), which Barabasi writes is one of the most influential, and most cited, sociology papers ever written (42). In the paper, Granovetter proposed that when it comes to finding a job, getting news, launching a restaurant, or spreading the latest fad, our weak social ties are more important that our strong friendships (42).

The thinking behind this is that the people we are already close to are of limited help to our job search because they move in the same circles we do and have access to pretty much the same information that we have access to. It is by accessing our weak ties, the people with whom we are only acquainted, that we gain access to new information and/or opportunities that we didn’t have before. Our weak ties do not move in the same circles we move in, so they will have access to different information that may be of more help to us in the job search.

After learning about Granovetter’s weak ties, we are introduced to Duncan Watts. Watts was working on his PhD in applied mathematics when he was asked to investigate how crickets synchronize their chirping. While doing so, he kept coming up with more and more questions about how the cricket’s network (there are different types of networks) affected their synchronized chirping and approached his advisor Steven Strogatz for assistance (46).

The result was that Watts and Strogatz introduced a quantity called the clustering coefficient, which is obtained by dividing the number of actual links by the number of possible links. A number close to 1.0 means that all the links are close links (47). This is now known as the Watts-Strogatz model. Barabasi uses the clustering coefficient to introduce readers to the Erdos number.

Paul Erdos published over 1,500 papers with 507 coauthors. According to Barabasi, it is an “unparalleled honor” to be counted among his hundreds of coauthors, and short of that it is a great distinction to be only two links from him. Barabasi writes that to keep track of their distance from Erdos, mathematicians introduced the Erdos number. Erdos has Erdos number zero, coauthors one, those who wrote a paper with an Erdos coauthor two, and so on (47).

Barabasi writes that most mathematicians turn out to have rather small Erdos numbers, being typically two to five steps from Erdos, although his influence reaches well beyond his immediate field (48). He continues, writing that Erdos numbers demonstrate how the scientific community forms a highly interconnected network, and the smallness of most Erdos numbers indicates that “this web of science” truly is a small world and is a small-scale example of our social network (48).

Having familiarized us with how to measure clustering using the clustering coefficient, and shown how it could be adapted for real world use with the Erdos number, Barabasi next introduces us to the concept of clustering, itself. He begins by telling us that Watts and Strogatz’s most important discovery is that clustering does not stop at the boundary of social networks (50).

Due to the work of Watts and Strogatz, Barabasi writes that we now know that clustering is present on the Web; we have spotted it in the physical lines that connect computers on the Internet; economists have detected it in the network describing how companies are linked by joint ownership; ecologists see it in food webs that quantify how species feed on each other in ecosystems; and cell biologists have learned that it characterizes the fragile network of molecules packed within a cell (51).

From the ubiquity of clusters, Barabasi moves us on to the concept of connectors. He quotes Malcolm Gladwell‘s book The Tipping Point : “Sprinkled among every walk of life… are a handful of people with a truly extraordinary knack of making friends and acquaintances. They are connectors.” (55) In scientific terms, connectors are nodes with an “anomalously large” number of links (56), and according to the author, a random universe, which Erdos and Renyi believed, does not support them (62).

Barabasi then introduces us to hubs. He writes that the architecture of the World Wide Web is dominated by a few highly connected nodes, or hubs (ex: Yahoo! or Amazon.com) that are extremely visible (58). He goes on to say that the discovery that on the Web a few hubs grab most of the links initiated a frantic search for hubs in many areas, with startling results: Hollywood, the Web, and society are not unique. Hubs surface in the cell, and exist on the molecular level among many other places.

In chapter six, we are introduced to power laws. Barabasi writes that most quantities in nature follow a bell curve, but on occasion nature generates quantities that follow a power law distribution instead of a bell curve distribution (67). The distinguishing feature of a power law is not only that there are many small events but that they coexist with a few very large ones (67). We are then introduced to the concept of scale-free networks, which are networks with power law degree distributions (70).

Power law distributions predicts that each scale-free network will have several large hubs that will define the network’s topology; that is, how a network is organized and laid out (68). Barabasi writes that with the realization that most complex networks in nature have a power law degree distribution, the term “scale-free networks” was quickly adopted by most academic disciplines that dealt with complex webs (70).

Chapter seven begins with Barabasi telling us that the Erdos-Renyi and Watts-Strogatz network models assumed that there were a fixed number of nodes that remained unchanged for the life of the network, thus making that network static (83). He goes on to explain that real networks, as opposed to simulated ones, are not static and that growth should be factored into network models (83).

A growing network starts from a tiny core and nodes are added one after another. But, the links that connect to the nodes are not all equivalent to each other. Barabasi writes that there are clear winners and losers, with the oldest nodes having the advantage due to having had the most time to collect links (83).

He goes on to explain that the Webpages we prefer to link to are not ordinary nodes, but hubs – the better known they are the more links point to them, and the more links they attract the easier it is to find them on the Web, and the more familiar we are with them. Thus, Barabasi introduces the reader to the concept of preferential attachment. When deciding which Webpages to link to, chances are that we will link to the ones we know and/or the most well-connected pages (85).

Barabasi states that preferential attachment helps the more connected (popular) nodes (Webpages) get a disproportionately large number of links, attracting new links at a rate proportional to the number of its current links (88). New Webpages are at a disadvantage because they have not existed long enough to attract links pointing to them. The chapter ends by asking how he newer Webpages, which he calls “latecomers”, gain popularity in a system where the more established and popular sites flourish and continue to grow. Restated, the question is how do newer nodes become connected in a system where the winner takes all?

In chapter eight, Barabasi addresses the process that separates the winners from the losers: competition in complex systems (95). He introduces us to the fitness model – in a competitive environment each node has a certain fitness. To explain the concept of fitness he gives a practical example: fitness is your ability to make friends relative to everybody else in your neighborhood.

Fitness is a quantitative measure of a node’s ability to stay in front of the competition (95). Nodes with higher fitness are linked to more often, and independent of when a node joins the network, a fit node will soon leave behind all nodes with smaller fitness (97). Barabasi writes that all networks fall into two fitness categories: fit-get-rich or winner-takes-all.

In the fit-get-rich model, the fittest node will grow to become the biggest hub, but its lead will never be significant as it will be followed closely by a smaller node that has almost as many links. In the winner-takes-all model, the fittest node grabs all of the links, leaving little, if any, for the rest of the nodes. Barabasi writes that when the winner takes all, there is no room for a potential challenger (103).

In chapter nine, Barabasi seeks to answer the question: How long will it take a network to break into pieces once we randomly remove nodes? Restated, how many routers must be removed from the Internet to break it into isolated computers that cannot communicate with each other? (112)

Barabasi and his team of graduate students conducted computer simulations on scale-free networks and found that a significant fraction of nodes can be randomly removed from any scale-free network (i.e. World Wide Web, cells, social networking)  without breaking it apart (113). These results indicate that scale-free networks’ resilience to errors is an inherent (built-in) property of their topology. This resilience is termed topological robustness.

Next, Barabasi’s team set out to find the source of scale-free networks’ topological robustness. Further simulations and experimentation revealed that topological robustness is rooted in the “structural unevenness” of scale-free networks because failures disproportionately affect small nodes since there are so many more of them. However, despite their higher numbers, small nodes contribute little to a network’s integrity (114).

Barabasi’s team discovered that scale-free networks break down only after all nodes have been removed, which he says that for all practical purposes is never (115). In laymen’s terms, this means that for the World Wide Web to completely, randomly fail, every single Internet router in the world would have to malfunction and fail all at the same time. The odds of that happening? Never. Unless, of course, you live in the make-believe world of the NBC television show Revolution. But, I digress.

Barabasi’s team next turned to a new set of experiments. No longer selecting nodes randomly, the team set out to find out what would happen if the Internet was attacked in a systematic and coordinated way. They set up computer simulations that directly targeted not the nodes, but the hubs (116).

The simulations took out the largest hubs first, one after the other. It was soon evident that while the remaining hubs compensated for the first, and largest, hubs’ demise and kept the Internet running, they were no longer able to do so after several hubs were taken out. Barabasi’s team observed that, in their simulation, large chunks of nodes were falling off the network, becoming disconnected from the main cluster.

As the team pushed forward with the simulation, they observed the network’s “spectacular” collapse (116). The team also observed that the “critical point” (where a scale-free network started breaking), which was absent under random failures, was present during targeted attacks, and that removal of only a few hubs during attack broke the Internet into tiny, hopelessly isolated pieces.

Barabasi’s team had learned that vulnerability to attack is an inherent property of scale-free networks, and the proverbial “cost” to be paid in exchange for the resilience they displayed (117). Following one logical conclusion to the next, through their simulations and experimentation, the team had discovered scale-free network’s Achilles’ heel, thus the aptly applied title of chapter nine.

Advertisements