Hearing the clusters of a graph: A distributed algorithm
From MaRDI portal
Publication:445023
DOI10.1016/J.AUTOMATICA.2011.09.019zbMATH Open1244.93016arXiv0911.4729OpenAlexW2963662649MaRDI QIDQ445023FDOQ445023
Authors: Tuhin Sahai, Alberto Speranzon, Andrzej Banaszuk 
Publication date: 24 August 2012
Published in: Automatica (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/0911.4729
Recommendations
- Experimental and Efficient Algorithms
- A decentralized algorithm for spectral analysis
- Distributed algorithms for finding local clusters using heat kernel PageRank
- A decentralized algorithm for spectral analysis
- A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
Decentralized systems (93A14) Large-scale systems (93A15) Applications of graph theory to circuits and networks (94C15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Towards a theoretical foundation for Laplacian-based manifold methods
- An Efficient Heuristic Procedure for Partitioning Graphs
- Community structure in social and biological networks
- Title not available (Why is that?)
- Title not available (Why is that?)
- A decentralized algorithm for spectral analysis
- Diffusion maps, spectral clustering and reaction coordinates of dynamical systems
- Learning Theory
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Decentralized estimation of Laplacian eigenvalues in multi-agent systems
- Title not available (Why is that?)
- Can One Hear the Shape of a Drum?
- Communities in Networks
- A simple min-cut algorithm
- Gossip algorithms
- Fastest Mixing Markov Chain on a Graph
- Wave equations for graphs and the edge-based Laplacian
- Distributed Kalman Filtering and Sensor Fusion in Sensor Networks
- Title not available (Why is that?)
- Learning Theory
- Uniform Convergence of Adaptive Graph-Based Regularization
- Graph Laplacian Tomography From Unknown Random Projections
- An efficient algorithm for the parallel solution of high-dimensional differential equations
Cited In (19)
- Dynamical Systems Theory and Algorithms for NP-hard Problems
- A filter-based clock synchronization protocol for wireless sensor networks
- Continuous relaxations for the traveling salesman problem
- Step-size sequence design for finite-time average consensus in secure wireless sensor networks
- Spectral complexity of directed graphs and application to structural decomposition
- On nonintrusive uncertainty quantification and surrogate model construction in particle accelerator modeling
- An efficient algorithm for the parallel solution of high-dimensional differential equations
- Spectral identification of networks using sparse measurements
- Admissible output consensualization control for singular multi-agent systems with time delays
- Experimental and Efficient Algorithms
- Leader-follower guaranteed-cost consensualization for high-order linear swarm systems with switching topologies
- Fast distributed algebraic connectivity estimation in large scale networks
- Polynomial chaos based uncertainty quantification in Hamiltonian, multi-time scale, and chaotic systems
- A decentralized algorithm for spectral analysis
- On the advantage of overlapping clusters for minimizing conductance
- Seeking community structure in networks via biogeography-based optimization with consensus dynamics
- Distributed estimation of Laplacian eigenvalues via constrained consensus optimization problems
- Spectral echolocation via the wave embedding
- Spectrum Consistent Coarsening Approximates Edge Weights
Uses Software
This page was built for publication: Hearing the clusters of a graph: A distributed algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q445023)
