Spectral Clustering with Epidemic Diffusion

Start: 04/03/2013 - 1:15pm
End  : 04/03/2013 - 2:15pm

Applied Math Seminar

Laura Smith (USC Information Sciences Institute)


Epidemic diffusion on a graph is a dynamic process that transitions simultaneously to all of a node's neighbors, in contrast to a random walk, which selects only a single neighbor. Epidemic diffusion is described by the replicator operator, an analog of the graph Laplacian that describes the behavior of random walks. We study the properties of the replicator operator. We show that the replicator is equivalent to the symmetric normalized Laplacian on a graph with edges reweighted by the eigenvector centralities of their incident nodes. Thus, more weight is given to edges connecting more central nodes. We propose a spectral clustering method, partitioning the nodes based on the componentwise ratio of the replicator's second eigenvector to the first. We compare the performance of our clustering technique to traditional spectral clustering methods on a variety of real world and synthetic graphs. We demonstrate how the replicator gives preference to cliques and clique-like structures, enabling it to more effectively discover communities that may be obscured by dense intercommunity linking.