Before we turn to algorithmic small worlds, let's focus on the existence of short paths, or the existence property. So on the surface it seems pretty fascinating that you can likely reach anyone in six sets or fewer. But on second thought, you may give it a simple thought experiment and think, okay, well, if I have 20 friends. And each of them has 20 friends. Then how many people can I reach in six steps? So, what that's saying is, you're here, and you've got 20 friends. I'm not going to draw all 20, but you get the idea. So these are your 20 friends. I'll just focus on the first four of them. Now, each of them also has 20 friends, and so forth. So, we can draw that down for each of them, and in this sort of tree-like structure. And as we go all the way out and expand this network, we keep expanding it, and each one and do this whole process a total of six times. And so, this is starting from the origin, this is in one hop. This is two steps, and we'll do that all the way for six steps. So, in six steps, if you have 20 friends, and each of your friends also has 20 friends, and each of your friends also has 20 friends. It's their friends also, those 20 friends. Each of them also has 20 friends, and each of them also has 20 friends. We have six groups of 20 here. Eventually after six steps, one, two, three, four, five, six, that's going to be about 64 million people. So by this logic, I would be saying if everybody in the world has 20 friends, then that means in six steps you could reach 64 million people. So in a maximum six steps there's 64 million people you could reach. But the problem here is that the int, your intuition here, if you thought this way is actually wrong. And the reason that it's wrong is that there's a lot of overlap between friends, right? So a lot of your friends are probably also friends with each other, for instance. So this whole 20 times 20 times 20 argument doesn't propagate all the way through. We have to look at what are called triad closures of social relationships. So triad closures are really just triangles in networks. And basically, what this is saying here is that, okay, well if, if Charlie's friends with Anna. And Charlie's also friends with Ben, there's a chance that Annie and Ben are also going to be friends too. They may not be friends, but if they are then we're going to have a triangle of social relationship here. And what triad closures also imply is that there's transitivity in a graph and that's not to be confused if you ever heard of. Transitivity in voting, this is a different property. Transitivity in a graph is concerned with the existence of triangles and social networks are also triad closures. So all these things are roughly synonymous. So in other words, the catch of the 64 million argument is that you need each of your friend's friends not to overlap with your own friends. And otherwise that argument's going to fail. And of course though, many of your friends' friends are going to be your friends, too, right? And that's going to be true for everyone else as well, so the argument's going to fail. There's going to be a lot of overlap. And this is also tied in with the idea of homophily which we can introduce here. And homophily is the idea that people who are alike, tend to form relationships with one another right? So, you probably tend to be alike in some where, you have some similar interest with your friends. And therefore, by the argument, they're probably going to have similar interest as well, at least someone never going to overlap in some interest space. And so this idea from homophily that, it also means very intuitively to try enclosures. And as we will discuss later triad closures, transitivity, triangles and homophily. They can all be quantified roughly by what's called a clustering coefficient, clustering coefficient. And so we will be looking at that as well in this lecture. And so now the six degree of separation concept is truly surprising, right? So because it, that, that, that these triangles had to exist so in realistic networks we have to have these triangles. But we also have to be able to propagate ou,t and be able to reach people in as little as six steps. We have to have both these triangles and homophily existing, we also have to reach people in a few number of steps. It's truly going to be surprising. And additionally, what's even more interesting is that Milgram type experiments suggest something even stronger. Not only are there short paths, but, as we said, they can also be discovered by each individual node. Using very limited, local information about the destination and only its own local information. So very little information about the network itself and very, very, only local information about the network going on. And that's harder than packet routing, as we've said because there's no message passing going on. And people really have to rely on that help in the case of the Milgram's experiment that's going to exist in that letter. Of being able to know where the destinations going for. So the occupation of having some, some idea of where the person works. And the fact that they're probably going to know other people that they work with, or people who are in a similar work area. And also their name slash location. Some geographic proximity and you'd have to be able to basically combine each of these two things, obviously. Because Milgram experiment work's so well, you would have to be able to combine just these two things. To be able to come up with some notion of a social distance. And so is it a coincidence that this type of a social search strategy is going to be able to discover these short paths? So in the rest of this lecture we're going to walk through some models that have been constructed over the years. To be able to explain the small world phenomena. And we'll start with some of them that have been proposed to explain the existence of them. And then we'll also look at one in particular, that can help explain the algorithmic portion of it. And how these social distances can be constructed, and how people can go from social destination in six hops.