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.