0:00
Okay. So, let's talk a little bit about
understanding these diameters and why we see short average path links in a, in a
bit of detail. so when we looked at this last one the
theorem we just talked about in terms of the average distance being proportional
to log n over log d for a certain class of random graphs.
when we do these kinds of calculations you know, the, the ideas are fairly
simple even though that some of the, the details behind the theorems can be
complicated. And so, what, what we can start with is a
very easy calculation, let's suppose that we had something which is a very regular
tree, what might be known as a, a Cayley Tree.
So, each node be, besides the very end nodes in a tree, are going to have degree
d. So, let's start with some degree d, say,
you know, say, 4. And each node then reaches other, four
others, and then the end nodes will just have one connection.
So, the idea here would be for instance you know, we start with one node, it has
four neighbors. so, we reach, you know, say, d nodes and,
at the first step. And then, we can keep track of how far
we're reaching out, how many nodes we're going to reach out to.
And what we'll do is just keep track of, and in order to do a rough calculation
of, say, the, the path length from this node to other nodes, we'll keep track of
how long it takes to reach the furthest out node to make sure that we've reached
everybody. So, on, on step 1, we reached the other
nodes. the next step, we reach another d minus
1, right? So now, each one of these has 4
neighbors, so we get 3 more neighbors out here, and so forth.
So, we reach d on the first step, we reach another d times d minus 1 on the
second step. then d times d minus 1 squared, d times d
minus 1 cubed, and so forth. So, after l steps, after we've gone out l
steps, we've reached roughly d to the l nodes in, in total.
So, in particular, if you sort of, you know, move out l, l links from the root
in each direction, we're hitting d plus d times d minus 1, and so forth, you, you
total all this up. You can go through this looks like d
times d minus 1 to the l and minus 1 over d minus 2, you can sort of, you know, sum
up what that series is. But roughly, for a reasonably large d
this is going to begin to look like d minus 1 to the l, okay?
So, this captures sort of how much you're reaching out, and you're reaching out
exponentially. So, in order to reach, if we want to
reach n minus 1, the rest of all the nodes, how many steps do we have to go
out until we've reached that many? Well we need d minus 1 to the l to be
equal to n, right, roughly, or n minus 1. I mean, either way.
so these are approximate calculations. So, what is if we solve this for l, we
can take a log of both sides of this equation to solve it for l.
What we get is that the l that solves this equation has to be in the order of
log n log of d minus 1 which is basically, there's going to be similar to
log of d if d is reasonably large. So, we end up with l on the order of log
n over log d. Well, not by accident, this is exactly
the number we saw in that theorem about the Erdos-Renyi random graphs.
If you just put out a random graph, we're getting something like that.
So, if we had a really regular tree, we would end up having this kind of
calculation for how long it took to, to reach somebody at the center to reach the
other ones. Now, you know, there's, there's going to
be calculations, this is just one node reaching the other ones.
the overall diameter is going to be on the order of twice this, but roughly
proportional to that. and so, in terms of details you know,
what if this was not a tree but actually an Erdos-Renyi random graph?
Why is it going to come out to be similar number here?
so here, what we have is all have the same degree.
really in, in reality, they're random, right?
And so, part of the difficulty is that not everybody is going to have the same
degree. well part of the proof that the
Erdos-Renyi random graph has the same diameter as what we just went through is
going to be that the fraction of nodes that have nearly the average degree, is
going to be close to 1 in a large network.
And nearly, I mean, you know, with, with within some factor of, of the, the
degree. what's another problem, here, we're
assuming that things branch out really nicely from a given node and we keep
reaching new nodes at every point in time.
Part of the difficulty is that when you actually do this calculation explicitly,
some of the links might be by branching it back, right?
So, we start at a given node, we reach other nodes, we reach further ones, but
maybe at some point some of the links actually come back to, to, to earlier
parts of the graph. And so what, what's going to be important
is that most of the links, until you get to this sort of a last step in this
process, are still reaching new nodes that haven't been reached.
That's another part of the proof. so, when you go through and, and do these
calculations in detail then you can find that, that roughly a random graph still
has a lot of the same properties that a tree has.
And those properties mean that you keep branching out fairly well and with
roughly the average growth pattern until you get till you've reached almost all
the nodes, and so you get a calculation that looks a lot like log n over log d.
And for those who are interested, I'll have a lecture that goes through in a
little bit more detail into how those calculations work, and how you can
actually balance some of these probabilities.
for those who aren't, who don't really want to deal with the math next, we'll
take a look at some, some numbers to check whether this log n over log d looks
reasonable in terms of a calculation or not.
Matthew O. JacksonProfessor
