Graph Characterization via Ihara Coefficients

TY - JOUR

T1 - Graph Characterization via Ihara Coefficients

AU - Ren, P.

AU - Wilson, R. C.

AU - Hancock, E. R.

PY - 2011/2

Y1 - 2011/2

N2 - 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.

AB - 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.

KW - Ihara coefficients

KW - Ihara zeta function

KW - adjacency matrix

KW - clustering graphs

KW - cycle structure

KW - edge-weighted graphs

KW - graph class structure

KW - permutation invariant manner

KW - polynomial coefficients

KW - quasi characteristic polynomial

KW - reduced Bartholdi zeta function

KW - spectral analysis

KW - unit edge weights

KW - unweighted graph characterization

KW - vertex order permutations

KW - graph theory

KW - pattern clustering

KW - polynomial matrices

UR - http://www.scopus.com/inward/record.url?scp=79951673682&partnerID=8YFLogxK

U2 - 10.1109/TNN.2010.2091969

DO - 10.1109/TNN.2010.2091969

M3 - Article

SN - 1045-9227

VL - 22

SP - 233

EP - 245

JO - IEEE Transactions on Neural Networks

JF - IEEE Transactions on Neural Networks

IS - 2

M1 - 5648360

ER -