| Title:
|
On some properties of the Laplacian matrix revealed by the RCM algorithm (English) |
| Author:
|
Pedroche, Francisco |
| Author:
|
Rebollo, Miguel |
| Author:
|
Carrascosa, Carlos |
| Author:
|
Palomares, Alberto |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
66 |
| Issue:
|
3 |
| Year:
|
2016 |
| Pages:
|
603-620 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
ordering algorithm |
| Keyword:
|
reverse Cuthill-McKee algorithm |
| Keyword:
|
graph partitioning |
| Keyword:
|
Laplacian matrix |
| MSC:
|
05C50 |
| MSC:
|
15B36 |
| idZBL:
|
Zbl 06644022 |
| idMR:
|
MR3556856 |
| DOI:
|
10.1007/s10587-016-0281-y |
| . |
| Date available:
|
2016-10-01T15:11:14Z |
| Last updated:
|
2023-10-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145860 |
| . |
| Reference:
|
[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. MR 1694677, 10.1137/S1064827597326845 |
| Reference:
|
[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. Zbl 1226.05125, MR 2782776 |
| Reference:
|
[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. Zbl 1217.65063, MR 2776793 |
| Reference:
|
[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. 10.1145/800195.805928 |
| Reference:
|
[5] Abreu, N. M. M. de: Old and new results on algebraic connectivity of graphs.Linear Algebra Appl. 423, (2007), 53-73. Zbl 1115.05056, MR 2312323, 10.1016/j.laa.2006.08.017 |
| Reference:
|
[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. MR 1887751, 10.1023/A:1014082430392 |
| Reference:
|
[7] Fiedler, M.: Algebraic connectivity of graphs.Czech. Math. J. 23 (1973), 298-305. Zbl 0265.05119, MR 0318007, 10.21136/CMJ.1973.101168 |
| Reference:
|
[8] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory.Czech. Math. J. 25 (1975), 619-633. Zbl 0437.15004, MR 0387321, 10.21136/CMJ.1975.101357 |
| Reference:
|
[9] Fortunato, S.: Community detection in graphs.Phys. Rep. 486 (2010), 75-174. MR 2580414, 10.1016/j.physrep.2009.11.002 |
| Reference:
|
[10] George, J. A.: Computer Implementation of the Finite Element Method.Doctoral Dissertation, Stanford University, Stanford (1971). |
| Reference:
|
[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). Zbl 0516.65010, MR 0646786 |
| Reference:
|
[12] Gilbert, J. R., Moler, C., Schreiber, R.: Sparse matrices in MATLAB: Design and implementation.SIAM J. Matrix Anal. Appl. 13 (1992), 333-356. Zbl 0752.65037, MR 1146669, 10.1137/0613024 |
| Reference:
|
[13] Gross, J. L., Yellen, J., eds.: Handbook of Graph Theory.Discrete Mathematics and Its Applications CRC Press, Boca Raton (2004). MR 2035186 |
| Reference:
|
[14] Horn, R. A., Johnson, C. R.: Matrix Analysis.Cambridge University Press, Cambridge (1985). Zbl 0576.15001, MR 0832183 |
| Reference:
|
[15] Jungnickel, D.: Graphs, Networks and Algorithms.Algorithms and Computation in Mathematics 5 Springer, Berlin (2008). Zbl 1126.68058, MR 2363884, 10.1007/978-3-540-72780-4_11 |
| Reference:
|
[16] Juvan, M., Mohar, B.: Laplace eigenvalues and bandwidth-type invariants of graphs.J. Graph Theory, 17 (1993), 393-407. Zbl 0785.05077, MR 1220999, 10.1002/jgt.3190170313 |
| Reference:
|
[17] Kumfert, G., Pothen, A.: Two improved algorithms for envelope and wavefront reduction.BIT 37 (1997), 559-590. Zbl 0891.65043, MR 1483674, 10.1007/BF02510240 |
| Reference:
|
[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. MR 0501813, 10.1137/0713020 |
| Reference:
|
[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. Zbl 0840.05059, MR 1170831 |
| Reference:
|
[20] Molitierno, J. J.: The spectral radius of submatrices of Laplacian matrices for graphs with cut vertices.Linear Algebra Appl. 428 (2008), 1987-1999. Zbl 1137.05045, MR 2401634 |
| Reference:
|
[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. 10.1109/APVIS.2007.329289 |
| Reference:
|
[22] Nascimento, M. C. V., Carvalho, A. De: Spectral methods for graph clustering---a survay.Eur. J. Oper. Res. 211 (2011), 221-231. MR 2774401, 10.1016/j.ejor.2010.08.012 |
| Reference:
|
[23] Newman, M. E. J.: Networks. An Introduction.Oxford University Press, Oxford (2010). Zbl 1195.94003, MR 2676073, 10.1093/acprof:oso/9780199206650.003.0001 |
| Reference:
|
[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. MR 1054210, 10.1137/0611030 |
| Reference:
|
[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. |
| Reference:
|
[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. Zbl 1123.65027, MR 2262982, 10.1137/050629938 |
| Reference:
|
[27] Saad, Y.: Iterative Methods for Sparse Linear Systems.Society for Industrial and Applied Mathematics Philadelphia (2003). Zbl 1031.65046, MR 1990645 |
| Reference:
|
[28] Schaeffer, S. E.: Graph clustering.Comput. Sci. Rev. 1 (2007), 27-64. Zbl 1302.68237, 10.1016/j.cosrev.2007.05.001 |
| Reference:
|
[29] Tarjan, R.: Depth-first search and linear graph algorithms.SIAM J. Comput. 1 (1972), 146-160. Zbl 0251.05107, MR 0304178, 10.1137/0201010 |
| Reference:
|
[30] Varga, R. S.: Matrix Iterative Analysis.Springer Series in Computational Mathematics 27 Springer, Berlin (2000). Zbl 0998.65505, MR 1753713, 10.1007/978-3-642-05156-2 |
| . |
