Abstract

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 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 …

Date

January 1, 1970

Authors

Laura M Smith, Kristina Lerman, Cristina Garcia-Cardona, Allon G Percus, Rumi Ghosh

Journal

Physical Review E—Statistical, Nonlinear, and Soft Matter Physics

Volume

88

Issue

4

Pages

042813

Publisher

American Physical Society