is a mathematical construct consisting of a number of nodes
, any of which may be connected to any other. The standard type of network which people have studied is one in which the connections between the nodes are made at random
. If you plot the distribution
of the number of connections a node has for such a network, what you see tends to a normal distribution
). Such networks have often been used to model real-life situations, such as ecosystems and epidemics.
However, it has recently become clear, thanks largely to the work of one Albert-Laszlo Barabasi, that another type of network is more prevelant in nature. The scale-free
network is one in which, when you plot the distribution
of number of connections, you get an exponential distribution
. A famous property of this distribution means that if you imagine 'zoom
ing' in and out of the network, that is looking at nodes with more or fewer connections, it will always 'look the same' - much like a fractal
has a similar structure at any level.
So what we have is loads of nodes with only a few connections, but also a few with masses of them. The latter we call hub
s, though any cut-off mark is purely arbitrary. Now, this kind of network has been found in many different fields of study. Originally, the idea came out of study of the web. Here, the hubs are the big portal site
s like Yahoo
and so on, which have connections all over the place. The internet
itself - that is, the network of computers that make it up - also form a scale-free network.
In general, a scale-free network grows when two conditions are met - firstly that new nodes are coming into the network all the time, and new conncections are being added; and secondly that there is some sort of preference
mechanism - so some nodes are more attractive than others, and new nodes try to connect to them preferentially.
A scale-free network has a number of interesting properties. Firstly, it acts as a "small world
" network - that is, if you pick any two nodes then the chances are you will only have to travel through a small number of other nodes relative to the size of the network to get between them. So, on average you can get from any website to any other in only 19 links - and even if the the web expanded to 10 times its current size it would only take 21. It has been claimed that human connections also form a small-world network, with only the famed six degrees of separation
between any two people, though recently the evidence behind this has come under fire.
Another important property of a scale-free network is the way it reacts to damage - that is, when some nodes are taken out of operation. Unlike the random networks discussed above, if nodes are taken out at random a scale-free network feels little effect - that is, the average distance between nodes doesn't increase much. However, if a directed
attack takes out the hubs preferentially then the scale-free network suffers much more. I'll illustrate this with a couple of examples. First, let's take E2. This can easily be seen as a network, with nodes as node
) and softlinks
as connections. Now I don't know for sure, but my guess would be that it is at least approximately a scale-free network. We have new nodes and links coming in all the time, and we have central hub nodes for various concepts and peripheral ones which link to them. Try picking a couple of random nodes and see how many links it takes to get between them. But anyway, the point is that if some great illustrious God
, with lots of important, famous, central nodes one day decided in a huff to delete all their nodes, then the network would lose its cohesivit - but if the database glitched and lost a few random nodes probably no-one would notice.
A second example - and (perhaps) a rather more important one - comes from epidemiology
. Consider a population
, with nodes for its members and links for people people meet (or, if we're talking an STD
, have sex
with). Now the rate at which an infection will spread is closely related to the distance between nodes in the network. So the basic tactic to control its spread is to immunise
members of the population in the hope of increasing that distance. Now, epidemiological theory always used to assume that these networks were random ones, and so random immunisation is fine. But we've got the classic conditions for a scale-free network - new people being born, and differences in popularity/promiscuity. If we do have a scale-free network, and new evidence suggests we could well at least in the case of HIV
, then traditional immunisation just won't work. You need to immunise the hubs to control the disease, and if you don't the infection can still spread however many you randomly immunise.
Sources - New Scientist, Psychology Today