In the past videos, we've looked at different types of graphs. We've looked at undirected graphs, directed graphs, multi-graphs, signed graphs, weighted graphs, and so on. We haven't looked at a particular type of graph that is very interesting and useful for certain types of applications, and these are called bipartite graphs. We've already told you what the actual definition of a bipartite graph, let me give you a little sense in what cases they're important or just a particular example of what describes a bipartite graph. Here's an example of fans of specific basketball teams. The nodes on green; A, B, C, D, and E, are people who are fans of basketball teams 1, 2, 3, and 4. Here the edges represent the fact that a particular fan is a fan of a particular team. One aspect of this graph is that you couldn't imagine that it would make sense to add an edge between the fans, because fans are not fans of other fans, they're fans of teams, or edges between the basketball teams because basketball teams have fans, they're not really fans of other teams. This graph has a particular structure that all the edges go from one set of nodes to another set of nodes. In this case, one set of nodes is fans and the other set of nodes is basketball teams. That's exactly what a bipartite graph is. Just to be a little bit more specific, a graph is a bipartite graph if it has two sets of nodes, which we call L and R, and every single edge connects a node from L to R. So no edge connects a node from L to another node in L, and no edge connects a node in R to another node in R. In this particular example, the two sets would be the sets of fans, this will be L, and the set of basketball teams, which would be R. Network X does not have a separate class for bipartite graph, but it does have a set of algorithms that allow us to study them and to analyze them and to do things with them. For that, we would import bipartite to get that set of algorithms. To construct this bipartite graph, what I'm going to do is I'm going to use the class graph. Like I said, there's no separate class for bipartite graphs. Now, the first thing I'm going to do is I'm going to add the nodes. To add the nodes, I'm going to use the function add_nodes_from rather than add_nodes, and what this allows me to do is to add a set of nodes from a list. Rather than adding one by one, I can add all of the nodes all at once. Then I'm going to give these set of nodes an attribute called bipartite, and I'm going to give that value zero. What I'm basically doing here is I'm telling network X that these set of nodes are going to be one side of my bipartite graph. In this case, will be the left side. Then I'll add the nodes from the other side. I'll add nodes one through four, and these will have value 1 for the bipartite attribute. Then I can add the edges, and same thing here, you can apply these to other cases not only when you're using these to construct bipartite graphs, but if you use the function add_edges_from, it allows you to add a list of edges rather than adding one edge at a time, which is very useful sometimes. Now we've constructed this bipartite graph. Notice that I gave it the name B rather than G so it stands for bipartite. What kinds of things can we do in network X with bipartite graphs? First thing, we can check if a particular graph is bipartite. For this we'd use a function is_bipartite, and this would say yes it is bipartite. Now notice that if we were to add the edge AB, so this would add, then it's like this right here, then now the graph B is no longer bipartite because there aren't two sets that are such that all the edges go from one set to the other. I'm breaking that rule when I add this edge right here, and so then when I ask if B is bipartite, it would say false, because it's no longer bipartite. Let's remove edge AB to keep our graph bipartite. What else can you do? You can also check if a set of nodes, it's a bipartition of the graph. By that I mean, is this set of nodes one of the two sets of nodes such that all the edges go from one set to the other? For example, if I construct this set X to be the nodes one through four, I can ask if this set of nodes X is a bipartition of the graph B by using this function here, and then it would tell me, yes, this is a bipartition of this graph B. Same thing if I were to add the nodes A through E, it would say that it is a bipartition. If I construct the set 1, 2, 3, 4, and the node A, and I ask whether that's a bipartition of the graph, then it would say, no, it's false because it's not true that all the edges go from this set of 1, 2, 3, 4, A, to the rest of the nodes, and so this would be false. The other thing we can do is, if we don't know which two sets are the two bipartitions of the graph, then we can ask network X to output those two sets. If we say sets of B, then it would output the two sets that are bipartitions of the graph. Notice that if we, again, add the edge AB here, then B is no longer bipartite, and so what would happen if we ask for the two bipartitions of this graph B, which is no longer bipartite, well, we'll get an error that says, graph is not bipartite, so it's not possible to find the two sets. Let's remove, again, edge AB to keep our graph bipartite. Let's look at this slightly larger example of a bipartite graph that has the same meaning. So on one side, we have fans and on the other side, we have basketball teams. Now imagine that you were interested in creating a network among the fans and have the edges represent some type of affinity in terms of what teams they follow, whether they tend to follow the same teams or not. This network could be important for viral marketing. If two people tend to follow the same teams, they might also like the same other type of product, and so you would be interested in knowing who is likely to impact whom in terms of that other product and the fact that they follow the same kinds of teams might give you that hint. This network could be useful for certain things. But let's just say that you're interested in constructing that network. Well, you can do this and what it's called, it's called the L-bipartite graph projection of the bipartite graph. What it is, is a network among the nodes in one side of the group, in this case the L side, in this case the fans, where each pair of nodes is connected if they have a common neighbor in the R side of the bipartite graph. In this case, there would be exactly a network between the fans such that they're connected if they have at least one team in common. You will have a similar definition for the R-bipartite graph. That would be a network among the basketball teams and two teams would be connected if they have at least one fan in common. What would that network look like for the fans? Again, it's a network of fans who have at least one team in common. This looks something like this. In this network, the edge AH appears in the projection because both A and H are fans of Team 1. The edge JE appears in this network because they're both fans of Team 4. You can actually get network X to give you this projected network. The way you do it is again, you define the graph, you add all the edges. We're constructing this case the bipartite graph B. Now we defined a set X to be the set of fans. Then we use the function projected graph and it takes the input, B, which is the bipartite graph. Then X, which is the set of notes that you want the projected graph on. Then you get this network. Now this is the network P. Now what if you wanted the projected graph for the teams? In this case, you would now say X is the set of basketball teams and then P will be the projected graph using that set. Then this is the network that would come out. In this network, the nodes 1 and 2 are connected because they both have at least one fan in common. They have C in common. But in fact, as you can see here, they have also B and E in common. So B, C, and D are all fans of 1 and 2. Now let's compare that with the Edge 1 and 3. Edge 1 and 3 appears here in the projected graph because both Teams 1 and 3 have H as a fan in common. But notice that it's only one fan. Edge 1 and 3 has one fan in common, whereas 1, 2 has three. This suggests that we actually probably would want to have weights on these edges. We would want to know that actually 1 and 2, yes, they have at least one in common but in this case it's three, whereas 1 and 3, they have only one fan in common. That's something we would like to capture. Indeed that's something you can capture. This is called the L-bipartite weighted graph projection. What it is, is well, just like we saw it, rather than just defining an edge in the projected graph to connect any two nodes that have at least one connection incoming on the other side, now we're going to add weights on these edges and their weights are going to be proportional to the number of common neighbors that they have. Their weighted projected graph for the basketball teams would look like this now where now we have the edges and we also have a number next to them that says how many common neighbors they have. Here I have the size of the edges be also proportional to that weight just to show you visually the difference. In network X, you can use the weighted projected graph to now output not just the projected graph, but the weighted projected graph, in this case of the basketball teams. You could do the same thing for the set of fans. In summary in this video, we've looked at bipartite graphs. The main thing is that, well the definition, what it means. Two sets of nodes and all the edges go from one set to the other and no edge goes from the set to itself. Then to construct them on network X, we're not going to use a separate class, we use the same classes though we already know. But rather we use a set of algorithms that allow us to do certain things for bipartite graphs. Now, I will note that many of the algorithms that are available only work for the graph class. That's something you have to be careful with. The kinds of things we looked at here that you can do is you can check if a graph is bipartite. You can check if set of notes is a bipartition of the graph. You can actually try to get the two bipartitions of the graph if the graph is bipartite, if not, then you'll get an error. We talked also about the projected graphs, which can be useful like in the case of the fans and basketball teams, it would be useful to see what teams have fans in common and what fans have teams in common. You can get these projections using network X with a projected graph and then the weighted projected graph, which now adds not only an edge if the two teams have at least one fan in common but it actually captures how many. This is the end of this lecture and I hope to see you in the next one.
