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.