SCALE-FREE NETWORKS

Scale-free networks are everywhere. The can be seen in airline traffic routes, connections between actors in Hollywood, weblog links, sexual relationships, and terrorist networks. So what exactly is a scale-free network? A scale-free network is one that obeys a power law distribution in the number of connections between nodes on the network. Some few nodes exhibit extremely high connectivity (essentially scale-free) while the vast majority are relatively poorly connected. The reason that scale-free networks emerge, as opposed to evenly distributed random networks, is due to these factors:

• Rapid growth confers preference to early entrants. The longer a node has been in place the greater the number of links to it. First mover advantage is very important.
  
• In an environment of too much information people link to nodes that are easier to find. This preferential linking reinforces itself by making the easier to find nodes even more easy to find.
  
• The greater the capacity of the hub (bandwidth, work ethic, etc.) the faster its growth.

The Strength and Weaknesses of Scale-Free Networks
The proliferation of scale-free networks and our increasing dependence on them (particularly given their prevalence in energy, transportation, and communications systems) begs the question: how reliable are these networks? Here's some insight into this:

• Scale-free networks are extremely tolerant of random failures. In a random network, a small number of random failures can collapse the network. A scale-free network can absorb random failures up to 80% of its nodes before it collapses. The reason for this is the inhomogeneity of the nodes on the network -- failures are much more likely to occur on relatively small nodes.
  
• Scale-free networks are extremely vulnerable to intentional attacks on their hubs. Attacks that simultaneously eliminate as few as 5-15% of a scale-free network's hubs can collapse the network. Simultaneity of an attack on hubs is important. Scale-free networks can heal themselves rapidly if an insufficient number of hubs necessary for a systemic collapse are removed.
  
• Scale-free networks are extremely vulnerable to epidemics. In random networks, epidemics need to surpass a critical threshold (a number of nodes infected) before it propogates system-wide. Below the threshold, the epidemic dies out. Above the threshold, the epidemic spreads exponentially. Recent evidence indicates that the threshold for epidemics on scale-free networks is zero.

What this means for Counter-terrorists
Given the vulnerability of scale-free networks to intentional disruption, what does this mean for counter-terrorist planners (which I hope, but doubt, they are thinking about)? This theory has strong implications for defense as well as offense given that terrorist networks are likely highly heterogeneous. Here's what it means:

• Eliminating terrorist network hubs will likely not be effective. Non-state terrorist networks exhibit small world properties (see "TERRORIST CELLS" for more). This means that while large hubs still dominate the network, the presence of tight clusters (cells), continues to provide local connectivity when the hubs are removed. This implies that the attack on al Qaeda's Afghanistan training camps (the location of multiple hubs) did not collapse its network in any meaningful way. Rather, it atomized the network into anonymous clusters of connectivity until the hubs could reassert their priority again. Additionally, many of these clusters, even without the global connectivity provided by the hubs, will still be able to conduct attacks if they are of sufficient size and complexity (a variety of skill sets). A better approach may be to observe the hubs covertly to assertain the location of local clusters that need to be shut down.
  
• Critical terrorist social network hubs cannot be identified based on the number of links alone. Hubs vary in value depending on multiple vectors such as depth of connections (strong face-to-face social history is extremely important for trust development in covert networks -- see MAPPING TERRORIST NETWORKS for more), frequency of contact (which may indicate the individual is a conduit for information flow rather than an resource), and duration of links (which is tied to the importance of that individuals skill set to ongoing operations of cells they connect to). Analysis of the network along each of vectors can make for better decision making.
  
• Defense against attacks on hubs can be achieved in ways other than physical defense. These methods include: increasing the capacity of all hubs to absorb the taffic of failed hubs (a kind of surge protection), limiting or decreasing the maximum number of connections to any one hub (reduction in criticality), and increasing the cross connectivity of the network (local pooling of resources).

Comments

[John]

Linked is an excellent book by Albert-Laszlo Barabasi.

[Beau]

I liked this comment about improving the stability of the scale-free networks;

"increasing the cross connectivity of the network (local pooling of resources)."

and it strikes me as very 'computer-networky'. Your tactics for defending hubs within a network like this read very much like what a Systems Admin would be trying to do to ensure adequate redundancy in a network to maintain as close to 100% uptime as possible.

You might find it useful to talk to someone who designs networks as a web host or some other similar, large-scale network to hear about their process, strategies etc?

Beau

[John Robb]

That's a good idea for a post. I know just the guy to talk to about this. Also, I included a link to "Linked" on the front page of the site.

[Shishir Nagaraja]

n continuation of what the above article says about random and
targeted attacks on scale free networks, we have from Barabasi's work
that, random networks withstand a targeted attack best, while a scale
free network does pretty badly.

Given that many networks are scale free by nature, how do you secure them?

My research currently deals with these questions, and I have been able
to come up with a number of defence strategies by a scale-free network
to fight off an attack. An obvious idea in continuation to Barabasi's
paper is to design a dynamically adaptive network whose state
oscillates between pure random and scale-freeness depending upon the
scale (global or localised attack) and intensity of an attack.

My proposed strategies are based on clever edge relinking between
nodes to offer better resistance to attacks. I have found that
relinking has interesting properties, in that there is a threshold
point at which benefit is maximal, and tthe benefit curve levels off
in response to increased relinking beyond threshold. Of course the
specific characteristics of each defence strategy differs.

These techniques are also useful to apply when you think of p2p
networks, where nodes need to fend off attackers who might destroy it
by contaminating it with unk mp3s, infiltrating with different user
id's all of the same person etc.

If you are interested in knowing more about my work please do get in
touch with me.

Shishir Nagaraj
PhD Student
Computer Laboratory
University of Cambridge, UK

[Horacio Castellini]

Muy interesante.... Saludos desde Argentina...

[Mark Round]

FYI, there's been an interesting piece of conflict modelling reported from Oxford Uni, offering an explanation of the pressures that cause insurgencies to follow a universal power-law distribution [Neil Johnson et al. 2006, “Universal Patterns Underlying Ongoing Wars and Terrorism", http://xxx.lanl.gov/abs/physics/0605035]

[docsharp01]

Excellent article and comments.
http://www.1-satellite-tv-facts.com