Okay, hello again. So now we're going to talk a little bit more about random networks and in particular we can talk about what are known as thresholds, and phase transitions. So just to get some terminology out there, and to take a look a little bit at the Erdos Renyi networks to understand them a little better. so first thing, when we talked about these properties, we were talking about monotone properties. So we're specifying that on a given set of nodes and we have a particular property and we'll say that some function of n called t, t of n is a threshold function for some property. If the probability that that property holds goes to 1 as long as the probability of links compared to this threshold is becoming quite large, heading towards infinity. So, if we're, got a probability that's much bigger than this threshold, we get the property for sure. And if we have a probability compared to the threshold which goes to 0, so the probability shrinks compared to the threshold, then the, the, property does not hold. Okay? So the idea here is[COUGH], we'll identify some level of probability that node, that links have to form with. And if you're above that, then the property holds and if you're below that, the property doesn't. So that's a threshold function and we'll say that a phase transition occurs at this threshold, meaning that if your probability is above that, you're getting the property. If not, you don't. So, the the network structure is changing, and either satisfying or not satisfying that property as you cross those thresholds. So lets have a look at some threshold functions, and we can then put a little more meat on this. So, what do these thresholds functions look like? so the first question is, you know, when do you begin to get some links. So if p is much smaller than 1 over n squared, you're not going to get any links with a high probability you won't see any links at all. If p is bigger than 1 over n squared, then the network's going to begin to have some links. So this is basically where the average degree is 1 over n. So, you, you have a fairly small average degree, but now when you aggregate across a bunch of, of nodes, somebody is, is likely to have at least one link. the second threshold then is where you, you get to 1 over n to the 3 halves and now the network begins to have a component with at least 3 links. so this begin, begin to see some, some nodes connect to each other appearing. so this is the average, average degree is 1 over the square root of n. the next point at which you get a threshold here at 1 over n. Is going to be a threshold for the network having a cycle, the network having a unique largest component where a a giant component where. A giant component means that for some fixed a less than 1, you've got at least n a nodes in that component. so just basically the point where average degree is 1 so everybody expects to have at least one neighbor or on average have one neighbor. Then if you're above this you begin to have cycles and the network starts to look connected. Below this you don't have cycles and you tend to not have a giant component. So things look like lots of small components or, or disconnected nodes. then probably one of the more interesting thresholds comes in at the point where you hit log n over n. So the average degree, now people expect to have log n neighbors. And at that point, the network starts to path connected. So now you can go from every node to every other node and you, you actually have a connected network. so let's just have a, a look at some of these pictures. Of, of networks drawn in this way. So here I started with a fairly low p And 50 nodes, we begin to see there's, there's not much. the, the nodes are fairly separate. a lot of isolates. A few links here and there. once we hit the point where we've crossed the first the threshold for the emergence of cycles and a giant component, that's 0.02 in this particular case. So we get to p equal 0.03 so now everybody has an expectation of about 1.5 friends. we're, we're, above that level, we begin to see this giant component emerging, we see some cycles emerging, right, so there's some cycles in here. We still see some small disconnected components and a bunch of isolated nodes. So we're still at a point where we're small enough that things aren't completely connected, but we start to see a giant component. As we continue to increase the p, so now we make it that you have an, on average two and a half friends. Now this, this giant component gets larger, there's actually only a few isolated nodes left we've seen more cycles. Its, its beginning to take more shape, and then once we get to p equal 0.1, so now we've got an expectation of five, five links roughly per, per node. Then we're looking at a situation where above the threshold for overall connection. Remember, it was on the order of log n. And now indeed we begin to see that we've got one large component, and every node is able to reach every other node. So what we saw here is a series of different threshold functions. And as you kept increasing p, you're getting more and more properties, in terms of these monotone properties, holding. And we're seeing more connectedness fewer isolated nodes cycles beginning to form. Eventually the whole network is connected. We don't have any small components left. And these are very sharp transitions in the sense that, you know, it, once you get a little bit above these, even for 50 nodes, the transition's work fairly sharply. And there's a lot of mathematics that's been worked out about the properties of these random graphs and understanding them. What we'll do, is, is in the next video, we'll go through understanding exactly how some of these are proven. For people who don't want to go through the mathematics of that, you can skip this one the next one. what I'll do is just go through an explicit calculation of these and sort of show you one of these theorems is proven. And in particular the sort of threshold for not having isolated nodes and, and making sure that things have, have coalesced into a network.
