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.
