Graphs as adjacency matrices
In class, we have calculated connected components of various graphs. In this post, I wanted to introduce another way of calculating connected components, aside from visual inspection. As a reminder, we define nodes as the vertices in the graph, and edges as the connections between vertices. In practice, it can become quite laborious to sketch graphs of 100+ nodes, which occur quite often in industry. Hence, it is often convenient to represent these graphs as an adjacency matrix. This is a matrix where, if an edge exists between two nodes, then we mark a ‘1’ in the corresponding entry. Otherwise, that entry is ‘0’. For example, take the following graph:
Mary is connected to herself, David, and Linda, so she should have a ‘1’ in those corresponding columns. To represent this, we would create a 4 x 4 matrix and represent it as the following:
A few important observations: the diagonals of the matrix will always be ‘1’, i.e., there always exists a path from a node to itself in an undirected graph. Secondly, the adjacency matrix for an undirected graph will always be symmetric, which is to say that each entry (row i, column j) will equal (row j, column i), or the matrix equals its transpose. A symmetric matrix implies that the matrix is square (n by n for any n>=0). This makes sense because the adjacency matrix describes every path from every node. If we have n nodes, and we want to describe n paths for each node, then we will have n*n entries = n² entries, which is a perfect square. This last result enables us to do matrix exponentiation, which is just repeated matrix multiplication! In case you forgot, here’s a quick refresher on multiplication of a 2 by 2 matrix.
It turns out that if you exponentiate a matrix to the total number of nodes in the graph, you can count the number of connected components! Let’s see why using two different graphs.
Observe that, as we exponentiate the matrix to greater powers, the rows of graphs with more connections become populated by values greater than zero. For example, take the entry: (row 1, column 4) for M1 ². This entry is a 1 because there is exactly one path from node 1 to 4 with a length of 2 or less: [ 1 → 3 → 4]. We can use inductive reasoning to conclude that an adjacency matrix raised to some arbitrary power of k counts the number of paths of length k or less for every combination of node i to j. We can view this idea of a matrix raised to some kth power as denoting this idea of reachability. This lends itself to a simple algorithm:
(1) raise a matrix to the nth power, where n = the number of nodes in the graph. We do this because the longest path that is NOT a cycle in any graph will be of length n (The reason being: If you can reach something, you’ll do it in n steps or less; otherwise you can’t reach it, and you’d just be retracing your previous paths).
(2) Take this resulting matrix, and replace all the entries greater than 0 with a 1.
(3) Finally, count the number of unique rows the results from the matrix. This count will be the number of connected components.
As an example, M1 ³ already has every entry populated, so each row will become (1,1,1,1). Since every row is like this, the number of unique rows is just 1. This contrasts with M2 ³: {(1,0,0,0), (0,1,0, 0), (0,0,1,0), (0,0,0,1)} → 4 total unique rows/components. In computer science, we refer to this as the transitive closure of a graph. In python:
Source:
https://www.ics.uci.edu/~irani/w15-6B/BoardNotes/MatrixMultiplication.pdf