Structural Analysis of Laplacian Spectral Properties of Large-Scale Networks
Using methods from algebraic graph theory and convex optimization, we study the relationship between local structural features of a network and the eigenvalues of its Laplacian matrix. In particular, we propose a series of semidefinite programs to find new bounds on the spectral radius and the spect...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/91004 https://orcid.org/0000-0002-5930-7694 |
| _version_ | 1826198164676280320 |
|---|---|
| author | Preciado, Victor M. Jadbabaie, Ali Verghese, George C. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Preciado, Victor M. Jadbabaie, Ali Verghese, George C. |
| author_sort | Preciado, Victor M. |
| collection | MIT |
| description | Using methods from algebraic graph theory and convex optimization, we study the relationship between local structural features of a network and the eigenvalues of its Laplacian matrix. In particular, we propose a series of semidefinite programs to find new bounds on the spectral radius and the spectral gap of the Laplacian matrix in terms of a collection of local structural features of the network. Our analysis shows that the Laplacian spectral radius is strongly constrained by local structural features. On the other hand, we illustrate how local structural features are usually insufficient to accurately estimate the Laplacian spectral gap. As a consequence, random graph models in which only local structural features are prescribed are, in general, inadequate to faithfully model Laplacian spectral properties of a network. |
| first_indexed | 2024-09-23T11:00:13Z |
| format | Article |
| id | mit-1721.1/91004 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:00:13Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/910042022-10-01T00:28:45Z Structural Analysis of Laplacian Spectral Properties of Large-Scale Networks Preciado, Victor M. Jadbabaie, Ali Verghese, George C. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Verghese, George C. Using methods from algebraic graph theory and convex optimization, we study the relationship between local structural features of a network and the eigenvalues of its Laplacian matrix. In particular, we propose a series of semidefinite programs to find new bounds on the spectral radius and the spectral gap of the Laplacian matrix in terms of a collection of local structural features of the network. Our analysis shows that the Laplacian spectral radius is strongly constrained by local structural features. On the other hand, we illustrate how local structural features are usually insufficient to accurately estimate the Laplacian spectral gap. As a consequence, random graph models in which only local structural features are prescribed are, in general, inadequate to faithfully model Laplacian spectral properties of a network. United States. Office of Naval Research. Multidisciplinary University Research Initiative United States. Air Force Office of Scientific Research 2014-10-20T18:38:48Z 2014-10-20T18:38:48Z 2013-08 2012-11 Article http://purl.org/eprint/type/JournalArticle 0018-9286 1558-2523 http://hdl.handle.net/1721.1/91004 Preciado, Victor M., Ali Jadbabaie, and George C. Verghese. “Structural Analysis of Laplacian Spectral Properties of Large-Scale Networks.” IEEE Trans. Automat. Contr. 58, no. 9 (n.d.): 2338–2343. https://orcid.org/0000-0002-5930-7694 en_US http://dx.doi.org/10.1109/tac.2013.2261187 IEEE Transactions on Automatic Control Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Preciado, Victor M. Jadbabaie, Ali Verghese, George C. Structural Analysis of Laplacian Spectral Properties of Large-Scale Networks |
| title | Structural Analysis of Laplacian Spectral Properties of Large-Scale Networks |
| title_full | Structural Analysis of Laplacian Spectral Properties of Large-Scale Networks |
| title_fullStr | Structural Analysis of Laplacian Spectral Properties of Large-Scale Networks |
| title_full_unstemmed | Structural Analysis of Laplacian Spectral Properties of Large-Scale Networks |
| title_short | Structural Analysis of Laplacian Spectral Properties of Large-Scale Networks |
| title_sort | structural analysis of laplacian spectral properties of large scale networks |
| url | http://hdl.handle.net/1721.1/91004 https://orcid.org/0000-0002-5930-7694 |
| work_keys_str_mv | AT preciadovictorm structuralanalysisoflaplacianspectralpropertiesoflargescalenetworks AT jadbabaieali structuralanalysisoflaplacianspectralpropertiesoflargescalenetworks AT verghesegeorgec structuralanalysisoflaplacianspectralpropertiesoflargescalenetworks |