Review: Linked, by Albert-László Barabási

[Russ Allbery]

Linked
by Albert-László Barabási

Publisher: Plume
Copyright: 2002, 2003
Printing:  May 2003
ISBN:      0-452-28439-2
Format:    Trade paperback
Pages:     241

Barabási at the time of this writing was a professor of physics at
Notre Dame University (he's now the director of Northeastern
University's Center of Complex Networks). Linked is a popularization of
his research into scale-free networks, their relationship to power-law
distributions (such as the distribution of wealth), and a proposed
model explaining why so many interconnected systems in nature and human
society appear to form scale-free networks. Based on some quick
Wikipedia research, it's worth mentioning that the ubiquity of
scale-free networks has been questioned and may not be as strong as
Barabási claims here, not that you would know about that controversy
from this book.

I've had this book sitting in my to-read pile for (checks records) ten
years, so I only vaguely remember why I bought it originally, but I
think it was recommended as a more scientific look at phenomenon
popularized by Malcolm Gladwell in The Tipping Point. It isn't that,
exactly; Barabási is much less interested in how ideas spread than he
is in network structure and its implications for robustness and
propagation through the network. (Contagion, as in virus outbreaks, is
the obvious example of the latter.)

There are basically two parts to this book: a history of Barabási's
research into scale-free networks and the development of the
Barabási-Albert model for scale-free network generation, and then
Barabási's attempt to find scale-free networks in everything under the
sun and make grandiose claims about the implications of that structure
for human understanding. One of these parts is better than the other.

The basic definition of a scale-free network is a network where the
degree of the nodes (the number of edges coming into or out of the
node) follows a power-law distribution. It's a bit hard to describe a
power-law distribution without the math, but the intuitive idea is that
the distribution will contain a few "winners" who will have orders of
magnitude more connections than the average node, to the point that
their connections may dominate the graph. This is very unlike a normal
distribution (the familiar bell-shaped curve), where most nodes will
cluster around a typical number of connections and the number of nodes
with a given count of connections will drop off rapidly in either
direction from that peak. A typical example of a power-law distribution
outside of networks is personal wealth: rather than clustering around
some typical values the way natural measurements like physical height
do, a few people (Bill Gates, Warren Buffett) have orders of magnitude
more wealth than the average person and a noticeable fraction of all
wealth in society.

I am moderately dubious of Barabási's assertion here that most prior
analysis of networks before his scale-free work focused on random
networks (ones where new nodes are connected at an existing node chosen
at random), since this is manifestly not the case in computer science
(my personal field). However, scale-free networks are a real phenomenon
that have some very interesting properties, and Barabási and Albert's
proposal of how they might form (add nodes one at a time, and prefer to
attach a new node to the existing node with the most connections) is a
simple and compelling model of how they can form. Barabási also
discusses a later variation, which Wikipedia names the
Bianconi-Barabási model, which adds a fitness function for more complex
preferential attachment.

Linked covers the history of the idea from Barabási's perspective, as
well as a few of its fascinating properties. One is that scale-free
networks may not have a tipping point in the Gladwell sense. Depending
on the details, there may not be a lower limit of nodes that have to
adopt some new property for it to spread through the network. Another
is robustness: scale-free networks are startlingly robust against
removal of random nodes from the network, requiring removal of large
percentages of the nodes before the network fragments, but are quite
vulnerable to a more targeted attack that focuses on removing the hubs
(the nodes with substantially more connections than average).
Scale-free networks also naturally give rise to "six degrees of
separation" effects between any two nodes, since the concentration of
connections at hubs lead to short paths.

These parts of Linked were fairly interesting, if sometimes clunky.
Unfortunately, Barabási doesn't have enough material to talk about
mathematical properties and concrete implications at book length, and
instead wanders off into an exercise in finding scale-free networks
everywhere (cell metabolism, social networks, epidemics, terrorism),
and leaping from that assertion (which Wikipedia, at least, labels as
not necessarily backed up by later analysis) to some rather overblown
claims. I think my favorite was the confident assertion that by 2020 we
will be receiving custom-tailored medicine designed specifically for
the biological networks of our unique cells, which, one, clearly isn't
going to happen, and two, has a strained and dubious connection to
scale-free network theory to say the least. There's more in that vein.
(That said, the unexpected mathematical connection between the state
transition of a Bose-Einstein condensate and scale-free network
collapse given sufficiently strong attachment preference and permission
to move connections was at least entertaining.)

The general introduction to scale-free networks was interesting and
worth reading, but I think the core ideas of this book could have been
compressed into a more concise article (and probably have, somewhere on
the Internet). The rest of it was mostly boring, punctuated by the
occasional eye-roll. I appreciate Barabási's enthusiasm for his topic —
it reminds me of professors I worked with at Stanford and their
enthusiasm for their pet theoretical concept — but this may be one
reason to have the popularization written by someone else. Not really
recommended as a book, but if you really want a (somewhat dated)
introduction to scale-free networks, you could do worse.

Rating: 6 out of 10

Reviewed: 2018-12-02

-- 
Russ Allbery (eagle at eyrie.org)              <http://www.eyrie.org/~eagle/>