Minisymposium on “Matrix Methods in Network Analysis”
July 13, 2016 at ILAS in KU Leuven.
Talk given on joint work with Olivia Simpson (UCSD); David F. Gleich (Purdue University)
Eigenvectors of network-related matrices are powerful tools in uncovering graph clusters, in both global and local settings. Spectral information like the Fiedler vector or a set of eigenvectors can be used to obtain clusters with quality guarantees described by Cheeger-type inequalities. Recent work introduced a locally-biased version of the Fiedler vector to obtain local clusters, and demonstrated an equivalency between this local Fiedler vector and the personalized PageRank diffusion. We discuss an equivalency of a generalization of PageRank to a set of modified Laplacian eigenvectors. PageRank itself can be understood as a matrix function, and many recent graph diffusions for local clustering have expanded on PageRank by exploring alternative matrix functions, like the heat kernel. We show that these alternative graph diffusions are equivalent to special cases of the same generalization of PageRank, use this new framework to adapt a fast algorithm for PageRank to compute these alternative diffusions, and explore their use in “customizable” clustering.