1 00:00:08,050 --> 00:00:12,055 Hi. Today we're going to be talking about Triadic Closure. 2 00:00:12,055 --> 00:00:16,040 Triadic Closure is the tendency for people who share lots of connections, 3 00:00:16,040 --> 00:00:18,750 to form a connection themselves to become connected. 4 00:00:18,750 --> 00:00:20,780 So, people who share lots of 5 00:00:20,780 --> 00:00:25,095 friends have an increased likelihood of becoming connected themselves. 6 00:00:25,095 --> 00:00:28,875 There are many mechanisms that give rise to this process. 7 00:00:28,875 --> 00:00:33,350 But, today we're going to be focusing on figuring out how to measure in a network. 8 00:00:33,350 --> 00:00:36,275 So, let's say you have a network like this, and you're asked, 9 00:00:36,275 --> 00:00:39,750 what edges are likely to come to the network next? 10 00:00:39,750 --> 00:00:42,190 What edges are likely to arrive? 11 00:00:42,190 --> 00:00:44,750 Well, Triadic Closure would say that those edges that closed 12 00:00:44,750 --> 00:00:47,930 triangles are good candidates for edges that may show up next. 13 00:00:47,930 --> 00:00:51,920 So, here, all the red edges form closed triangles, 14 00:00:51,920 --> 00:00:55,405 and so, these are good candidates for edges that may show up. 15 00:00:55,405 --> 00:00:58,115 However, we don't always have time stamps, 16 00:00:58,115 --> 00:01:03,105 or we don't always know the ordering in which the edges come into the network. 17 00:01:03,105 --> 00:01:07,100 Sometimes, we're just given a static network with no time stamps, and sometimes, 18 00:01:07,100 --> 00:01:10,670 we want to know whether Triadic Closure is present in this network, 19 00:01:10,670 --> 00:01:13,015 whether it has lots of triangles or not. 20 00:01:13,015 --> 00:01:15,425 And so, what we're going to be talking about in this video is, 21 00:01:15,425 --> 00:01:18,762 how can we measure the prevalence of Triadic Closure in a network? 22 00:01:18,762 --> 00:01:23,475 Another way of referring to Triadic Closure is Clustering. 23 00:01:23,475 --> 00:01:25,510 So, lots of the definitions that we're going to be 24 00:01:25,510 --> 00:01:28,550 covering today are referred to as Clustering. 25 00:01:28,550 --> 00:01:32,775 So, we'll start with a local version of measuring Clustering. 26 00:01:32,775 --> 00:01:37,395 We're going to be measuring Clustering from the point of view of a single node. 27 00:01:37,395 --> 00:01:40,400 And, this is called a Local Clustering Coefficient. 28 00:01:40,400 --> 00:01:43,310 And, the way it's defined is the fraction 29 00:01:43,310 --> 00:01:46,970 of pairs of the nodes friends that are friends with each other. 30 00:01:46,970 --> 00:01:48,180 The best way to show you how Local Clustering 31 00:01:48,180 --> 00:01:51,413 Coefficient works is by showing you an example. 32 00:01:51,413 --> 00:01:56,050 So, let's say, you wanted to compute the Clustering Coefficient of node C. What you 33 00:01:56,050 --> 00:01:58,340 would need to do is to take the ratio of the number of 34 00:01:58,340 --> 00:02:01,145 pairs of C's friends who are friends with each other, 35 00:02:01,145 --> 00:02:06,025 and the total number of pairs of C's friends. 36 00:02:06,025 --> 00:02:08,960 Okay. So, C has four friends in this network. 37 00:02:08,960 --> 00:02:12,290 That means that C has a degree of four. 38 00:02:12,290 --> 00:02:14,080 That's what we refer to as degree. 39 00:02:14,080 --> 00:02:16,070 It's the number of connections that a node has. 40 00:02:16,070 --> 00:02:18,080 And, we refer to it as DC as well. 41 00:02:18,080 --> 00:02:21,580 So, DC here, which the degree of C is four. 42 00:02:21,580 --> 00:02:25,170 Now, how many pairs of C's friends are there? 43 00:02:25,170 --> 00:02:28,430 Well, there are four friends of C, 44 00:02:28,430 --> 00:02:30,065 and you can easily see that, 45 00:02:30,065 --> 00:02:32,780 if you have four pairs of four people, 46 00:02:32,780 --> 00:02:35,420 then there are six total possible pairs of people. 47 00:02:35,420 --> 00:02:38,570 And so, the total number of pairs of C's friends is six. 48 00:02:38,570 --> 00:02:41,675 Now, this is easy to see because there is only four friends of C, 49 00:02:41,675 --> 00:02:44,450 but sometimes, there are many more and 50 00:02:44,450 --> 00:02:47,720 it might be harder to see how many possible pairs of friends you have. 51 00:02:47,720 --> 00:02:52,150 So, what you can do is you can just use this formula here which tells you how many. 52 00:02:52,150 --> 00:02:54,875 It's dc times dc-1 over two. 53 00:02:54,875 --> 00:02:57,695 In this case, that number is six, 54 00:02:57,695 --> 00:03:00,780 which is 12 or 2. 55 00:03:00,780 --> 00:03:04,010 Okay. So, that will be our denominator. What about the numerator? 56 00:03:04,010 --> 00:03:08,300 The number of pairs of friends of C who are friends with each other. 57 00:03:08,300 --> 00:03:12,650 Well, there are only two pairs of friends of C that are friends with each other. 58 00:03:12,650 --> 00:03:16,210 AB and EF. So, that number is two. 59 00:03:16,210 --> 00:03:21,345 So then, the Local Clustering Coefficient of node C is two over six or one-third. 60 00:03:21,345 --> 00:03:24,470 That means that one-third of all the possible pairs of friends of C 61 00:03:24,470 --> 00:03:28,510 who could be friends, are actually friends. 62 00:03:28,510 --> 00:03:30,605 Okay. Let's do another example. 63 00:03:30,605 --> 00:03:34,025 Compute the Local Clustering Coefficient of node F. Again, 64 00:03:34,025 --> 00:03:36,230 we need to compute the ratio of 65 00:03:36,230 --> 00:03:38,960 the number of pairs of F's friends who are friends with each other, 66 00:03:38,960 --> 00:03:42,035 and the total number of pairs of F's friends. 67 00:03:42,035 --> 00:03:44,640 So, we'll do the same thing here. 68 00:03:44,640 --> 00:03:46,660 F has a degree of three. 69 00:03:46,660 --> 00:03:52,930 So, the number of pairs of F's friends is three times two over two which is three. 70 00:03:52,930 --> 00:03:58,135 And then, there's only one pair of friends of F who are actually friends with each other. 71 00:03:58,135 --> 00:04:01,515 That's C and E. And so, 72 00:04:01,515 --> 00:04:05,630 the Local Clustering Coefficient of F is also one-third. 73 00:04:05,630 --> 00:04:06,980 All right. 74 00:04:06,980 --> 00:04:08,085 And one last example. 75 00:04:08,085 --> 00:04:12,200 Compute the Local Clustering Coefficient of node J. All right. 76 00:04:12,200 --> 00:04:17,790 So, node J has only one friend which is node I, 77 00:04:17,790 --> 00:04:22,040 which means that J actually has zero pairs of friends. 78 00:04:22,040 --> 00:04:24,620 And, because that's what we're supposed to put in the denominator, 79 00:04:24,620 --> 00:04:27,215 we're in trouble because we cannot divide by zero. 80 00:04:27,215 --> 00:04:30,325 And so, what we're going to do for cases like this, 81 00:04:30,325 --> 00:04:35,680 where the definition doesn't work for nodes that have less than two friends, 82 00:04:35,680 --> 00:04:37,540 is we're going to assume that nodes that have 83 00:04:37,540 --> 00:04:40,270 less than two friends have a Local Clustering Coefficient of zero. 84 00:04:40,270 --> 00:04:44,550 And this is consistent with what network X does. All right. 85 00:04:44,550 --> 00:04:45,780 So, toggling network X, 86 00:04:45,780 --> 00:04:49,935 how do you compute the Local Clustering Coefficient using network X? 87 00:04:49,935 --> 00:04:53,700 Well, let's say we load up this graph in the way that we already know how to do it, 88 00:04:53,700 --> 00:04:56,130 and we compute the Clustering. 89 00:04:56,130 --> 00:04:57,930 We use the function Clustering to compute 90 00:04:57,930 --> 00:05:03,055 the Local Clustering Coefficient of node F. This case, it's 0.33. 91 00:05:03,055 --> 00:05:04,950 So, we have same. 92 00:05:04,950 --> 00:05:07,350 For node A, it is 0.66, 93 00:05:07,350 --> 00:05:09,325 and for node J, 94 00:05:09,325 --> 00:05:11,800 as we had seen, it is zero. 95 00:05:11,800 --> 00:05:14,005 Okay. So, this allows you to compute 96 00:05:14,005 --> 00:05:17,025 the Local Clustering Coefficient of each node in the graph. 97 00:05:17,025 --> 00:05:20,170 But, what we were interested in is trying to figure out 98 00:05:20,170 --> 00:05:23,544 whether Triadic Closure is prevalent in the whole network. 99 00:05:23,544 --> 00:05:26,830 And so, how do we go from having a local measure of 100 00:05:26,830 --> 00:05:29,710 Local Clustering Coefficient for each node to 101 00:05:29,710 --> 00:05:33,095 a global measure of Clustering Coefficient for the whole network? 102 00:05:33,095 --> 00:05:35,410 We're going to talk about two different approaches. 103 00:05:35,410 --> 00:05:37,630 The first one, which is pretty simple, straightforward, 104 00:05:37,630 --> 00:05:42,520 is to simply take the average Local Clustering Coefficient or all the nodes in the graph. 105 00:05:42,520 --> 00:05:45,340 And, you can do this in network X by using 106 00:05:45,340 --> 00:05:48,430 the function average Clustering of the graph G. And, 107 00:05:48,430 --> 00:05:52,045 in this case, that is 0.29. 108 00:05:52,045 --> 00:05:53,905 That's approach number one. 109 00:05:53,905 --> 00:05:58,150 A second approach, it's the following. 110 00:05:58,150 --> 00:06:01,105 We're going to try to measure the percentage of 111 00:06:01,105 --> 00:06:04,450 open triads in the network that are triangles. 112 00:06:04,450 --> 00:06:07,660 Okay. So, what our open triads and what are triangles? 113 00:06:07,660 --> 00:06:12,690 Triangles are simply three nodes that are connected by three edges. 114 00:06:12,690 --> 00:06:16,350 And this is called a triangle because it looks like a triangle. 115 00:06:16,350 --> 00:06:22,275 Now, open triads are three nodes that are connected by only two edges. 116 00:06:22,275 --> 00:06:24,730 The thing to notice here is that 117 00:06:24,730 --> 00:06:28,746 a triangle actually contains three different open triads, right? 118 00:06:28,746 --> 00:06:32,020 So, if we consider this triangle here, 119 00:06:32,020 --> 00:06:34,891 you will notice that it contains three different open triads. 120 00:06:34,891 --> 00:06:40,700 The first open triad considers the three nodes and all the edges, 121 00:06:40,700 --> 00:06:45,110 these two edges but not this one. 122 00:06:45,110 --> 00:06:47,490 That is the first open triad. 123 00:06:47,490 --> 00:06:53,340 But, you can also consider the three nodes and these two edges in this one. 124 00:06:53,340 --> 00:06:57,510 Or, we could consider the three nodes and these two edges but not this one. 125 00:06:57,510 --> 00:07:00,420 Right. So, inside each triangle, 126 00:07:00,420 --> 00:07:03,600 there are three different open triads. 127 00:07:03,600 --> 00:07:06,810 So, if you go out in the network and count how many triangles it has, 128 00:07:06,810 --> 00:07:09,600 and then it counts how many possible open triads it has, 129 00:07:09,600 --> 00:07:11,425 for each time that you see a triangle, 130 00:07:11,425 --> 00:07:14,045 you're going to count three different open triads. 131 00:07:14,045 --> 00:07:15,570 And so, what we're going to do for 132 00:07:15,570 --> 00:07:18,300 the second approach for measuring Clustering Coefficient, 133 00:07:18,300 --> 00:07:20,220 which is actually called the Transitivity, 134 00:07:20,220 --> 00:07:23,250 is simply that it's going to take the number of closed triads, 135 00:07:23,250 --> 00:07:24,485 which are the triangles, 136 00:07:24,485 --> 00:07:28,335 multiplied times three divided by the number of open triads. 137 00:07:28,335 --> 00:07:35,086 And that is the percentage of open triads that are actually triangles or close triads. 138 00:07:35,086 --> 00:07:37,840 You can use network X to get 139 00:07:37,840 --> 00:07:41,200 the Transitivity of the network by using the function Transitivity. 140 00:07:41,200 --> 00:07:45,370 And, in this case, this network has a Transitivity of 0.41. 141 00:07:45,370 --> 00:07:49,840 Okay. So, we have two different ways of measuring the global Clustering Coefficient. 142 00:07:49,840 --> 00:07:51,455 Are these two ways the same? 143 00:07:51,455 --> 00:07:54,275 Which one is better? Are there are differences between the two? 144 00:07:54,275 --> 00:07:57,330 Well, it turns out that there are differences between the two. 145 00:07:57,330 --> 00:08:00,670 They both try to measure the tendency for the edges to form triangles, 146 00:08:00,670 --> 00:08:02,770 but it turns out the Transitivity weights 147 00:08:02,770 --> 00:08:05,910 the nodes with a larger number of connections higher. 148 00:08:05,910 --> 00:08:08,970 It weights the nodes with a larger degree higher. 149 00:08:08,970 --> 00:08:12,180 The best way to see that is by looking at examples. 150 00:08:12,180 --> 00:08:16,630 So, here is this graph that kind of looks like a wheel. 151 00:08:16,630 --> 00:08:18,370 If you look at this graph closely, 152 00:08:18,370 --> 00:08:22,806 you'll find that most nodes actually have a pretty high Local Clustering Coefficient. 153 00:08:22,806 --> 00:08:25,120 So, all the nodes that are on the outside of 154 00:08:25,120 --> 00:08:29,080 the wheel have a Local Clustering Coefficient of one because, 155 00:08:29,080 --> 00:08:30,670 each one of these nodes, 156 00:08:30,670 --> 00:08:33,085 you see that it has two connections. 157 00:08:33,085 --> 00:08:34,930 So, he has one pair friends, 158 00:08:34,930 --> 00:08:37,530 and that pair friend is connected. 159 00:08:37,530 --> 00:08:40,420 So, this node here has a Local Clustering Coefficient of 160 00:08:40,420 --> 00:08:45,635 one and the same is true for all the nodes on the outside of the wheel. 161 00:08:45,635 --> 00:08:49,670 So, most nodes have a high Local Clustering Coefficient. 162 00:08:49,670 --> 00:08:52,515 However, if you consider the node inside the wheel, 163 00:08:52,515 --> 00:08:53,955 the central node there, 164 00:08:53,955 --> 00:08:59,715 that one has a pretty high degree but it has a very low Clustering Coefficient. 165 00:08:59,715 --> 00:09:01,665 That is because it has many, 166 00:09:01,665 --> 00:09:04,290 many connections in many pairs of connections and only a 167 00:09:04,290 --> 00:09:07,460 few of those are actually connected to each other. 168 00:09:07,460 --> 00:09:09,390 But, most of them are not connected. 169 00:09:09,390 --> 00:09:11,900 For example, these two nodes are not connected. 170 00:09:11,900 --> 00:09:13,165 These two nodes are not connected. 171 00:09:13,165 --> 00:09:14,784 These two nodes are not connected and so on. 172 00:09:14,784 --> 00:09:19,123 Even though all of them are friends with that central node. 173 00:09:19,123 --> 00:09:21,855 So, in this graph, 174 00:09:21,855 --> 00:09:25,630 the average Clustering Coefficient is pretty high, 175 00:09:25,630 --> 00:09:27,550 it's 0.93 because most nodes have 176 00:09:27,550 --> 00:09:31,885 a very high Local Clustering Coefficient, except for one. 177 00:09:31,885 --> 00:09:35,310 However, the Transitivity of this network is 0.23. 178 00:09:35,310 --> 00:09:39,445 And that's because Transitivity weights the nodes with high degree higher. 179 00:09:39,445 --> 00:09:40,825 And so, in this network, 180 00:09:40,825 --> 00:09:43,690 there's one node with a very high degree compared to the others that has 181 00:09:43,690 --> 00:09:47,255 a very small Local Clustering Coefficient compared to the others, 182 00:09:47,255 --> 00:09:49,200 and Transitivity penalizes that. 183 00:09:49,200 --> 00:09:51,991 So, you get a much lower Transitivity. 184 00:09:51,991 --> 00:09:54,825 Okay. Can you see an example that goes the other way around? 185 00:09:54,825 --> 00:09:57,657 Well, here is this network. In this network, 186 00:09:57,657 --> 00:10:01,615 most nodes have a very low Local Clustering Coefficient. 187 00:10:01,615 --> 00:10:07,065 So, each one of these outer nodes here has a Local Clustering Coefficient 188 00:10:07,065 --> 00:10:10,080 of zero because they either have 189 00:10:10,080 --> 00:10:14,210 only one friend or they have two friends but those two are not connected. 190 00:10:14,210 --> 00:10:16,480 And, there are 15 nodes like that. 191 00:10:16,480 --> 00:10:20,025 The nodes inside here, 192 00:10:20,025 --> 00:10:22,605 there are only five nodes like that and they have high degree, 193 00:10:22,605 --> 00:10:25,910 and then they have high Local Clustering Coefficient. 194 00:10:25,910 --> 00:10:28,860 So, when you look at the average Clustering Coefficient and Transitivity, 195 00:10:28,860 --> 00:10:31,560 you find that the average Local Clustering Coefficient 196 00:10:31,560 --> 00:10:34,425 of this network is pretty low because most nodes, 197 00:10:34,425 --> 00:10:35,715 the 15 outer nodes, 198 00:10:35,715 --> 00:10:38,790 have very low Local Clustering Coefficient. 199 00:10:38,790 --> 00:10:42,180 However, the Transitivity is high because the nodes with 200 00:10:42,180 --> 00:10:46,536 high degree happen to have high Local Clustering Coefficient. 201 00:10:46,536 --> 00:10:50,445 So, these two graphs showed you the differences between the Local Clustering Coefficient, 202 00:10:50,445 --> 00:10:53,175 the average Local Clustering Coefficient, and Transitivity. 203 00:10:53,175 --> 00:10:59,140 One weights the nodes with a large degree higher. 204 00:10:59,140 --> 00:11:02,195 In summary, we've learned that Clustering Coefficient measures 205 00:11:02,195 --> 00:11:06,130 the degree to which nodes in a network tend to cluster or form triangles. 206 00:11:06,130 --> 00:11:09,215 And there are several ways in which you can measure this. 207 00:11:09,215 --> 00:11:10,765 So, the first way, 208 00:11:10,765 --> 00:11:15,745 we look at the Local Clustering Coefficient and this is measured on a node by node basis. 209 00:11:15,745 --> 00:11:19,645 And in two other ways, we found the global Clustering Coefficient which measures 210 00:11:19,645 --> 00:11:24,671 Clustering Coefficient on a global scale for the whole network. 211 00:11:24,671 --> 00:11:26,374 For the Local Clustering Coefficient, 212 00:11:26,374 --> 00:11:28,510 this one is defined as simply the fraction of 213 00:11:28,510 --> 00:11:31,600 pairs of nodes friends who are friends with each other. 214 00:11:31,600 --> 00:11:35,035 And just to remind you, in this case, 215 00:11:35,035 --> 00:11:39,100 the Local Clustering Coefficient of node C was one-third because one-third 216 00:11:39,100 --> 00:11:43,810 of the pairs of friends of C are actually friends with each other. 217 00:11:43,810 --> 00:11:45,860 For global Clustering Coefficient, 218 00:11:45,860 --> 00:11:48,340 the first way in which we could measure these was by simply 219 00:11:48,340 --> 00:11:51,530 taking the average of the Local Clustering Coefficient over all the nodes. 220 00:11:51,530 --> 00:11:55,375 And you could use the function average Clustering in network X to do it. 221 00:11:55,375 --> 00:11:59,365 And then, the second way was this thing called Transitivity, 222 00:11:59,365 --> 00:12:01,600 which was the ratio of the number of 223 00:12:01,600 --> 00:12:05,065 triangles and the number of open triads in a network. 224 00:12:05,065 --> 00:12:09,190 And this one puts a larger weight on high degree nodes compared to 225 00:12:09,190 --> 00:12:12,130 the average Local Clustering Coefficient and you can 226 00:12:12,130 --> 00:12:16,050 measure it in network X using the function Transitivity. 227 00:12:16,050 --> 00:12:17,740 This is all for today. Thank you for watching. 228 00:12:17,740 --> 00:12:20,000 And I hope to see you next time.