Python Tutorial: Bipartite graphs

Great work. I hope you're feeling warmed up for what's coming next. We're going to talk about bipartite graphs here. There are two conditions for defining a bipartite graph. Firstly, it's a graph in which the nodes are partitioned into two sets. Secondly, the nodes in one set cannot be connected to one another. They can only be connected to nodes in the other set. This is in contrast to the unipartite graphs that you've been using in the previous course, in which the nodes are not explicitly partitioned into two sets. Let's use an example to make this concrete. An example where bipartite graphs may come in handy is in the modeling of purchases that a customer makes. In this case, the the nodes are partitioned into two sets. The customer's partition and the product's partition edges denote that a customer has purchased a particular product. In this case, it makes perfect sense that products cannot be connected to one another. After all, a product cannot purchase a product. Likewise for customers. How do we encode this information in NetworkX? Though it is not required by the API by convention, bipartite information is encoded as part of the node attributes or metadata. Using the bipartite keyword in the toy example above, let's say I'm modeling the connectivity between a customer's and a product's partition. In constructing the graph, I can use the graph object's method add nodes from passing in the list of nodes from each partition as the first argument. By passing in the bipartite equals customers or bipartite equals products argument, the method will automatically create the node's metadata dictionary with a key bipartite and the corresponding value products or customers. If we inspect the nodes of the graph while passing in the data true argument, we'll see the partition information stored. Now let's recall the definition of degree centrality metric, which is a measure of node importance for any graph. The degree centrality of a node in the graph is defined as the number of neighbors in the graph divided by the number of possible neighbors it could have. In a bipartite graph, the the denominator is the number of nodes present in the other partition. Again, let's look at this visually to make the concept concrete. For the case of node 2 in the graph it's connected to the nodes A and B. The number of neighbors it has is 2, and the total number of neighbors it could possibly be connected TO is also 2. Thus, it has a degree centrality metric of 1.0. What would be the degree centrality of node A? Pause for a bit and think about it if you answered 1/3 that's right. Because NetworkX doesn't provide an explicit bipartite graph class, you will need to learn how to filter a graph for a node set. This is most commonly accomplished by using list comprehensions. For example, if I want to get the nodes in the customer's partition, I can use the list comprehension as shown in input 1 above, in which we loop over each node n and its associated metadata dictionary d. In the graph, we include nodes only. If in D the bipartite key's value is customers, let's inspect that variable Cust nodes Note how there's only customer nodes contained in that list. Now, as a teaser for how this gets used later, we can get the bipartite degree centrality of a graph by calling on the bipartite degree centrality function, which requires a graph g and a list of nodes from one partition as its arguments. It can be either partition. In the example above, we're using the cust nodes partition. This API design is a design choice by the bipartite module creator and provides a lot of flexibility. Okay, let's relieve our coding itch and get practicing.