1 00:00:00,470 --> 00:00:03,090 Our general plan of attack today will be to 2 00:00:03,090 --> 00:00:06,890 think about generative models for networks. 3 00:00:06,890 --> 00:00:08,710 So our goal will be the following. 4 00:00:08,710 --> 00:00:09,490 Actually, first, 5 00:00:09,490 --> 00:00:14,270 I will start tell, talk, telling you about, how do we generate networks, right? 6 00:00:14,270 --> 00:00:17,880 So if I have some model, how can I generate a network, a graph, 7 00:00:17,880 --> 00:00:18,620 from this model? 8 00:00:18,620 --> 00:00:20,070 Right? Where, you know, 9 00:00:20,070 --> 00:00:21,930 nodes, nodes represent some entities or 10 00:00:21,930 --> 00:00:25,870 people and edges represent let's say friendships and so on. 11 00:00:25,870 --> 00:00:28,920 And our goal in some sense will be that we will want to 12 00:00:28,920 --> 00:00:32,950 define a model that is able to generate realistic looking graphs. 13 00:00:32,950 --> 00:00:35,387 And then in the second step what we will do is to say, 14 00:00:35,387 --> 00:00:39,104 actually, given a real graph, imagine, given, like, a Facebook graph. 15 00:00:41,633 --> 00:00:45,049 What we will want to do is we will want to go and fit, or 16 00:00:45,049 --> 00:00:48,960 find a generative model that has generated our graph. 17 00:00:48,960 --> 00:00:52,360 And by doing so we will go and detect communities. 18 00:00:52,360 --> 00:00:55,350 So this is the overall idea for today. 19 00:00:56,840 --> 00:01:00,840 Our next thing now is to actually say, what is a good generative models for, 20 00:01:00,840 --> 00:01:02,260 model for networks. 21 00:01:02,260 --> 00:01:04,630 So, let me tell you how to think about this. 22 00:01:04,630 --> 00:01:05,310 All right? 23 00:01:05,310 --> 00:01:09,570 Our goal is to say we want to define a generative model for network. 24 00:01:09,570 --> 00:01:13,270 And in some sense, our model will have a set of parameters, right, that we will, 25 00:01:13,270 --> 00:01:17,500 kind of, later want to estimate given, given our real data. 26 00:01:17,500 --> 00:01:21,170 And by estimating those parameters, we will in some sense implicitly 27 00:01:21,170 --> 00:01:24,600 actually detect these social communities that I was talking about. 28 00:01:24,600 --> 00:01:27,620 So the question is, given a set of nodes, 29 00:01:27,620 --> 00:01:31,990 how do communities generate the edges of the underlying social network? 30 00:01:31,990 --> 00:01:36,010 So we need kind of define the way the edges arise given a set of notes. 31 00:01:37,340 --> 00:01:40,340 The model we will be talking about is called 32 00:01:40,340 --> 00:01:42,500 the community-affiliation graph model. 33 00:01:42,500 --> 00:01:44,070 And the way this works is the following. 34 00:01:44,070 --> 00:01:45,360 All right? So our goal is, 35 00:01:45,360 --> 00:01:48,360 we want to define the model that will generate a network. 36 00:01:48,360 --> 00:01:51,120 So the model has specified the following. 37 00:01:51,120 --> 00:01:55,890 We have a set of nodes V, these are the nodes of my underlying social network. 38 00:01:55,890 --> 00:01:57,350 Imagine here they are. 39 00:01:57,350 --> 00:02:00,750 And then I have also another set of nodes that I will talk, and 40 00:02:00,750 --> 00:02:02,640 I will call them communities. 41 00:02:02,640 --> 00:02:04,830 I call this set C, okay. 42 00:02:04,830 --> 00:02:06,360 And then what I will do is the following, 43 00:02:06,360 --> 00:02:10,630 I will say that every node can be a member of any of the communities. 44 00:02:10,630 --> 00:02:14,330 So in some sense I will have these edges here that are basically community 45 00:02:14,330 --> 00:02:15,250 memberships, right. 46 00:02:15,250 --> 00:02:19,180 So what this will tell me is that the blue node is member of community A, 47 00:02:19,180 --> 00:02:23,600 green nodes are members of community B, and the four red nodes, 48 00:02:23,600 --> 00:02:26,660 they belong both to community A and to community C. 49 00:02:26,660 --> 00:02:30,340 So this is now my specification of my model. 50 00:02:30,340 --> 00:02:31,880 Now what I want to do is, 51 00:02:31,880 --> 00:02:34,540 given this model, I will want to generate the network. 52 00:02:35,610 --> 00:02:39,800 So the affiliation graph model is a generative model for networks, 53 00:02:39,800 --> 00:02:44,720 and the model can be specified as with, kind of, four types of parameters. 54 00:02:44,720 --> 00:02:47,030 I need to know the set of nodes in the network. 55 00:02:47,030 --> 00:02:48,170 This is the set V. 56 00:02:48,170 --> 00:02:50,500 I need to know the set of communities. 57 00:02:50,500 --> 00:02:52,050 That is the set C. 58 00:02:52,050 --> 00:02:55,680 I need to know the set of edges, the membership edges between nodes and 59 00:02:55,680 --> 00:02:57,300 the corresponding communities. 60 00:02:57,300 --> 00:03:00,320 And then what we will also have is every community has a single 61 00:03:00,320 --> 00:03:05,130 parameter associated with it, and we call this parameter p sub A, p sub B, 62 00:03:05,130 --> 00:03:08,660 and in general, there is a set of these parameters that we will call p sub C. 63 00:03:08,660 --> 00:03:09,160 Okay? 64 00:03:09,160 --> 00:03:13,740 So the, the model above is uniquely defined by this tuple of 65 00:03:13,740 --> 00:03:16,670 four four different sets. 66 00:03:16,670 --> 00:03:20,270 Now kind of what we want to do next is to specify, 67 00:03:20,270 --> 00:03:23,050 how does this model generate the network, right? 68 00:03:23,050 --> 00:03:27,270 We need to define, what is the process from going from this affiliation network 69 00:03:27,270 --> 00:03:31,930 here on the left to actually the edges of the underlying social network. 70 00:03:31,930 --> 00:03:37,220 For example, one thing we already know is that, that the set V, the number of nodes 71 00:03:37,220 --> 00:03:42,170 at the bottom here, is exactly the number of nodes of our social network. 72 00:03:42,170 --> 00:03:45,140 What we need to do now is define how are these edges of 73 00:03:45,140 --> 00:03:49,910 the social network created or how do they arise out of our model. 74 00:03:49,910 --> 00:03:51,632 So, the way we do this, is to think, 75 00:03:51,632 --> 00:03:55,170 to think about the affiliation graph modeling the following way. 76 00:03:55,170 --> 00:03:58,240 We can think that every of the communities that a pair of 77 00:03:58,240 --> 00:04:01,250 nodes shares generates an edge with some probability. 78 00:04:01,250 --> 00:04:06,970 So in some sense the idea is, if we both belong to soccer community, 79 00:04:06,970 --> 00:04:10,330 and we also both go, attend the same university, then because we 80 00:04:10,330 --> 00:04:14,150 are playing soccer together, that has some probability of us being friends. 81 00:04:14,150 --> 00:04:16,920 And also because we, I don't know, attend the same university, 82 00:04:16,920 --> 00:04:20,490 that has us also some probability for us becoming friends. 83 00:04:20,490 --> 00:04:23,998 So the idea is that each of such social communities in some sense creates 84 00:04:23,998 --> 00:04:27,865 an opportunity for a pair of nodes to meet and create a friendship connection. 85 00:04:27,865 --> 00:04:32,746 So the idea is that every community, let's call this community A, has a, 86 00:04:32,746 --> 00:04:34,991 has a single parameter p sub A, and 87 00:04:34,991 --> 00:04:40,183 this parameter tells us with, how likely, with what probability does a pair of 88 00:04:40,183 --> 00:04:44,780 nodes connect if they both belong to this community A, okay? 89 00:04:44,780 --> 00:04:47,920 So now we can ask, okay, given a pair of nodes and all the communities they 90 00:04:47,920 --> 00:04:51,500 belong to, how likely is this pair of nodes to connect with each other. 91 00:04:51,500 --> 00:04:54,962 And the way we will do this is we will say they connect if at 92 00:04:54,962 --> 00:04:59,031 least one of the communities they have in common creates an edge. 93 00:04:59,031 --> 00:05:02,032 And the formula that describes this, I have it down here. 94 00:05:02,032 --> 00:05:05,141 All we are saying is the probability that node u and v 95 00:05:05,141 --> 00:05:10,845 are connected is 1 minus the product over all the communities they have in common. 96 00:05:10,845 --> 00:05:15,130 1 minus the probability of each given community creating a connection. 97 00:05:15,130 --> 00:05:18,130 The way to think about this formula is the following, right. 98 00:05:18,130 --> 00:05:21,518 1 minus p sub C basically tells us, what is the probability that they, 99 00:05:21,518 --> 00:05:25,600 that the pair of nodes does not connect, because they have a community in common. 100 00:05:25,600 --> 00:05:28,370 So the product over these probabilities tells us, 101 00:05:28,370 --> 00:05:31,750 what is the probability that all, all of the communities they, 102 00:05:31,750 --> 00:05:35,760 they have in common, all of these said, no, I don't want a connection. 103 00:05:35,760 --> 00:05:38,750 So 1 minus that is the probability that at least one of 104 00:05:38,750 --> 00:05:40,670 the communities created a connection. 105 00:05:42,190 --> 00:05:44,800 So one way to think about this expression here is that in 106 00:05:44,800 --> 00:05:46,630 some sense this is an OR function. 107 00:05:46,630 --> 00:05:49,530 A pair of nodes will connect if at least one of 108 00:05:49,530 --> 00:05:53,280 the communities they have in common actually creates, creates an edge. 109 00:05:54,330 --> 00:05:57,050 What is also interesting here is that we already see that 110 00:05:57,050 --> 00:06:00,760 this is an increasing function in the number of common communities. 111 00:06:00,760 --> 00:06:04,220 Why does it increase, is because the more communities we have in common, 112 00:06:04,220 --> 00:06:06,460 the more numbers are in this product. 113 00:06:07,470 --> 00:06:11,410 Each of the elements of this product is a number smaller than 1, so 114 00:06:11,410 --> 00:06:16,765 the more numbers that are smaller than 1 we multiply together, the smaller 115 00:06:16,765 --> 00:06:22,064 the total product, so 1 minus a small number is, is a bigger number, right? 116 00:06:22,064 --> 00:06:25,100 So this means that the more communities a pair of nodes has in common, 117 00:06:25,100 --> 00:06:27,660 the more likely they will be to link with each other. 118 00:06:29,150 --> 00:06:33,457 So now we specify basically how to create edges of our network, right. 119 00:06:33,457 --> 00:06:35,218 The way we create edges here is that for 120 00:06:35,218 --> 00:06:38,940 every pair of nodes, we ask, what are the communities you have in common? 121 00:06:38,940 --> 00:06:41,260 And we apply this formula down here and 122 00:06:41,260 --> 00:06:46,300 say that this way we compute the total probability of a connection, flip a coin, 123 00:06:46,300 --> 00:06:48,800 and if the coin says yes, we create a connection, right? 124 00:06:48,800 --> 00:06:51,000 The nodes that have multiple communities in common, 125 00:06:51,000 --> 00:06:55,010 they will basically get multiple chances, in some sense, to create an edge. 126 00:06:55,010 --> 00:06:57,260 So what is now, what we have done so 127 00:06:57,260 --> 00:07:01,570 far is that we have our affiliation graph model of networks. 128 00:07:01,570 --> 00:07:02,670 We specify the model. 129 00:07:02,670 --> 00:07:04,750 So here is a different specification of the model, 130 00:07:04,750 --> 00:07:06,690 where we have three communities. 131 00:07:06,690 --> 00:07:10,410 Each of these communities has a different linking parameter. 132 00:07:10,410 --> 00:07:13,000 And given such model, we can now generate a network. 133 00:07:13,000 --> 00:07:14,420 Right. So, from the model, 134 00:07:14,420 --> 00:07:15,710 we can go to the network. 135 00:07:15,710 --> 00:07:19,430 Here's a picture of the network that would arise from the model above. 136 00:07:19,430 --> 00:07:21,770 What we nicely see here is that each of these communities, 137 00:07:21,770 --> 00:07:23,500 we can think of it as a tile. 138 00:07:23,500 --> 00:07:27,760 We see that, for example, the red nodes here in the overlap of all three 139 00:07:27,760 --> 00:07:30,030 communities, they are very well connected. 140 00:07:30,030 --> 00:07:33,710 We see that, for example, the pink nodes also connect heavily with each other. 141 00:07:33,710 --> 00:07:36,930 And then we see that the other parts of the communities where, kind of, 142 00:07:36,930 --> 00:07:39,540 there is no overlaps, they are less well connected. 143 00:07:39,540 --> 00:07:47,430 But the model that we specified here is able to generate us the network, below. 144 00:07:47,430 --> 00:07:50,490 So what is good about the affiliation graph model and 145 00:07:50,490 --> 00:07:53,660 the way I described the model so far is that this model is able to 146 00:07:53,660 --> 00:07:57,850 express a variety of different structures of networks. 147 00:07:57,850 --> 00:08:02,490 So for example, if I want communities, social communities or clusters that don't 148 00:08:02,490 --> 00:08:06,270 overlap with each other, this is how I could really present this using our model. 149 00:08:06,270 --> 00:08:09,790 Right, so the idea is, I have a community A, I have a community B, 150 00:08:09,790 --> 00:08:13,180 and imagine I have maybe a few edges across these two communities. 151 00:08:13,180 --> 00:08:17,697 The way I would represent this in terms of our model, the affiliation graph model, 152 00:08:17,697 --> 00:08:22,211 is basically to say, I have one community node A, I have another community node B, 153 00:08:22,211 --> 00:08:24,466 and then a set of nodes is a member of A, and 154 00:08:24,466 --> 00:08:26,560 the other set of nodes is a member of B. 155 00:08:27,600 --> 00:08:32,530 Of course, given the way I defined the formula on the previous slide, the idea 156 00:08:32,530 --> 00:08:36,850 is, if a pair of nodes has no community in common, then they link with a small 157 00:08:36,850 --> 00:08:41,220 probability epsilon, so that we still get a few edges crossing the two communities. 158 00:08:41,220 --> 00:08:43,754 So this is the idea for how to model non-overlapping or 159 00:08:43,754 --> 00:08:46,480 these kind of partition-based communities. 160 00:08:46,480 --> 00:08:49,380 If you want, we already know how to model overlapping communities. 161 00:08:49,380 --> 00:08:51,330 The idea here is I, have communities A and 162 00:08:51,330 --> 00:08:55,870 B, they overlap in this yellow area, so how does the model, AGM model look like? 163 00:08:55,870 --> 00:08:56,990 Here is the model. 164 00:08:56,990 --> 00:09:00,840 Basically, the idea is that I have these two yellow nodes that actually belong to 165 00:09:00,840 --> 00:09:04,040 both communities, to community A and community B. 166 00:09:04,040 --> 00:09:07,350 And what's interesting, we can even, like, think about nested or 167 00:09:07,350 --> 00:09:11,580 hierarchically nested communities, where we could have, you know, the mother 168 00:09:11,580 --> 00:09:17,350 community B, that then has two smaller communities A and C embedded in it. 169 00:09:17,350 --> 00:09:22,260 The way we would model this using our affiliation network model is to say, okay, 170 00:09:22,260 --> 00:09:25,230 we have three communities, the nodes at the bottom, 171 00:09:25,230 --> 00:09:27,800 every node is a member of the community B. 172 00:09:27,800 --> 00:09:28,590 But in some set, 173 00:09:28,590 --> 00:09:33,130 subset of them is also a member of A, and another subset is a member of C. 174 00:09:33,130 --> 00:09:37,230 So this way, we nicely model the hierarchy structure of the network. 175 00:09:37,230 --> 00:09:41,730 So basically the bottom line is that this model for generating networks is very 176 00:09:41,730 --> 00:09:46,160 flexible, and if somebody gives us the structure of this bipartite graph, 177 00:09:46,160 --> 00:09:50,320 this affiliation network below, we are able to generate the network. 178 00:09:50,320 --> 00:09:54,480 Of course, what we will do next is actually turn the problem around. 179 00:09:54,480 --> 00:09:57,560 We will say, given a network we want to find the model. 180 00:09:57,560 --> 00:10:00,390 So this'll be the topic of our next lecture.