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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Multiscale Clustering of Hyperspectral Images Through Spectral-Spatial Diffusion Geometry
Clustering algorithms partition a dataset into groups of similar points. The primary contribution of this article is the Multiscale Spatially-Regularized Diffusion Learning (M-SRDL) clustering algorithm, which uses spati…
ClusteringThe spectral dimension of simplicial complexes: a renormalization group theory
Simplicial complexes are increasingly used to study complex system structure and dynamics including diffusion, synchronization and epidemic spreading. The spectral dimension of the graph Laplacian is known to determine t…
Diffusion Subspace Clustering for Hyperspectral Images
Hyperspectral image (HSI) subspace clustering remains a challenging task due to the poor spatial and rich spectral resolutions of HSIs. Most of the existing HSI subspace clustering approaches just extract the spatial and…
ClusteringUnsupervised Clustering and Active Learning of Hyperspectral Images with Nonlinear Diffusion
The problem of unsupervised learning and segmentation of hyperspectral images is a significant challenge in remote sensing. The high dimensionality of hyperspectral data, presence of substantial noise, and overlap of cla…
Active LearningClusteringLarge-scale spectral clustering using diffusion coordinates on landmark-based bipartite graphs
Spectral clustering has received a lot of attention due to its ability to separate nonconvex, non-intersecting manifolds, but its high computational complexity has significantly limited its applicability. Motivated by th…
ClusteringImage/Document ClusteringSemantic Segmentation