Bipartite graphs
1. Bipartite graphs
Great work! I hope you’re feeling warmed up for what's coming next!2. Bipartite graphs
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.3. Bipartite graphs: Example
Let’s use an example to make this concrete. An example where a bipartite graphs may come in handy is in the modeling of purchases that a customer makes. In this case, the nodes are partitioned into two sets: the customers partition, and the products 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.4. Bipartite graphs in NetworkX
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 “customers” and a “products” 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, product or customers.5. Bipartite graphs in NetworkX
If we inspect the nodes of the graph, while passing in the data equals True argument, we’ll see the partition information stored. Now,6. Degree centrality
let’s recall the definition of the 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 denominator is the number of nodes present in the other partition. Again,7. Bipartite centrality metrics
let’s look at this visually to make the concept concrete. For the case of node 2 in the graph, it is connected to 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-point-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 need8. Filtering graphs
to learn how to filter a graph for the node set. This is most commonly accomplished by using list comprehensions. For example, if I want to get the nodes in the ‘customers’ 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 flexibility9. Let's practice!
Okay! Let’s relieve our coding itch and get practicing!Create Your Free Account
or
By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.