1 00:00:07,810 --> 00:00:10,550 Hello. As we have seen before, 2 00:00:10,550 --> 00:00:14,700 the degree of a node in an undirected graph is the number of neighbors that it has, 3 00:00:14,700 --> 00:00:19,437 but sometimes we're not interested in that particular degree of a specific node. 4 00:00:19,437 --> 00:00:22,190 We're interested in seeing how the degrees of 5 00:00:22,190 --> 00:00:25,700 all the nodes are distributed across the whole network. 6 00:00:25,700 --> 00:00:27,590 For example, here in this network, 7 00:00:27,590 --> 00:00:30,530 we see that many of the nodes have degree two, 8 00:00:30,530 --> 00:00:31,983 some have degree three, 9 00:00:31,983 --> 00:00:34,415 and only one of them has a degree four, 10 00:00:34,415 --> 00:00:36,380 and one has degree one. 11 00:00:36,380 --> 00:00:39,950 We like to see how these are distributed over the network, and when we do, 12 00:00:39,950 --> 00:00:42,680 we look at the network's degree distribution which is 13 00:00:42,680 --> 00:00:46,640 the probability distribution of the degrees over the entire network. 14 00:00:46,640 --> 00:00:48,590 If we let P(k), 15 00:00:48,590 --> 00:00:49,715 where k is degree, 16 00:00:49,715 --> 00:00:52,220 be the degree distribution of this network, 17 00:00:52,220 --> 00:00:59,120 we'll find that P(k) has the following values: P(1) would be 1/9 because only one node, 18 00:00:59,120 --> 00:01:02,555 node E, has degree one out of all nine nodes; 19 00:01:02,555 --> 00:01:08,960 P(2) will be 4/9 because there are four nodes that have degree two over the nine nodes; 20 00:01:08,960 --> 00:01:15,240 and then P(3) is 3/9 or one-third because three nodes have degree three. 21 00:01:15,240 --> 00:01:17,780 We can plot the degree distribution of a network 22 00:01:17,780 --> 00:01:20,855 using Network X in the following way: first, 23 00:01:20,855 --> 00:01:24,200 we use the function degrees which returns a dictionary where 24 00:01:24,200 --> 00:01:28,200 the keys are nodes and the values are the degree of the nodes; 25 00:01:28,200 --> 00:01:32,360 and then we construct a list of sorted degrees (so this would 26 00:01:32,360 --> 00:01:37,165 just have the degrees of all the nodes in the network in a sorted list); 27 00:01:37,165 --> 00:01:39,750 then we construct a histogram that tells us 28 00:01:39,750 --> 00:01:43,035 how many nodes of a particular degree we have; 29 00:01:43,035 --> 00:01:47,255 and then we can just plot a bar plot of these histogram. 30 00:01:47,255 --> 00:01:49,110 If we do that for this network, 31 00:01:49,110 --> 00:01:51,145 this is what that histogram looks like. 32 00:01:51,145 --> 00:01:53,700 We see that as we had seen before, 33 00:01:53,700 --> 00:01:55,665 most of the nodes have degree two, 34 00:01:55,665 --> 00:01:57,090 then some of them have a degree three, 35 00:01:57,090 --> 00:02:00,175 and very few of them have degrees one and four. 36 00:02:00,175 --> 00:02:04,345 This allows us to see how these degrees are distributed over the network. 37 00:02:04,345 --> 00:02:08,545 Now, sometimes we're working with directed graphs instead of undirected graphs, 38 00:02:08,545 --> 00:02:10,420 and then in that case, 39 00:02:10,420 --> 00:02:13,970 we would be interested in the in-degree or the out-degree of the nodes. 40 00:02:13,970 --> 00:02:17,350 Usually, we look at the in-degree, and in this case, 41 00:02:17,350 --> 00:02:18,700 if we look at the in-degrees, 42 00:02:18,700 --> 00:02:20,600 this is how they're distributed. 43 00:02:20,600 --> 00:02:25,285 If we look at the in-degree distribution, say P_in(k), 44 00:02:25,285 --> 00:02:29,260 that degree distribution would have these values: we have 45 00:02:29,260 --> 00:02:33,885 P_in(0) is 2/9 because two nodes have degree zero, 46 00:02:33,885 --> 00:02:40,125 P_in(1) is 4/9 because four of the nodes have in-degree one and so on. 47 00:02:40,125 --> 00:02:43,670 We can also visualize the in-degree distribution in 48 00:02:43,670 --> 00:02:47,150 the same way that we did for the degree distribution in the undirected graph, 49 00:02:47,150 --> 00:02:50,945 but now we use the in-degree function rather than the degree function, 50 00:02:50,945 --> 00:02:52,750 and everything else is the same, 51 00:02:52,750 --> 00:02:56,460 and we can visualize the in-degree distribution of this network. 52 00:02:56,460 --> 00:02:58,865 So one interesting question to ask is, 53 00:02:58,865 --> 00:03:02,630 what does the degree distribution look like for real networks? 54 00:03:02,630 --> 00:03:04,565 Let me show you three examples. 55 00:03:04,565 --> 00:03:07,550 Here are the degree distributions of three different networks, 56 00:03:07,550 --> 00:03:12,015 and let me tell you what the networks are: Network A is a network of 57 00:03:12,015 --> 00:03:17,285 225,000 actors connected when they appear in a movie together, 58 00:03:17,285 --> 00:03:21,025 B is a network of the World Wide Web so it 59 00:03:21,025 --> 00:03:24,750 has about 325,000 documents that are connected by URLs, 60 00:03:24,750 --> 00:03:27,880 and then C is a network of 61 00:03:27,880 --> 00:03:30,565 the US Power Grid so it's a network of 62 00:03:30,565 --> 00:03:34,135 about 5,000 generators connected by transmission lines. 63 00:03:34,135 --> 00:03:37,838 There are two things to notice about these degree distributions. 64 00:03:37,838 --> 00:03:40,795 The first thing is that they're all in log-log scale, 65 00:03:40,795 --> 00:03:47,245 meaning that the x-axis and the y-axis are both on log scale rather than linear scale. 66 00:03:47,245 --> 00:03:49,240 The second thing to notice is that, 67 00:03:49,240 --> 00:03:51,130 for at least part of these distributions, 68 00:03:51,130 --> 00:03:54,563 they tend to look like straight lines for all three cases. 69 00:03:54,563 --> 00:03:57,235 When you put those two things together when you have 70 00:03:57,235 --> 00:04:01,495 a degree distribution on a log-log scale and it looks kind of like a straight line, 71 00:04:01,495 --> 00:04:06,225 then we say that this degree distribution looks kind of like a power law. 72 00:04:06,225 --> 00:04:09,325 A power law degree distribution would have the form 73 00:04:09,325 --> 00:04:13,205 P(k) equals C times k to the negative alpha, 74 00:04:13,205 --> 00:04:15,895 where C and alpha are constant, 75 00:04:15,895 --> 00:04:22,210 and the alpha values for these three distributions that we have here are 2.3 for A, 76 00:04:22,210 --> 00:04:25,385 2.1 for B, and four for C. Okay, 77 00:04:25,385 --> 00:04:27,025 these details are not so important, 78 00:04:27,025 --> 00:04:28,351 at least for this course, 79 00:04:28,351 --> 00:04:31,630 but the thing to know about power law degree distributions is 80 00:04:31,630 --> 00:04:34,930 that they tend to have most of the nodes with very, 81 00:04:34,930 --> 00:04:40,565 very small degree, but you have a few nodes that accumulate a very, very large degree. 82 00:04:40,565 --> 00:04:44,545 For example, if we look at the degree distribution for Network A, 83 00:04:44,545 --> 00:04:48,760 we have that most actors have a very small degree 84 00:04:48,760 --> 00:04:52,912 so they have appeared in movies with a very small number of other actors, 85 00:04:52,912 --> 00:04:57,170 but few actors actually appear in a movie with many, many actors. 86 00:04:57,170 --> 00:05:00,995 Some appear in at least one movie with almost 1,000 actors. 87 00:05:00,995 --> 00:05:05,785 You can notice that when you look at this degree distribution, 88 00:05:05,785 --> 00:05:10,360 these actors have accumulated a degree that's very large, almost 1,000. 89 00:05:10,360 --> 00:05:15,555 Whereas, most actors actually have a very small degree. 90 00:05:15,555 --> 00:05:19,341 And that's typical of power law degree distributions. 91 00:05:19,341 --> 00:05:24,250 One of the things we try to ask when we see something like this is, 92 00:05:24,250 --> 00:05:29,290 what could explain this property that we observe happening in many different networks? 93 00:05:29,290 --> 00:05:33,570 The way we try to answer this question is by coming up with models that 94 00:05:33,570 --> 00:05:38,190 generate networks that make a few assumptions about how these networks get formed, 95 00:05:38,190 --> 00:05:41,360 and then they give rise to whatever properties we observe. 96 00:05:41,360 --> 00:05:43,080 So in this case, the question would be, 97 00:05:43,080 --> 00:05:46,560 can we come up with a model that generates 98 00:05:46,560 --> 00:05:50,885 a network that has a power law-like degree distribution? 99 00:05:50,885 --> 00:05:55,915 One of the models that achieves this property is called a Preferential Attachment Model. 100 00:05:55,915 --> 00:05:59,080 Let me tell you how the preferential attachment model works. 101 00:05:59,080 --> 00:06:03,173 First, we start with just two nodes that are connected by an edge, 102 00:06:03,173 --> 00:06:05,100 and then at each time step, 103 00:06:05,100 --> 00:06:06,950 we're going to add a new node, 104 00:06:06,950 --> 00:06:10,710 and the new node is going to connect to a single existing node. 105 00:06:10,710 --> 00:06:14,910 The sort of special sauce in 106 00:06:14,910 --> 00:06:20,550 the model comes when you decide which node to pick out of the existing nodes. 107 00:06:20,550 --> 00:06:23,850 The way that these new node is going to pick an existing node to attach 108 00:06:23,850 --> 00:06:27,685 to is going to be that it's going to choose it at random, 109 00:06:27,685 --> 00:06:33,945 but it's going to choose it with probability proportional to the node's current degree. 110 00:06:33,945 --> 00:06:38,517 So the probability of connecting to a node u that has a degree, k_u, 111 00:06:38,517 --> 00:06:44,135 is going to be k_u divided by the sum of all the degrees of all the other nodes. 112 00:06:44,135 --> 00:06:46,930 Let's run an example of this model. 113 00:06:46,930 --> 00:06:49,415 Again, we start with these two nodes connected by an edge, 114 00:06:49,415 --> 00:06:52,040 and then at each time step we're going to add a new node. 115 00:06:52,040 --> 00:06:56,180 Node three is going to come in and is going to attach to a single node, 116 00:06:56,180 --> 00:06:57,970 either node one and node two, 117 00:06:57,970 --> 00:07:02,205 but it's going to do so with probability proportional to their degree. 118 00:07:02,205 --> 00:07:05,325 But right now, node one and two both have degree of one, 119 00:07:05,325 --> 00:07:08,655 so the probability of choosing one and two is 50/50 for node three. 120 00:07:08,655 --> 00:07:11,005 Let's say, it chooses node two. 121 00:07:11,005 --> 00:07:13,670 Now, node four comes in, but now, 122 00:07:13,670 --> 00:07:14,890 node two has degree of two, 123 00:07:14,890 --> 00:07:17,595 and nodes one and three have degree one, 124 00:07:17,595 --> 00:07:20,660 and so the probability of attaching to node two is 0.5, 125 00:07:20,660 --> 00:07:25,085 and the probability of attaching to nodes one or three is 0.25. 126 00:07:25,085 --> 00:07:28,355 Node four attaches to node three, 127 00:07:28,355 --> 00:07:30,365 which had a lower probability. 128 00:07:30,365 --> 00:07:33,090 That could happen. So it attaches to node three. 129 00:07:33,090 --> 00:07:35,405 Now, node five comes in, 130 00:07:35,405 --> 00:07:37,755 and we have to recompute all the probabilities. 131 00:07:37,755 --> 00:07:40,950 Well, now, nodes two and three both have degree two, 132 00:07:40,950 --> 00:07:43,430 and nodes one and four have degree one. 133 00:07:43,430 --> 00:07:47,120 So nodes two and three are going to have a higher probability of attaching, 134 00:07:47,120 --> 00:07:49,910 and so that's 0.33 for nodes two and three, 135 00:07:49,910 --> 00:07:52,530 and 0.17 for nodes one and four. 136 00:07:52,530 --> 00:07:55,190 Let's say, five attaches to node two, 137 00:07:55,190 --> 00:07:57,345 and we continue this node six, 138 00:07:57,345 --> 00:07:58,909 again, we recompute the probabilities. 139 00:07:58,909 --> 00:08:01,090 Now, node two has the highest degree, 140 00:08:01,090 --> 00:08:04,550 so we will have the highest probability of getting that new attachment. 141 00:08:04,550 --> 00:08:07,205 So six, let's say, attaches to two. 142 00:08:07,205 --> 00:08:08,445 Now, seven comes in, 143 00:08:08,445 --> 00:08:10,030 we recompute the probabilities. 144 00:08:10,030 --> 00:08:12,560 Again, now, node two has an even higher degree so it has 145 00:08:12,560 --> 00:08:15,635 an ever higher probability of getting that new node. 146 00:08:15,635 --> 00:08:18,685 Second is node three that has a degree or two 147 00:08:18,685 --> 00:08:22,295 with probability of getting that new node edge at 0.2, 148 00:08:22,295 --> 00:08:24,515 and seven attaches to two. 149 00:08:24,515 --> 00:08:27,302 Node eight comes in, we recompute the probabilities. 150 00:08:27,302 --> 00:08:30,143 Node two probability becomes even larger, 151 00:08:30,143 --> 00:08:33,605 but this node eight attaches to node three, and so on. 152 00:08:33,605 --> 00:08:35,115 You can see how this continues. 153 00:08:35,115 --> 00:08:42,005 The thing to notice here is that as node two started to get larger and larger degree, 154 00:08:42,005 --> 00:08:46,290 its probability of getting a new edge became larger and larger as well. 155 00:08:46,290 --> 00:08:48,620 There is this sort of rich get richer phenomenon, 156 00:08:48,620 --> 00:08:52,340 where as the nodes get larger and larger degree, 157 00:08:52,340 --> 00:08:57,475 they also start to become more and more likely to increase their degree. 158 00:08:57,475 --> 00:09:02,780 What we can prove about this particular mechanism is that it gives rise to a power law. 159 00:09:02,780 --> 00:09:07,390 It approaches a power law as the number of nodes gets larger, and larger, and larger. 160 00:09:07,390 --> 00:09:13,860 So it matches the kind of degree distribution that we see in these real networks. 161 00:09:13,860 --> 00:09:19,360 This type of modeling technique allows us to explain or at least have 162 00:09:19,360 --> 00:09:22,060 some hypothesis for what kind of mechanism could give and 163 00:09:22,060 --> 00:09:25,300 rise to this shape of the degree distribution that we observe. 164 00:09:25,300 --> 00:09:27,775 For example, if we believe that 165 00:09:27,775 --> 00:09:31,030 a very popular actor that has 166 00:09:31,030 --> 00:09:35,080 appeared with many other actors in movies has a higher likelihood 167 00:09:35,080 --> 00:09:39,820 of getting an additional actor to co-appear in 168 00:09:39,820 --> 00:09:42,610 a movie than a maybe less popular actor 169 00:09:42,610 --> 00:09:45,415 that has not appeared with many other actors in movies, 170 00:09:45,415 --> 00:09:49,870 then this is the kind of mechanism that could be explaining 171 00:09:49,870 --> 00:09:55,475 the sort of very skewed power law distribution that we observed. 172 00:09:55,475 --> 00:09:57,730 In Network X, you can use the function, 173 00:09:57,730 --> 00:10:03,290 barabasi_albert_graph, which is named after the researchers that came up with this model, 174 00:10:03,290 --> 00:10:06,025 with input powers n and m, 175 00:10:06,025 --> 00:10:09,070 where n is the number of nodes and m is 176 00:10:09,070 --> 00:10:13,175 the number of new nodes that an arriving node would attach to. 177 00:10:13,175 --> 00:10:15,010 In our example, the way we define it, 178 00:10:15,010 --> 00:10:17,755 this m parameter would be one because we said that 179 00:10:17,755 --> 00:10:21,820 every new node would attach to only a single existing node, 180 00:10:21,820 --> 00:10:28,720 but you can generalize this and have it so that every node attaches to m existing nodes, 181 00:10:28,720 --> 00:10:36,690 and that m will not change the fact that you still get a power law degree distribution. 182 00:10:36,690 --> 00:10:39,910 You can use this function in Network X to create 183 00:10:39,910 --> 00:10:44,440 networks that follow these Preferential Attachment Model. 184 00:10:44,440 --> 00:10:48,618 Let's create one here with a million nodes and an m(1), 185 00:10:48,618 --> 00:10:51,450 so every node attaches to a single existing node. 186 00:10:51,450 --> 00:10:55,000 Now, let's plot the degree distribution in the same way that we 187 00:10:55,000 --> 00:10:58,330 did before except that now I'm not using a bar plot, 188 00:10:58,330 --> 00:10:59,695 I'm using a scatter plot, 189 00:10:59,695 --> 00:11:01,635 and now I'm setting the scales, 190 00:11:01,635 --> 00:11:04,690 the y-scale and x-scales to be logged so we can see 191 00:11:04,690 --> 00:11:09,130 that straight line that gets formed on the log-log scale for the degree distribution. 192 00:11:09,130 --> 00:11:11,290 Here it is. We see that it forms 193 00:11:11,290 --> 00:11:15,090 the straight line that characterizes the power law degree distribution. 194 00:11:15,090 --> 00:11:18,250 So in summary, we have the degree distribution of a graph is 195 00:11:18,250 --> 00:11:22,030 the probability distribution of the degrees over the entire network, 196 00:11:22,030 --> 00:11:25,270 and in many real networks that we see, 197 00:11:25,270 --> 00:11:28,750 this degree distribution tends to look sort of like a power law 198 00:11:28,750 --> 00:11:34,500 because it looks sort of like a straight line on a log-log scale. 199 00:11:34,500 --> 00:11:38,860 We also discussed that models of networks generation allows to identify 200 00:11:38,860 --> 00:11:43,280 mechanisms that give rise to patterns that we observe in real networks. 201 00:11:43,280 --> 00:11:44,855 In this case, we observed that 202 00:11:44,855 --> 00:11:47,965 many real networks tend to have these power law degree distribution, 203 00:11:47,965 --> 00:11:50,290 and then we covered a model that gives 204 00:11:50,290 --> 00:11:52,570 rise to this particular property which allows us to have 205 00:11:52,570 --> 00:11:54,640 some insight about the kinds of things that could be 206 00:11:54,640 --> 00:11:57,355 given rise to these properties in real networks. 207 00:11:57,355 --> 00:12:00,400 In this case, this was the Preferential Attachment Model that produces 208 00:12:00,400 --> 00:12:03,763 these networks with power law degree distribution. 209 00:12:03,763 --> 00:12:06,135 In Network X, you can use this function, 210 00:12:06,135 --> 00:12:10,670 barabasi_albert_graph to construct networks that have n nodes and where 211 00:12:10,670 --> 00:12:12,937 every single node attaches to m 212 00:12:12,937 --> 00:12:15,970 existing nodes following the Preferential Attachment Model. 213 00:12:15,970 --> 00:12:19,000 That's all for today. I hope to see you next time.