# Does an $n\times n$ adjacency matrix of a scale-free network graph have $n$ distinct eigenvalues?

Question updated

Suppose that I have an $n\times n$ adjacency matrix $\mathbf{A}$ of a simple graph $G$ where the entry $(i,j)$ represent the number of edges between node $i$ and $j$ in $G$. Note that a simple graph is a unweighted, undirected graph containing no self-loops or multiple edges. All these datasets are scale-free networks whose degree distribution follows a power law, at least asymptotically; that is, the fraction $P(k)$ of nodes in the network having $k$ connections to other nodes goes for large values of $k$ as $$P(k) \sim ck^{-\gamma}$$ where $c$ is a normalization constant and γ is a parameter whose value is typically in the range $2 < \gamma < 3$, although occasionally it may lie outside these bounds. (This definition is from the corresponding article from Wikipedia.)

I'm interested in applying spectral techniques to analyze real-life large graph datasets. For example, these datasets are available at Stanford Large Network Dataset Collection. These datasets may be collaboration networks (who collaborated with whom), protein-protein interaction networks, or friend relations on a social network such as Facebook or Twitter.

When analyzing a certain property of these scale-free networks, my approach would be much simpler if the adjacency matrix representation of graphs has all distinct eigenvalues. My question is, can I assume that all these matrices have distinct eigenvalues? Very few is known about the spectrum of these matrices, but it is conjectured that the eigenvalue distribution also follows a power law for the highest eigenvalues.

Reference

-
In the first sentence of the last paragraph, I assume you mean "matrices" instead of "graphs"? And what does it mean for the graphs to be power-law distributed? Also, you ask different questions in the title and the body of the question -- which one is actually your question? The answer to the question in the body is "no": The adjacency matrix of the complete graph consists entirely of $1$s, and the eigenvalue $0$ has multiplicity $n-1$. – joriki Nov 24 '11 at 5:26
Also, the adjacency matrix of the complete bipartite graph $K_{m,n}$ has eigenvalues $\sqrt{mn}$, $-\sqrt{mn}$ and $0$ with multiplicity $1$, $1$ and $m+n-2$ respectively. – Paul Nov 24 '11 at 7:03
A random matrix will have distinct eigenvalues (under any reasonable model). Eigenvalue "clumping" is really a coincidence. You matrices are not random, but if they are real-life then probably their eigenvalues are distinct. Anyhow, for numerical reasons it's difficult (for large matrices) to tell whether two close eigenvalues are the same or not. – Yuval Filmus Nov 24 '11 at 8:24
@YuvalFilmus Can you give me some reference on random matrices having distinct eigenvalues (under any reasonable model)? – Endo Nov 25 '11 at 16:14
The characteristic polynomial of a random graph is random, so you don't expect it to have repeated roots. I'm not aware of any particular reference, though. – Yuval Filmus Dec 2 '11 at 23:42

I would expect many of your graphs to not have distinct eigenvalues.

Here's one reason: They have a very large number of degree $1$ vertices. Enough, in fact, that there will probably be a decent number of degree $1$ vertices which share a common neighbor with another degree $1$ vertex. These will give rise to many independent vectors in the nullspace of your matrix, so $0$ will be a multiple eigenvalue.

More generally, you can imagine the following situation: We say a subgraph $G'$ "dangles" from a vertex $v$ if the only edge connecting $G'$ to the remainder of the graph goes from some vertex $w \in G'$ to $v$. If you have two copies of $G'$ dangling from the same $v$ in the same way ($w$ occupies the same position in both graphs), then all the eigenvalues of $G'$ appear in the spectrum of $G$: The eigenvector is equal to $x$ on one copy of $G'$, $-x$ on the other copy, and $0$ elsewhere in the graph, where $x$ is an eigenvector of $G'$.

You can check, for example, that if instead of a power law graph you had the Erdős-Rényi graph $G(n,c/n)$ for fixed $c$, then every tree $T$ of fixed size appears as a dangling subgraph $c'n$ times (where $c'$ is positive and depends on the tree and $c$). This in turn implies there will be on average $c''n$ vertices having two copies of $T$ dangling from them, and for every such vertex you'll get a copy of all the eigenvalues of $T$. You might expect a similar phenomenon to happen with power law graphs, though I haven't checked this. (I did check a couple of graphs from the Stanford collection to see if they had $0$ as a multiple eigenvalue, and the ones I checked had it many times over).

This is all dependent on there being a sizable number of degree one vertices though. If we move to, say, random Erdős-Rényi graphs with edge probability $1/2$, I would expect the eigenvalues to be distinct with high probability, though as far as I know proving this is still an open problem (EDIT: This was recently proved by Tao and Vu -- their preprint is here and is described in this blog post of Tao's).

For more on this issue, albeit for random preferential attachment trees instead of graphs, check out the recent paper Spectra of Large Random Trees by Bhamidi, Evans, and Sen.

-
Thank you for your answer. For Erdös-Rényi random graph model, this doesn't seem to capture scale-free behaviors of real-life network data. In my analysis, I can only focus on non-zero eigenvalues ignoring eigenvalues of value 0. That's the reason I expected all the non-zero eigenvalues are distinct in scale-free networks. – Endo Nov 27 '11 at 10:35
Even if you can ignore $0$ eigenvalues, the problem still remains. If your graph is sparse enough that certain small structures will appear many times, that may cause repeated eigenvalues. For example, the ArXiv.phys collaboration graph (I pulled the smallest graph off of the SNAP archive since I'm searching for structures manually with Excel) has 89 isolated edges, each of which supports eigenvectors with eigenvalues $1$ and $-1$ It also has two instances of the following structure: Two degree $2$ vertices each sharing a common neighbor and each having their other neighbor with degree $1$. – Kevin Costello Nov 27 '11 at 19:58
(continued) That gives another pair of $\pm 1$ eigenvectors. As I mentioned in my original answer, this is all pretty heavily dependent on there being low degree vertices, and there are some graphs (e.g. the Facebook graph) for which I would expect this not to be so much a problem. But I don't think you can really necessarily assume no repeated eigenvalues. On the other hand, all these small-subgraph examples still have a full set of eigenvectors...if that's the reason you're assuming distinct eigenvalues, they don't cause problems in that way. – Kevin Costello Nov 27 '11 at 20:00
As an amateur in this field, I'd like to ask you a few questions. You said 'isolated edges supports eigenvectors with eigenvalues 1 and -1.' I don't understand what 'edges supports eigenvectors with eigenvalues' means and why this statement is true. – Endo Nov 27 '11 at 22:44
What I meant by this is that any time there's an isolated edge in the graph (an edge connecting two degree one vertices), then you immediately get an eigenvalue of $1$ corresponding to the eigenvector which is $1$ on the vertices of that edge and $0$ elsewhere, and also an eigenvector with eigenvalue $-1$ by giving the two vertices of the edge opposite sign and making everything else $0$ (In general, for a disconnected graph the spectra comes from the union of the spectra for each component). The "support" here just means "where the eigenvector is nonzero". – Kevin Costello Nov 27 '11 at 23:08