Splitting a network into connected components
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.
Citation pour cette source
Sebastian thomas (2024). Splitting a network into connected components (https://www.mathworks.com/matlabcentral/fileexchange/46457-splitting-a-network-into-connected-components), MATLAB Central File Exchange. Récupéré le .
Compatibilité avec les versions de MATLAB
Plateformes compatibles
Windows macOS LinuxCatégories
Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Découvrir Live Editor
Créez des scripts avec du code, des résultats et du texte formaté dans un même document exécutable.
Version | Publié le | Notes de version | |
---|---|---|---|
1.2.0.0 | Replaced Inv with Moore-Penrose inversion to take care of non-invertible adjacency matrices. |
||
1.1.0.0 | Description correction. |
||
1.0.0.0 |