We usually store a graph in terms of its adjacency matrix A, where A[i,j] is set to 1 if nodes i and j are connected, and will be set to 0 if they are not connected.
The question is; given the adjacency matrix of a graph such as above, can we get any idea about the structure of the graph? For example, can we find out if there are two connected components, or can find out if there is any triangle in the graph? (e.g. nodes 9-13-10 form a triangle in the graph below) You might say, well, I will just draw the graph and then will visually inspect the graph, quite easy! You might be able to do so in case of a small graph of small like the graph below, but what about the graph of a social network such as Facebook?
The answers to this question will be given by the "spectral graph theory", which is very useful for analyzing complex networks, let it be a social network or a chemical compound. One of the basic tools in spectral graph theory as the name implies is "computing the spectral of a given graph", i.e. its set of eigenvalues along with their multiplicity.
Now, in case of the adjacency matrix, the largest eigenvalue of A is termed the index (let's denote it by $\lambda_1(\textbf{A})$). Here are some properties of eigenvalue of A:
But the adjacency matrix is not the only matrix that gives us some idea about the structure of a graph. Besides A, we can also extract useful information from the spectra of another related matrix called the "Laplacian" (which is always positive semi-definite). The Laplacian is defined as:
$\textbf{L} = \textbf{D}- \textbf{A}$
Here, D denotes the diagonal degree matrix. We have the following properties for spectra of L:
Besides A and L, there is one more important matrix: normalized Laplacian $\textbf{L}_N$:
$\textbf{L}_N = \textbf{D}^{-1/2}\textbf{A}\textbf{D}^{-1/2}$
We have the following properties for $\textbf{L}_N$:
The question is; given the adjacency matrix of a graph such as above, can we get any idea about the structure of the graph? For example, can we find out if there are two connected components, or can find out if there is any triangle in the graph? (e.g. nodes 9-13-10 form a triangle in the graph below) You might say, well, I will just draw the graph and then will visually inspect the graph, quite easy! You might be able to do so in case of a small graph of small like the graph below, but what about the graph of a social network such as Facebook?
The answers to this question will be given by the "spectral graph theory", which is very useful for analyzing complex networks, let it be a social network or a chemical compound. One of the basic tools in spectral graph theory as the name implies is "computing the spectral of a given graph", i.e. its set of eigenvalues along with their multiplicity.
Now, in case of the adjacency matrix, the largest eigenvalue of A is termed the index (let's denote it by $\lambda_1(\textbf{A})$). Here are some properties of eigenvalue of A:
- The spectra of a bipartite graph is symmetric around 0, i.e. we will have both $\lambda_i(\textbf{A})$ and $-\lambda_i(\textbf{A})$.
- Index is bounded: $d_{min} \leq d_{avg} \leq \lambda_1(\textbf{A}) \leq d_{max}$.
- The size of the maximum clique in the network is at least $\frac{n}{n-\lambda_1(\textbf{A})}$.
- A graph for which $\lambda_1(\textbf{A}) \geq \sqrt{m}$, necessarily contains a triangle (m is the multiplicity of $\lambda_1(\textbf{A})$).
But the adjacency matrix is not the only matrix that gives us some idea about the structure of a graph. Besides A, we can also extract useful information from the spectra of another related matrix called the "Laplacian" (which is always positive semi-definite). The Laplacian is defined as:
$\textbf{L} = \textbf{D}- \textbf{A}$
Here, D denotes the diagonal degree matrix. We have the following properties for spectra of L:
- The multiplicity of $\lambda_1(\textbf{L}) = 0$ shows the number of connected components.
- $\lambda_2(\textbf{L})$ is called the algebraic connectivity, the further it is from $0$, the more connected is the graph.
- $0 \leq \lambda_j(\textbf{L}) \leq 2d_{max}$.
- $\lambda_n(\textbf{L}) \geq d_{max}$.
Besides A and L, there is one more important matrix: normalized Laplacian $\textbf{L}_N$:
$\textbf{L}_N = \textbf{D}^{-1/2}\textbf{A}\textbf{D}^{-1/2}$
We have the following properties for $\textbf{L}_N$:
- $0 \leq \lambda_j(\textbf{L}_N) \leq 2$
- $ \lambda_j(\textbf{L}_N) \geq \frac{n}{n-1}$
