3.9: SERGMs

Loading...

From the course by Stanford University

Social and Economic Networks: Models and Analysis

315 ratings

Stanford University

Social and Economic Networks: Models and Analysis

315 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

Random Networks

Poisson Random Networks, Exponential Random Graph Models, Growing Random Networks, Preferential Attachment and Power Laws, Hybrid models of Network Formation.

3.1: Growing Random Networks17:42

3.2: Mean Field Approximations 8:12

3.3: Preferential Attachment 10:56

3.4: Hybrid Models 14:45

3.5: Fitting Hybrid Models 17:05

3.6: Block Models 9:37

3.7: ERGMs 9:05

3.8: Estimating ERGMs 15:58

3.9: SERGMs 9:43

3.10: SUGMs 6:00

3.11: Estimating SUGMs (Optional/Advanced 21:03)21:05

3.12: Week 3 Wrap3:16

Meet the Instructors

Matthew O. Jackson
Professor
Economics

So we're talking about exponential random graph models

and some of the issues in estimating those.

And so now what I want to do is, is talk

about another class of models

called Statistical Exponential Random Graph Models.

So SERGMs for short.

And so what we've been through is we had

sets of models that are, are linked based, other models

which are still link by link based which can

begin to capture different things like clustering and so forth.

We brought in attributes

in the Stochastic block models.

And then we said okay, now there's the class of models which allow us

to capture richer things where there's two

dependencies and trying to estimate those things statistically.

Exponential Random Graph Models, but as we

saw there is difficulties in estimating those.

So what I want to talk about now is a

class of new ones called Statistical Exponential Random Graph Models.

That'll allow us to keep the track of these local features

and dependencies and actually do some accurate and fast and easy estimation.

'Kay.

So, the Exponential Random Graph Models are

not accurately estimable in, in many cases.

There's basically just too many alternative networks to consider.

So what's the idea here?

What's the way out?

The way out is going to be that many networks lead to the same statistics.

So for instance in the, in the simulations we did in

the last video what we had was a series of you know,

45 links, 10 triangles and 20 isolated nodes.

And in fact, under the statistical, under an Exponential Random Graph

formulation, any network that had exactly

those characteristics would be equally likely.

They'd all lead to the same function, they'd lead to the same probability.

So what we can do is we can just say,

okay look, even though there's many different networks to search over,

In fact, what we really need to keep track of is just the number of different

types of statistics, because all the networks that

have the same statistic have the same probability.

And so we can look at those as equivalent ones.

Collapse all those equivalent networks.

And that makes the summation and the area that we have

to be searching over much smaller than what it was before.

Okay.

And, and part of this came out, you know, so, so why am I

going to talk about this, this is coming out of a paper with Arun Chandrasekhar.

And effectively, the way I got interested in this

was in projects where I had to be using Exponential

Random Graph Models, or, or something that really accounted

for dependencies, and finding that the software just didn't work.

And, and I couldn't find any models that were actually working.

And so, the idea was, okay, we need some models, so let's go develop them.

So, so here I am going to tell you about a class of

models which I have been working with, which I think solve a lot

of the problems that we have there in the literature.

When you collapse these equilvalent networks and so

lets just go through the, the idea here.

So we start with our exponential random graph model, right?

So we have got some vector of statistics.

Vector of, of coefficients on that.

We've got the summation that we're having to do.

And so what we're going to do is, let's let N of

s prime be the number of networks that would have statistics equal to s prime.

So how many different networks are there that have 20 isolates?

Okay, say 10 triangles,

and 45 links. Okay, so that's a set of statistics.

That's our S of g.

So how many different networks would have exactly

this, that will let N of s be this.

Now that's not necessarily an easy number to, to calculate.

And in some cases it can actually be a, a complicated number

to even estimate, but we'll talk about that in, in a moment.

So what we can do is, is we take this original Exponential

Random Graph Model and what we can do is, is instead of summing

over all g prime, we say that any g primes that have the same

statistics are going to lead to the same exponential here, right?

So if two, if g prime and g double prime have

the same statistics, they're going to give us the same number down here.

So instead, let's just sum across the s primes, and

then weight that by how many different

networks would have generated that same s prime.

Okay?

So we've changed this into a summation

over statistics, instead of of the raw networks.

So now, now we just have to worry

about how many, instead of how many different networks

there are in the world, we just need to think of how many, what's the range here.

