14
$\begingroup$

If I have an adjacency matrix for a graph, can I do a series of matrix operations on the adjacency matrix to find the connected components of the graph?

$\endgroup$
1
  • $\begingroup$ Hint: square the matrix, cube the matrix etc... to power of matrix to number of nodes $\endgroup$
    – sashas
    Jan 16 '15 at 16:24
15
$\begingroup$

Yes! Perhaps the easiest way is to obtain the Laplacian matrix and find a basis of its kernel.

In words, call $A$ your adjacency matrix. Obtain the diagonal matrix $D$ of the degrees of each vertex. Set $L=D-A$. Now $\dim \ker L = $ number of connected components. Moreover, the kernel of $L$ is spanned by vectors constant on each connected component.

For example, a block diagonal matrix $A=diag(A_1,\dots,A_n)$, with blocks representing the connected components of your graph, will have an associated Laplacian matrix $L$ with kernel spanned by vectors $v_i=(0,\dots,0,1,\dots,1,0,\dots,0)$ where the string of ones is as long as the number of vertices in $A_i$, and specifically in the entries corresponding to the vertices of that connected component.

EDIT: Edited to more directly answer the original question. Sorry that I misread it earlier!

$\endgroup$
12
  • $\begingroup$ In what text would someone find a result such as this? $\endgroup$ Jan 16 '15 at 17:09
  • $\begingroup$ @PaulSundheim By googling "spectral graph theory book" I found this book by Fan Chung math.ucsd.edu/~fan/cbms.pdf $\endgroup$
    – Max
    Jan 16 '15 at 20:56
  • 1
    $\begingroup$ Sorry, but this doesn't quite answer my question. I would like to find the actual connected components, not just how many there are. Thank you, though! $\endgroup$ Jan 18 '15 at 23:43
  • $\begingroup$ @user2073068 I think slightly better can be done. My memory is failing me, so I can't remember specifics (which is why I didn't explain above), but I think you can find the connected components easily from the Laplacian. Maybe by checking the eigenbasis corresponding to the eigenvalue 0? If I have time to check I will augment my answer. $\endgroup$
    – Max
    Jan 18 '15 at 23:56
  • 1
    $\begingroup$ Wow, this is super cool! Thank you so much. To complete the task I was looking at, I ended up just using SciPy's connected_component function, but its interesting to know this anyway. $\endgroup$ Jan 23 '15 at 3:44
4
$\begingroup$

If you want use the adjacency matrix and you need the actual components, not just their number, then a brute force approach is as follows. Suppose the graph has adjacency matrix $A$ and $n$ vertices. Compute $M=(A+I)^n$. Now define vertices $u$ and $v$ to be equivalent if $M_{u,v} \ne 0$. The equivalence classes of this relation are the connected components of the graph.

This works because $M_{u,v}$ is positive if and only if there is a walk of length at most $n-1$ from from $u$ to $v$, and if two vertices are in the same component they are joined by a walk of length at most $n$.

It is not practical because no-one in their right mind would compute such a large power of $A$. It could be made workable, but there are other methods for finding components, e.g., find a spanning forest.

$\endgroup$
2
  • $\begingroup$ Hate to necro an old thread, but I think the high power of $M$ is pretty easily computable in $O(n^3 \log n)$ time. Just perform repeated squaring of $M$ for $\lceil \log_2 n\rceil$ iterations. $\endgroup$
    – MSha
    Oct 11 at 17:39
  • $\begingroup$ I did say it could be made workable. $\endgroup$ Oct 12 at 13:56
3
$\begingroup$

If the graph is regular, the multiplicity of the largest eigenvalue of the adjacency matrix will provide the same result. Let $X_{1}, ..., X_{n}$ be the connected components of the graph. Then these are the diagonal submatrices of the adjacency matrix. And so $p_{G}(\lambda) = \prod_{i=1}^{n} p_{X_{i}}(\lambda)$, where $p_{G}(\lambda)$ is the characteristic polynomial of $\lambda$.

Since $G$ is $k$-regular, $\lambda = k$ is the dominant eigenvalue of each component as well as of $G$. And so $k$ appears $n$ times.

If $G$ is not regular, then you should use the Laplacian method as described above.

$\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.