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.

Â