Albert-László Barabási is one of the biggest names in networking theory, up there with Jon Kleinberg and Duncan Watts. Since he was the only one of those three whom I hadn’t met, I was thrilled to discover that he was giving a keynote at SIGIR 2009, entitled “From Networks to Human Behavior“.
Much the keynote was a stump speech about the failure of Erdős–Rényi networks to explain real-world network phenomena and the surprising prevalence of scale-free networks that exhibit power law degree distributions (these are heavy-tailed distributions, unfortunately known to many as “long tail”). But it was an extremely compelling stump speech, and I found myself as mesmerized as those who were hearing this material for the first time. Barabási also pulled out some examples that I’d never seen before–in particular, that of a bot passing a sort of Turing test by emulating the bursty pattern of human-generated traffic. He also tried to explain competitive market dynamics (specifically Google vs. competitors) in terms of scale-free networks–an explanation that I thought was a bit of a stretch (the model included a fitness function vague enough for me to wonder if it was falsifiable), but nonetheless interesting. All in all, it was an excellent talk, especially given that it was a physicist talking about network theory to an audience of information retrieval researchers.
But what impressed me just as much was how Barabási handled questions. First, whatever information retrieval system his brain uses has incredible recall–he seemed to have a reference at his fingertips for any topic a questioner brought up. Second, he was incredibly warm, fielding questions that must have struck him as basic without showing even a hint of condescension.
Indeed, I asked a question that had plagued me for years. As Barabási explained, scale-free networks arise from preferential attachment–basically a pattern of network growth in which the rich (nodes) get richer (i.e., more edges). As a simple example, think of citation networks, like the World Wide Web. You’re more likely to cite (link to) pages that already have a lot of links, and hence there is a positive feedback loop. Yes, we’ll get to my question in a moment. Barabási further explained how scale-free networks are at once robust and vulnerable. Their connectedness is robust in the face of random failure: since the vast majority of nodes are those with small degree, a random failure is unlikely to take out a high-degree hub. But they are vulnerable to calculated attack, since removing the few hubs can have devastating consequences–an observation not lost on guerrillas or terrorists.
Yes, my question. I asked Barabási if the ubiquity of scale-free networks suggested that they had evolved because robustness in the face of random failure was a real-world fitness (in the Darwinian sense), and whether inter-species (or intra-species) competition would lead to the disappearance of those networks because of their vulnerability to calculated attack. In other words, were scale-free networks a transitional phase in our evolution as a global ecosystem?
Barabási’s answer surprised me: apparently one of his colleagues tried for two years to produce a compelling evolutionary argument for the ubiquity of scale-free networks, and failed to do so. Indeed, the best he could suggest is that scale-free networks, despite their obvious weaknesses, represent a good-enough solution from nature. Evolution satisfices.
I was stunned–both by the answer and by Barabási’s candor. I’d briefly worked on this problem myself as an amateur a few years ago (I wanted to reuse my graph drawing code!), but I assumed that the professionals had figured it all out. It’s humbling to know that nature and its tangled web of connections still holds deep mysteries that defy the intuition of its most astute observers.
ps. You can also read Jeff Dalton’s notes on the keynote.
The Noisy Channel 