5
$\begingroup$

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

  • 2
    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$.2011-11-24
  • 0
    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.2011-11-24
  • 3
    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.2011-11-24
  • 0
    @YuvalFilmus Can you give me some reference on random matrices having distinct eigenvalues (under any reasonable model)?2011-11-25
  • 0
    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.2011-12-02

1 Answers 1