Spectral Graph Analysis

The topological properties (e.g., patterns of connectivity) of graphs can be analyzed using spectral graph theory. Each RNA graph has a Laplacian matrix representation and a corresponding eigenvalue spectrum (see Graph Isomorphism); the number of eigenvalues is equal to the rank of the matrix. The eigenvalues are related to the connectivity pattern (or topology) of the RNA graph. In particular, the second smallest eigenvalue is a measure of the compactness (more precisely, algebraic connectivity) of a graph. A large second eigenvalue indicates a compact graph, whereas a small eigenvalue implies an elongated topology. The following tree graphs illustrate the relationship between second Laplacian eigenvalue and graph structure. (Note that only the eigenvalues of graphs with the same number of vertices can be meaningfully compared.)