Hypergraphs, Characteristic Polynomials and the Ihara Zeta Function

摘要

In this paper we make a characteristic polynomial analysis on hypergraphs for the purpose of clustering. Our starting point is the Ihara zeta function [8] which captures the cycle structure for hypergraphs. The Ihara zeta function for a hypergraph can be expressed in a determinant form as the reciprocal of the characteristic polynomial of the adjacency matrix for a transformed graph representation. Our hypergraph characterization is based on the coefficients of the characteristic polynomial, and can be used to construct feature vectors for hypergraphs. In the experimental evaluation, we demonstrate the effectiveness of the proposed characterization for clustering hypergraphs.