Partitioning Networks by Eigenvectors
Andrew Seary, William D. Richards · 2004
A survey of published methods for partitioning sparse arrays is presented. These include early attempts to describe the partitioning properties of eigenvectors of the adjacency matrix. More direct methods of partitioning are developed by introducing the Laplacian of the adjacency matrix via the directed (signed) edge-vertex incidence matrix. It is shown that the Laplacian solves the minimization of total length of connections between adjacent nodes, which induces clustering of connected nodes by partitioning the underlying graph. Another matrix derived from the adjacency matrix is also introduced via the unsigned edge-vertex matrix. This (the Normal) matrix is not symmetric, and it also is shown to solve the minimization of total length in its own non-Euclidean metric. In this case partitions are induced by clustering the connected nodes. The Normal matrix is closely related to Correspondence Analysis.