QuickStudy: Scale-Free Networks

Put simply, the nodes of a scale-free network aren't randomly or evenly connected. Scale-free networks include many "very connected" nodes, hubs of connectivity that shape the way the network operates. The ratio of very connected nodes to the number of nodes in the rest of the network remains constant as the network changes in size.

In contrast, random connectivity distributions—the kinds of models used to study networks like the Internet before Barabasi and his team made their observation—predicted that there would be no well-connected nodes, or that there would be so few that they would be statistically insignificant. Although not all nodes in that kind of network would be connected to the same degree, most would have a number of connections hovering around a small, average value. Also, as a randomly distributed network grows, the relative number of very connected nodes decreases.

Significant Differences

The ramifications of this difference between the two types of networks are significant, but it's worth pointing out that both scale-free and randomly distributed networks can be what are called "small world" networks. That means it doesn't take many hops to get from one node to another—the science behind the notion that there are only six degrees of separation between any two people in the world. So, in both scale-free and randomly distributed networks, with or without very connected nodes, it may not take many hops for a node to make a connection with another node. There's a good chance, though, that in a scale-free network, many transactions would be funneled through one of the well-connected hub nodes - one like Yahoo Inc.'s Web portal.

Because of these differences, the two types of networks behave differently as they break down. The connectedness of a randomly distributed network decays steadily as nodes fail, slowly breaking into smaller, separate domains that are unable to communicate.

Resists Random Failure

Scale-free networks, on the other hand, may show almost no degradation as random nodes fail. With their very connected nodes, which are statistically unlikely to fail under random conditions, connectivity in the network is maintained. It takes quite a lot of random failure before the hubs are wiped out, and only then does the network stop working. (Of course, there's always the possibility that the very connected nodes would be the first to go.)

In a targeted attack, in which failures aren't random but are the result of mischief, or worse, directed at hubs, the scale-free network fails catastrophically. Take out the very connected nodes, and the whole network stops functioning. In these days of concern about cyberattacks on the critical infrastructure, whether the nodes on the network in question are randomly distributed or are scale-free makes a big difference.

Epidemiologists are also pondering the significance of scale-free connectivity.

Until now, it has been accepted that stopping sexually transmitted diseases requires reaching or immunizing a large proportion of the population; most contacts will be safe, and the disease will no longer spread. But if societies of people include the very connected individuals of scale-free networks—individuals who have sex lives that are quantitatively different from those of their peers—then health offensives will fail unless they target these individuals. These individuals will propagate the disease no matter how many of their more subdued neighbors are immunized.

Now consider the following: Geographic connectivity of Internet nodes is scale-free, the number of links on Web pages is scale-free, Web users belong to interest groups that are connected in a scale-free way, and e-mails propagate in a scale-free way. Barabasi's model of the Internet tells us that stopping a computer virus from spreading requires that we focus on protecting the hubs.