SPECTRA, EUCLIDEAN REPRESENTATIONS AND CLUSTERINGS OF HYPERGRAPHS

We would like to classify the vertices of a hypergraph in the way that 'similar' vertices (those having many incident edges in common) belong to the same cluster. The problem is formulated as follows: given a connected hypergraph on n vertices and fixing the integer k (1 < k less-than-or-equal-to n), we are looking for k-partition of the set of vertices such that the edges of the corresponding cut-set be as few as possible. We introduce some combinatorial measures characterizing this structural property and give upper and lower bounds for them by means of the k smallest eigenvalues of the hypergraph. For this purpose the notion of spectra of hypergraphs - which is the generalization of C-spectra of graphs - is also introduced together with k-dimensional Euclidean representations. We shall show that the existence of k 'small' eigenvalues is a necessary but not sufficient condition for the existence of a good clustering. In addition the representatives of the vertices in an optimal k-dimensional Euclidean representation of the hypergraph should be well separated by means of their Euclidean distances. In this case the k-partition giving the optimal clustering is also obtained by this classification method.