So we just saw the magic of small worlds with a large clustering coefficient. We have triad closures with most of our friends, so in a regular graph the people that are close, next to us. And small fraction of our friends though are going to be outside of our typical, quote en quote, social circle, our normal circle, social, social circle. So, all Milgram needed to observe six degrees of separation, was this very small fraction of long range links. So, these, this small fraction is a very important part of establishing small world, six degrees separation. So, as we said, the shortest path is an extremal quantity. And we only care that there exists a shortest path, not that their all short. And that should make sense right because you know if you were driving somewhere for instance. Why would you want to tak ea longer route, you just want to take the shortest route none of the other ones necessarily matter. Unless of course there's a detour or something but don't have to get into that here, because that's not relevant. You only really care about the shortest path. You just know that if I can get some, to someone in two hops then I'm going to say that I have a distance of two from them. But there's is actually a catch to this, right. These is an issue with the shortest path existence. We just said that, this is an extremal quantity, because we're just concerned with the fact that there exists a short path. Not that all the paths are short. But if there's only one shortest path, people need to find these shortest paths. So how is someone going to be able to tell if one is shortest or not. Sort of like if you're driving somewhere, right, and if someone tells you well there is a way to get to your destination in 15 minutes. All right, that's not really going to do much for you, because you have to be able to actually find how to get there in 15 minutes. So you can use roadsigns, and other things that you'd see along the way, but other than that, you're not really going to have much help. You're not going to be able to find these short paths. But Milgram, saw in his experiment that people with very limited, local information were able to find these short paths. And now we can illustrate that here in this Watts Strogatz type graph, right so. For A, A can get to C in just 2 hops, right? You could, A can go right to B, and then to C. But, how is A going to know to get to C that way? So why wouldn't A, for instance, go to this node, who would then in turn go to this node. Who maybe then knows that he should go this way, and then up here. But that's already now having hopped length of one, two, three, four, rather than a hop length of two. So, people need to be able to find short paths, and it's not always easy. Because we don't know the network structure, we don't know who you're friends, or friends with necessarily. So how can six steps be locally discoverable? And this is the algorithmic portion, portion of the problem. How can people find these short paths with very limited local information? And that's what we're going to focus on now for the rest of the lecture. So, if you were one of those people participating in Milgroom's experiment, how would you decide the next hop? Probably would have been some combination of geographic proximity which is relatively easy to see. Just to see how close, a person is to the destination they need to get in terms of where they live. And, also occupational proximity, which could be harder to determine cause its not clear necessarily which occupations would tend to know each other. Certain occupations that could seem completely opposite may actually work together in certain types of jobs. And, you would do this you would combine thee two to come up with some hybrid social distance metric. In order to determine how far you think a person is away from the destination then choose the best one. Or at least that's the case in Greedy social, social search. In Greedy social search what we do is you choose the best, next hop, based upon this social distance metric. So everybody does what they know based upon their own local information. You make the best possible decision. For the next step and that's why it's actually called greedy. Because you're only doing what you know, and what's best base upon your current information. Of course it may not turn out to be the optimal overall. Because who you go to next may not be necessarily what's going to get you to the destination in the quickest number of pops. Now we can illustrate that in a example here. So suppose X, this person X, is an engineer located in Princeton, New Jersey. All right, so this engineer wants to get to destination Y, which is, who is a lawyer in Pala Alto, California. So, the engineer takes a look at who he knows, and, he knows an actuary who's in Summit also in New Jersey. And he knows someone else. He also knows a politician who's in Seattle, Washington. And he says to himself, okay well politicians kind of close to a lawyer. You know, they probably run into some similar cir, circles and so forth. So, Andy is in Seattle and Seattle Washington's a lot closer to Palawatha California than New Jersey is so I'm going to forward it over to A. And once a politician gets it, he also runs the next, that same greed social search process. And chooses the next best hop based upon his local information. And says, okay, well I don't know the lawyer directly, from, to California. But I know a politician in Los Angeles, California, who is closer than I am cause he's in California and he forwards it to B. And then it turns out that politician happens to know the lawyer at the destination. So this took a total of one, two, three hops to get there. But it turns out that in reality this actuary in Summit, actually knew the lawyer directly. So, but how would the person know if this actuary in summit, New Jersey is going to know the lawyer in Palo Alto California? So if, if X knew the entire network he would have said, all right, well I need to forward it to C, and then forward it to Y. But we could see here that he couldn't choose his shortest path, the, the shortest path between him and Y. Because he doesn't have total view of the network, he only has his own local information. And, as we said, this process continues. So X does it, passes it to A, A does it, passes it to B, B, C is the destination. So this is not going to result in the optimal route because nobody has a global view of the network. But we wonder why there's, the average length discovered by such a previous search could be close to the average shortest path length. And if so, if we can come up with such a network where this type of greedy search would result in something close to the average shortest path length? Then in addition to being plausible, we could say that shortest paths are actually discoverable. So we're looking for that discoverability, Still. So we want to be able to show that this can lead to that under a certain network.
