By the same authors

From the same journal

From the same journal

Graph Characterization via Ihara Coefficients

Research output: Contribution to journalArticle



Publication details

JournalIEEE Transactions on Neural Networks
DatePublished - Feb 2011
Issue number2
Number of pages13
Pages (from-to)233 -245
Original languageEnglish


The novel contributions of this paper are twofold. First, we demonstrate how to characterize unweighted graphs in a permutation-invariant manner using the polynomial coefficients from the Ihara zeta function, i.e., the Ihara coefficients. Second, we generalize the definition of the Ihara coefficients to edge-weighted graphs. For an unweighted graph, the Ihara zeta function is the reciprocal of a quasi characteristic polynomial of the adjacency matrix of the associated oriented line graph. Since the Ihara zeta function has poles that give rise to infinities, the most convenient numerically stable representation is to work with the coefficients of the quasi characteristic polynomial. Moreover, the polynomial coefficients are invariant to vertex order permutations and also convey information concerning the cycle structure of the graph. To generalize the representation to edge-weighted graphs, we make use of the reduced Bartholdi zeta function. We prove that the computation of the Ihara coefficients for unweighted graphs is a special case of our proposed method for unit edge weights. We also present a spectral analysis of the Ihara coefficients and indicate their advantages over other graph spectral methods. We apply the proposed graph characterization method to capturing graph-class structure and clustering graphs. Experimental results reveal that the Ihara coefficients are more effective than methods based on Laplacian spectra.

    Research areas

  • Ihara coefficients, Ihara zeta function, adjacency matrix, clustering graphs, cycle structure, edge-weighted graphs, graph class structure, permutation invariant manner, polynomial coefficients, quasi characteristic polynomial, reduced Bartholdi zeta function, spectral analysis, unit edge weights, unweighted graph characterization, vertex order permutations, graph theory, pattern clustering, polynomial matrices

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations