Hi. In this next lecture on networks, what we wanna do is we wanna talk about the logic. Through which networks form. And by that I mean we want to think of these nodes as being agents in a way. These nodes make decisions about who, what other nodes to connect to. And, as they make those decisions that's gonna result in a structure to the network. So we're also gonna see how that process works, and how we go really from the micro-level actions of the nodes, which are making these connections, to macro-level properties of the network. So the network structure's gonna be something that emerges through these micro-level interactions. We're gonna focus on three very simple ways from in networks might form. The first one's gonna be random connections, where each node and randomly decided to connect to other nodes. The second one is gonna be a small worlds model. And the is, is gonna work as follows. Each person is gonna have some friends that are, sort of, belong to a clique. They're sort of nearby. And then some friends that are random, that they randomly connect to. So we're gonna start out by having people connected to just people near them. And then assume that they sort of rewire, in a way, and randomly connect to some people who are further away in social space. ?Cause this is what a lot of social networks look like. And the last thing we're gonna do is we're gonna look at something called a preferential attachment network. And this has been used to describe the internet. And the world wide web. And the idea here is the following. It's that you're more likely to connect to nodes that are more connected. So, that's true certainly in the world wide web. [inaudible] like it links into Google. Or links into major universities because they're more connected than we are to link to less connected things. And we'll see how that micro-level rule results in properties in the network globally, structure in terms of measures that might not have been anticipated. Okay, so let's get started. Random networks, here's what you do. You assume there's N nodes and p is the probability that you can. Back to another node. So what you do is you just, you draw a bunch of nodes. Like this. And then with just some probability. You draw connections between the nodes randomly and you get some sort of random graph. Now this has been studied. They're sometimes called Aridish Rainy networks. These have been studied in great detailed and here's a really interesting result. It turns out you get a contextual tipping point. For a large [inaudible]. That means you have a lot, a large number of nodes. The network almost always becomes connected if P, the probability of being connected, is bigger than 1/N-1. So what you can get is here's our graph. Here's the probability of being connected which is one of the measures we care about. And here's 1/N-1. And what you get is you get a graph that looks like this. You get a tip. So you're less than one of N minus one for large N, odds are you're not connected. And once you get bigger than one of N minus one, odds are you are fully connected. So it's cool. A tipping point within networks. Now these random graphs, you can prove a lot of nice results about random graphs but the thing is, that's not what real social networks look like. Remember here's that middle school graph from James Moody. That doesn't look random. Here's the Adult Network graph from the Friendly Ham study, that doesn't look really random either and here's an email network. That doesn't look random either. So, we'd like to do is have a network that looks more like what real networks look like. And this leads to the small-world graph idea, and this is due to Duncan Watts whose a network theorist and Steve Strogratz, so here's the idea behind the Small World network. You've got a pre-, percentage of friends who are local. Or near you, like sort of click friends. And then you got other friends who are more random. So, your, your local or click friends would be the people you work with, the people you live nearby, that sort of things. And your random friends are the people you went to summer camp with, or your old college roommate, things like that. So if you look at real world social networks, they've got these sort of clicks of people that interact, and then each person has sort of a random friend someplace else, and those random friends also belong to the clicks a little bit. So let's look at that network and see how it works. So we're gonna open a net logo model here. And what we can do is we can set this thing up and we're just gonna put people in a circle. Now the thing to notice is that in the circle each person is connected to people on either side and there's 40 nodes, and what I can do is I can start rewiring people. One at a time. So that they've got more and more. Randomly rewired nodes, and then what I can do, is I can ask, what's happening to the graph. Now notice here on the graph, you see clustering coefficient, and over here, you see average path length. And this graph you see up here on the upper left, the green line, so it's the clustering coefficient. And the red line shows average path length. So as I rewire, what you can see is that average path length is falling, but the clustering coefficient. He's also falling. So let's do this one more time. I'm going to sit here and I'm going to rewire. Notice the clustering coefficient starts out at a half and the average path length is 5.4. Now as I start rewiring, the clustering coefficient falls, and that's because before, everybody was connected just to their neighbors around them so there were lots of clusters. So the clustering coefficient falls. And the average path length. Is falling fast, it's not under 2.8, 2.7 and so on and so again we see this every time we run this we see a decrease in the [inaudible] coefficient and a decrease in the average path length as we construct this small world network. So what we get is, is people have more random friends, we get less clustering and we also get an average, a shorter average distance between people. So that's the Small Rope model. We'll come back to that a little bit in the next lecture. Cuz the Small Rope model, small rope network actually tells us a lot about social network systems, and it can help us explain the six degree of separation property that I talked about in the first lecture. Now, let's go to our third way that nodes can connect unannounced, and this is called preferential attachment. In preferential attachment, nodes arrive on the scene, and then they get to decide, who do I connect to? So think of yourself moving into a new city, or think of you creating a webpage. So, your, your webpage is your node. Now, you've got to decide what other webpages do I connect to? We're gonna assume that the probability to connect to an existing node is proportional to the number of connections it already has. So, here's an example. Here's a network and some new node comes in. And it's trying to think about what are the, what's the likelihood I should connect each one of these nodes? Well this node only has one network connection, one edge. This one has four. And so, what's gonna happen, is, when this node comes in, it's gonna be four times as likely to connect to here as it is to over here. So the probability of connecting to someone is proportional to the number of nodes it already has. Let's look at a Net Logo model of preferential attachment. Now, I'm gonna set this up, and what's gonna happen, is, I'm gonna let this go once. I'm just gonna add one node at a time for a second. And what you're seeing here on these different graphs. The top graph is showing the degree distribution. So there's one node, these are the nodes that have one edge. Connected to it and this is in the nodes that have one of them has the degree of six, and this lot below is going to plot that redistribution on a log, log plot. So let's let this thing run. And this is always sort of a fun video because you can see these nodes being added and drawing new connections. And I want you to notice two things. Let me stop it for a second. I want you to notice two things. First is there's some nodes that are way more connected to others and that's captured in this degree distribution. There's a lot of nodes that only have one and then there's a handful of nodes including one that has 23. Now I can resize the nodes by the number of connections and that give you another way to see that this degree distributions always skewed. So there's some nodes with very few, with. Very low degree and there's some with a lot. So if I let this run even further what you see is that degree di-, distribution stays skewed, like there's some nodes that have lots of awful connections and then others that have very, very few. So this preferential attachment rule results in this very skewed degree distribution, which is interesting. Now we saw that happen once but just to prove it happens every time lets run it again, and I'll put the re-size node button on and again, you see the exact same sort of degree distribution showing up where. Sub nodes are highly connected others are less connected but we're getting a very different network. So one of the interesting things is the distribution properties [inaudible] extend the same even though the exact network you're gonna get is going to be a little bit different depending on how the process played out. Well, guess what? That means its path dependent. So the exact network you're gonna get is gonna be path dependent. The equilibrium distribution of degrees is actually not gonna be path dependent. You're almost always gonna get the exact same degree distribution. But the network you get is gonna depend a lot on the particular history. So we've got sort of path dependent outcomes, but we don't have a path dependent equilibrium in terms of the degree distribution. That we know. Just from this process. At least we figured it out. It's, you know, physicist network there is to figure it out, that you're always going to get this degree distribution. And this is the way to think of it. What you'll get [inaudible] long tail of degree distribution. So what that means is, there's a whole bunch of nodes that have a degree of one. And then there's a handful of nodes that have a large degree. And so this is the probability that you have one degree, and here's the probability of a large degree. And this is what that preferential [inaudible] gives you. This sort of long tail. This is something that's called a long tailed distribution. And distribution's always gonna occur when you have preferential attachment rule. Now, which nodes end up being large degree and which ones don't, that ends up being somewhat path dependent. But. The distribution itself is not you get these long tails. And what that means is there's a big skew, some sites have lots of, look at the internet, the World Wide Web. Some sites have lots of links, other sites have very, very few links. Alright. So, that's some sense of the logic of networks. If you can stuff random connections then you get this interesting tipping point phenomena. If you have a small world connect network, then as people have more random friends, you get a lot less clustering, but you get shorter social distance between people. And finally, from the preferential attachment rule what we end up getting is we get this long tailed degree distribution where most nodes have very, very low degree, but a handful of nodes have a really, really high degree. Alright? Thanks.