Eigenvalues and eigenvectors
Graphs

In spectral graph theory, an eigenvalue of a graph is defined as an eigenvalue of the graph's adjacency matrix A {\displaystyle A}, or (increasingly) of the graph's Laplacian matrix due to its discrete Laplace operator, which is either D − A {\displaystyle D-A} (sometimes called the combinatorial Laplacian) or I − D − 1 / 2 A D − 1 / 2 {\displaystyle I-D^{-1/2}AD^{-1/2}} (sometimes called the normalized Laplacian), where D {\displaystyle D} is a diagonal matrix with D i i {\displaystyle D_{ii}} equal to the degree of vertex v i {\displaystyle v_{i}}, and in D − 1 / 2 {\displaystyle D^{-1/2}}, the i {\displaystyle i} th diagonal entry is 1 / deg (v i) {\textstyle 1/{\sqrt {\deg(v_{i})}}}. The k {\displaystyle k} th principal eigenvector of a graph is defined as either the eigenvector corresponding to the k {\displaystyle k} th largest or k {\displaystyle k} th smallest eigenvalue of the Laplacian. The first principal eigenvector of the graph is also referred to merely as the principal eigenvector.

The principal eigenvector is used to measure the centrality of its vertices. An example is Google 's PageRank algorithm. The principal eigenvector of a modified adjacency matrix of the World Wide Web graph gives the page ranks as its components. This vector corresponds to the stationary distribution of the Markov chain represented by the row-normalized adjacency matrix; however, the adjacency matrix must first be modified to ensure a stationary distribution exists. The second smallest eigenvector can be used to partition the graph into clusters, via spectral clustering. Other methods are also available for clustering.
detectable_format:number_highlighted_sections[2], language:response_language[Italian]