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.
Matthew O. JacksonProfessor
