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
6.3: Convergence in DeGroot Model
Loading...
From the course by Stanford University
Social and Economic Networks: Models and Analysis
315 ratings
From the lesson
Learning on Networks
Bayesian Learning on Networks, The DeGroot Model of Learning on a Network, Convergence of Beliefs, The Wisdom of Crowds, How Influence depends on Network Position..
Meet the Instructors
Matthew O. JacksonProfessor
Economics
Okay, hi folks. So, we're talking about learning still,
and we're going to talk more about the DeGroot model now, and try and understand
some of its convergence properties. And one, one thing just to start with,
let me, sort of give you reiterate a little bit on the structure of the model
here. So, we have a bi of t looking like the
sum over js of Tij bj at t minus 1. So how much the person i puts on
different people's weight of beliefs in the previous period.
So it's a very simple model. The nice thing about this is that if we
want to think about the belief structure. If we're talking about what the beliefs
b1, so we represent this as a vector of b2's belief at t and so forth down to bn
of t. This is just equal to this T matrix times
the vector b1 at t minus 1 and so forth, bn, t minus 1.
Right. So, when we're thinking about what this
looks like, we can think of this as represent, as b at time t, as a vector,
as just equal to t times b at time t minus 1.
Okay. So this fact that this thing looks like a
very simple vector means that it's very easy to work with in terms of updating
and some of the mathematics behind it. And in particular this means that we can
represent the belief at some time t, b of t is just going to be equal to T raised
to the tth power, times b at 0. Right?
because b1 is equal to t times this, right?
So to get b1 you do this, to get t2 you do the belief.
Right? So, we're just raising this to t powers.
And, the reason that this model's going to be so nice to work with is that
we know a lot about matrices raised to powers, and in particular matrices where
the rows all sum to one and are non-negative.
Those are nicely behaved matrices and there's a lot of study that's been
developed in, in different areas of mathematics, in particular in the study
of Markov chains which have these kinds of properties in understanding these kind
of, of mathematics. So the beliefs take a very simple form,
and what we can do now is begin to ask questions about, when is there
convergence, when is there a consensus, who has influence, and when is there
convergence, when is there consensus. That's just going to depend on properties
of this matrix and who has influence will also depend on what this matrix ends up
looking like when we raise this to multiple, to higher and higher powers,
what does it end up looking like? Who ends up with a lot of weight in that
system? Okay?
So, understanding this is really going to depend on those, these kinds of
properties. Okay, so let's talk a little bit about
convergence. So let's start with an example a very
simple example person 3 here just listens to person 2, 2 just listens to 1, and 1
puts equal weight on 2 and 3. Okay, so this is a world where nobody
pays attention to themselves, they're all listening to somebody else and who
they're listening to depends on who they are.
this is a world that will converge. And let's start with say, example, you
know, belief 1 for person 1 0 for person 2 and 3.
And so that's this initial belief. And what's going to happen, well so
person 1 starts with the belief of 1. person 2 is going to take over belief,
right, they're going to update. So after that we can go through, what's
the next belief going to be while person 2 is now putting weight 1 on 1.
They're going to get this. Person 1's averaging 2 zeros.
They're going to get a zero, person 3 is, is just paying attention to 2, so they're
going to get a zero, so the belief after one period goes to this.
You can, you know, keep looking at this and, and so forth.
this will eventually converge to two-fifths, two-fifths, two-fifths.
So if you look at what this process will converges to it's going to be two-fifths
for each agent and it, and it converges fairly nicely.
Okay. Let's look at another example.
And all I'm going to do now is switch. So, before, 3 was listening to 2.
And we're going to move that and have instead 3 listen to 1.
Okay? So, this was a 1 before.
And we're going to move the weight. Instead of 3 listening to 3, 3's now
going to listen to 1. Okay?
And let's look at what happens in this particular setting.
So now we're in a setting, and let's start with the same beliefs we did
before. So all we did was change 3's belief from
listening to 2 to listening to 1. And what happens now?
Well, we start with these beliefs And after one period, 1 is going to now
believe 0. But both 3 and 2 are listening to 1, so
they're both going to swtich to 1. Okay?
okay, so, so now we've got a situation where both 2 and 3 believe 1 and 1
believes 0. And 1 is listening to 2 and 3, and 2 and
3 are listening to 1 so they're going to switch again, right?
And then they're going to switch again, and switch again, and so forth.
So what is happening here is that keep just exchanging beliefs.
An even easier example of something like this would just be, you know, if, if
person 1 listened to person 2 and person 2 just listened to person 1, they're just
going to keep swapping beliefs back and forth.
And that's effectively what's going on here.
So, we get blinking, we get no convergence in this, in this setting,
okay? So the beliefs just keep changing over
time, they never converge. And, obviously, this is, you know, fairly
naive in the sense that the agents don't realize they keep exchanging beliefs back
and forth. And they keep doing that infinitely
often. But this is, is a system that's not
convergent. Okay, Now what's true about this, in
order for this to happen. it's actually based on the cycles in this
graph and here all the cycles are of length two.
And we've got the beliefs in, in such a way that they keep blinking back and
forth, and so it's possible for the beliefs to keep switching back and forth
on these cycles. And so it's there's a cyclicity in the
graph which gets is possible to reproduce in the beliefs.
Okay? Now, it could be that, you know, for
other beliefs you would, might have converged.
If we started everybody with a belief of 1, they would've converged to a belief of
1. So it depends on which things which we
choose but whenever there are even cycles, all the cycles are even in, in a
given graph, then we could find situations where we're going to get
non-convergence. So more generally let's actually look at
the conditions which are going to define convergence.
So let's say that we'll, we'll starting with some particular network of weights
that people put on different individuals. We'll say that that society converges.
T converges, if the limit of this process raised to the t.
So the limiting belief exists for all initial beliefs.
In, in so, so no matter what initial beliefs we started with, we would end up
with convergence of this overall belief. Okay?
So, that'll be a definition. And in terms of characterizing this we'll
say that T is aperiodic if the greatest common divisor of all its simple cycles
is 1, okay? So, for instance, of these two things we
looked at before here we could find a cycle, so let's look at this, we have a
cycle of length three. So we have one cycle of length three, we
have a cycle of length two. The greatest common deduct, divisor of
three and two they don't divide into each other, the only thing that divides both
of those is one. Greatest common divisor is one.
This thing is aperiodic. Right.
So this one is aperiodic. What do those cycles look like over here?
Well, there's a cycle of length two. Here's a cycle of length two.
Here's a cycle of length four. All the cycles are even.
All cycles are 2, 4, 6, 8, etc. Greatest common divisor, 2.
So, this one is periodic. It's not aperiodic, not aperiodic.
Okay? So when we, when we're looking at, at the
structure of these matrices, what turns out to be true is that this aperiodicity
is going to be what defines whether or not you get convergence of this process.
So in particular, there's a theorem, which you can get out of a variety of
sources. But basically can be derived from work in
Markov chain theory and, and more generally in linear algebra.
Suppose that we have Tb strongly connected.
And let me say a little about what strongly connected means.
Strongly connected is going to say that from every given individual, there exists
a path, a, a directed path from i to j. So there exists a directed path from i to
j for all i, j. Okay.
So basically, we're not in a situation where some people could never end up
getting information from other individuals, everybody could eventually
hear from everybody else. Okay?
If you, if you have non-strong connection, the con, the characterization
here gets a little more complicated. if you're interested in that, I have a
paper with Ben Golub in 2010 which gives the complete characterization of
convergence for non-strongly connected networks.
We'll just deal with the strongly-connected ones, and that's most
of the intuition. Okay.
So what's the theorem say? The theorem says that you get convergence
if and only if you get aperiodicity. So that aperiodic aperiodicity is
necessary and sufficient for convergence. and separate parts, so first part is
aperiodicity is going to give you convergence.
And in the second part of, that we learn is if things are convergent, then we're
also going to have that the limit of this matrix actually looks like every row is
going to converge to having, so if we look at, at what T raised and, and a
limit raised to the infinite power looks like.
What it looks like is a vector. A set of each row has entries S1 to Sn,
the same S1 to Sn. So, everybody ends up putting this in the
limit the same weights on other people's initial beliefs indirectly.
Where s is the unique left hand side eigenvector that has eigen value 1.
Okay, so that's a mouthful, but it says that in fact, what this is, is the same
eigenvector that we were talking about when we talked about eigenvectors
centrality. So this an eigenvector that has
eigenvalue 1. in this case it's going to be the unique
one if we've got strongly connected and aperiodicity.
this thing's going to be convergent and it's going to have nicely-defined weights
here S1 through Sn, and in fact, they will all be non-negative, they'll all be
positive, in fact. So, so these is a very powerful set of
results here. It tells us, aperiodicity, gives us
convergence, moreover, convergence occurs to a very specific limit and that limit's
given by the left hand side unit eigenvector of the matrix.
And that's where those 2 sevenths and 2 sevenths, 2 sevenths came from and the
other numbers that we found in those examples before.
Okay. So, what we're going to look at next is
I'll go through how you prove this. it involves a bit linear algebra and some
theorems from that, so if you're you can skip that if you like.
If you want to see the details I'll explain how you can derive that kind of
theorem. And then afterwards we'll begin to put
this in process. So what we've got is convergence from
aperiodicity plus we know what the limit looks like so we'll then talk a little
more in detail about what this S vector actually means; what it comes from.
And look at some examples and, and try and understand how we might use this,
this model a bit.
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.
