2.7: Random Networks - Thresholds and Phase Transitions

Loading...

From the course by Stanford University

Social and Economic Networks: Models and Analysis

386 ratings

Stanford University

Social and Economic Networks: Models and Analysis

386 ratings

Learn how to model social and economic networks and their impact on human behavior. How do networks form, why do they exhibit certain patterns, and how does their structure impact diffusion, learning, and other behaviors? We will bring together models and techniques from economics, sociology, math, physics, statistics and computer science to answer these questions. The course begins with some empirical background on social and economic networks, and an overview of concepts used to describe and measure networks. Next, we will cover a set of models of how networks form, including random network models as well as strategic formation models, and some hybrids. We will then discuss a series of models of how networks impact behavior, including contagion, diffusion, learning, and peer influences. You can find a more detailed syllabus here: http://web.stanford.edu/~jacksonm/Networks-Online-Syllabus.pdf You can find a short introductory videao here: http://web.stanford.edu/~jacksonm/Intro_Networks.mp4

From the lesson

Background, Definitions, and Measures Continued

Homophily, Dynamics, Centrality Measures: Degree, Betweenness, Closeness, Eigenvector, and Katz-Bonacich. Erdos and Renyi Random Networks: Thresholds and Phase Transitions

2.1: Homophily10:05

2.2: Dynamics and Tie Strength 6:44

2.3: Centrality Measures 14:31

2.4: Centrality – Eigenvector Measures 13:07

2.5a: Application - Centrality Measures 12:50

2.5b: Application – Diffusion Centrality 6:46

2.6: Random Networks 10:10

2.7: Random Networks - Thresholds and Phase Transitions 7:09

2.8: A Threshold Theorem (optional/advanced 13:00)13:00

2.9: A Small World Model 7:26

2.10 Week 2 Wrap3:33

Meet the Instructors

Matthew O. Jackson
Professor
Economics

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.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play