Now, in continuing our quest for a graph Explain to us what the small world phenomenon is and explain explain to us how it comes about. We're going to consider a graph that's at start contrast to the random graph that we just looked at. And so, the regular graph, in this case, is a set of nodes that are living on a ring. All right. So, basically we typically represent a regular graph as just a, a set of nodes that are living on some ring here. So it means that they're all connected in like a circular manner. So everyone is friends with everyone next to them. And two numbers are going to determine the structure. The first one is the number of nodes that are living on the ring. Which in this case, one, two, three, four, five, six, actually has to be an even number as we'll see in a minute. So I'll just make it eight. In this case there would be eight nodes on the ring. And then the number of links that each node has, which is a parameter called links per node. Here each node has exactly two links in this case. But we can, really we can increase the number of link that each node has and the way that we do that is then by connecting a node to, more of its neighbors right? So as the number of links per nodes increases nodes are going to connect to more of their closest neighbors. So, both of these numbers have to be even numbers. All of these are even so. Here the number of links per node is two. What if we increase it to four? That means that each node has to have four neighbors. So two of the neighbors are going to be on the left side, and two of the neighbors are going to be on the right side of the node. So for this node here, that means then, we're going to take the next closest neighbor and make a direct connection that way. For this node here we're going to take the next closest neighbor. And then we repeat that for each of the nodes just like this. And this will get a little messy here now. But this is exactly how we would do that and how we create the graph searcher. And so we continue that process so forth and we're going to come up with something that looks like we'll show in a minute. And we as we've said, we're going to choose an equal number of nodes on each side and both these parameters have to be even numbers for this to work out. So, when you have two links per node, the graph is just a simple ring, right? Just a simple circular ring, that is illustrated in this case right here, where each node, as we said is going to have two neighbors, one each side. But now as we go to four links per node, we have a little more complicated of a structure so each node has four links, two on each side. And as we go to six links per node, each node is going to have six links, three on each side. So half of them are going to be on the left side, half of them are going to be on the right side. And the way that you can envision this really happening in reality is like by having, if you told the number of people basically standing in a room to arrange themselves in such a way that their closest neighbors were going to be. On the left and the right sides. So here we have six people so basically if you said. Everyone okay arrange yourselves so that your two closest neighbors are going to be right next to you. That would be how we would arrange each other, or arrange the graph in this sort of a ring structure. And then if we said arrange yourself so that the, your closest four neighbors are going to be right next to you, then they would say, this person also is friends with that person. This person's also close fiends with that person, and so forth around the ring. So, this is two links per node, this is four links per node, and these are the two parameters that are going to determine the structure of a regular graph. So how do we evaluate the clustering coefficient for a regular graph? Well, we're not going to derive the general formula for the clustering coefficient as a function of the number of links per node. But let's look at an example before I present the general formula. Let's look at an example of two different cases. The first one is when we have just two links per node. So, when we have two links per node, as we said we just have a simple ring where each, all the nodes are just living on one ring. And, there's no triangles so we have no triangles. Because, there's no set of nodes that are, there's no set of three nodes that are connected in a triangular structure we would need something like that to it, if happened. So, since there's no triangles, the number of triclosures is going to be equal to zero. That means that the, clustering coefficient, clustering coefficient, is going to be equal to zero. Very simple. Now let's look what happens when we increase, up to four links per node. So, let's just focus first on the case of one node. All right. And like in this graph right here. So we're going to focus on this one center node right here. And let's just look at the number of triangles and the number of connected triples that there are just centered at this one node. So when we look at the number of triangles, there's actually, only one triangle. Right? So, the one triangle centered at this node is just, exactly what we drew up in this case over here. Just right here. So between this blue node and this black node. So there's one triangle. Now the number of triples that we have gets a little more complicated. So as we said, for each triangle there's going to be three triples. So we already have three from that one pair. But we're also going to have three other connected triples, which are also highlighted in this diagram right here. But basically when we have the six nodes, I'm just going to draw each of the separate cases out so that it'll be easier to see. Again, we're just considering everything centered at this one node for the time being. But if you can see, as you see here, one sot of connect, one connected triple is going to be from this node to this node. There, that's one connected triple. That's one additional one. Another connected triple is going to be from, if we reach, draw this again one more time. We have two, three, four, six, here, our five nodes here and another connected triple would be, connecting this node to this node and then connecting over to that point there. That's going to be another one and then we have just one more, which I won't draw in this case, but, from this node connecting to this node and then off the top like that. So it's going to be another one, so there's going to be six total connected triples. So we have three of them coming from the triangle. We've got this outer triple here and then we have two triples involving the inner nodes and again we're only considering the case or of the triples and the triangles here that are centered at this nodes. All right. So, this, this node is the center point of this triple. This is the center point of this triple and this is also the center point of this triple. So, now the question is, do we have to look at the rest of the nodes and redo this computation? And the answer is, actually, no. Because the next property that regular graphs is that all the notes have the exact same number of links. And, the structures are all the same. So, each node is going to have the exact same number of triangles, in this case, one. And, the exact same number of triples, in this case, six, centered. So, we only need to consider one center node, because if we do everything else, it'll all just cancel out in the end since we're taking the ratio of the tri, of the triangles to triples. Because the number of nodes, the full number of nodes in this graph is going to have no effect. The only thing that's going to affect the clustering coefficient is the number of the number of links that each node has. So the clustering coefficient in this case right here, just considering this one node right here, is going to be one triangle, and we have six triples over three, which is going to be one half. And to see why that wouldn't matter. Note that if we consider all of the nodes to three, four, five, six, seven, eight here. We would just be multiplying the one by eight, and we also be multiplying the six in the denominator by eight which would be the equivalent of just one half again. So, there's no need to consider all the different nodes.
