0:07

So, 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.

Â So before I tell you what the actual definition of a bipartite graphs,

Â let me give you a little sense for,

Â in what kinds of cases they are important,

Â or just a particular example of what describes bipartite graph.

Â So, here's an example of fans of specific basketball teams.

Â So the nodes on green A,

Â B, C, D and E,

Â are people who are fans of basketball teams,

Â 1, 2, 3, and 4.

Â And here the edges represent the fact that

Â a particular fan is a fan of a particular team.

Â So, one aspect of this graph is that you couldn't

Â imagine that it would make sense to add an edge between the fans, right?

Â Because fans are not fans of other fans,

Â are fans of teams,

Â or edges between the basketball teams,

Â because basketball teams have fans,

Â they're not really fans of other teams.

Â So 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.

Â And that's exactly what a bipartite graphs is.

Â So, 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.

Â And so 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. NetworkX 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,

Â and so for that we would import bipartite to get that set of algorithms.

Â So, to construct these 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.

Â And now, well the first thing I'm going to do is I'm going to add the nodes,

Â and to add the notes 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.

Â So rather than adding one by one,

Â I can add all of the nodes all at once,

Â and then I'm going to give these set of nodes an attribute called bipartite,

Â and I'm going to give that value zero.

Â And what I'm basically doing here is,

Â I'm telling NetworkX that,

Â these set of nodes are going to be one side of my bipartite graph.

Â In this case will be the left side.

Â And then I'll add the nodes from the other side.

Â So I'll add nodes 1 through 4,

Â and these will have value 1 for the bipartite attribute.

Â And then I can add the edges,

Â and same thing here,

Â you can apply these to other cases not only when

Â you're using this 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.

Â Okay, so now we've constructed these bipartite graphs.

Â Notice that I gave it the name B rather than G,

Â just to, so it stands for bipartite.

Â Okay, so what kinds of things can we do in NetworkX with bipartite graphs?

Â So first thing, we can check if a particular graph is bipartite.

Â So, for this would use a function A as bipartite,

Â and this would say,

Â yes it is bipartite.

Â Now notice that if we were to add the edge A, B.

Â So these would add the nodes 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 side to the other.

Â I'm breaking the 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 A, B, 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, and 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.

Â And so for example,

Â if I construct this set X to be the nodes 1 through 4,

Â 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 1, 2, 3,

Â 4, A, through 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 NetworkX to output those two sets.

Â So 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 A,

Â B 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 a 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 A,

Â B, 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 kind of tend to follow the same teams or not.

Â This kind of network could be important for viral marketing.

Â So, if two people tend to follow the same teams,

Â they may 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,

Â and so these this kind of 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 graphs projection of the bipartite graph.

Â And 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.

Â So, in this case, there would be exactly the network between the fans,

Â such that they're connected if they have at least one team in common.

Â You would have a similar definition for the R-bipartite graphs,

Â so that would be a network among the basketball teams,

Â and two teams will be connected if they have at least one fan in common.

Â So, what would that network look like for the fans?

Â So again this network of fans will have at least one team in common,

Â this looks something like this.

Â So in this network,

Â the edge A, H,

Â appears in the projection because both A and H are fans of Team 1,

Â and the edge J, E,

Â appears in this network because they're both fans of team 4.

Â Okay, so you can actually get NetworkX to give you this projected network,

Â and the way you do it is again you define the graph,

Â you add all the edges.

Â So we're constructing in this case the bipartite graph B,

Â and now we defined the set X to be the set of fans,

Â and then we'd use the function projected graph, and it takes the input B,

Â which is the bipartite graph,

Â and then X which is the set of nodes that you want the projected graph on,

Â and then you get this network,

Â so now this is the network P. Now,

Â what if you wanted the projected graph for the teams?

Â So 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,

Â and then this is the network that would come out.

Â So in this network,

Â the nodes 1 and 2 are connected because they both

Â have at least one fan in common. They have C 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,

Â and 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.

Â So edge 1, 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.

Â So we would want to know that actually 1 and 2,

Â yes they have at least one in common but in this case is three,

Â whereas 1 and 3,

Â they have only one fan in common.

Â So that's something we would like to capture,

Â and indeed that's something you can capture.

Â So this is called the L-bipartite weighted graph projection.

Â And what it is is, well just like we saw,

Â rather than just defining an edge in the projected graph to be,

Â connect any two nodes that have at least one connection in common 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.

Â So, the 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.

Â And here I have the size of the edges B,

Â also proportional to that weight,

Â Just to show you visually the difference.

Â And in NetworkX 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.

Â So in summary, in this video we've looked at bipartite graphs.

Â The main thing is that,

Â well the definition, right what it means.

Â So, two sets of nodes and all the edges go from one side to the

Â other and no edge goes from the set to itself.

Â And then to construct them on NetworkX,

Â we're not going to use a separate class,

Â we use the same classes that 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,

Â and so that's something you have to kind of be careful with.

Â The kinds of things we looked at here,

Â what you can do is you can check if a graph is bipartite.

Â You can check if set of nodes is 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.

Â And 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,

Â and you can get these projections using NetworkX with

Â the projected graph and 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.

Â And this is the end of this lecture and I hope to see you in the next one.

Â