Spectral Clustering with Epidemic Diffusion
  Spectral clustering is widely used to partition graphs into distinct modules
or communities. Existing methods for spectral clustering use the eigenvalues
and eigenvectors of the graph Laplacian, an operator that is closely associated
with random walks on graphs. We propose a new spectral partitioning method that
exploits the properties of epidemic diffusion. An epidemic is a dynamic process
that, unlike the random walk, simultaneously transitions to all the neighbors
of a given node. We show that the replicator, an operator describing epidemic
diffusion, is equivalent to the symmetric normalized Laplacian of a reweighted
graph with edges reweighted by the eigenvector centralities of their incident
nodes. Thus, more weight is given to edges connecting more central nodes. We
describe a method that partitions the nodes based on the componentwise ratio of
the replicator's second eigenvector to the first, and compare its performance
to traditional spectral clustering techniques on synthetic graphs with known
community structure. We demonstrate that the replicator gives preference to
dense, clique-like structures, enabling it to more effectively discover
communities that may be obscured by dense intercommunity linking.
