The Mathematics of Breakups

Key Takeaways

in this video we'll be talking about the mathematics of breakups and my breakups we really mean anything from a rift between two people in a relationship to a schism between two corporations to even a split in a political faction into two smaller political factions now the motivating question why do we care about the mathematics of breakups why do we really want to analyze this the real question Regina answer is given some network so here's the network and we have all these are people so here's a person here's a person all these people around here these dots are all people and the links between them so a line between two people says they have something in common maybe they're part of the same family maybe they share a class at a university maybe they're part of the same recreational club for example given this network who holds the most political power in this network that is if this narrowed were to split we're not saying it's going to split but if it's not record a split into two networks to smaller groups that have no connections between each other who will be the leaders of those two groups and who will follow those leaders into those respective groups you know leaving behind the other people so it seems like to answer that question in this network it seems kind of obvious maybe it's I've suggested it by drawing these two leaders kind of big and drawing these as black lines rather than gray lines but even without that it seems kind of our intuition that these two people let's call mr. red and mrs. blue would be the leaders of the two separate groups and the people they would take with them would be for mrs. blue all these green people on the outside and mr. read all these pink people on the outside and that necessarily means in our case in our studies that if these two groups were to happen if this group were to split into two groups these links between groups so this pink to the screen would be severed this link would be severed this link between the leader of between mr. red and mrs. blue would have to be severed and all these link would be severed so those links being severed we now have two distinct groups we have the red group and we have the blue group over here so now to do our analysis this was just kind of a toy example that I drew we're gonna be looking at a real world example by researcher by the name of Wayne Zachary he did studies around nineteen seventy in a university on a karate club let's take a look now at zachary's karate Network let's expand the screen here so we see we have all the people in the network we have number one the instructor and we have number thirty-four the precedent and we have all the links between people shown by these black lines now we're going to assume this network will split into two groups we're going to look at the two people who have the highest degree the top two and as it turns out as we can kind of visually guess that's going to be the instructor number one and the president number 34 now what we'll do is we'll color the instructor number one blue will color the precedent number 34 red and what we'll do is for everybody else we'll see do they have more links to the instructor or the precedent and that really comes down to the fact that if somebody has a link to the instructor and not the precedent they get the color of the instructor and if it's the other way around you have a link to the instructor the President and not the instructor they get the color of the precedent now in the case that they have links to both or they have links to neither we leave them colored as white and try to deal with them in the next iteration all right let's expand this guy we see everyone colored a darker shade of red here is going to be with the precedent and everyone colored this lighter shade of blue here is going to be with the instructor there's still a lot of people who are colored white for example let's look at this guy this number 20 he has three links one is to the instructor when is to the President and one is to somebody else who is also colored way which is why they weren't colored in the first round because we couldn't decide whether they would go with the instructor or the precedent at this point now the next iteration what we do is we look at each person who's still colored white these people were not sure about and we look at all their neighbors so let's look at number 17 this is the person on the very left here this number 17 is connected only to blue people so we're going to assume that this person will go with the blue group the group of number one now let's look at somebody like number let's look at something like number 25 at the very bottom here this person has three connections to our two people who are colored white and another one is to number 28 which is colored red so we're going to assume this person will go with red people because they have more connections to the red group than the blue group now what about number 20 they have a connection to the main blue person the Maine Red person that's number one and 34 and just someone who's also colored white still but the fact that that number 20 comes after the number two so what happens with number two number two we see is going to be colored blue after the next iteration and so number 20 will have more connections to the blue group ie they'll have one connection to the blue group through number two and it'll have no connections to the red group that is besides 34 so it'll be colored blue as well so that's kind of how we sort out the rest of the white notes and let's see what happens when we go ahead and do our second iteration we see every single note is colored now and is colored either a blue or some kind of red so we see here our accuracy is 94.1 2% about and how many people does that come out to remember there were 34 people in the karate club so we're going to multiply that number that point 9 for 12 ish x 34 and we get 32 people predicted correctly out of 34 so that's pretty good it seems our naive approach even though it does seem very simplistic does end up working very very well through this community detection now that seemed very simplistic but it did seem to work a give us a very high accuracy but now you're probably asking you know are there more complicated methods are there more interesting methods we can use and the answer is yes the method that Wayne Zach were used in his original paper and I'll link this paper in the description because it's actually pretty interesting read the method that he used was that he looked at a minimum cut and let me define roughly I mean by that so what I mean by that is this is a cut we chose between these between this network we could have chosen any other cut really we could have drawn a cut you know something like here and we could have put these two people in their own network and put everybody else in a different network now there's probably some reason we didn't do that it doesn't seem like the right thing to do it seems like this orange cut right here which suffers these connections seems like a much better idea than to do any other kind of cut now let's kind of solidify what we mean in Zachary's Karate Club paper and the paper that he broke he had weights between each of these edges and these weights were determined by how strong the connection was or how many connections there were for example whether some people were just two classmates or whether there were classmates also they were in the same recreational club also they were you know maybe they're even brother and sister or something like that based based on those connections so for example let's just give to our network here some weights let's say each of these weights that is going to get severed through this kyra here has a weight one and that might make sense because they're between these two groups that are end up separate they might not be very strong connections maybe just connections in passing acquaintances things like that let's say these acquaintances within these two groups that we have set up here are much stronger for example maybe this one's too maybe this one's three maybe this one's five and maybe the one here is 23 you know for connections like that so now what we want to try to do and this seems like it makes sense is that we want to cut this network we want to cut it so that the the the lines were cutting the connections that were kind of severing our of the smallest way so we're getting the minimum cut so what happens when we cut it here along this orange line we're cutting one two three four so this cut has we can assign a kind of value for now what happens if we did this brown cut that would suggest a little bit earlier now this is doing a lot more for example it's cutting 12 it's cutting 34 it's cutting 5 connections and we said that this connection is not cutting this one sorry it's cutting these four connections and we're saying that these connections are weighted much more heavily for example if the connection if each of these connections is weighted to we're getting 2 4 6 8 so this cut already has value eight which is exceeding this for so based on those assumptions were making and he doesn't much more concretely in his paper I suggest you check it out i'll put the link in the description again is that we're only cutting for here so we're making the least amount of severing connections we r you know kind of cutting our losses in the least amount rather than you know cutting these high-level connections here and the same thing we don't want to put a cut on the red side because it's going to have the same issue of being higher than four so that's kind of what he did and the algorithm the exact algorithm he used to do this and I think we'll do a video on this because it's really interesting for other reasons it's called the ford-fulkerson algorithm so ford-fulkerson this algorithm actually has many many other applications and I think we will do with liana it's a very interesting algorithm but that's how we that's what I used to get the minimum cut so this actually has a lot of applications whether you use this this Ford Focus algorithm or whether you just go to the naive process that we used which got us pretty high accuracy by the way with this process he got 33 out of 34 predicted correctly so he did one better than we did which is a pretty good improvement actually so I whether use this or whether you use our method the naive method this has a lot of different applications for example this was with the karate club but you can do this with politics you can look at where political power is centered across the world maybe within the UN maybe within some other political body and you can say if this were to get split into two or three or 4k oops which would be the leaders of those k groups and you know which country is which entities would go with each of those leaders and even if the group has no intention of splitting whether it never will split it still really helps to know where the power is centered in network because that that you can you can you can look at how those people have power who those people have power over and whether there's expected to be any shift in power over a certain amount of time so hopefully this was kind of interesting in the next few videos we'll be looking a little bit deeper to machine learning will be looking at a method called k-means to predict the weather