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?
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.