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
3.9: SERGMs
Loading...
From the course by Stanford University
Social and Economic Networks: Models and Analysis
416 ratings
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.
Meet the Instructors
Matthew O. JacksonProfessor
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.
© 2019 Coursera Inc. All rights reserved.
