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
2.9: A Small World Model
Loading...
From the course by Stanford University
Social and Economic Networks: Models and Analysis
316 оценки
From the lesson
Background, Definitions, and Measures Continued
Homophily, Dynamics, Centrality Measures: Degree, Betweenness, Closeness, Eigenvector, and Katz-Bonacich. Erdos and Renyi Random Networks: Thresholds and Phase Transitions
Meet the Instructors
Matthew O. JacksonProfessor
Economics
Okay so now we're going to talk a little bit about random networks and, and
enriching them to start to capture some properties that we actually observe in
real networks and we'll talk about small world.
And before I get in to that, let me just sort of put in context where we are in
term of the course. Again, we're talking about network
formation now. random network models and we had a whole
series of properties that we observed in real networks that are sort of stylized
facts that, that sometimes emerge in different contexts and we might begin to
start thinking about, well what kinds of models would we need to match that and
so. simple Erdos-Renyi networks gave us some
insight in to why the average path links might be small.
But one thing that they didn't do very well was give an of of clustering, so we
saw that that social a lot of social networks that one observes actually have
clustering coefficients which look significantly different Than what would
have happened if we were just working with a Erdős–Rényi random network.
So somehow, those networks are missing features that are actually going on.
So, when we look at enriching models, what we might want to do is, is start to
generate some clustering. So how can it be that we get clustering.
which is, is non trivial and you know, that's going to be one thing we might be
interested in. the other thing we saw, we saw that the
distributions didn't necessarily match the Erdős–Rényi random graphs.
We saw these fat tails. Can we generate models that have
different tails? can we generate more flexible classes,
general classes of models to, to fit data?
So that's where we're going and in particular we're going to start by just
asking you know, something about clustering.
And then we'll move on to sort of enriching the model to become richer and
richer, and, and try to fit more things as we go along.
okay, so, err, an early paper, Watts and Strogatz paper in 99, was basically
asking the question, how do we match these two different features of networks,
small average path length together with high clustering in one model.
In the, one important observation is that the Erdos-Renyi model misses clustering
because the clustering is on the ordering of p which is going to have to go to 0
unless the average degree is becoming very, very large.
And, you know, with billions of, of people in the world is not as if we each
have billions of heighbours. we, we have a, you know, hundreds or
thousands of neighbors. So the idea is that, we, we need to have
something which captures the, the, high clustering, and yet has, a small p.
and, and so their idea was what they we're going to do is, is a, has a, a
following observation. Those started with what's known as a ring
lattice, a very particular structure of a network, and then randomly picked some
links and rewired them, okay. And the idea is you, by starting with
this lattice structure you start with a network which had very high clustering
but also has high diameter. And then you just change a few links in
it. And the idea is that as you begin to
change these links, that actually you don't need to change many links in order
to get a very low diameter. So a few randomly placed links will
actually shrink the diameter of a graph very quickly.
Any average path length as well. And if you don't rewire too many, you
sort of keep this high clustering. And so let's have a peek at that, and and
then we can talk a little bit more about some of the conclusions of it.
So here's just picture I drew of here of a set, a set of nodes.
So 25 nodes in a ring lattice. And so initially they're connected, each
node is connected to its two immediate neighbors.
So if we look here we have node one, and it's connected two and three, and also
connected to 25 and 24. Right?
So it's got these connections going here and here.
and then, each one of the nodes is, in terms of these in terms of the red, have
connections to the, the different neighbors, okay?
So we've, we've, we are connected to your 2 neighbors.
What that does is, in terms of this original lattice is give you very high
clustering. So 1 is connected to both 2 and 3, and 2
and 3 are connected to each other. 1 is connected to the 2 and 25, and 2 and
25 are connected to each other. And so forth.
So the clustering is is high when you start.
And then what you can do is is actually what I've done is this picture is rewire
the links but just to had a few random links.
Links. So let's just stick a few random links in
a network. And so what happens is initially if you
wanted to get without these initial, without these random links here, if you
wanted to get from node one to node 15 your path length would be quite far.
Right? You'd have to go sort of marching around
the circle. Your path length, especially if you
expanded this thing to be a much larger graph, your path link would be quite far.
By putting in these few connections, these extra ones, now to get from 1 to
15, you just go, you know, you've got a, a fairly short path, right?
You're connected in a, at a distance 4. to get from one to 14, you know, you're
connected at a distance three. So a few of these extra things allow you
to get so one can get to ten now through, in, in just two hops, and so forth.
So a few extra links actually dramatically shortens the average path
length. but it doesn't change the clustering too
much. Right?
And if you just, you know, deleted some links, but some of these new ones in, as
long as you're keeping it in the sort of sweet spot, what Watson Strogeth noticed
Wwas that you could just do a little bit of rewiring that shrinks the diameter
dramatically, and yet you keep reasonably high clustering.
Okay? Now of course, if you look at this
network, and you look at the, the shape of it, it's still not going to match a
lot of real-world networks. why not?
Well, because, you know, a lot of these nodes basically have degree four still,
or, or, you know, fairly regular. So it's, it's not going to fat, match the
fat tails and other kinds of things that we actually observe, but what it does do
is it begins to sort of answer some of the questions so that if that for some
reason we had high clustering on our, on, to start with in terms of some local
level And then we just add a few random links on top of that.
We can get at least two features in common, right, so it gives us some
explanation of how these things can begin to arise in common.
You don't need many random links to actually shorten average path length
dramtically. Now, you know, this model is far from one
we would want to take to data. But it begins to put some different
things together. And what we'll going to begin to do now
is start to enrich the models so that they're at the level where we can begin
to look at different things, put them in, take them to data and then ask things
about, you know, are we reproducing a lot of the features that we actually observe
in, in real world networks. So, we'll, we'll take a more detailed
look at random networks.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
