Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
ordering algorithm; reverse Cuthill-McKee algorithm; graph partitioning; Laplacian matrix
ordering algorithm; reverse Cuthill-McKee algorithm; graph partitioning; Laplacian matrix
Summary:
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.
References:
[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 10.1137/S1064827597326845 | MR 1694677
[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 2782776 | Zbl 1226.05125
[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 2776793 | Zbl 1217.65063
[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 10.1145/800195.805928
[5] Abreu, N. M. M. de: Old and new results on algebraic connectivity of graphs. Linear Algebra Appl. 423, (2007), 53-73. DOI 10.1016/j.laa.2006.08.017 | MR 2312323 | Zbl 1115.05056
[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 10.1023/A:1014082430392 | MR 1887751
[7] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. DOI 10.21136/CMJ.1973.101168 | MR 0318007 | Zbl 0265.05119
[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 10.21136/CMJ.1975.101357 | MR 0387321 | Zbl 0437.15004
[9] Fortunato, S.: Community detection in graphs. Phys. Rep. 486 (2010), 75-174. DOI 10.1016/j.physrep.2009.11.002 | MR 2580414
[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 0646786 | Zbl 0516.65010
[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 10.1137/0613024 | MR 1146669 | Zbl 0752.65037
[13] Gross, J. L., Yellen, J., eds.: Handbook of Graph Theory. Discrete Mathematics and Its Applications CRC Press, Boca Raton (2004). MR 2035186
[14] Horn, R. A., Johnson, C. R.: Matrix Analysis. Cambridge University Press, Cambridge (1985). MR 0832183 | Zbl 0576.15001
[15] Jungnickel, D.: Graphs, Networks and Algorithms. Algorithms and Computation in Mathematics 5 Springer, Berlin (2008). DOI 10.1007/978-3-540-72780-4_11 | MR 2363884 | Zbl 1126.68058
[16] Juvan, M., Mohar, B.: Laplace eigenvalues and bandwidth-type invariants of graphs. J. Graph Theory, 17 (1993), 393-407. DOI 10.1002/jgt.3190170313 | MR 1220999 | Zbl 0785.05077
[17] Kumfert, G., Pothen, A.: Two improved algorithms for envelope and wavefront reduction. BIT 37 (1997), 559-590. DOI 10.1007/BF02510240 | MR 1483674 | Zbl 0891.65043
[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 10.1137/0713020 | MR 0501813
[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 1170831 | Zbl 0840.05059
[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 2401634 | Zbl 1137.05045
[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 10.1109/APVIS.2007.329289
[22] Nascimento, M. C. V., Carvalho, A. De: Spectral methods for graph clustering---a survay. Eur. J. Oper. Res. 211 (2011), 221-231. DOI 10.1016/j.ejor.2010.08.012 | MR 2774401
[23] Newman, M. E. J.: Networks. An Introduction. Oxford University Press, Oxford (2010). DOI 10.1093/acprof:oso/9780199206650.003.0001 | MR 2676073 | Zbl 1195.94003
[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 10.1137/0611030 | MR 1054210
[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 10.1137/050629938 | MR 2262982 | Zbl 1123.65027
[27] Saad, Y.: Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics Philadelphia (2003). MR 1990645 | Zbl 1031.65046
[28] Schaeffer, S. E.: Graph clustering. Comput. Sci. Rev. 1 (2007), 27-64. DOI 10.1016/j.cosrev.2007.05.001 | Zbl 1302.68237
[29] Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1 (1972), 146-160. DOI 10.1137/0201010 | MR 0304178 | Zbl 0251.05107
[30] Varga, R. S.: Matrix Iterative Analysis. Springer Series in Computational Mathematics 27 Springer, Berlin (2000). DOI 10.1007/978-3-642-05156-2 | MR 1753713 | Zbl 0998.65505
Search
Partner of
