Spectral recognition of graphs
At some time, in the childhood of spectral graph theory, it was conjectured that non-isomorphic graphs have different spectra, i.e. that graphs are characterized by their spectra. Very quickly this conjecture was refuted and numerous examples and families of non-isomorphic graphs with the same s...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Belgrade
2012-01-01
|
| Series: | Yugoslav Journal of Operations Research |
| Subjects: | |
| Online Access: | http://www.doiserbia.nb.rs/img/doi/0354-0243/2012/0354-02431200025C.pdf |
| _version_ | 1811265400554389504 |
|---|---|
| author | Cvetković Dragoš |
| author_facet | Cvetković Dragoš |
| author_sort | Cvetković Dragoš |
| collection | DOAJ |
| description | At some time, in the childhood of spectral graph theory, it was conjectured that non-isomorphic graphs have different spectra, i.e. that graphs are characterized by their spectra. Very quickly this conjecture was refuted and numerous examples and families of non-isomorphic graphs with the same spectrum (cospectral graphs) were found. Still some graphs are characterized by their spectra and several mathematical papers are devoted to this topic. In applications to computer sciences, spectral graph theory is considered as very strong. The benefit of using graph spectra in treating graphs is that eigenvalues and eigenvectors of several graph matrices can be quickly computed. Spectral graph parameters contain a lot of information on the graph structure (both global and local) including some information on graph parameters that, in general, are computed by exponential algorithms. Moreover, in some applications in data mining, graph spectra are used to encode graphs themselves. The Euclidean distance between the eigenvalue sequences of two graphs on the same number of vertices is called the spectral distance of graphs. Some other spectral distances (also based on various graph matrices) have been considered as well. Two graphs are considered as similar if their spectral distance is small. If two graphs are at zero distance, they are cospectral. In this sense, cospectral graphs are similar. Other spectrally based measures of similarity between networks (not necessarily having the same number of vertices) have been used in Internet topology analysis, and in other areas. The notion of spectral distance enables the design of various meta-heuristic (e.g., tabu search, variable neighbourhood search) algorithms for constructing graphs with a given spectrum (spectral graph reconstruction). Several spectrally based pattern recognition problems appear in many areas (e.g., image segmentation in computer vision, alignment of protein-protein interaction networks in bio-informatics, recognizing hard instances for combinatorial optimization problems such as the travelling salesman problem). We give a survey of such and other graph spectral recognition techniques used in computer sciences. [Projekat Ministarstva nauke Republike Srbije, br. ON174033 and III44006] |
| first_indexed | 2024-04-12T20:23:05Z |
| format | Article |
| id | doaj.art-c716179e47144a0196cd3d091c213f60 |
| institution | Directory Open Access Journal |
| issn | 0354-0243 1820-743X |
| language | English |
| last_indexed | 2024-04-12T20:23:05Z |
| publishDate | 2012-01-01 |
| publisher | University of Belgrade |
| record_format | Article |
| series | Yugoslav Journal of Operations Research |
| spelling | doaj.art-c716179e47144a0196cd3d091c213f602022-12-22T03:17:57ZengUniversity of BelgradeYugoslav Journal of Operations Research0354-02431820-743X2012-01-0122214516110.2298/YJOR120925025CSpectral recognition of graphsCvetković DragošAt some time, in the childhood of spectral graph theory, it was conjectured that non-isomorphic graphs have different spectra, i.e. that graphs are characterized by their spectra. Very quickly this conjecture was refuted and numerous examples and families of non-isomorphic graphs with the same spectrum (cospectral graphs) were found. Still some graphs are characterized by their spectra and several mathematical papers are devoted to this topic. In applications to computer sciences, spectral graph theory is considered as very strong. The benefit of using graph spectra in treating graphs is that eigenvalues and eigenvectors of several graph matrices can be quickly computed. Spectral graph parameters contain a lot of information on the graph structure (both global and local) including some information on graph parameters that, in general, are computed by exponential algorithms. Moreover, in some applications in data mining, graph spectra are used to encode graphs themselves. The Euclidean distance between the eigenvalue sequences of two graphs on the same number of vertices is called the spectral distance of graphs. Some other spectral distances (also based on various graph matrices) have been considered as well. Two graphs are considered as similar if their spectral distance is small. If two graphs are at zero distance, they are cospectral. In this sense, cospectral graphs are similar. Other spectrally based measures of similarity between networks (not necessarily having the same number of vertices) have been used in Internet topology analysis, and in other areas. The notion of spectral distance enables the design of various meta-heuristic (e.g., tabu search, variable neighbourhood search) algorithms for constructing graphs with a given spectrum (spectral graph reconstruction). Several spectrally based pattern recognition problems appear in many areas (e.g., image segmentation in computer vision, alignment of protein-protein interaction networks in bio-informatics, recognizing hard instances for combinatorial optimization problems such as the travelling salesman problem). We give a survey of such and other graph spectral recognition techniques used in computer sciences. [Projekat Ministarstva nauke Republike Srbije, br. ON174033 and III44006]http://www.doiserbia.nb.rs/img/doi/0354-0243/2012/0354-02431200025C.pdfSpectral graph theoryspectral recognitioncomputer scienceinternetdata mining |
| spellingShingle | Cvetković Dragoš Spectral recognition of graphs Yugoslav Journal of Operations Research Spectral graph theory spectral recognition computer science internet data mining |
| title | Spectral recognition of graphs |
| title_full | Spectral recognition of graphs |
| title_fullStr | Spectral recognition of graphs |
| title_full_unstemmed | Spectral recognition of graphs |
| title_short | Spectral recognition of graphs |
| title_sort | spectral recognition of graphs |
| topic | Spectral graph theory spectral recognition computer science internet data mining |
| url | http://www.doiserbia.nb.rs/img/doi/0354-0243/2012/0354-02431200025C.pdf |
| work_keys_str_mv | AT cvetkovicdragos spectralrecognitionofgraphs |