0
$\begingroup$

I have a matrix that is effectively a non-directed adjacency matrix for a graph. My problem is to find all disconnected subgraphs. I know this can be done computationally by first creating a graph representation and then performing a flood fill algorithm to find the subgraphs, however, I was hoping there might be a mathematical way to do this on just the matrix.

For example, I have the following symmetric adjacency matrix: $$\begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ \end{bmatrix}$$

Where each row $i$ and columns $j$ correspond to whether there is an edge between node $i$ and node $j$ represented by $1$ if there is an edge, $0$ if not.

This particular matrix represents a graph with two disconnected subgraphs, that is: $$n_2 \leftrightarrow n_1 \leftrightarrow n_5 \leftrightarrow n_6 \textrm{ and } n_3 \leftrightarrow n_4$$

Every node is connected to itself although this can be changed if necessary.

If I could find a way to separate out any rows/columns that do not overlap using some matrix operations, the resulting subgraphs could be extracted computationally.

Is this possible? Or am I stuck using a computational method on a graph?

$\endgroup$
  • $\begingroup$ I'm pretty sure that any algorithm using matrix operations will be essentially equivalent to the graph theory algorithms that find components. Maybe someone's answer will surprise both of us. $\endgroup$ – Ethan Bolker Aug 23 '17 at 16:28
  • 1
    $\begingroup$ Start with an identity matrix and keep right multiplying it with the adjacency matrix (maybe binary multiplication would be better). You'll end with a matrix whose independent rows are the nodes in the connected subgraphs. $\endgroup$ – N74 Aug 23 '17 at 19:29
  • 1
    $\begingroup$ It should be enough to raise the adjacency matrix to its dimension. $\endgroup$ – N74 Aug 24 '17 at 5:29
  • 1
    $\begingroup$ You could find the kernel of the Laplacian matrix, which can be computed from the adjacency matrix $A$ via $L=D-A=\operatorname{diag}(A\mathbf 1)-A$. Surprisingly to me, computing matrix powers appears to be more efficient, at least for the graphs that I tried. $\endgroup$ – amd Aug 29 '17 at 8:01
  • 1
    $\begingroup$ I expected it to be more efficient, too, but when I tested a few methods in Mathematica with your matrix and some slightly larger ones, computing $A^N$ and then extracting the unique rows/columns (which is basically a flood fill) always turned out to be faster. If the graph is highly connected, the matrix powers will likely stabilize after only a few iterations, and, as you say, computing powers of sparse matrices has optimization opportunities. I’m reluctant to make any conclusions about which is more efficient without a broader test. $\endgroup$ – amd Aug 29 '17 at 18:22
1
$\begingroup$

[Collecting up the suggestions from the comments.]

You can do what’s effectively a parallel flood fill by computing powers of the incidence matrix $A$ until the zero entries stabilize. Each of the linearly independent rows/columns of the result represents a connected component of the graph, with nonzero entries in positions that correspond to the nodes in that component.

This will require $d-1$ iterations, where $d$ is the diameter of the graph. However, the process is guaranteed to stabilize in at most $n-1$ iterations, where $n$ is the order of the matrix, so instead of testing each iteration for changes, you could simply compute the $(n-1)$th power of the adjacency matrix. At first glance this seems like it might not scale well, but for your example computing $A^6$ and extracting unique rows turned out the be faster in Mathematica than other methods.

Another approach is to compute the null space of the graph’s Laplacian matrix $L$, which is easily derived from the adjacency matrix: $L=D-A=\operatorname{diag}(A\mathbf 1)-A$. Here, $D$ is the degree matrix, a diagonal matrix with entries equal to the degree of each node, and $\mathbf 1$ is the vector of all $1$s. $A\mathbf 1$ is thus just the vector of row sums of $A$. The null space is spanned by a set of mutually exclusive (orthogonal) incidence vectors, one for each connected component of the graph.

To illustrate with your adjacency matrix $A$, using binary multiplication we have $$A^3=A^4=\begin{bmatrix}1&1&0&0&1&1\\1&1&0&0&1&1\\0&0&1&1&0&0\\0&0&1&1&0&0\\1&1&0&0&1&1\\1&1&0&0&1&1\end{bmatrix}.$$ The unique rows are $(1,1,0,0,1,1)$ and $(0,0,1,1,0,0)$, which correspond to the two connected subgraphs you identify in your question.

The degree matrix is $\operatorname{diag}(3,2,2,2,3,2)$, so the Laplacian is $$L=\left[\begin{array}{r} 2&-1&0&0&-1&0 \\ -1&1&0&0&0&0 \\ 0&0&1&-1&0&0 \\ 0&0&-1&1&0&0 \\ -1&0&0&0&2&-1 \\ 0&0&0&0&-1&1 \end{array}\right].$$ Row-reduction results in $$\left[\begin{array}{r} 1&0&0&0&0&-1 \\ 0&1&0&0&0&-1 \\ 0&0&1&-1&0&0 \\ 0&0&0&0&1&-1 \\ 0&0&0&0&0&0 \\ 0&0&0&0&0&0 \end{array}\right]$$ from which we can read the kernel basis vectors $(1,1,0,0,1,1)^T$ and $(0,0,1,1,0,0)^T$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.