On some properties of the Laplacian matrix revealed by the RCM algorithm

Pedroche, Francisco ; Rebollo, Miguel ; Carrascosa, Carlos ; Palomares, Alberto

Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 603-620

Abstract (VO)

In this paper we present some theoretical results about the irreducibility of the Laplacian matrix ordered by the Reverse Cuthill-McKee (RCM) algorithm. We consider undirected graphs with no loops consisting of some connected components. RCM is a well-known scheme for numbering the nodes of a network in such a way that the corresponding adjacency matrix has a narrow bandwidth. Inspired by some properties of the eigenvectors of a Laplacian matrix, we derive some properties based on row sums of a Laplacian matrix that was reordered by the RCM algorithm. One of the theoretical results serves as a basis for writing an easy MATLAB code to detect connected components, by using the function ``symrcm'' of MATLAB. Some examples illustrate the theoretical results.

Détail

DOI : 10.1007/s10587-016-0281-y

Classification : 05C50, 15B36
Keywords: ordering algorithm; reverse Cuthill-McKee algorithm; graph partitioning; Laplacian matrix

Bibliographie

[1] Benzi, M., Szyld, D. B., Duin, A. C. N. van: Orderings for incomplete factorization preconditioning of nonsymmetric problems. SIAM J. Sci. Comput. 20 (1999), 1652-1670. | DOI | MR

[2] Boley, D., Ranjan, G., Zhang, Z.-L.: Commute times for a directed graph using an asymmetric Laplacian. Linear Algebra Appl. 435 (2011), 224-242. | MR | Zbl

[3] Bolten, M., Friedhoff, S., Frommer, A., Heming, M., Kahl, K.: Algebraic multigrid methods for Laplacians of graphs. Linear Algebra Appl. 434 (2011), 2225-2243. | MR | Zbl

[4] Cuthill, E., McKee, J.: Reducing the bandwidth of sparse symmetric matrices. Proc. 24th Nat. Conf. of the ACM, ACM Publ P-69, Association for Computing Machinery, New York, 1969 157-172 doi:10.1145/800195.805928. | DOI

[5] Abreu, N. M. M. de: Old and new results on algebraic connectivity of graphs. Linear Algebra Appl. 423, (2007), 53-73. | DOI | MR | Zbl

[6] Corso, G. M. Del, Romani, F.: Heuristic spectral techniques for the reduction of bandwidth and work-bound of sparse matrices. Numer. Algorithms 28 (2001), 117-136. | DOI | MR

[7] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. | DOI | MR | Zbl

[8] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25 (1975), 619-633. | DOI | MR | Zbl

[9] Fortunato, S.: Community detection in graphs. Phys. Rep. 486 (2010), 75-174. | DOI | MR

[10] George, J. A.: Computer Implementation of the Finite Element Method. Doctoral Dissertation, Stanford University, Stanford (1971).

[11] George, A., Liu, J. W.-H.: Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall Series in Computational Mathematics Prentice-Hall, Englewood Cliffs (1981). | MR | Zbl

[12] Gilbert, J. R., Moler, C., Schreiber, R.: Sparse matrices in MATLAB: Design and implementation. SIAM J. Matrix Anal. Appl. 13 (1992), 333-356. | DOI | MR | Zbl

[13] Gross, J. L., Yellen, J., eds.: Handbook of Graph Theory. Discrete Mathematics and Its Applications CRC Press, Boca Raton (2004). | MR

[14] Horn, R. A., Johnson, C. R.: Matrix Analysis. Cambridge University Press, Cambridge (1985). | MR | Zbl

[15] Jungnickel, D.: Graphs, Networks and Algorithms. Algorithms and Computation in Mathematics 5 Springer, Berlin (2008). | DOI | MR | Zbl

[16] Juvan, M., Mohar, B.: Laplace eigenvalues and bandwidth-type invariants of graphs. J. Graph Theory, 17 (1993), 393-407. | DOI | MR | Zbl

[17] Kumfert, G., Pothen, A.: Two improved algorithms for envelope and wavefront reduction. BIT 37 (1997), 559-590. | DOI | MR | Zbl

[18] Liu, W-H., Sherman, A. H.: Comparative analysis of the Cuthill-McKee and the reverse Cuthill-McKee ordering algorithms for sparse matrices. SIAM J. Numer. Anal. 13 (1976), 198-213. | DOI | MR

[19] Mohar, B.: The Laplacian spectrum of graphs. Graph theory, Combinatorics, and Applications Vol. 2. Proc. Sixth Quadrennial International Conf. on the Theory and Applications of Graphs, Kalamazoo, Michigan, 1988 Y. Alavi et all John Wiley & Sons, New York (1991), 871-898. | MR | Zbl

[20] Molitierno, J. J.: The spectral radius of submatrices of Laplacian matrices for graphs with cut vertices. Linear Algebra Appl. 428 (2008), 1987-1999. | MR | Zbl

[21] Mueller, C., Martin, B., Lumsdaine, A.: A comparison of vertex ordering algorithms for large graph visualization. Visualization Asia-Pacific Symposium on Visualization 2007, Sydney, Australia (2007), 141-148 doi: 10.1109/APVIS.2007.329289. | DOI

[22] Nascimento, M. C. V., Carvalho, A. De: Spectral methods for graph clustering---a survay. Eur. J. Oper. Res. 211 (2011), 221-231. | DOI | MR

[23] Newman, M. E. J.: Networks. An Introduction. Oxford University Press, Oxford (2010). | DOI | MR | Zbl

[24] Pothen, A., Simon, H. D., Liou, K. P.: Partitioning sparse matrices with eigenvector of graphs. SIAM J. Matrix Anal. Appl. 11 (1990), 430-452. | DOI | MR

[25] Rebollo, M., Carrascosa, C., Palomares, A., Pedroche, F.: Some examples of detection of connected components in undirected graphs by using the Laplacian matrix and the RCM algorithm. Int. J. Complex Systems in Science 2 (2012), 11-15.

[26] Reid, J. K., Scott, J.A.: Reducing the total bandwidth of a sparse unsymmetric matrix. Siam J. Matrix Anal. Appl. 28 (2006), 805-821. | DOI | MR | Zbl

[27] Saad, Y.: Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics Philadelphia (2003). | MR | Zbl

[28] Schaeffer, S. E.: Graph clustering. Comput. Sci. Rev. 1 (2007), 27-64. | DOI | Zbl

[29] Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1 (1972), 146-160. | DOI | MR | Zbl

[30] Varga, R. S.: Matrix Iterative Analysis. Springer Series in Computational Mathematics 27 Springer, Berlin (2000). | DOI | MR | Zbl