0:00

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.

Â