[MUSIC] Okay, so this was about the links and how they are connected and how we can count them. What about now a more global view of the network? How can I roam around the network? Here, we also have different terms, different jargons. For example, you can walk around the network. That means you just pass along nodes through the links, kind of like, yeah, you walk over these bridges that connect the nodes and you walk around. A path is a specific kind of walk, you only pass through different nodes. You don't ever repeat any node when you walk, and that's called a path. So for example, here, we have a network, and what I've drawn here is a path and also a walk. because every path is a walk, but not the other way around. From 1 to 7, right, we go from 1 to 2, from 2 to 3, from 3 to 4, 4 to 5, 5 to 6, 6 to 7. Now this here, this walk is a walk which is not a path. I go from 1 to 2, 2 3, 3 4, 5, then I go back to 3. So I've been at 3 twice, so that wouldn't be considered a path, that's called a walk. So you know the words walk and path, but when you do a network analysis, these are technical terms that you have to learn in order to be able to talk and analyze with other people, social networks, for example. Now, there are also cycles, yeah, that's really just a cycle you go, and you come back, very intuitive. So for example, you started at 1 and you'll go back at the 1, so that's a cycle and a walk, by the way, not a path, because you go to the 1 twice, right? So 1, 2, 3 and you go around this, that's a cycle. Here, you have another cycle that you go 1, 2, 3, 4, 5, 3, 1, so that's another cycle and a walk, again, not a path. So these are terms and you can see now, we have walk, path, cycle. And then you can also see how many possible cycles are there in a network. That is very interesting because, can a rumor, for example, come back to you? So it's important to count how many possible cycles there are. And how many rumors are there that go through paths, that means they don't double-cross somebody, or how many that go through walks. So that's why it's important to define these concepts. Geodesic, very important, comes from geography, this term, and that's the shortest path between two nodes. So the shortest path, not a walk, between two nodes. This being said, which one is for our, the geodesic between nodes 2 and 6 in this network? Well, there's several ways you can go from node 2 to 6. You could go from now to 2 to 3 to 4 to 5 to 6, but that would not be the shortest. So the shortest, the quickest way you can get from 2 to 6 is in three steps. And you can do that two ways, 2, 3, 7, 6, or 2, 3, 5, 6. So the geodesic is three steps, the three degrees of separation between node 2 and node 6. So that's the shortest path, which is very important, often. So how quickly can somebody reach somebody else? How many intermediating steps are there, what's the shortest path between these two? And that has the term geodesic, that's it. The diameter is the longest shortest path, and the average path length is just the average of the geodesic. So I see, what's the quickest way of getting from everybody to everybody was the quickest way? In our example, it was three, I could go two ways, but it's still three. And then I do that for everybody and I count the average path length. And in some networks, I have a short average path length. Everybody can get to everybody quite quickly. In some, I have a very long average path length, and that obviously has, then, effects. For example, if you want to do marketing, how quickly you can reach people. Or if you want to spread a new innovation or a rumor, for example, or if a disease is spreading. Now after these definitions, try to answer that question, what's the minimum possible average path length of a network? Think about it, what's the minimum possible? What's the minimum possible average path length of a network? The minimum, the smallest possible average path length of a network is one. That's when everybody is connected to everybody. Because if you're connected to everybody, you can get to everybody in one step, and so can they. So if you have a network here of nine nodes, I need 8 connections per node, I have 72 connections. So in these nine nodes with 72 connections, with 72 degrees, I can connect to everybody. Now, that's an awful lot of connections, an awful lot of degrees, and degrees are often very costly. For example, if you want to connect to all of your friends, you don't have the time, right, that's very time-intensive. And sometimes you might lose friends, they get upset because you don't give them enough attention. You have a scarcity in attention here that you can distribute. A company might not have enough financial resources to maintain ties with everybody. An airline company, for example, cannot fly directly to each airport, right, that would be just way too costly. Even so, if you would have a direct flight from every city to every city, fantastic. Well, they're not doing that because it would just be too costly. So that leads us to the question, what's kind of like a good mix between the number of links and the shortest average path length? And I will give part of the answer already away. You can get the shortest average path length down to two. So in two steps, you can get from everybody to everybody. But you need way less links and degrees than you had before. Think about it, what is the network structure of that network? It looks like a star, but it's sometimes called a hub-and-spoke network because you have this hub in the middle, and the spokes like in a wheel. So here, actually, with our nine nodes, I only need eight links. And with these eight links, I can connect to the central node. And from the central node, I can get out to every other node. So I reduce the number of links significantly, but I still have a pretty short average path length, average path length of two. And that's actually what airline companies do, right, that's why you always end up in these cities like, I don't know, like in Dallas and so forth, because that's where you change planes. So they'll all ship you there, in the United States, usually in the middle of the country, and from there, they distribute you out. So that's a mathematical problem, how you actually do that best. But you can still have a pretty short average path length if you have this hub and spoke network structure with these central hubs. It turns out that society has a surprisingly small average path length. That means, in very few steps, we are all connected to everybody. Actually, the term is, there's six degrees of separation between you and everybody else on planet Earth. So between you and the 7 to 8 billion people that are on planet Earth, in six degrees of separation, only going through six. That means it's you, it's a friend, a friend of a friend, a friend of a friend of a friend, a friend of a friend of a friend of a friend, and then already you can get to, on average, to the most hidden, faraway person in Africa, in Asia, in Australia, in South America. That is kind of like what this idea says, the six degrees of separation, how did we come up with that? Well, there was a researcher called Milligram and he, back in the 60s, 70s, actually just sent letters. So he sent letters from from Nebraska and from Kansas, and he said he gave this letter to somebody and said, this letter should go to somebody in Boston in Massachusetts. But if you know this person already by first name basis, send this letter directly to this person, if not, send it to a person that that might know this person. So maybe you don't know the final person< but you know somebody who is maybe in the same profession, I think it was a lawyer in Boston. So you might give it to a lawyer or you might give it to somebody who has maybe relatives in Boston, that. So it turned out that in 5.5 steps, the letters actually got through the right person in Boston. So that was in the 60s and 70s, turns out on Facebook, the degrees of separation between everybody on planet Earth, so these are the 2 billion Facebook users, two out of seven people on planet Earth are on Facebook. Their degrees of separation is 4.7, so less than five degrees of separation, there are, actually. And this should not be too surprising, actually, think about it, how many friends do you have on Facebook? You don't have to answer that, you probably don't, I don't know, but there's a lot, right? So now imagine you have 100 friends on Facebook that are not overlapping with the friends of your friends. Well, many of them are overlapping, you have many friends in common. But imagine you have 100 friends on Facebook that are not overlapping with this one friend, right? So you start, you have 100 friends, and then this friend has also 100 friends that are not overlapping with you. So now you already actually went to 10,000 people, right? So if you go out, 100 friends of mine, and each one of these 100 friends has 100 friends that are not overlapping with me, then I have 100 I have, and each one of them has 100. So it's 100 times 100, we have 10,000 people already. Well, that's quite a lot, it's 10,000 people. Now imagine each one of them has 100 friends that are not overlapping with each one of them. Well, they have many more friends, but 100 that are not overlapping. We're already at 1 million, we have six zeros already, right, 100 and 100 and 100. We have six zeros already, we're already at 1 million people. Now let's do that again, multiply by 100, we're at 100 million already. And let's do it again, multiply by 100, we're at 10 billion, but how many people are there on planet Earth? 7, 7 point something, 7 to 8 billion, right? So we already have, with one, two, three, four steps, we already went beyond the people that are on planet Earth. So that's the power of networks, there's this exponential multiplier effect that you have with networks. So it's not so surprising that actually, with a small average path length, you can reach a very large group of people.
