Computer Science – Discrete Mathematics
Scientific paper
2009-11-24
Computer Science
Discrete Mathematics
Scientific paper
We propose a novel distributed algorithm to cluster graphs. The algorithm recovers the solution obtained from spectral clustering without the need for expensive eigenvalue/vector computations. We prove that, by propagating waves through the graph, a local fast Fourier transform yields the local component of every eigenvector of the Laplacian matrix, thus providing clustering information. For large graphs, the proposed algorithm is orders of magnitude faster than random walk based approaches. We prove the equivalence of the proposed algorithm to spectral clustering and derive convergence rates. We demonstrate the benefit of using this decentralized clustering algorithm for community detection in social graphs, accelerating distributed estimation in sensor networks and efficient computation of distributed multi-agent search strategies.
Banaszuk Andrzej
Sahai Tuhin
Speranzon Alberto
No associations
LandOfFree
Hearing the clusters in a graph: A distributed algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Hearing the clusters in a graph: A distributed algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hearing the clusters in a graph: A distributed algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-622561