Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees
Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

6.3: Convergence in DeGroot Model

Loading...

Social and Economic Networks: Models and Analysis

Stanford University

4.8 (430 ratings) | 32K Students Enrolled

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

Skills You'll Learn

Social Network, Game Theory, Network Analysis, Network Theory

Reviews

4.8 (430 ratings)

5 stars
360 ratings
4 stars
60 ratings
3 stars
8 ratings
1 star
2 ratings

MG

Apr 17, 2018

Great survey course for social network analysis. Dr. Jackson's lectures motivated me to buy the book, and I hope to come back to this course later to work more on the optional parts.

TC

Apr 30, 2017

An overview of concepts and models of how networks form. There are applicable with basic concepts from probability theory, statistics, and some light calculus astonishingly well.

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..

6.1: Learning26:05

6.2: DeGroot Model 15:55

6.3: Convergence in DeGroot Model 13:42

6.4: Proof of Convergence Theorem (Optional/Advanced 10:25)10:25

6.5: Influence 6:51

6.6: Examples of Influence 8:13

6.7: Information Aggregation 9:15

6.8: Learning Summary 4:54

6.9: Week 6 Wrap4:24

Taught By

Matthew O. Jackson
Professor

Transcript

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.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates