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
- Eigenvalue distribution in scale free graphs S. Gago, Aplimat-Journal of Applied Mathematics, 2008
Best Answer
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.