Now, I'll run through very quickly some examples of networks which follow power laws and have been trying to follow power laws. Peter showed this picture, he said it was the Internet, it's not. It's the World Wide Web which is different. The Internet is the infrastructure, it's the hardware. The World Wide Web is documents with hyperlinks. Barabasi had this data. What was expected was that it was following a normal distribution. But what he found was it followed a power law. You can analyze these for in-degree and out-degree as well. This is a sample of the World Wide Web that he used for this analysis. However, the same thing does hold for the internet backbone. This is the routers and the wires and everything else that's also following power law. I mentioned this as well, so scientific co-authorship. This was Newman, again, following the power law. This is for math and neuroscience. You can look at metabolic networks for all types of species and all types of living organisms. Again, these things follow a power law. You get the picture? Protein networks, again, following a power law. Human protein-protein interaction networks, again following a power law. IMDB network, actors sharing a film together also follow a power law and then on and on. The story goes that Barabasi and Rekha are there, they were working on this data, and then eventually he was sat in a conference so the story goes. You can read it in his book. It was a conference on physics, and at the time no one was really paying any attention to networks. Then he got a fax from Rekha saying that the IMDB data is also a power law. Then another fax, saying, it's also a power law. Then he sat there thinking and he couldn't concentrate for a day. Then you'll see in the PDF he's written his notes trying to understand why these networks look like they do. It must be a very simple, very general mechanism that describes these types of networks. That's where the BA model came about. In that conference, in about a day, he developed this model. Then that model subsequently was published in Nature and led to many subsequent Nature publications related to this. It's very simple actually, the concept of how you get this scale-free. Remember, the scale-free is this power-law distribution. Which means we have many nodes with very few links and a few nodes with many, many links. When you think about the World Wide Web, that means some web pages have lots of outgoing links. There's a few many Web pages which are actually just on their own somewhere, they only have a few incoming and outgoing links. The two aspects of the model are the following. The other network models, both the Watts-Strogatz and the Random Network model, you start with a fixed end. You have a fixed network size and then you remove and add links. What this model does, is it starts to grow the network. You start from a single node and then you add nodes subsequently. Every timestep, it's a timestamped model. Every time step you add a new node, and that node connects to existing nodes in the network. At each time step, we add a new node with m links. You add m links, m is a parameter that you can vary, and those m links will connect to other nodes in the network. But it won't connect to other nodes in the network uniformly, it will prefer the ones that already have a high number of links. It's like the rich get richer idea. What you will see is the nodes that, well, what would you see? The nodes that start at the beginning, what will happen to the first node? What will it look like after 100 iterations versus the one that started at 75 iterations? You'll have more. You'll have more just because it gets a preference. Because at the beginning, this is one. You've only got one node that you can connect to, and then you'll get reinforced so the next time you'll have two. Even though these probabilities of connecting to other nodes slowly increases, you will still have a high probability all the way through so that the early nodes in the network will always end up as your hubs. It's very, very simple. The probability of connecting to node I is proportional to its degree relative to the total degree of the network. This is a simulation. This is in a piece of software called NetLogo, which is another tool that you can play around with. It has lots of nice existing models in there, all related to complexity science. You can download it. But there you start to see this, I think was our first node, and it ends up with being a hub. You can see the degree distribution slowly starts to emerge, and this is what I said. You can actually again analytically derive, given the timestamp at which the node was created, what will be the degree at timestamp n? You'll see that the degree of the node, the ones that start earlier, will always end up with higher degrees. If they're very close together, you might get a chance of changing. Like I said, people then took the Barabasi-Albert model, they compared it with data and they worked out what the path length was, what the clustering coefficient was, and we know that the degree distribution is power-law. This is the one that's matching the data the best. You can understand why now the paper appeared in nature that he found this fundamental phenomenon across all types of network, and then he gave a very simple description of how that structure emerges. Good. If I randomly remove a node from a scale-free network, what do I expect to happen? If I pick a random node, at random and I remove it, what's the likelihood of that disrupting the network? Low. Low? Why? A lot of nodes don't matter. A lot of nodes don't matter. Remember the scale-free distribution? Most nodes have only one edge. They are the periphery, completely the periphery. If I randomly select, am likely to hit one of those. If I look at the distribution, it's going to look, not on a log-log plot, but it's going to look something like this. The likelihood of hitting one of these nodes is much higher than the one of these. That's assuming that I've got a power system and one of the substations randomly fails, then having a scale-free structure will be beneficial because of the likelihood of failure. The internet and the World Wide Web, if it's susceptible to random failure, it's still going to be quite robust, and you're going to have to have a lot of random failures before the whole thing falls apart. How about now if I, instead of having a random failure, I want to attack the network? I target the nodes in some way. What happens? How would you target the network if you want to disrupt it? [inaudible]. Yes, you could pick the highest between us now, you could pick the highest closeness, you could pick the highest degree. But if you pick the highest degree, what you're doing is attacking the hubs. You're targeting specifically the nodes, this under the distribution. Every removal of a node will actually also remove a lot of links. Even after about three or four, five removals from a very large network, the whole thing will just fall apart. Now, what about if you take the same analysis and do it for a random network, what do you expect? Knowing that it's a person for large n? [inaudible]. An attack is always going to be more effective than a failure. That's what you expect, but the distribution is going to be less skewed. That means if you have a random failure, you're going to have a higher likelihood of sampling more towards the far end of the distribution. With a random failure, you do have a slightly higher chance of killing a more important node. However, with the attack, you're not going to have nodes which are hugely connected. You're not going to have these massive hubs.
