File Exchange

image thumbnail

Splitting a network into connected components

version 1.2.0.0 (2.01 KB) by Sebastian thomas
A function to return all the components of a graph

2 Downloads

Updated 09 Jun 2014

View License

This function returns the components of a graph represented by an adjacency matrix A. The idea is based on the fact that each element (i,j) in A^n represents the number of paths of size n from node i to node j. Extending this to all powers upto N where N is the number of nodes in the graph, it can be said that two nodes are in the same component iff the (i,j) element in S = A+A^2+A^3....+A^n is not zero. S can be worked out to be inv(I-A)*(A-A^(n+1)). It must be pointed out that even if A is sparse, there is no guarantee that A^(n+1) will also be sparse, so there is no use in exploiting MATLAB's sparse matrix functionality.

Cite As

Sebastian thomas (2020). Splitting a network into connected components (https://www.mathworks.com/matlabcentral/fileexchange/46457-splitting-a-network-into-connected-components), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (0)

Updates

1.2.0.0

Replaced Inv with Moore-Penrose inversion to take care of non-invertible adjacency matrices.

1.1.0.0

Description correction.

MATLAB Release Compatibility
Created with R2014a
Compatible with any release
Platform Compatibility
Windows macOS Linux