review of Ablert-László Barabási’s textbook Network Science

This was one of the textbooks for the Network Science course I just took at Georgia Tech. I mostly don’t care about the math proofs, but the high-level concepts are interesting. The idea is that when something can be modeled as a set of nodes linked by edges—examples studied in the book include the Internet, the network of citations among academic papers, the graph of who calls who on cell phones, and the map of binding interactions among proteins—we can learn many useful things about it just by studying the the structure of that graph, ignoring what the nodes and edges actually represent.

Barabási’s key claim is that in most real-world networks, the node degrees follow a power-law distribution. That is, if you count how many connections each node has (its “degree”), lower-degree nodes tend to be much more common than higher-degree nodes, but you can still expect to find some nodes with arbitrarily high degrees. This is not what you’d expect to find in a purely random network; for random networks, the degree distribution is binomial, so most nodes should have similar numbers of connections and extreme outliers are unlikely. Networks with a power-law degree distribution are also called “scale-free” networks.

The degree distribution has fascinating implications for how vulnerable a network is to attacks and random failures. How many nodes have to fail before some portion of the network becomes incapable of reaching some other portion?

• If the failures are happening randomly, they cause significantly more damage to a random (binomial degree distribution) network than to a scale-free (power-law degree distribution) network. Scale-free networks tend to contain some “hub” nodes that are extremely helpful in keeping the network connected, so unless you have the extreme bad luck of losing those hub nodes, the loss of a few random nodes doesn’t make much difference.
• But for the same reason, scale-free networks are very vulnerable to intelligent attacks, even moreso than random networks are. If an attacker knows which nodes are hubs and targets those first, the network can fall apart rapidly.

This book opens with a somewhat unusual “personal introduction” chapter that I appreciated—it describes some of the risks the author and his collaborators took, and disappointments he endured, in the long journey toward getting the academic community to see the value in studying this topic.