Spectral graph tools

The adjacency matrix and degree of vertices in the adjacency matrix contain information about the connectivity of vertices within the network. For an undirected network, the Laplacian matrix of the network is found by subtracting the adjacency matrix from the degree matrix (i.e., L = D - A, where D is the degree matrix and A is the adjacency matrix). This matrix contains information about many important properties of the network, including the number of connected components, the sparsest cut that can separate the network into separate components, and the strength of connection within the network overall.

Connectivity is an important concept in graph theory. A connected network is one in which there is a path between all pairs of vertices; a disconnected network is one in which some vertices do not have paths to all other vertices. Connected networks can be separated by cutting edges; the minimum cut set is the set of the fewest edges that need to be removed...