Bipartite graphs as matrices

1. Bipartite graphs as matrices

Congrats on finishing the last few exercises! We’re now going to train your mind to look at graphs in a new light!Remember how in visualizing a graph, we can use a matrix plot? Well, with a few modifications, we can represent bipartite graphs as matrices as well.

2. Matrix representation

Firstly, rather than making each row and column a single node, here, each row represents one node in one partition, and each column represents one node on the other partition. The cells are filled in based on whether an edge exists between two nodes in different partitions. Visually,

3. Matrix representation

it might look like this. Using the customer-product bipartite graph from before, we can represent it as a 3-row by 2-column matrix, in which the rows represent the customers, and the columns represent the product. How do we get the matrix representation of a bipartite graph?

4. Example code

Well, NetworkX provides such a function. As usual, we have to gather the nodes from each partition first. Once we’ve done that, we will then use the biadjacency_matrix function from the bipartite module. It takes in two mandatory arguments: the graph G, and row_order, which specifies the row order of the nodes from one partition. The optional argument is column_order; the biadjacency_matrix function can figure out, given the nodes from one partition, the complementary set of nodes on the other partition. However, if you have a particular ordering, you can set it by passing in a list of nodes to the column_order argument. What’s returned is a sparse matrix representation of the graph - what exactly is this? The short answer here is basically, “don’t worry! sparse matrices are, simply put, memory-efficient matrices!”, and for the purposes of this course, you don't need to know more than that. Now, one thing that’s really

5. Matrix projection

elegant about matrices is that there’s a direct way to compute the projection of a graph using matrix multiplication. If you're not familiar with matrices, thats fine, we will show you how to do it in the upcoming code; however, for those who know about matrices and linear algebra, here's some bonus material on matrix operations and how they relate to the graphs! Firstly, we transpose the matrix, which is essentially swapping the rows and columns. If we then take the bipartite graph and matrix multiply it by its transposed version in the middle, we get the projection onto the nodes that are the rows on the left matrix, and this is the matrix on the right hand side. The mechanics of the matrix multiplication are as such.

6. Matrix projection

We take the first row of the left matrix, and vector-vector multiply it by the first column of its transpose, yielding the upper left cell of the customer matrix. We then do the same for

7. Matrix projection

the second column,

8. Matrix projection

and then

9. Matrix projection

for the

10. Matrix projection

next row,

11. Matrix projection

and so on until we

12. Matrix projection

reach the

13. Matrix projection

final

14. Matrix projection

row. Looking at the result,

15. Matrix projection

the diagonals of the projection matrix correspond exactly to the degree of the node in the original graph; for example, node 1 was connected to 3 nodes, while node 2 was connected to 2 nodes, and

16. Matrix projection

the non-diagonal elements show us which nodes are connected to which other nodes, known as the "connectivity matrix". It turns out to be all-round quite elegant! How do you do this in Python?

17. Matrix multiplication in Python

Well, since Python 3-point-5, there’s the shiny new operator @ that allows you to take two matrices and multiply them together. Therefore, I can take a sparse matrix, and multiply it by its transpose (the dot T gives the transposed version), and very efficiently get back the projection onto the rows of the left side matrix.

18. Let's practice!

Okay! Let’s get some practice handling graphs with matrices!

Create Your Free Account

By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.