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.
