1 00:00:01,900 --> 00:00:07,087 Hello, this week, we've been looking 2 00:00:07,087 --> 00:00:14,574 at networks as dynamic structures that change over time. 3 00:00:14,574 --> 00:00:18,290 In the past two videos, we looked at different models of network evolution. 4 00:00:18,290 --> 00:00:23,110 That given the dynamics for how a network evolves from the beginning to the end. 5 00:00:23,110 --> 00:00:27,150 Today we're going to look at a related problem which is given a fixed network, 6 00:00:27,150 --> 00:00:30,349 can we predict how this network is going to look in the future. 7 00:00:30,349 --> 00:00:34,827 And more specifically, we're going to be looking at the link prediction problem. 8 00:00:34,827 --> 00:00:36,345 Which is given a network, 9 00:00:36,345 --> 00:00:40,010 can we predict which edges are going to be formed in the future? 10 00:00:40,010 --> 00:00:44,512 This problem has a lot of applications, for example if you're Facebook and 11 00:00:44,512 --> 00:00:47,748 you want to create a friend recommendation algorithm or 12 00:00:47,748 --> 00:00:51,349 a friend recommender to tell people who they should friend. 13 00:00:51,349 --> 00:00:53,408 Then, basically you're solving this problem. 14 00:00:53,408 --> 00:00:58,189 You're looking at the current Facebook network and you're trying to predict 15 00:00:58,189 --> 00:01:01,606 which new friendships are likely to form in the future. 16 00:01:01,606 --> 00:01:06,329 Let's take this small network as an example and let's try to ask the question, 17 00:01:06,329 --> 00:01:08,666 what new edges are likely to be formed? 18 00:01:08,666 --> 00:01:11,913 And more specifically, let's formulate the problem in this way. 19 00:01:11,913 --> 00:01:14,938 Let's say that we take a specific pair of nodes and 20 00:01:14,938 --> 00:01:18,551 we want to assess whether or not they're likely to connect. 21 00:01:18,551 --> 00:01:22,455 What we're going to do today is we're going to go over several measures, 22 00:01:22,455 --> 00:01:25,068 seven of them, to try to make this assessment. 23 00:01:25,068 --> 00:01:29,632 To try to decide whether a specific pair of nodes are likely 24 00:01:29,632 --> 00:01:31,689 to become friends or not. 25 00:01:31,689 --> 00:01:33,675 And so, we've actually thought about this kind of question before. 26 00:01:33,675 --> 00:01:37,959 If you remember, we talked about triadic closure which is the tendency for 27 00:01:37,959 --> 00:01:42,733 people who share connections in a social network to become connected themselves. 28 00:01:42,733 --> 00:01:45,446 So triadic closure actually gives us a hint for 29 00:01:45,446 --> 00:01:48,656 what the first measure that we're going to look at is. 30 00:01:48,656 --> 00:01:50,602 And that is very simple measure, 31 00:01:50,602 --> 00:01:54,574 just look at the number of common neighbors that the two nodes have. 32 00:01:54,574 --> 00:01:59,793 Now this is very simple, but let me define this measure to introduce some notation. 33 00:01:59,793 --> 00:02:04,609 So we're going to say that the number of common neighbors of nodes X and 34 00:02:04,609 --> 00:02:10,269 Y is going to be the size of a set, which is the intersection of the sets N(X) and 35 00:02:10,269 --> 00:02:14,942 N(Y), where N(X) defines the set of neighbors of the node X. 36 00:02:14,942 --> 00:02:19,674 And so for example, the common neighbor measure for nodes A, 37 00:02:19,674 --> 00:02:25,873 C in this network is going to be 2 because nodes A and C have two common neighbors. 38 00:02:25,873 --> 00:02:27,453 That is node B and node D. 39 00:02:27,453 --> 00:02:31,670 So A, C have two common neighbors. 40 00:02:31,670 --> 00:02:35,207 In network X, we can use the function common neighbors, 41 00:02:35,207 --> 00:02:37,872 which takes in as input the graph to nodes. 42 00:02:37,872 --> 00:02:43,860 And it outputs an iterator of all the common neighbors of the two nodes. 43 00:02:43,860 --> 00:02:47,836 And so here, what I'm doing is I'm creating a list of tuples which 44 00:02:47,836 --> 00:02:51,104 have the two nodes and the number of common neighbors. 45 00:02:51,104 --> 00:02:55,633 And I'm only including the nodes that are not connected with each other. 46 00:02:55,633 --> 00:03:00,773 The ones that don't have an edge between them by using the function non_edges. 47 00:03:00,773 --> 00:03:02,156 And if I sort this list, 48 00:03:02,156 --> 00:03:06,730 we can see the pairs of nodes that have the most common neighbors between them. 49 00:03:06,730 --> 00:03:10,859 And we see that the pair A, C has two neighbors in common, 50 00:03:10,859 --> 00:03:15,260 there are many others that have only one neighbor in common. 51 00:03:15,260 --> 00:03:18,370 And then many others that have zero neighbors in common. 52 00:03:18,370 --> 00:03:22,159 And so if we start to compare between different edges, for 53 00:03:22,159 --> 00:03:26,020 example we look at the pair A, G and the pair H, I, and ask, 54 00:03:26,020 --> 00:03:29,834 which one of these two is more likely to become connected? 55 00:03:29,834 --> 00:03:34,304 Then by looking at the number of common neighbors, we actually can't tell, 56 00:03:34,304 --> 00:03:37,759 because both of these have exactly one neighbor in common. 57 00:03:37,759 --> 00:03:41,713 And so let's look at other measures that may potentially give us different answers 58 00:03:41,713 --> 00:03:43,529 for these particular pairs of nodes. 59 00:03:43,529 --> 00:03:48,194 The next measure we're going to look at is called the Jaccard coefficient. 60 00:03:48,194 --> 00:03:52,359 And what it does is that it looks at the number of common neighbors but 61 00:03:52,359 --> 00:03:56,468 it normalizes it by the total number of neighbors of the two nodes. 62 00:03:56,468 --> 00:04:01,680 So the way that we write it down is we say the Jaccard coefficient of nodes X and 63 00:04:01,680 --> 00:04:06,009 Y is going to be the fraction of the number of common neighbors. 64 00:04:06,009 --> 00:04:11,049 That's in the numerator, so it's the intersection of the sets N(X) and 65 00:04:11,049 --> 00:04:14,489 N(Y), divided by the number of neighbors of X and 66 00:04:14,489 --> 00:04:17,700 Y which would be the union of N(X) and N(Y). 67 00:04:17,700 --> 00:04:23,523 And so here, the pair of nodes of A and C, have a Jaccard coefficient of 68 00:04:23,523 --> 00:04:28,581 one-half because they have two common neighbors, B and D. 69 00:04:28,581 --> 00:04:31,743 And they have four total neighbors, nodes B, D, E, and F. 70 00:04:31,743 --> 00:04:35,873 And so that's 2 over 4 which is one-half. 71 00:04:35,873 --> 00:04:40,851 In network X, we can use the function jaccard_coefficient which takes as 72 00:04:40,851 --> 00:04:46,065 input the graph and it outputs an iterator of tuples which have the two nodes and 73 00:04:46,065 --> 00:04:48,920 the Jaccard coefficient of the two nodes. 74 00:04:48,920 --> 00:04:53,571 But it only outputs the pairs of nodes that are not already connected, so 75 00:04:53,571 --> 00:04:54,569 the non edges. 76 00:04:54,569 --> 00:04:57,917 So if we sort this list, we now find that I, 77 00:04:57,917 --> 00:05:01,559 H have the highest Jaccard coefficient of 1. 78 00:05:01,559 --> 00:05:03,470 And that's because I and 79 00:05:03,470 --> 00:05:08,850 H are both connected to a single neighbor which is a common neighbor G. 80 00:05:08,850 --> 00:05:12,810 Whereas the nodes A and G, they have one common neighbor, but 81 00:05:12,810 --> 00:05:17,471 they have more neighbors that are in the union of the neighbors of A and G. 82 00:05:17,471 --> 00:05:21,960 And so, therefore, they have a lower Jaccard coefficient. 83 00:05:21,960 --> 00:05:25,150 The next measure is called the Research Allocation Index. 84 00:05:25,150 --> 00:05:29,817 And the intuition behind it is that it considers a fraction of a resource for 85 00:05:29,817 --> 00:05:34,557 example, information or something else that a node can send to another node 86 00:05:34,557 --> 00:05:36,722 through their common neighbors. 87 00:05:36,722 --> 00:05:39,802 And so first, let me tell you how it's defined mathematically and 88 00:05:39,802 --> 00:05:43,716 then I'll tell you a little bit more about what the intuition is behind the measure. 89 00:05:43,716 --> 00:05:48,790 So the Resource Allocation index of the nodes X, Y is going to be the sum 90 00:05:48,790 --> 00:05:54,125 over all the common neighbors of X and Y of one over the degree of the nodes. 91 00:05:54,125 --> 00:05:57,931 So in this case, if X and Y have a lot of common neighbors and 92 00:05:57,931 --> 00:06:01,839 they're going to have a large Resource Allocation index. 93 00:06:01,839 --> 00:06:06,100 But if they have a lot of neighbors that have low degree, 94 00:06:06,100 --> 00:06:11,552 then they're going to have an even larger Resource Allocation index. 95 00:06:11,552 --> 00:06:13,642 Now what's the intuition behind this? 96 00:06:13,642 --> 00:06:17,071 Let's consider two nodes X and Y, and let's say that we're measuring 97 00:06:17,071 --> 00:06:19,832 the Resource Allocation index between these two nodes. 98 00:06:19,832 --> 00:06:25,031 And let's say that they have exactly one common neighbor, Z. 99 00:06:25,031 --> 00:06:28,913 Now imagine that X is trying to send to Y a unit of something, 100 00:06:28,913 --> 00:06:31,800 let's say information or something else. 101 00:06:31,800 --> 00:06:33,915 And is going to do so by passing it for 102 00:06:33,915 --> 00:06:36,957 X to Z and then hoping that Z will pass this unit to Y. 103 00:06:36,957 --> 00:06:41,287 But actually what Z does is that when it receives this unit from X 104 00:06:41,287 --> 00:06:46,034 is going to distribute this unit evenly among all the neighbors of Z. 105 00:06:46,034 --> 00:06:49,955 Then in that case, well Y is only going to get a fraction of that unit. 106 00:06:49,955 --> 00:06:53,427 And which fraction depends on what the degree of Z is. 107 00:06:53,427 --> 00:06:59,588 So if Z has degree N, then Y is only going to get 1 over N of that unit. 108 00:06:59,588 --> 00:07:03,632 And so if Z is the only common neighbor of X and Y, and 109 00:07:03,632 --> 00:07:07,316 Z has a lot of neighbors, a very large degree. 110 00:07:07,316 --> 00:07:14,437 Then X is going to be able to send less to Y, than if Z had a very few neighbors. 111 00:07:14,437 --> 00:07:19,541 And so that's why this research allocation index penalizes pairs of 112 00:07:19,541 --> 00:07:25,530 nodes that have common neighbors that themselves have lots of other neighbors. 113 00:07:25,530 --> 00:07:30,628 So for example, when we measure the Resource Allocation index of nodes A and 114 00:07:30,628 --> 00:07:33,349 C, we would have one-third for node B. 115 00:07:33,349 --> 00:07:36,969 because node B is the common neighbor of A and C and has degree of 3, 116 00:07:36,969 --> 00:07:38,988 plus 1 over 3 which is for node D, 117 00:07:38,988 --> 00:07:42,906 which also has degree 3 and it's also a common neighbor of A and C. 118 00:07:42,906 --> 00:07:48,992 So the Resource Allocation index of A, C is going to be two-thirds. 119 00:07:48,992 --> 00:07:51,993 We can use the function of Resource Allocation index to 120 00:07:51,993 --> 00:07:55,516 compute the Resource Allocation index of all pairs of nodes that 121 00:07:55,516 --> 00:07:58,270 are not connected by an edge already in the graph. 122 00:07:58,270 --> 00:07:59,275 And if we sort it, 123 00:07:59,275 --> 00:08:03,239 we can see the Resource Allocation index of all pairs in this network. 124 00:08:03,239 --> 00:08:08,671 And if we look at the two edges that we're being kind of following, 125 00:08:08,671 --> 00:08:10,999 we see that in this case, A, 126 00:08:10,999 --> 00:08:15,276 G has a higher Resource Allocation index than I, H. 127 00:08:15,276 --> 00:08:20,134 And that is because I, H has a common neighbor which is G. 128 00:08:20,134 --> 00:08:22,917 But G has a high degree, has a degree of four. 129 00:08:22,917 --> 00:08:26,944 Whereas A, G, they're common neighbor is E, and 130 00:08:26,944 --> 00:08:30,237 E has a slightly smaller degree of three. 131 00:08:30,237 --> 00:08:34,821 So, that will give A, G a larger Resource Allocation index than I, H. 132 00:08:34,821 --> 00:08:39,367 The next measure is called the Adamic-Adar index. 133 00:08:39,367 --> 00:08:42,748 Which is very similar to the research allocation index. 134 00:08:42,748 --> 00:08:45,976 The only difference is that rather than dividing by the degree, 135 00:08:45,976 --> 00:08:47,780 it divides by the log of the degree. 136 00:08:47,780 --> 00:08:52,908 So in this case, the Adamic-Adar index for nodes A, C instead of being 2 137 00:08:52,908 --> 00:08:58,890 over 3 is going to be 1 over the log of 3 plus 1 over the log of 3, which is 1.82. 138 00:08:58,890 --> 00:09:05,114 And there's a function for it too that you can use in network X is Adamic-Adar index. 139 00:09:05,114 --> 00:09:08,101 And again, we can compare A, G and H, I but in this case, 140 00:09:08,101 --> 00:09:11,425 it's going to be very similar to the Resource Allocation index. 141 00:09:11,425 --> 00:09:15,310 And so all we did was to put the log in the denominator. 142 00:09:15,310 --> 00:09:19,130 Next, measure 5 is going to be the preferential attachment score. 143 00:09:19,130 --> 00:09:23,233 So, if you recall, the preferential attachment model has the feature that 144 00:09:23,233 --> 00:09:27,096 nodes that have very high degree are more likely to get more neighbors. 145 00:09:27,096 --> 00:09:30,021 And so, the intuition behind this measure is that, well, 146 00:09:30,021 --> 00:09:33,472 if I'm looking at a pair of nodes and they both have a very high degree, 147 00:09:33,472 --> 00:09:36,949 then they're more likely to be connected to each other in the future. 148 00:09:36,949 --> 00:09:39,011 And so, what it does, is very simply, 149 00:09:39,011 --> 00:09:41,638 to take the product of the degree of the two nodes. 150 00:09:41,638 --> 00:09:43,235 And so, it's very simple. 151 00:09:43,235 --> 00:09:48,269 The preferential attachment score of X, Y is going to be the product 152 00:09:48,269 --> 00:09:53,323 of the number of neighbors of X, times the number of neighbors of Y. 153 00:09:53,323 --> 00:09:57,546 And A, C would have a preferential attachment score of 9. 154 00:09:57,546 --> 00:10:01,726 In network X, we can use the preferential_attachment function to 155 00:10:01,726 --> 00:10:05,688 compute the preferential attachment score over all the pairs of 156 00:10:05,688 --> 00:10:08,709 nodes that are not connected by an edge already. 157 00:10:08,709 --> 00:10:14,827 And here we can look at two edges that we've been following, A, G and H, I. 158 00:10:14,827 --> 00:10:19,278 And we see that A, G has a higher preferential attachment score than I, H, 159 00:10:19,278 --> 00:10:22,949 and that's because A has a degree of 3 and G has a degree of 4, 160 00:10:22,949 --> 00:10:26,370 which makes the preferential attachment score of 12. 161 00:10:26,370 --> 00:10:31,461 Whereas, I and H both only have one neighbor and so they have a score of 1. 162 00:10:31,461 --> 00:10:35,385 Okay, next, we're going to look at two other measures, 163 00:10:35,385 --> 00:10:39,722 that take in to account the community structure of the network. 164 00:10:39,722 --> 00:10:43,379 So in cases where you have a network and on top of the network, 165 00:10:43,379 --> 00:10:46,769 you have some knowledge about different communities. 166 00:10:46,769 --> 00:10:50,168 And here we'll think of communities as sets of nodes and 167 00:10:50,168 --> 00:10:54,668 we'll make the assumption that each node belongs only to one community. 168 00:10:54,668 --> 00:10:58,000 So one example is if this network was, for example, 169 00:10:58,000 --> 00:11:01,734 a network of communication among employees in a company. 170 00:11:01,734 --> 00:11:05,431 Then you may think that the department for which an employee works for 171 00:11:05,431 --> 00:11:06,907 would define a community. 172 00:11:06,907 --> 00:11:10,661 So for example, there's HR, and there's legal and so on, and so 173 00:11:10,661 --> 00:11:13,688 you could imagine thinking of those as communities. 174 00:11:13,688 --> 00:11:18,116 So if you had that type of structure, then you could use different measures for 175 00:11:18,116 --> 00:11:22,294 determining whether two nodes are likely to connect to each other or not. 176 00:11:22,294 --> 00:11:25,841 So in this case, let's assume that these network has two communities. 177 00:11:25,841 --> 00:11:27,493 So, these are the two communities. 178 00:11:27,493 --> 00:11:30,609 So there's A, B, D and C belong to Community 1, and 179 00:11:30,609 --> 00:11:32,982 the other nodes belong to Community 2. 180 00:11:32,982 --> 00:11:34,610 And what these two measures do, 181 00:11:34,610 --> 00:11:38,590 is they make the assumption that if two nodes belong to the same community, and 182 00:11:38,590 --> 00:11:41,931 they have many neighbors that also belong to the same community. 183 00:11:41,931 --> 00:11:45,794 Then they're more likely to form an edge, than if they had neighbors that belong to 184 00:11:45,794 --> 00:11:49,953 different communities, or if the two nodes themselves were in different communities. 185 00:11:49,953 --> 00:11:53,421 That's sort of the basic assumption that we make. 186 00:11:53,421 --> 00:11:56,413 And so this allows us to compute new measures, and so 187 00:11:56,413 --> 00:11:57,981 let's go over two of them. 188 00:11:57,981 --> 00:12:02,302 So the sixth measures that we are going to look at today is the number of common 189 00:12:02,302 --> 00:12:03,077 neighbors. 190 00:12:03,077 --> 00:12:07,774 But with a bonus for neighbors that belong to the same community as the two 191 00:12:07,774 --> 00:12:09,474 nodes we're looking at. 192 00:12:09,474 --> 00:12:13,744 So this is called the Common Neighbor Soundarajan-Hopcroft score. 193 00:12:13,744 --> 00:12:16,035 And if we're looking at nodes X and 194 00:12:16,035 --> 00:12:19,674 Y is simply going to be the number of common neighbors. 195 00:12:19,674 --> 00:12:23,963 So the size of intersection of N(X) and N(Y), plus some bonus, 196 00:12:23,963 --> 00:12:29,319 which is going to be the sum over all the common neighbors of this function, f(u). 197 00:12:29,319 --> 00:12:34,135 And f(u) is simply an indicator that tells us whether the u, which is 198 00:12:34,135 --> 00:12:39,456 a common neighbor of X and Y, belongs to the same community as X and Y, or not. 199 00:12:39,456 --> 00:12:41,195 And if it does, then it's a 1. 200 00:12:41,195 --> 00:12:42,388 If not, it's a 0. 201 00:12:42,388 --> 00:12:44,601 So it just simply gives a bonus for 202 00:12:44,601 --> 00:12:48,960 the common neighbors that belong to the same community as X and Y. 203 00:12:48,960 --> 00:12:54,082 And so for example, if we look at nodes A and C, their common neighbors are B and 204 00:12:54,082 --> 00:12:57,124 D, and they all belong to the same community. 205 00:12:57,124 --> 00:12:59,450 So A and C would get a score of 2 for 206 00:12:59,450 --> 00:13:03,950 having two common neighbors plus 2 bonus points, so we get 4. 207 00:13:03,950 --> 00:13:08,541 Nodes E and I would have a score of 2 because they both have a common neighbor, 208 00:13:08,541 --> 00:13:09,328 namely, G. 209 00:13:09,328 --> 00:13:11,330 And it belongs to the same community. 210 00:13:11,330 --> 00:13:14,675 So it would get a bonus point for a total of 2. 211 00:13:14,675 --> 00:13:17,555 But if we look at the edge A, G for example, 212 00:13:17,555 --> 00:13:20,603 they have one common neighbor, namely, E. 213 00:13:20,603 --> 00:13:22,978 But A and G are not in the same community. 214 00:13:22,978 --> 00:13:25,722 So E is not in the same community as A and G. 215 00:13:25,722 --> 00:13:28,940 Therefore A and G have a score of just 1. 216 00:13:28,940 --> 00:13:30,971 Now to use this on network X, 217 00:13:30,971 --> 00:13:36,061 we first have to tell network X which communities each node belongs to. 218 00:13:36,061 --> 00:13:40,365 So here, we're adding an attribute to each one of the nodes named, 219 00:13:40,365 --> 00:13:44,305 community, that tells which community the node belongs to. 220 00:13:44,305 --> 00:13:47,728 So for A through D, we'll say it belongs to community 0, and for 221 00:13:47,728 --> 00:13:50,168 the other ones it belongs to the community 1. 222 00:13:50,168 --> 00:13:55,459 And now we can use the function cn_soundarajan_hopcroft(G) 223 00:13:55,459 --> 00:14:01,132 which outputs an iterator of the tuples with the nodes and the score for 224 00:14:01,132 --> 00:14:06,350 each one, each pair, that is not already connected by an edge. 225 00:14:06,350 --> 00:14:10,599 And we can sort it and find which nodes have the highest score. 226 00:14:10,599 --> 00:14:15,087 And if we look at the two edges that we've been following, then we find that I, 227 00:14:15,087 --> 00:14:19,711 H has a score of 2, because their common neighbor G belongs to the same community 228 00:14:19,711 --> 00:14:21,957 as A do, whereas A, G has a score of 1. 229 00:14:21,957 --> 00:14:25,944 The last measure we're going to look at is a measure that is similar to 230 00:14:25,944 --> 00:14:30,413 the Resource Allocation index but it only takes into account nodes that are in 231 00:14:30,413 --> 00:14:33,595 the same community as the two nodes we're looking at. 232 00:14:33,595 --> 00:14:36,218 So if we're computing this measure which is called 233 00:14:36,218 --> 00:14:39,216 the Resource Allocation Soundarajan-Hopcroft score. 234 00:14:39,216 --> 00:14:44,720 And this is after the researchers that came up with this measure of X and Y. 235 00:14:44,720 --> 00:14:49,174 Then what we do is we sum over all the neighbors of X and Y. 236 00:14:49,174 --> 00:14:52,912 And rather than summing just one over the degree of the nodes of the common 237 00:14:52,912 --> 00:14:56,354 neighbors like we did in the standard Resource Allocation index. 238 00:14:56,354 --> 00:15:00,622 We now have this f(u) in the denominator of the fraction. 239 00:15:00,622 --> 00:15:03,464 And this function f(u) again is the same as before is 1, 240 00:15:03,464 --> 00:15:06,548 if u belongs to the same community as X and Y, and 0 otherwise. 241 00:15:06,548 --> 00:15:11,430 So in the case where you have a common neighbor that does not belong to the same 242 00:15:11,430 --> 00:15:14,405 community as X and Y, then that neighbor is not 243 00:15:14,405 --> 00:15:19,090 contributing anything to the sum because you have a 0 in the numerator. 244 00:15:19,090 --> 00:15:24,773 And so if we look at some examples for the nodes A and C, we would find that, 245 00:15:24,773 --> 00:15:31,029 well, because both of the neighbors B and D belong to the same community as A, C. 246 00:15:31,029 --> 00:15:35,067 Then we have the same score as we did before, and 1 over 3 plus 1 over 3, 247 00:15:35,067 --> 00:15:38,339 which is two-thirds for this Resource Allocation index. 248 00:15:38,339 --> 00:15:41,277 And if we look at for example, nodes E and I, 249 00:15:41,277 --> 00:15:45,336 we find that well, they have one common node which is node G. 250 00:15:45,336 --> 00:15:50,601 And node G has a degree of 4, so it has a score of 1 over 251 00:15:50,601 --> 00:15:55,399 4 because G belongs to same community as E and I. 252 00:15:55,399 --> 00:15:58,404 However, if we look at two nodes that are not in the same community like A and G. 253 00:15:58,404 --> 00:16:03,476 Then they would have score 0 because their common neighbor, while they have one, 254 00:16:03,476 --> 00:16:08,128 namely E, belongs to a different community as at least one of the two nodes. 255 00:16:08,128 --> 00:16:11,942 And so, it doesn't contribute anything to the sum, so 256 00:16:11,942 --> 00:16:14,795 these two don't get anything in the sum. 257 00:16:14,795 --> 00:16:17,735 So we get a score of 0. We can use this function in network X, 258 00:16:17,735 --> 00:16:23,350 ra_index_soundarajan_hopcroft to compute the scores of all the non edges. 259 00:16:23,350 --> 00:16:30,121 And here, we find that I, H has a score of 0.25, whereas A, G has score of 0. 260 00:16:30,121 --> 00:16:34,161 Again because A, G, their common neighbor is not in the same community, 261 00:16:34,161 --> 00:16:35,411 at least one of A and G. 262 00:16:35,411 --> 00:16:40,877 And so in this case again, we find that I, H has a higher score. 263 00:16:40,877 --> 00:16:44,873 Okay, so these were the seven measures I wanted to talk about today and 264 00:16:44,873 --> 00:16:46,578 I want to point out two things. 265 00:16:46,578 --> 00:16:52,024 One, none of these measures actually tell you whether or not you should 266 00:16:52,024 --> 00:16:57,395 predict that a particular edge is going to come up in the future or not. 267 00:16:57,395 --> 00:17:00,993 It just gives a score that is supposed to give you a sense for whether or 268 00:17:00,993 --> 00:17:03,240 not these two nodes are likely to connect. 269 00:17:03,240 --> 00:17:07,996 The second thing is that different measures can give you different scores, 270 00:17:07,996 --> 00:17:08,523 right? 271 00:17:08,523 --> 00:17:13,123 So for example, we saw that some measures would give the edge H, I, 272 00:17:13,123 --> 00:17:17,585 a higher score that A,G and some measures would do the opposite. 273 00:17:17,585 --> 00:17:21,413 And so these measures aren't necessarily consistent with each other. 274 00:17:21,413 --> 00:17:24,981 So if you're actually trying to solve the link-prediction problem, 275 00:17:24,981 --> 00:17:28,913 typically what would happen is that you would use these measures as features. 276 00:17:28,913 --> 00:17:33,203 And then you would use a classifier, if you have some label data, you would train 277 00:17:33,203 --> 00:17:37,510 a classifier and use these measures as features in order to make the prediction. 278 00:17:37,510 --> 00:17:38,486 And so in summary, 279 00:17:38,486 --> 00:17:42,451 we talked about the link prediction problem which says that given a network, 280 00:17:42,451 --> 00:17:46,178 we´re tying to predict which edges are going to be formed in the future. 281 00:17:46,178 --> 00:17:50,722 And to do so, we've talked about the five different measures, the number of common 282 00:17:50,722 --> 00:17:55,522 neighbors, the Jaccard coefficient, which takes the number of common neighbors, but 283 00:17:55,522 --> 00:17:59,236 normalizes by the total number of neighbors that the two nodes have. 284 00:17:59,236 --> 00:18:02,835 The Resource Allocation index which is thinking along the lines of, 285 00:18:02,835 --> 00:18:06,933 if I know I needed to pass information or pass a resource to another node through 286 00:18:06,933 --> 00:18:10,555 their common neighbors, how much of that would actually get there? 287 00:18:10,555 --> 00:18:15,269 The Adamic-Adar index which is similar to the Resource Allocation index, but 288 00:18:15,269 --> 00:18:17,459 it takes the log in the denominator. 289 00:18:17,459 --> 00:18:21,761 And the preferential attachment score which bases the score on the idea that in 290 00:18:21,761 --> 00:18:26,341 preferential attachment, nodes with high degree tend to accumulate more edges. 291 00:18:26,341 --> 00:18:30,096 As well as two measures that require community information. 292 00:18:30,096 --> 00:18:34,721 So if you do have community information on your network, then you can use these two, 293 00:18:34,721 --> 00:18:37,670 and they're very similar to other ones we saw above. 294 00:18:37,670 --> 00:18:41,208 We have one that takes the common neighbors and it gives a bonus for 295 00:18:41,208 --> 00:18:44,955 the common neighbors that are in the same community as the two nodes. 296 00:18:44,955 --> 00:18:49,658 And then the Resource Allocation one which only considers common 297 00:18:49,658 --> 00:18:53,858 neighbors that are in the same community as the two nodes. 298 00:18:53,858 --> 00:18:55,268 And this is all for this video, I hope to you see next time, thanks.