Characterizing Graphs Using Approximate von Neumann Entropy

摘要

In this paper we show how to approximate the von Neumann entropy associated with the Laplacian eigenspectrum of graphs and exploit it as a characteristic for the clustering and classification of graphs. We commence from the von Neumann entropy and approximate it by replacing the Shannon entropy by its quadratic counterpart. We then show how the quadratic entropy can be expressed in terms of a series of permutation invariant traces. This leads to a simple approximate form for the entropy in terms of the elements of the adjacency matrix which can be evaluated in quadratic time. We use this approximate expression for the entropy as a unary characteristic for graph clustering. Experiments on real world data illustrate the effectiveness of the method.