Hearing the clusters of a graph: A distributed algorithm
From MaRDI portal
(Redirected from Publication:445023)
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.
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
Cites work
- scientific article; zbMATH DE number 3681933 (Why is no real title available?)
- scientific article; zbMATH DE number 1333614 (Why is no real title available?)
- scientific article; zbMATH DE number 1181255 (Why is no real title available?)
- scientific article; zbMATH DE number 3417498 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- A decentralized algorithm for spectral analysis
- A simple min-cut algorithm
- An Efficient Heuristic Procedure for Partitioning Graphs
- An efficient algorithm for the parallel solution of high-dimensional differential equations
- Can One Hear the Shape of a Drum?
- Communities in Networks
- Community structure in social and biological networks
- Decentralized estimation of Laplacian eigenvalues in multi-agent systems
- Diffusion maps, spectral clustering and reaction coordinates of dynamical systems
- Distributed Kalman Filtering and Sensor Fusion in Sensor Networks
- Fastest Mixing Markov Chain on a Graph
- Gossip algorithms
- Graph Laplacian Tomography From Unknown Random Projections
- Learning Theory
- Learning Theory
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Towards a theoretical foundation for Laplacian-based manifold methods
- Uniform Convergence of Adaptive Graph-Based Regularization
- Wave equations for graphs and the edge-based Laplacian
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
- An efficient algorithm for the parallel solution of high-dimensional differential equations
- On nonintrusive uncertainty quantification and surrogate model construction in particle accelerator modeling
- Spectral identification of networks using sparse measurements
- Admissible output consensualization control for singular multi-agent systems with time delays
- 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
- On the advantage of overlapping clusters for minimizing conductance
- Experimental and Efficient Algorithms
- Seeking community structure in networks via biogeography-based optimization with consensus dynamics
- Distributed estimation of Laplacian eigenvalues via constrained consensus optimization problems
- A decentralized algorithm for spectral analysis
- Spectral echolocation via the wave embedding
- Spectrum Consistent Coarsening Approximates Edge Weights
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)
