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.11: Estimating SUGMs (Optional/Advanced 21:03)
Loading...
Из курса от партнера Stanford University
Social and Economic Networks: Models and Analysis
341 оценки
Из урока
Random Networks
Poisson Random Networks, Exponential Random Graph Models, Growing Random Networks, Preferential Attachment and Power Laws, Hybrid models of Network Formation.
Познакомьтесь с преподавателями
Matthew O. JacksonProfessor
Economics
[BLANK_AUDIO]
Okay, so we're back and we're going to talk now a
little bit about estimating these sub-graph generation models, or SUGMs.
And again, we're looking at sets of models now that allow us to
deal with link dependencies, and allow us
to have different types of sub-graphs formed.
And we want to capture those features and so we
want to see how it might estimate those statistically, okay.
So again, just to remind you the form of the model now.
The model
is that, that links form, triangles form.
You could allow the maybe it's links
between blue nodes, links between yellow nodes.
Links between blues and yellows, triangles involving three different kinds.
So, there could be different probabilities for each one of these things.
But, each type of different sub graph pops up with some probability.
These things might intersect and overlap.
We res, we observe a resulting network and
then we're trying to infer what these probabilities were.
So, are, are triangles really being formed independently of links and so forth.
So we are trying to estimate those probabilties.
Okay, so there is sort of two different approaches that one might use to do this.
One is sparse graphs then these incidental interactiosn are going to be
rare and direct estimation turns out to be valid and consistent.
There's also in paper with [UNKNOWN] you can
go ahead and we also provide an algorithm that
corrects for small numbers or gives estimates for non-sparse graphs.
There's algorithms that you can use to actually just go through and,
and try and estimate directly, how many links there would have been?
How many triangles there would have been?
And try and figure out how many of those
were incidentally or overlapped generated in terms of overlapping.
And then you can just do that directly.
I'm not
going to go through the algorithm for you to
the paper but lets just talk about this sparseness.
So the idea here is that incidentals
are generated by combinations of subgraphs that overlap.
Sparsity basically is a condition that I'll refer you
to the paper in terms of its full glory.
It basically says that, you know,
different types of sub-graphs are rare enough
that when it, they're not going to interact, so they can't grow too quickly.
And it
relies on conditions that, that, that just go through and
we calculate explicitly combinatorics of
different possible things generating each other.
And then bound those.
And, we end up with a fairly tight bound.
But, in terms of a, an intuitive example, if we just go with our links and triangles
then, as long as the probability of a link is, is smaller than the square
root of n, the probability of triangles is, is smaller than 3
N to the minus 3 halves basically what is that tell you, that's in the situation
where the typical node is involved in less
than root and links and root and triangles.
If you're looking at a fairly large social network that
kind of condition is fairly weak, its going to be fairly
easy to satisfy you know, the, the number of, of
friends I have on Facebook is, is actually fairly tiny.
And in that case, you know its not anywhere
near the number of nodes out there even root n.
And, and so root n can be a fairly good bound here.
So again we're, that limits the number of incidentals.
And if we went, went through for instance
on this network, and wanted to estimate things.
If we wanted to get estimates of what
those probabilities were, what we could do is to
start, let's try and estimate triangles.
Okay, well, we have, if you go through and count triangles, there
were actually nine that were originally
generated directly and then one incidental.
If we didn't see how they were generated, we would
estimate that there were actually ten generated on these 42 nodes.
And so what we're trying to figure out
what's the relative likelihood of, of triangles forming.
Well how many possible triangles are there?
Well, there's n different nodes, 42 here
42 choosing triples. So you can do 42 choose three.
If I did my calculation correctly it's 11,480.
And so what's our estimate?
Our estimate is going to be the ten that we observed out of the 11,480.
And so what we end up with is something about one
in 1000 of the triangles that could be there are there.
So that gives us an estimate on, on probabilities
of triangles. Okay?
And in fact the estimate should've been if we
were able to actually see what nature really did.
It should of been nine instead of ten, okay?
So the idea with sparcity, we're not off by far in terms of what our estimate was.
Estimation of links.
What we can do is now look at how many links there are not in triangles.
Okay, so we've got different numbers of links
that were formed not as part of triangles.
We count up those. You can go through and count those.
You're going to end up with 23, if I counted correctly.
So you end up with 23 not in triangles.
And here how many links could there have been?
Well how many pairs of
nodes are there? Theres n choose 2 861 in this case
minus 28 that appeared in the triangles and so we don't count those.
So there's 833 possible links that aren't in triangles.
We saw 23 of them, so what's the estimate there?
23 over 833, about a 3% probability on any link forming.
Okay?
So that would be
an estimate for this.
So we ended up estimating the number of triangles the
relative frequency of those things, and relative frequency of links.
And that gives us estimates for what those parameters are.
And then we can test whether they're different from zero.
Are they fall in some range.
We can test for homophily in this if we had different
colored nodes and so forth, so we can enrich that, okay?
So what's a theorem in the paper with a [INAUDIBLE] again?
So take a sequence of a sparse SUGMs.
And sparsity then has to be defined very carefully
in a way that says that that there are
certain bounds on the size the relative likelihoods of
the true parameters compared to the number of nodes.
Then the empirical frequency counts that we do by just looking at
whatever statistic here is, You're looking at, figure out how many did you
actually observe, how many could there have been, and
the theorem is that when you do this, in this
very simple way, the, that compared to the true one,
the ratio of those two things will go to one.
Okay, so we're going to get a consistent estimation
we're going to zero in on the true parameters.
And in particular you can also show that a normalized
difference of these things is going to be a zero mean,
normal random variable.
So in fact, you also know something about the errors,
there's a version of a central limit theorem that holds here.
So these things are consistent, and they
have nice, normal distributions in terms of
the differences between your actual estimator and
the true parameters, and so then we
get a, if you look at what this d matrix looks like, it gives
you the rates of convergence, and all the details are there in the paper.
But the idea here is these things'll be very easy
to estimate.
You're basically just doing binomial counts, so
you're counting how many links were there?
How many could there have been?
How many triangles are there? How many could have been?
So really simple estimation techniques.
And yet it gives us the same kinds of information that
we can then back out of an exponential random graph family.
And it gives us accurate estimation with trivially easy techniques.
Okay?
So let's try and see why we might be interested in these things.
So, What's the
need for these kinds of models?
Why don't we just do straight blocks models, why
bring triangles into the picture, why bring something else?
And what we are going to do is we are going to go
back to the Indian village data and what we can do is an
estimate a model and then use it to generate networks and then in
particular try and see how well do the models that we end up fitting.
End up recreating the networks. Okay?
So we just saw, there's easy ways to estimate these for the, for, to include
things like triangles.
Is it really necessary to include the triangles?
Suppose instead we worked with a block model.
We didn't bring this into the picture. Okay?
So what we're going to do is, we're
going to estimate the SUGM based on covariates.
Allowing for triangles.
We can also then compare that to what would
have happened if we just did a block model.
Counting for covariates. Does it do better,
you know, how well do they do at recreating the actual networks?
And does it, does, does the inclusion of
triangles really help us in some substantial way?
Okay. Okay so how are we going to do this?
We're going to do a very simple version of, of categorizing things.
We're going to have the nodes either be the same or different.
So we'll allow probabilities of links between two
of the si, similar nodes or different nodes.
And we'll say that they're, they're in the same class if they have the same caste.
And if the GPS distance between the homes,
is less than the median distance between homes, okay?
So going to a village, look at two
households, we say okay are they linked or not?
what, are they of the same caste?
Is the GPS distance greater or less than the median distance?
So when
we're looking at two households, we're say they're in similar if they have the same
caste and less than the median distance
between home, and otherwise we'll say they're different.
Okay, so if they're either of different castes or
greater distance than the median, then we'll put them.
So we're just going to make it a really simple model where we either keep
track of nodes, and we'll allow for
two probabilities, probabilities for nodes being similar and
nodes being different.
And similar here means they're very similar on
both the di, dimensions of caste and GPS location.
Okay?
So now what we can do is, we can fit a block model.
So we can say, what's, we'll allow
block model where we have two different probabilities.
Probability of a link of both of the same category
or similar to each other and probability if they are different.
And then we also fit subgraph generation model.
We're now what we're going to add in is also
triangles, and we'll allow triangles to have two different probabilities.
Probabilities of triangles for people that are all similar, and probability of
triangles if some of the people involved are different from each other.
Okay?
So we'll fit the block model, fit this sub-graph generation model.
Both of these are very easy to fit here, right?
So we can fit,
the block model's a special case of a SUGM where we just look at links.
So we can just count up lengths, count
up triangles, count up whether they're same or different.
So we're going to have four different counts and that
will gives us estimates on all these things, okay?
And the block model just looks, links,
ignoring whether they're in triangles or not.
This subgraph generation model keeps track of
triangles separately from links and estimated that way.
Okay, so that's the basic estimation technique.
So we estimate these block model. Step one.
We're going to estimate this probability of link,
probability of link if you're same or different.
Sub graph generation model we'll do the same
thing but we're going to add in triangle counts.
And then once we have these, the nice thing about these
kinds of models is then we can generate back networks very easily.
So how do we generate a network?
Well once we have this probabilities there, we can just take
this set of nodes, pick pairs, flip coins, put in links with probability same or
different depending on whether they're the same
or different, and then generate a, a network.
For the SUGM what we can do is randomly pick triangle, randomly pick
links and put them in with
these probabilities and then we generate networks.
Okay?
So we randomly generate these networks and then we try
to see whether or not these networks recreate the actual, original
observations. Okay, so here is what we get.
So here's the data.
How many triangles are there?
How many links were there that are not in triangle?
So, we'll call those unsupported links, so links that aren't part
of a triangle and then we also have, what's the average degree?
How many isolates there are?
And so forth.
So this, the red here in the first column is the actual data.
So we have
161 unsupported links, 39 triangles average degrees 2.3, 55 isolated nodes.
So then we can go through and here's the block model, the block model does very
well on fitting average degree, well it should
because what it's estimating is, is just link probabilities.
The SUGMs don't actually do quite as well on the estimates
of the average degree, because here they're also putting in triangles.
And so the number of, of links is, is slightly off.
But the number of triangles, and the number of unsupported links
actually matched much better, so in particular, it's doing better at matching
the number of triangles and unsupported
links, not surprisingly because its counting
those things directly and, and that's the way we're doing the estimation.
The sub graph generation models are not doing
us well on isolates, And so here this last
column here is you can also do a
subgraph generation model where you will allow for isolates.
And if you do that then you end up doing better on isolates.
While still doing as well on, on, on links and unsupported links.
So, okay. That, so far nothing too surprising.
What's interesting then is, lets go down here and
look at a series of other features of the
graph that we weren't trying to fit directly, okay?
So, clustering, how well do we do at clustering?
Well the data actually has about a 10% clustering rate.
The block model not surprisingly where all links to independent doesn't take that up.
And so, one explanation, people often say okay,
well you can get clustering on block models,
because if people were in the same group,
then they're more likely to have a higher density
of links. And so you're going to pick that up.
And here, you do see that people are much more likely to
form links of they're of the same caste, and close in GPS distance.
But that still doesn't come close to generating the clustering you need.
Whereas once you put in the triangles, then you come back and you hit this.
And actually if you pull out the isolates, you hit it right on the money.
So you can get the clustering much better by
allowing for links to be dependent in a triangular form.
Then you can also ask, you know, what's the fraction in the giant component?
And we see that, that you know again you do
better at fitting the fraction of nodes in a giant component.
You can, the first eigenvalue of the
adjacency matrix, that's how rapidly things expand.
again, you know, the, the sub-graph models are
going to do better than just the block model.
And in particular, once you get the isolates, you're coming pretty close.
Second eigenvalue of the stochastic, stochasticized
matrix. This is a measure of Mofily.
Actually once you throw the isolates in, into the sub-graph generation model, this
moves away a little bit, but it's still fairly good in terms of that.
Average path length.
You're going to come closer with the, the sub-graph generation model.
So these models aren't perfect, but what they are doing is it's
allowing you to get a little closer on some of the features.
And let's actually take a look at some graphs here.
So what do we have here?
This is a graph at the degree distribution.
So the truth, the actual data, is this gray line.
The sub graph generation model is this, blue line and the
block model is the red one here and what you begin to
see is even though the sub graph generation model didn't get the,
the average rate it actually masked the distribution of degrees much more
accurately than the block model did.
So it missed the, the first moment, but it was better at actually catching the whole
spread, and doing better at matching the tails
of this distribution than the block model did.
So it actually did better in some
dimensions of, of degree than the other model.
When you get to clustering, well the block model's just way off.
So here's the, you know, what's the clustering coefficient?
And what's the
CDF value of that?
So when you look across the distribution of clustering the block model basically
has you know, it, it says most, this shouldn't be clustering at all.
The actual data has quite a bit of clustering and the subgraph
generation model picks it up much better because it's allowing for these triangles.
But then you, you know, you can look at other kinds of things.
So yeah, here is another picture of the average clustering.
here, there are two different types of sub graph generation models, one with
different types of corrections done so the
algorithm is doing a finite state algorithm.
And then you can also the block models with just looking at
links only or, or allowing for different types of covariates and so forth.
And basically the block models are still going to miss the
clustering, no matter whether you
are incorporating different covariates, multiple covariates.
You know, similarly the eigenvalue,
you, you get different pictures or the block models end up not doing as well.
When you look at the second eigenvalue, actually these are incredibly
segregated villages, so the second eigenvalue, the is, is, is quite high.
And in fact, the SUGMs pick up that, that they're quite high,
the block models end up having a full spread on these things,
even though the actual data is all very close to one in terms of the level.
So here's the actual data numbers, they're all down here and
the sub-graph generation models are picking that up the block models aren't.
So what do we have, we have better fits on these
different things, you can look at the fraction of the giant component.
Neither of these do that well, but if you throw in
the isolates, then you'd actually pick up things a lot better.
Okay, so, what do we get?
Dependencies are really important to pick up in social networks.
Why, well that's the whole nature of social.
I mean, what does social mean?
It means that we're interacting in more than, than
but, well, generally more than two at a time.
And that's going to generate dependencies.
We need tractable models to capture and test these.
Exponential random graph models are a nice form.
It's a rich family that has a, a long tradition
in, history in statistics, but they're not always accurately estimable.
If we take a step back from these and
either work in a statistic space or just work
with the, generating these things directly, we get easy
and consistent estimation, these things are nice to work with.
And so there are ways of, of dealing with these things
directly, and then we can go ahead and test test things.
We'll see some tests of that in lectures
coming up in lecture 4.9 and others we'll begin to see how we
can test different theories using these kind
of models and, and do that explicitly.
Okay, so.
Statistical models gives us a, a medium to,
to go through and, and estimating these things.
Often we're going to need to put these models in context.
So, you know, where do these dependencies come from?
They, are they friends of friends?
Is there some social enforcement? So on top
of these models, we do need some
theory, some social theory or some economic theory.
To guide our thinking of, you know, we don't
want to just randomly put down different types of counts
into our exponential random graph models, we want to have
some idea of exactly what should we be testing for.
And again when we get to lecture 4.9.
Then we'll start with some particular theories.
We can go ahead and, and test those directly using these kinds of models.
Strengths of random networks, we can generate large
networks with well identified properties.
We can mimic real networks, at least in some characteristics
depending on the kinds of models we put down there.
So the beauty of these models is now
we can tie specific properties to specific processes.
So it's either sub-graph generation or could be
preferential attachment or sort of meeting friends of friends.
These different processes we looked, small worlds.
And we get some idea of why these different kinds
of things are happening in terms of the process that's there.
And some of the weaknesses of these models is we're still missing the why.
Why this particular model and not some other one?
And there we need to put in some social theory or economic theory behind that.
And it also then would allow us to, to say something about relevance.
So, you know, are, are we really worried about this?
We often we're worried about this things, you know.
Why do we worry about segregation because it might cause inequality, or might
lead to certain kinds of things So, we have
to have some idea of what to welfare is involved.
One other thing is that a lot of the kind of stylized facts we've talked about.
Small worlds, power laws, clustering and so forth.
These things are stylized facts but, often by just
saying okay, well here's another network that happens to
have this And, and the laws are, are basically
something that we've seen, in a series of different observations,
but we need something that can systematically begin
to look across and say, you know, is something
really statistically there as it there consistently do
we see it across different types of, of observations.
Well we can have some theory and, and luckily now we
have models that are beginning to address this kind of thing.
And allowing us to, to answer these kinds of questions.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
