Graph Characterization by Counting Sink Star Subgraphs

In this paper, we study the polynomial coefficients of the reduced Bartholdi zeta function for characterizing simple unweighted graphs and demonstrate how to use these coefficients for clustering graphs. The polynomial coefficients of the reduced Bartholdi zeta function are invariant to vertex order permutations and also carry information about counting the sink star subgraphs in a symmetric digraph of G. We also investigate the advantages of the reduced Bartholdi coefficients over other spectral methods such as the Ihara zeta function and Laplacian spectra. Experimental results indicate that the proposed method is more effective than the other spectral approaches, and compared to the Ihara zeta function, it has less sensitivity to structural noises such as omitting an edge.