Effect on normalized graph Laplacian spectrum by motif attachment and duplication

Abstract

To some extent, graph evolutionary mechanisms can be explained by its spectra. Here, we are interested in two graph operations, namely, motif (subgraph) doubling and attachment that are biologically relevant. We investigate how these two processes affect the spectrum of the normalized graph Laplacian. A high (algebraic) multiplicity of the eigenvalues $1,1\pm 0.5,1\pm \sqrt{0.5}$ and others has been observed in the spectrum of many real networks. We attempt to explain the production of distinct eigenvalues by motif doubling and attachment. Results on the eigenvalue $1$ are discussed separately.

References in corpus (5)

• Graph spectra and the detectability of community structure in networks
• Spectral plots and the representation and interpretation of biological data
• Laplacian Spectrum and Protein-Protein Interaction Networks
• On the spectrum of the normalized graph Laplacian
• A few properties of the eigenvalues of normalized graph Laplacian

Cited by in corpus (9)

• On the spectrum of the normalized Laplacian of iterated triangulations of graphs
• Systematic evaluation of a new combinatorial curvature for complex networks
• On the normalized spectrum of threshold graphs
• The normalized Laplacian spectrum of $n$-polygon graphs and its applications
• Phylogeny of Metabolic Networks: A Spectral Graph Theoretical Approach
• On some building blocks of hypergraphs
• Characteristics polynomial of normalized Laplacian for trees
• Symmetries of Hypergraphs and Some Invariant Subspaces of Matrices Associated with Hypergraphs
• Constructing transient amplifiers for death-Birth updating: A case study of cubic and quartic regular graphs