Laplacian Spectrum of Graphs, Structural Distance and Evolutionary Relationship of Networks

Existing graph measures can retrieve certain structural information, but are not sufficient to capture all aspects of a network. We develop a tool, spectra of normalized graph Laplacian, that helps to understand the network structure with deep perception. Evolution of a network with different graph operations produces specific eigenvalues. Thus, useful hypotheses about evolutionary processes can be made by investigating the spectra of real networks. We also demonstrate that real networks of different classes pose characteristic eigenvalue distributions. Applying a meaningful distance measure, we show that network structures are more similar within the same class than between classes. We analyze 43 metabolic networks from different species and find a separation of the three domains, Bacteria, Archaea and Eukarya.