Random networks technically often called Erdos-Renyi graphs. Again, the word graph is often used synonymously to the word network because in mathematic, mathematically it's a graph. So they are called Erdos-Renyi networks or Erdos-Renyi graphs. Erdos-Renyi are actually a very interesting combination of mathematicians. Renyi got famous because he made the statement that a mathematician is basically a machine that converts coffee into theorems, and Erdos was actually a much more interesting character. He basically lived on a suitcase. So he had about 500 collaborators in his life and he published 1,500 papers, and that's a lot. If you're a very accomplished scholar even nowadays, you're a senior and a very accomplished scholar, you have maybe 200 papers. These are like the many people that will get to 200 paper in an entire scientific career. He had 1,500, how he did that? He actually traveled. He really lived in a network. He was always at conferences, he was at people's houses. He expected them to host him to wash his laundry, and then also to help him to get to the next place. Then he will go to the next collaborator and usually even he would be at the front door he would just say, "My brain is open." Then he would collaborate with somebody for a few days given he's a very genius mathematician, and then move on. So Erdos himself has a very prolific network of collaborators. People often also try to understand how close they are to Erdos in their publishing. Because if I publish a paper, I can see how many degrees of separation I'm from Erdos, that's called your Erdos number. So he lived in this network and what these two coffee junkies, Erdos also drank a lot of coffee is reported where these two coffee junkies came up with this idea of these random networks, random graphs. That's what they said how you do it. You start with a specific number of nodes, n nodes, and then you form independent links, you basically randomly create these links among these nodes. You used to draw them. You can do that in two ways. One way would be with a certain probability p let's say 20 percent. Each node can grow link, or you have just a certain number of links, let's M links, and you throw these M links randomly into that, and then see what they connect with in your nodes. That gives you this benchmark, it's called G for graph, and then n, p, n is the number of nodes and p is the probability that the node can grow a link or have a link, or G(n,M), n is the number of nodes and M is the number of- is either you have a probability of creating a link or you have the number of links in them. Then you can look at some properties that these random networks actually should have. For example, you can ask in a random network, what's the average degree of this network? You can do that in two ways. You can have numerical solution, and these are two ways you can solve actually any. There are basically two ways you can solve a problem. The one is a numerical solution. That basically means you simulate and you just count. So let's do that. So if you have a random network here of G graph, n that's a three nodes, and M two links. Then we can have exactly three different graphs. So we have three nodes and two links. Every link is two degrees. So we can get- these are all the graphs we can make with this setup. If you have a bigger more nodes and more links, you can make many more combinations of graphs. But in this setup we can only make three kinds of graphs. Please convince yourself that's all the graphs you can do with three nodes and two links. So now we can ask now we have all of them in begin just now count, What's the average degree of a network with these specifications? A random network with these specifications. Well, we have four degrees. Every link has two degrees, all right, and three nodes. So the average degree is 1.333 like 1.1 third, all right, one and a third. So that's the average degree of this network. The other way I can do this also analytically, that means I just don't throw it out and I count, I really scratch my head and come up with the formula. That's what the formula looks like n-1 multiplied with p if I have the probability. So if I have my G and p network, sometimes is useful to have the M, sometimes is useful to have the p. That's how they defined it. I also get the same result, one and a third links on average, that will be the average number of degrees per nodes. Now the good thing is, the nice thing is that we get almost surely the specific properties with a specific setup of a random network. If I specify a network with so many nodes and so many links, then almost surely get a specific property. Like he have the property that on average every node has one and a third links. So I can ask question, What's the degree distribution as well of the network? If they throw it randomly in, how do these links actually distribute? The fact that they get that almost surely is the same as if you ever taken a statistics class, not necessary to follow what you say but if you have, you know about this distributions. These distributions grow with a large number. So it's because of the law of the large numbers of, for example, if I flip a coin, I get a binomial distribution, but I do that a lot it would approximate the continuous normal distribution. So the more you do it, the more certainty you have, that you get, for example, to the averages, that you get an average behavior because by the law of large numbers, basically. That's why you almost surely with enough nodes and links you get certain characteristics. I could also ask other question, for example, what's the likelihood of getting a hub with almost all links concentrated on it alone? Which could happen, by chance I'd thrown by links in and they could by chance just all connect to one node. Means a chance game, it's a random network. It might be very unlikely that all the links just fall on this one node if I do it randomly, but there's still alive probabilities, so I can calculate that. Now, or I can ask that, when are most nodes connected in one giant component? Remember what a component is?
