Because of the significant increase in size and complexity of the networks, the distributed computation of eigenvalues and eigenvectors of graph matrices has become very challenging and yet it remains as important as before. In this paper we develop efficient distributed algorithms to detect, with higher resolution, closely situated eigenvalues and corresponding eigenvectors of symmetric graph matrices. We model the system of graph spectral computation as physical systems with Lagrangian and Hamiltonian dynamics. The spectrum of Laplacian matrix, in particular, is framed as a classical spring-mass system with Lagrangian dynamics. The spectrum of any general symmetric graph matrix turns out to have a simple connection with quantum systems and it can be thus formulated as a solution to a Schr "odinger-type differential equation. Taking into account the higher resolution requirement in the spectrum computation and the related stability issues in the numerical solution of the underlying differential equation, we propose the application of symplectic integrators to the calculation of eigenspectrum. The effectiveness of the proposed techniques is demonstrated with numerical simulations on real-world networks of different sizes and complexities.
In comparison to @cite_7 we do not deform the system and we use new symplectic numerical integrators @cite_1 @cite_12 . For the problem of distributed spectral decomposition in networks, one of the first and prominent works appeared in @cite_5 . But their algorithm requires distributed orthonormalization at each step and they solve this difficult operation via random walks. But if the graph is not well-connected (low conductance), this task will take a very long time to converge. Our distributed implementation based on fluid diffusion in the network does not require such orthonormalization.
@cite_5 @cite_1 @cite_12 @cite_7
2158886595 1976957036 2124605172 2963662649
In many large network settings, such as computer networks, social networks, or hyperlinked text documents, much information can be obtained from the network's spectral properties. However, traditional centralized approaches for computing eigenvectors struggle with at least two obstacles: the data may be difficult to obtain (both due to technical reasons and because of privacy concerns), and the sheer size of the networks makes the computation expensive. A decentralized, distributed algorithm addresses both of these obstacles: it utilizes the computational power of all nodes in the network and their ability to communicate, thus speeding up the computation with the network size. And as each node knows its incident edges, the data collection problem is avoided as well.Our main result is a simple decentralized algorithm for computing the top k eigenvectors of a symmetric weighted adjacency matrix, and a proof that it converges essentially in O(τ MIX log2 n) rounds of communication and computation, where τ MIX is the mixing time of a random walk on the network. An additional contribution of our work is a decentralized way of actually detecting convergence, and diagnosing the current error. Our protocol scales well, in that the amount of computation performed at any node in any one round, and the sizes of messages sent, depend polynomially on k, but not on the (typically much larger) number n of nodes. We present a family of symplectic splitting methods especially tailored to solve numerically the time-dependent Schrodinger equation. When discretized in time, this equation can be recast in the form of a classical Hamiltonian system with a Hamiltonian function corresponding to a generalized high-dimensional separable harmonic oscillator. The structure of the system allows us to build highly efficient symplectic integrators at any order. The new methods are accurate, easy to implement, and very stable in comparison with other standard symplectic integrators. We provide a comprehensive survey of splitting and composition methods for the numerical integration of ordinary differential equations (ODEs). Splitting methods constitute an appropriate choice when the vector field associated with the ODE can be decomposed into several pieces and each of them is integrable. This class of integrators are explicit, simple to implement and preserve structural properties of the system. In consequence, they are specially useful in geometric numerical integration. In addition, the numerical solution obtained by splitting schemes can be seen as the exact solution to a perturbed system of ODEs possessing the same geometric properties as the original system. This backward error interpretation has direct implications for the qualitative behavior of the numerical solution as well as for the error propagation along time. Closely connected with splitting integrators are composition methods. We analyze the order conditions required by a method to achieve a given order and summarize the different families of schemes one can find in the literature. Finally, we illustrate the main features of splitting and composition methods on several numerical examples arising from applications. We propose a novel distributed algorithm to cluster graphs. The algorithm recovers the solution obtained from spectral clustering without the need for expensive eigenvalue eigenvector 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.