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.

Bipartite Graphs

Applied Social Network Analysis in Python

Meet the Instructors