Well it's the number of triangles you could possibly have with the number

of links you could possibly have which is going to be much smaller.

And the second thing we're going to do is

then, instead of thinking about the probability of a

network, we can actually think of what's the

probability that we see a certain set of statistics.

So ultimately, it's not so much that we're interested in the particular network

we saw, as much as it had 20 isolates, 10 triangles and 45 links.

So that was the really important aspect, was that it had certain attributes.

Those are the kinds

of things we're going to want to test as scientists.

You know, does the network have certain characteristics?

That was a very a very particular network realized, as opposed to some other one.

Whatever the characteristics we're really interested

in, we can put into those statistics.

And so this is what we're ultimately interested in.

What's the probability that we see a network that has certain characteristics.

Okay?

So now we're going to call this the statistical form here.

Because we've gotten rid of the networks and we are just talking about the

properties of the network.

And all estimations are now in statistics based which

can be a much smaller space than we are working

in than the original space in, in that ideas

as the idea behind the Statistical Exponential Random Graph Models.

And of course, anywhere one of these representations of

an Exponential Random Graph Model then has a corresponding

representation in this format.

And if we can estimate the parameters here, then that

tells us what the parameters would be in the original model.

So we can work in this space, if we can do the

estimation and, and track back and we get the Exponential Random Graph spot.

So the basic idea here, just to emphasize.

Instead of asking what the probability of a specific network is, we ask

what's the probability of seeing certain

density of links, clustering, average path length.

Whatever the statistics are you're interested

in, what is the probability of seeing something that has those characteristics?

Okay.

Now one other thing is, one, once we start representing

things in this form, so we got this statistical form.

Then we can begin to say, you know, why do

we have what's known as particular, what's known as reference distributions.

So here this is the number of graphs that have a certain set

of statistics but it's not obvious that we might not want something else.

And in particular,

you can put in whatever k function you know, instead

of the number of graphs that have a certain statistics.

Put in some other number.

You could weight these differently.

And that would still be a valid model of how statistics are generated.

And in particular in a few minutes, we're going to

see a model which give us, will give rise to

Ks which will look actually very different than the ones

that come out of the usual Exponential Random Graph family.

So there's a,

a natural way of thinking of other kinds of weights than the ones that are there.

Okay.

So I, I, I have just been through emphasizing idea.

So now we have got thing in statistical space that's going to

be easier to work with and working directly in a graph space.

Okay.

Now, one, one thing is you can encode whatever you want in terms of statistics.

You can also begin to, to put in preference based models.

And we'll see some of that

I guess in, in the fourth week of the course.

So we'll come back and, and you can begin to do preference-based models.

And test for whether people have certain kinds of

preferences, and biases and preferences in these models as well.

Okay.

So what's the real challenge now still in estimating these, just to reemphasize?

What was, usually faced with is one network, right?

We don't see many different networks.

Usually, we just see one realization. And now we've

got these inter-dependencies.

So we've got problems in, in working with large

numbers because we've, we have basically only got one observation.

But we do have many observations of how

many links are present, which triangles are present.

Even though these qui, aren't quite independent, we

can still ask the question, are they enough?

Is there enough information in one of these things to estimate a model?

Okay?

And, and so it's not completely obvious that

as you estimate these kinds of

models, where you've got all these, inter-dependencies,

that whatever estimates of the parameters

you're going to get are going to be accurate.

So we can do, you know, we can go ahead and do say maximum likelihood

on this kind of model, an Exponential

Random Graph Model, now within a statistical form.

And we can go through and estimate these things.

So, you know, we saw certain statistic come out.

We can say okay, what are the betas which actually maximize this function

that make it most likely that we saw these statistics rather than some other ones?

Now we can just go ahead and do maximum likelihood on this function.

And we can ask, when is it that these

betas will be accurate estimates of the true parameters.

How large does the, does our data set has to be before we're

pretty sure that were getting an accurate look at what nature was doing?

Okay.

So there is a set of theorems that we have in

a paper.

In a 2012 paper, where we actually show classes

of, of statistical Exponential Random Graph Models for which

maximum likelihood is going to converge to the true parameters

and grows and provides some easy ways of estimating those.

And instead of going into that detail, you, you,

you are free to to look at the paper.

What I'm going to do is look at a very

simple related set of models, which will generate particular

case, give us some idea of how this things

work, and they do really simple and, and fast estimation.

So that will be your next topic.

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.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play