CLASSIFICATION OF MULTIGRAPHS VIA SPECTRAL TECHNIQUES

Abstract

Classification problems of the vertices of large multigraphs (hypergraphs or weighted graphs) can be easily handled by means of linear algebraic tools. For this purpose nocion of the Laplacian of multigraphs will be introduced, the eigenvectors belonging to k consecutive eigenvalues of which define optimal k-dimensional Euclidean representation of the vertices. In this way perturbation results are obtained for the minimal (k+1)-cuts of multigraphs (where k is an arbitrary integer between 1 and the number of vertices). The (k+1)-variance of the optimal k-dimensional representatives is estimated from above by the k smallest positive eigenvalues and by the gap in the spectrum between the kth and (k+1)th positive eigenvalues in increasing order. These results are of statistical character. However, they are useful and well-adopted to automatic computation in the case of large multigraphs when one is not interested in strict structural properties and, on the other hand, usual enumeration algorithms are very time-demanding.