0:00

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.

Â 4:14

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.

Â 5:48

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.

Â