doiSerbia

Graph spectral techniques in computer sciences

Arsić Branko (Mathematical Institute SANU, Belgrade)
Cvetković Dragoš (Mathematical Institute SANU, Belgrade)
Simić Slobodan K. (Mathematical Institute SANU, Belgrade)
Škarić Milan (Computer Science Faculty, Union University, Belgrade)

We give a survey of graph spectral techniques used in computer sciences. The survey consists of a description of particular topics from the theory of graph spectra independently of the areas of Computer science in which they are used. We have described the applications of some important graph eigenvalues (spectral radius, algebraic connectivity, the least eigenvalue etc.), eigenvectors (principal eigenvector, Fiedler eigenvector and other), spectral reconstruction problems, spectra of random graphs, Hoffman polynomial, integral graphs etc. However, for each described spectral technique we indicate the fields in which it is used (e.g. in modelling and searching Internet, in computer vision, pattern recognition, data mining, multiprocessor systems, statistical databases, and in several other areas). We present some novel mathematical results (related to clustering and the Hoffman polynomial) as well.

Keywords: spectral graph theory, computer science, internet, complex networks, spectral clustering