6.2 Spectral Graph Theory

Spectral graph theory connects the structure of graphs to the properties of their adjacency matrices. It explores how eigenvalues and eigenvectors reveal information about connectivity, components, and overall graph characteristics.

This powerful approach enables efficient algorithms for graph partitioning, clustering, and centrality measures. By analyzing the spectrum of a graph, we can uncover hidden patterns and solve complex problems in various fields.

Adjacency matrix properties

Definition and structure

Top images from around the web for Definition and structure

• 

  Adjacency matrix - Wikiversity View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

• 

  Adjacency matrix - Wikipedia View original

  Is this image relevant?

• 

  Adjacency matrix - Wikiversity View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and structure

• 

  Adjacency matrix - Wikiversity View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

• 

  Adjacency matrix - Wikipedia View original

  Is this image relevant?

• 

  Adjacency matrix - Wikiversity View original

  Is this image relevant?

• 

  CS 360: Lecture 15: Graph Theory View original

  Is this image relevant?

1 of 3

• The adjacency matrix A of a graph G is a square matrix where the entry A[i,j] is 1 if there is an edge between vertices i and j, and 0 otherwise
• The adjacency matrix is symmetric for undirected graphs, meaning A[i,j] = A[j,i] for all i and j
• The diagonal entries of the adjacency matrix are always 0 for simple graphs (no self-loops)

Degree and connectivity information

• The sum of the entries in the i-th row or column of the adjacency matrix represents the degree of vertex i
  • For example, if the i-th row of A has three 1's, then vertex i has degree 3
• The powers of the adjacency matrix A^k contain information about the number of walks of length k between any pair of vertices
  • The entry (A^k)[i,j] gives the number of walks of length k from vertex i to vertex j
  • This can be used to compute the number of triangles in a graph by looking at the diagonal entries of A^3

Graph spectrum interpretation

Eigenvalues and characteristic polynomial

• The spectrum of a graph is the set of eigenvalues of its adjacency matrix
• The eigenvalues of a graph are the roots of the characteristic polynomial det(A - λI) = 0, where A is the adjacency matrix, λ is an eigenvalue, and I is the identity matrix
  • The characteristic polynomial encodes important information about the graph structure

Spectral properties and graph characteristics

• The largest eigenvalue (in absolute value) of a connected graph is called the spectral radius and is related to various graph properties, such as the maximum degree and the diameter
  • A graph with high spectral radius tends to have high connectivity and small diameter
• The multiplicity of the zero eigenvalue in the spectrum is equal to the number of connected components in the graph
  • For example, if a graph has three connected components, its spectrum will have eigenvalue 0 with multiplicity 3
• The spectral gap, which is the difference between the two largest eigenvalues, is an important measure of graph connectivity and expansion properties
  • Graphs with large spectral gaps are well-connected and have good expansion properties (small sets of vertices have many edges leaving the set)

Eigenvalues and eigenvectors for graph structure

Eigenvectors and connected components

• Eigenvectors corresponding to the zero eigenvalue are indicators of connected components in the graph
  • If a graph has k connected components, there will be k linearly independent eigenvectors with eigenvalue 0
  • The support of each eigenvector (the set of vertices with nonzero entries) corresponds to a connected component

Perron-Frobenius theorem and centrality measures

• The Perron-Frobenius theorem states that for a connected graph, the eigenvector corresponding to the largest eigenvalue (the Perron vector) has all positive entries and is unique up to scaling
• The Perron vector can be used to measure the centrality or importance of vertices in a graph, as it assigns higher values to vertices with more connections or influence
  • This is similar to the PageRank algorithm used by search engines to rank web pages

Fiedler vector and graph partitioning

• The Fiedler vector, which is the eigenvector corresponding to the second smallest eigenvalue (also called the algebraic connectivity), can be used for graph partitioning and clustering
• The sign of the entries in the Fiedler vector can be used to partition the graph into two subsets, minimizing the number of edges between them
  • Vertices with positive entries in the Fiedler vector are assigned to one subset, while vertices with negative entries are assigned to the other subset
  • This is the basis for spectral bisection, a graph partitioning algorithm

Spectral graph theory for partitioning and clustering

Spectral clustering using graph Laplacian

• Spectral clustering is a technique that uses the eigenvectors of the graph Laplacian matrix (L = D - A, where D is the degree matrix) to partition the graph into clusters
• The k smallest eigenvectors of the graph Laplacian (excluding the zero eigenvalue) are used as a low-dimensional representation of the vertices, which can be clustered using algorithms like k-means
  • Each vertex is represented by a point in k-dimensional space, where the coordinates are given by the corresponding entries in the k eigenvectors
  • Clusters in this low-dimensional space correspond to clusters in the original graph

Normalized cut and normalized Laplacian

• The normalized cut criterion, which measures the quality of a graph partition, can be approximated using the eigenvectors of the normalized Laplacian matrix (L_norm = D^(-1/2) L D^(-1/2))
  • The normalized cut balances the size of the partitions while minimizing the number of edges between them
• Spectral partitioning methods aim to find a partition of the graph that minimizes the normalized cut or similar objective functions
  • These methods often involve solving eigenvalue problems or optimization problems based on the graph Laplacian or its variants

Applications and considerations

• Applications of spectral graph theory in clustering include image segmentation, community detection in social networks, and data clustering in high-dimensional spaces
  • For example, spectral clustering can be used to segment an image into regions based on pixel similarity
• The performance of spectral clustering and partitioning methods depends on the choice of the number of clusters (k) and the quality of the eigenvector approximation
  • Selecting an appropriate value for k is often a challenge and may require domain knowledge or data-driven approaches
  • Efficient algorithms for computing eigenvectors, such as the Lanczos method or power iteration, are crucial for large-scale applications