Spectral recognition of graphs

Yugoslav Journal of Operations Research

关键词: Spectral graph theory;    spectral recognition;    computer science;    internet;    data mining;   

DOI  :  10.2298/YJOR120925025C

来源: DOAJ

【 摘 要 】

At some time, in the childhood of spectral graph theory, it was conjecturedthat non-isomorphic graphs have different spectra, i.e. that graphs arecharacterized by their spectra. Very quickly this conjecture was refuted andnumerous examples and families of non-isomorphic graphs with the samespectrum (cospectral graphs) were found. Still some graphs are characterizedby their spectra and several mathematical papers are devoted to this topic.In applications to computer sciences, spectral graph theory is considered asvery strong. The benefit of using graph spectra in treating graphs is thateigenvalues and eigenvectors of several graph matrices can be quicklycomputed. Spectral graph parameters contain a lot of information on the graphstructure (both global and local) including some information on graphparameters that, in general, are computed by exponential algorithms.Moreover, in some applications in data mining, graph spectra are used toencode graphs themselves. The Euclidean distance between the eigenvaluesequences of two graphs on the same number of vertices is called the spectraldistance of graphs. Some other spectral distances (also based on variousgraph matrices) have been considered as well. Two graphs are considered assimilar if their spectral distance is small. If two graphs are at zerodistance, they are cospectral. In this sense, cospectral graphs are similar.Other spectrally based measures of similarity between networks (notnecessarily having the same number of vertices) have been used in Internettopology analysis, and in other areas. The notion of spectral distanceenables the design of various meta-heuristic (e.g., tabu search, variableneighbourhood search) algorithms for constructing graphs with a givenspectrum (spectral graph reconstruction). Several spectrally based patternrecognition problems appear in many areas (e.g., image segmentation incomputer vision, alignment of protein-protein interaction networks inbio-informatics, recognizing hard instances for combinatorial optimizationproblems such as the travelling salesman problem). We give a survey of suchand other graph spectral recognition techniques used in computer sciences.[Projekat Ministarstva nauke Republike Srbije, br. ON174033 and III44006]

【 授权许可】

Unknown