Meaning of eigenvalue 1 and symmetry in Laplacian spectra of graphs

The answer to your question is to look for literature on the spectrum of the graph adjacency matrix, with particular attention paid to its nullity (multiplicity of eigenvalue zero). This is due to Claim 1.

One very interesting property is the link between the nullity of $A$ and the chromatic number of the matrix. In particular, there is something known as the rank-coloring conjecture. Graphs with a large $m_1(L)$ will have a low-rank $A$, and thus have a lower chromatic number.

Sample refs below. More can be found via google.

• Brouwer, Andries E., and Willem H. Haemers. Spectra of graphs. Springer, 2011.
• A.A. Razborov, The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear, Discrete Mathematics, Volume 108, Issues 1–3, 28 October 1992, Pages 393-396, ISSN 0012-365X, http://dx.doi.org/10.1016/0012-365X(92)90691-8.

To answer the part about symmetry. A matrix with $\pm$ adjacency eigenvalue pairs (i.e. symmetric about zero) is bipartite, i.e. 2-colorable, and these become symmetric about 1 in the normalized Laplacian spectrum (this is a simple corollary of the proof below). As a graph becomes more bipartite, its Laplacian spectrum becomes more symmetric about 1.

In other words, you have two sets of nodes in your graphs which are (for the most part) disconnected from each other. For instance, your graph could represent the email exchanges between users on a dating site. Most of the edges (i.e. messages) are between men and women; there are fewer, but nonzero messages between men and men, and women and women. The graph would be mostly, but not completely bipartite, and the Laplacian spectra would be mostly, but not completely symmetric about 1.

Notations. The normalized graph Laplacian is defined $L=I-D^{-1/2}AD^{-1/2}$, where $D$ and $A$ are the usual degree and adjacency matrices. Let us write the multiplicity of an eigenvalue $\lambda$ in matrix $M$ as $m_{\lambda}(M)$.

Claim 1. For any graph with no isolated vertices, the following equality holds between the normalized Laplacian, $L$, and the Adjacency matrix, $A$, $$m_1(L) = m_0(A).$$

Proof. Let us expand the eigenvalue identity for $\lambda=1$, and substitute the definition of the matrix

$$\begin{align*} Lv & =v\\ \implies v-D^{-1/2}AD^{-1/2}v & =v\\ \implies D^{-1/2}AD^{-1/2}v & =0\\ \implies Ax & =0 \end{align*}$$

where we have introduced $x:=D^{-1/2}v$. Clearly, any $x$ that satisfies this comes from $x\in\mathrm{null}(A)$, and $X\ni x$ must necessarily satisfy $X=\mathrm{null}(A)$.

Next, let us write out the space containing $v$. We have assumed that the graph has no isolated, i.e. degree-zero vertices, such that $D^{-1/2}$ is necessarily full-rank (i.e. a bijective mapping) with inverse $D^{1/2}$. If $x \in X$, then $v\in D^{1/2}X$.

Putting these together, we have $$m_1(L)\equiv\mathrm{dim}(D^{1/2}X)\\=\mathrm{dim}(X)\equiv\mathrm{dim}(\mathrm{null}(A))\equiv m_0(A)$$ QED.

A high density/peak on eigenvalue 1 can indicate that the network contains many local symmetries.

The shape of the normalized Laplacian spectrum provides a fingerprint of the structure of the underlying graph. The paper "The role of symmetry in neural networks and their Laplacian spectra" (open-access PDF) examined the peak around 1 and showed a strong empirical and theoretical relation between the height of the peak on eigenvalue 1 and the level of local symmetries in the graph. Local symmetries refer to node pairs that are "copies", i.e. nodes that have similar connectivity patterns, and that can for example result from a generative graph model in which nodes are repetitively duplicated.

Questions 2. and 3. A low peak around 1 would indicate (relatively) low levels of local symmetry. The red spectrum, looks very interesting and is distinct from the spectra of many empirical networks, e.g. based on neurons, food webs, email, football or power grids (de Lange et al., 2013, "The Laplacian spectrum of neural networks")

The work of Anirban Banerjee, Jürgen Jost and Frank Bauer, provides very much insight in the normalized Laplacian spectrum as a tool to explore the structure of graphs and how specific motifs result in specific peaks. See for example the thesis: The Spectrum of the Graph Laplacian as a Tool for Analyzing Structure and Evolution of Networks