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
1.4: Diameter
Loading...
From the course by Stanford University
Social and Economic Networks: Models and Analysis
306 ratings
From the lesson
Introduction, Empirical Background and Definitions
Examples of Social Networks and their Impact, Definitions, Measures and Properties: Degrees, Diameters, Small Worlds, Weak and Strong Ties, Degree Distributions
Meet the Instructors
Matthew O. JacksonProfessor
Economics
Hi, it's Matt again. And now, we're going to be talking a
little bit about the diameter of a network.
So again, we're still in our basic definitions, trying to understand how we
represent networks, things we can talk about in terms of their characteristics
and diameter is a very important one. Diameter and average path length refer to
how close nodes are to each other. So, how long will it take to get from one
node to another in some sense? How fast will information spread?
How, how quickly can we get from one part of the graph to another?
These are going to be questions that are going to be answered by things like
diameter and average path length. So, when we look at the diameter, the
definition here is the largest geodesic in the network.
So, the largest shortest path. so if, if we have a network which is not
connected, often when people talk about the diameter, they'll talk about the
diameter of the largest component. It get's a little iffy spent a lot of
time's, you're going to be stuck with a few isolated nodes in a network.
And so diameter often will then just to re, refer to the component largest
component. one thing about diameter is it can be
prone to outliers. It could be that there's, that happen to
be one pair of nodes which are very far from each other, but a lot of the other
ones are, are relatively well connected to each other.
So, average path length is going to be a different measure than the diameter
inside of the maximum geodesic. It's going to be the average geodesic in
the network. And if we look at different network
structures, diameter begins to tell us things about it.
So, for instance, if we look here at the network on the left.
We've got a ring or a circle of different nodes connected to each other.
And in that situation, when we look at these nodes, we end up seeing that they
are some of them can be quite far from each other.
And the diameter in this case is on the order of half the number of nodes.
So, either n over 2 or n minus 1 over 2, depending on whether we've got even or
odd number of nodes. Whereas, if we look at a tree, the
situation on the right here in this picture, what we have is a much more
efficient way of getting from one node to another.
And so, if it, if we think about the number of levels that this tree has.
So, in this case it has three different sets of, of links.
So, one, two, three depth. so in this case, we're going to end up
or, or we're, we're going to end up covering a number of nodes where n is
equal 2 to the K plus 1 minus 1. So, you can just go through and, and keep
track of that yourself. when you look at the relationship between
how many levels you have and how many nodes you have, you end up, in this case,
having K is equal to log base 2 of n plus 1 minus 1.
So, a very simple formula. And with that in, in this case the
diameter is 6. It's twice what this K was.
So you, getting from node 25 here to node 30.
it takes a path link of 6 to go up 3, and then down 3.
So, it's twice times K is going to be the, the longest shortest path in this
network. And what this tells us is that the order
of, of the diameter is going to be roughly 2 times this log of n plus 1.
So, that's giving us sort of how quickly we reach out.
And the idea here is a tree is a much more efficient way of connecting nodes in
term of short paths than we saw in terms of this circle.
Because now we, we end up connecting nodes to each other in a manner which is,
is quite efficient in terms of the branching process.
And so, even with a small number of, of links, we're able to more efficiently
connect things. And so, instead of scaling linearly with
the number of nodes, this is going to scale with the log of the number of
nodes, which is going to tend to be a much smaller number.
Now, in, in terms of small average path lengths and diameters, one thing that's
been found quite extensively in terms of looking at social networks in the real
world is that they tend to have short average path lengths and short diameters.
And what do we mean by short? It means intuitively that we connect a
large number of nodes with a, a fairly small number of connections.
The famous most famous example of this was Stanley Milgram's experiment where he
had people sending letters from one part of the US to another.
I believe it was part of the Midwest, say, Kansas and Nebraska, and you were
trying to get a letter to somebody on the East Coast, say, in Massachusetts.
he would give them say, a person's name and the rough location of where this
person was and maybe some basic background information about the person.
So, you know, I'm supposed to get something to John Smith who lives in, in
Massachusetts and who is a lawyer in Amherst.
And I live in Lincoln, Nebraska. And the, the idea was that I could,
should send the letter to somebody I know.
And then, the instructions in the letters tell them to send it to somebody they
know and so forth, with the intent of eventually getting to, the letter to the
person that was named. And the amazing thing that Milgram found
was that out of the letters that were originally mailed from the initial points
the median number of hops that it took to get to the end point was 5.
And in fact, 25% of the letters made it. So that, that's first of all, fairly high
in terms of response rate for this kind of participation in an experiment.
And secondly, the median of five seem to be quite small given that you're starting
with somebody in, in one part of the country who had no knowledge of the other
individual, in another part of the country and it took them only five steps
to get to that individual. this kind of experiment has been
replicated in, in more, more advanced settings, we're working with e-mail and
other kinds of things. one thing that's sort of interesting
about this experiment is that when, you know, if we think about the median of 5,
we have to be a little bit careful about how we interpret that result.
Why? Well out of the 75% that didn't make it,
the longer a path is, that, that would actually take to, to go from one person
to another, if we think that there's some probability that people won't send it on,
the longer the path, the more likely it, it becomes that it won't appear as having
made it in, in the experiment. So the, the letter will never reach the
final point where Stanley Milgram could then collect it and get all the names.
So, the ones that actually reach are going to tend to be shorter than the
others. So in, in experiments that have followed
up on this, you can begin to try and estimate, you know, how many didn't make
it. And, and those are going to be biased
upwards. But it's still sort of an important
number because people are getting it in only five steps and they didn't get to
see the network. It's not as if they saw the network of
all the connections in the US and we're able to figure out what the most
efficient path was. They were just trying to send it to
somebody they thought might know somebody.
You know, if I, If this person's a lawyer then, if I know a lawyer and I know a
lawyer in Massachusetts, maybe I send it to them or if I know a lawyer in Chicago
who might have a friend in Massachusetts. So, I'm, I'm trying to navigate the
network without actually knowing the explicit structure of the network.
There's a number of other studies that have found small path links in, in
different settings. So Grossman's study of, of co-authorships
among mathematicians average path length 7.6, maximum a month, in a giant
component, 27. Newman's study of physics co-authorships,
average 5.9, max 20. Goyal of, of [UNKNOWN] Gonzales of
Economics 9.5 as an average, max 29. So here, you're seeing things again that,
you know, the averages somewhere in the order 5 to 10, max closer to 30 in this
case. there is a study by Lada Adamic and
Pitkow on the Worldwide Web. There, they found an amazing number a
mean file 3.1 on a giant component reaching 85% of about 50 million pages.
Facebook mean of about 4.74, recently found by Backstrom and a set of
co-authors. This is, is 721 million users.
So, actually, they're, when you start working with, with networks of that size,
even trying to calculate the average path length is going to be something which is
going to take some doing. You're going to have to work carefully to
find algorithms to calculate these things.
so there's some very interesting findings there and in terms of the average path
length. So, in order to say a little bit more
about diameters and understand why we see these short average path lengths.
first it's going to be useful. I have a couple more definitions in hand.
the neighborhood of a node i, in, in network g N sub i of g is going to be the
set of other nodes that i is linked to in g.
And again, our usual convention is we won't allow for i to be linked to i.
And then, the degree of a node, which is a very important concept, the degree of
node i is just simply counting up how many neighbors a given node i has in the
network g. So, degree is a basic idea, which is can
be very important in keeping track of things in, in networks.
And in understanding why we have short average path lengths, one thing that's
going to be very useful is understanding the most basic form of random graph.
Which is due to Erdos and Renyi in a set of papers in the 1950s.
Also there was independent work by [UNKNOWN] around the same time.
And the, the model is the simplest possible network you could imagine in
terms of random graph. We start with n nodes.
And each link is just formed independently with some probability p.
So, what do we do? We have a coin, say, it has a
three-quarters chance of, of coming up heads.
And for every link, we look, okay, should one be linked to two, flip a coin,
three-quarters possibility of yes, one quarter possibility of no.
If it comes up heads, we, we color the, the link, if not, we don't.
And we do that for every link we just keep repeatedly flipping the coin, okay?
And, and, the coin comes up heads with some probability p.
this is known as G n, p graph on n nodes with a probability p.
it's a very important benchmark in understanding things.
Why is it an important benchmark? Because if we see some network out there
in the real world if we know what the properties of, of a random network of n
nodes with some probability p was, then we can compare the real world network
that we see to this benchmark network and say does it look like something
systematic is going on? Does this network look systematically
different than if nature had just picked nodes I'm sorry, links at random?
Or does it look like something is systematically different?
So, that's going to be an important benchmark.
And in order to talk about properties of these kinds of networks, it's going to be
useful to talk about large networks. Why large networks?
Well, because if, if we're dealing with very small networks, every single network
has some possibility of arising if we're just flipping coins.
And so, making statements about what's going to happen on a small network is
going to be a very complicated probabilistic statement.
But when we get to large numbers, laws of large numbers are going to allow us to
say things like with a probability close to one.
Then, we should observe that the network should be connected.
something like that. So, we can talk about, you know, the
average path length ought to be 6 with a probability very close to 1, on a network
of such and such a size. So, by looking at sequences of networks
on larger and larger sets of nodes, we can begin to make statements like that.
So, in particular, lets look at Erdos and Renyi networks.
And I'm going to talk about large networks.
And in particular, we're going to look at the networks that have two different
properties. So, one is we're going to be thinking
about the degree, now as a function of n. So, we have to talk about, you know, if
it has a million nodes, what's the average degree, if it has two million
nodes and so forth. We want that to be something which is at
least as large as the log of the number of nodes.
And we'll talk about that later. But what this is going to make sure is
that there's actually paths from any two, two nodes to each other with a high
probability. So, with a high probability, you can get
from any node to any other node. Then, we can actually calculate the
diameter. Okay, so, so we'll take d of n to be at
least log n. And we'll also, we're going to make sure
that the network isn't too complete. So, d of n ought to be a small number
relative to the overall size n, so that it's not as if every node just reaches
every other node in a path of length one. We'll want to, you know, have something
interesting going on. So, it's not as if I have I'm connected
to everybody in the world. I'm connected to some fraction of people
in the world and will make sure that, that's at least log in in, in terms of
size. Okay.
So, what's a theorem? A basic theorem on basic structure is
that if we have these two conditions, and then we start looking at large enough n,
the average path length and the diameter of this random graph, these GNP graphs
are going to be approximately proportional to log of the number of
nodes over log of the degree. So, a very simple formula should give you
a very accurate approximation with a high probability to what the average path
length in diameter are in these kinds of networks.
So, these kinds of theorems have been proven for the original Erdos-Renyi
random graphs that we studied through the 50s and 60s.
paper by Moon and Moser, there's a set of, of calculations by Bollobas.
a series of papers which look at, at these kinds of calculations.
It's been looked at in, in richer and richer models.
Chung and Lu have a paper in 2001 looking at a different set of models.
I have a paper in 2008 that allows for node types and other kind of, of
complications to this model. You still get the same formula in this
kind of, of setting. So, what does this tell us?
this gives us an idea of why, why we end up with a very short average path lengths
and short diameters if we had something in a, in a random graph.
And that'll tell us something about real world networks to the extent that random
graphs are going to be part of those or embedded in those kinds of things.
So when we look at this we, you know, we can state the theorem more succinctly in
terms of mathematical notation. a fore statement of the theorem is that
under these conditions if we're looking at this GNP, then the average distance
compared to the log n over log d is converging in probability to 1.
So basically, average distance is going to be proportional to log n over
log d. The same for the diameter.
So the next thing we're going to do is just try and understand the logic behind
this. And then, I'll also have a separate
lecture, sort of a, a, a more advanced lecture that'll give part of the proof of
this for people who really want to dig into the mathematics.
but the intuition on, behind this is fairly simple.
We'll go through that intuition, and then people who want the more advance part can
actually go through pieces of the proof as well.
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.
