Then the plan for now is, I will give you again a brief introduction to some of the concepts that we'll see later in the next IPython Notebook. What I will teach you about is two types of network models. So we've seen like some real data, some real networks. Where you can also find are a few models which generate different types of network. There's one called the random network. There's one called the Watts-Strogatz network, and there's one called the Barabasi-Albert network. These are very simple models that will generate networks of certain structure. With those model networks, we can reason about things like what is the average path length? We can do this analytically. What is the degree distribution? We can do this analytically. If we understand something about those model networks, what we can do is look at some real data and say which type of model network does it map to? Then what we learn about the model networks we can then apply to the real network as well. So you'll come across those three types of networks a lot in the literature. If you're developing an algorithm or you developing a measure, you will usually test it on real data plus these model networks. So there's three. I don't have time to go through all of them. What we'll do in the second part in the practical side of things, we'll actually assess the robustness of these two darker networks. So random networks and scale-free networks. First, I'll go into bit more detail about the random networks and give you a very small flavor of how you do things analytically. So how are you come up with the degree distribution? So we go back to our friend Erdos, again. I do recommend you have a look at his Wikipedia page because it's quite funny. In one of his 1,500 papers, he develops with Alfred Renyi the random network model. You'll hear the type of network as being referred to as a random network model, or the ER model, or the Erdos-Renyl model. It's a very simple model. You have number of nodes and every pair of nodes in that network connects with a probability p. That's it. So if you have p equal to 0, you have a network with no links and no edges. If you have p equal to 1, it means you see every single edge in the network so it's a fully-connected network. Then anything in between, you will get a different arrangement of links. It's just defined by two things, the model. N being the number of nodes and p being the probability of making a connection. So if I make some nodes, in this case N is equal to how many did I draw? Seven. If I set p equal to be 0.5, how many links do I expect? Three or four. But if I run the model, the way it will work as it will generate three links or four links differently every time. Sometimes it might even generate five links or six links, but on average you would expect somewhere between three and four, or three and a half. [inaudible] It's a connection. Every connection is established with probability p. This has probability p of being realized. It's not that you have probability p this way, and that way, it's just that link has probability p of being realized. So what you would expect in this situation is that you'd see three links. So let's say that we do get three links. Three links per node. How many links do you expect at this node i? Of those links that I showed, how many do you expect to realize? So it's three. The total is a bit different. We'll look at that later. Let's say I get this. Can I write down an expression to define the probability of this happening in terms of p and N or just in terms of p? What's the probability that i looks like this in terms of its connections? Now you have to think back to high school mathematics and Bernoulli trials. Tossing a coin. If you have no link here, the probability of that is what? One-half. Well, we don't know what p is. p is no longer a half. In general it's 1 minus p. This is probability 1 minus p. This is probability 1 minus p. This is p, p, p, and 1 minus p. So you do 1 minus p times 1 minus p times p times p times p times 1 minus p. Or you can just make that more general. What would you say? Did I miss the 1, 2? [inaudible]. p? Yeah, but more generally, what if it was like this? He said it's p to the three times 1 minus p to the three, which you can combine as well. But what is three here? [inaudible]. What is three? The number of connections to node i, which we know is k_i. So it's going to be p to the power k. Then what will this exponent be? [inaudible]. Almost. [inaudible] N minus 1 minus k, yeah. It's all the other options minus k. Now it should start to look familiar. That's the probability of this particular arrangement. But that doesn't tell me what's the probability of getting a Degree 3. That's telling me the probability of getting these particular three edges. Then I have to think, well, I can get Degree 3 like this, but I can also get Degree 3 like this, or like this. Many ways. How many ways can I rearrange those three edges? Or in general? [inaudible] Almost, n minus 1 choose k. Does everyone remember this? It's just combinations and permutations and mathematics. I won't go through it because I think most people understand it. That now tells me what the probability of getting Degree k is. If I expand this, that's the probability. Does anyone recognize what that is? Binomial distribution. The binomial distribution. From this, we know that the random network, the degree distribution will follow a binomial distribution. We can also work out what the average degree is by just knowing what the average or what the mean is, of the binomial distribution. What will be the average degree? p is- [inaudible] Exactly. That's what you expect on average, fraction p of the N minus 1 possibility is to be realized. That's what your degrees is. You can also derive the same thing from the binomial distribution. You'll see that [inaudible]. That basically what gives you a flavor. This is the most simple kind of degree distribution you can come up with and work out analytically. But for the Watts-Strogatz, for the Barabasi-Albert model, you can do the same thing and people will have. You can also analytically come up with descriptions of the clustering coefficient of the average path length and so on. People have done that, but there's been whole research papers. Sometimes the mathematics gets a little bit trickier than this. This is some examples. This is just a simulation where the network has been generated. It's the same parameters just run three different times and you get three different networks. There's one more thing I want to introduce here which gets important later on, which is a term called the giant component. The giant component is the largest fully connected sub-graph. Well in this case, not all the nodes are connected to the main component, the giant component. Some are missing. In this case you've got N is equal to 100, so that's 100 nodes and total. Five are missing. The giant component contains 95 nodes, or the fraction of nodes in the giant component is 0.95, 95 percent This fraction of the nodes in giant component, this is important later when we're talking about robustness. Because if we start to remove nodes from the network and we pick a node very carefully, that splits the node in two. What you'll see is that fraction, which is originally 100 percent, drops to 50 percent or 60 percent because you really separate the network in two. That's one of the measures we will look at for how robust the network is. Fully connected means that you can reach any node from every other node following the links. In this case, we're ignoring direction, but there's a notion of weakly connected and strongly connected. Strongly connected means you follow the arrows, weakly connected means you ignore them. Arrows don't matter. You can work out what the fraction for all of these things is. It's 94 percent for the right one, the six's missing, 95 percent here, and 95 percent here. Now, what you might get in other types of network, is you might have two components, one contains 40 percent and one contains 60 percent. The giant component is still the largest one. It's not that they have to be individually arranged, they can still be in another network. That's what we just worked out on the board, that the degree distribution looks like this. It's a binomial. Now, are there any mathematicians here? Or any physicists? Or nobody wants to admit to it, but I guess they are. What do we know about the binomial distribution that we can do if N or N minus one is much, much, much larger than k, is there anything that we can do? Well, yeah, almost. A Poisson distribution. If N is much, much larger than k, you get to a Poisson distribution. What that allows you to do, you have a discrete form, which is a binomial distribution and you have a continuous form which is the Poisson distribution. That allows you to do more things analytically. Normally, when you're talking about real networks, the number of nodes is much, much larger than the degree. Then from this, you can work out average degree in different situations and so on. The maths throughout this is not particularly tricky. The other thing I forgot to mention yesterday, is that I'm following the Barabasi book. A lot of the slides that I take, well, they are his slides and those slides follow the book that he has free online. If you want to dig more into this, he has a derivation for this in one of the chapters. You can do a lot more with a random network, but now we can establish some things. We can work out what the average path length is, we can work out what the clustering coefficient is, and we can work out what the degree distribution is. Or we did, this is just the binomial. The clustering coefficient's very easy, that's just p. The average path length's a bit more involved. But what we can do is now say, "Okay, to these three metrics from the random network, how much do they relate to real data?" We take all the network data that we have and say, "do they match?" They don't. The only thing that really matches well is the path length. The clustering coefficient and the degree distribution don't match what you see in real data. The plots, these are the colored dots here are the real data, real networks that's been analyzed and the trend lines show what the random network is predicting. What you can also do if you do this a little bit more, you can look at different types of network. You can look at the regular network which is just a lattice. You see if that agrees with data. The Erdos-Renyi, which is the one we just looked at, does that agree with data and what parts? Remember, these are the three metrics that we learned about yesterday, the average path length, clustering coefficient, and the degree distribution. The Watts-Strogatz, which is about small-world networks. It's a slight adaptation of a lattice to allow short-circuits. It's a very, very simple model, you can read about that. That does well with path length and also the clustering, but it doesn't get this degree distribution. The degree distribution that we're talking about is this power-law that you've heard about all today and all yesterday. That's the question. The story about this goes that at some point, well, why do you think this happened when it did? I think I mentioned this yesterday. But about 15 years ago, there was an explosion in the amount of large network data that was available. Social networks, IMDb, things online, so people could actually download the data and analyze it and find out some patterns.
