×

zbMATH — the first resource for mathematics

Hearing the clusters of a graph: A distributed algorithm. (English) Zbl 1244.93016
Summary: 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.

MSC:
93A15 Large-scale systems
94C15 Applications of graph theory to circuits and networks
93A14 Decentralized systems
Software:
GVF
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akyildiz, I.F.; Su, W.; Sankarasubramaniam, Y.; Cayirci, E., A survey on sensor networks, IEEE communications magazine, 40, 8, 102-114, (2002)
[2] Alrikson, P., & Rantzer, A. (2007). Experimental evaluation of a distributed Kalman filter algorithm. In IEEE conference on decision and control.
[3] Belkin, M.; Niyogi, P., Towards a theoretical foundation for Laplacian-based manifold methods, Journal of computer and system sciences, 74, 1289-1308, (2008) · Zbl 1157.68056
[4] Boyd, S.; Diaconis, P.; Xiao, L., Fastest mixing Markov chain on a graph, SIAM review, 46, 667-689, (2004) · Zbl 1063.60102
[5] Carli, R.; Chiuso, A.; Schenato, L.; Zampieri, S., Distributed Kalman filtering based on consensus strategies, IEEE journal on selected areas in communications, 26, 622-633, (2008)
[6] Chung, F.R.K., ()
[7] Coifman, R.R.; Shkolnisky, Y.; Sigworth, F.J.; Singer, A., Graph Laplacian tomography from unknown random projections, IEEE transactions on image processing, 17, 10, 1891-1899, (2008) · Zbl 1372.94055
[8] Evans, L.C., Partial differential equations, (1998), American Mathematical Society
[9] Fiedler, M., Algebraic connectivity of graphs, Czechoslovak mathematical journal, 23, 289-305, (1973) · Zbl 0265.05119
[10] Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak mathematical journal, 25, 4, 619-633, (1975) · Zbl 0437.15004
[11] Franceschelli, M., Gasparri, A., & Seatzu, A. G. C. (2009). Decentralized Laplacian eigenvalues estimation for networked multi-agent systems. In Proceedings of the conference on decision and control. · Zbl 1284.93017
[12] Friedman, J.; Tillich, J.P., Wave equations for graphs and edge-based Laplacians, Pacific journal of mathematics, 216, 2, 229-266, (2004) · Zbl 1072.35107
[13] Speer, N., Fröhlich, H., Spieth, C., & Zell, A. (2005). Functional grouping of genes using spectral clustering and gene ontology. In IEEE international joint conference on neural networks. Vol. 1 (pp. 298-303).
[14] Ghiasi, S.; Srivastava, A.; Yang, X.; Sarrafzadeh, M., Optimal energy aware clustering in sensor networks, Sensors, 2, 258-269, (2002)
[15] Girvan, M.; Newman, M.E.J., Community structure in social and biological networks, Proceedings of the national Academy of sciences, 99, 12, 7821-7826, (2002) · Zbl 1032.91716
[16] Golub, G.; Loan, C.V., Matrix computations, (1996), John Hopkins University Press
[17] Hein, M., Uniform convergence of adaptive graph-based regularization, (), 50-64 · Zbl 1143.68416
[18] Hein, M.; Audibert, J.-Y.; von Luxburg, U., From graphs to manifolds—weak and strong pointwise consistency of graph Laplacians, (), 470-485 · Zbl 1095.68097
[19] Herman, I.; Melançon, G.; Marshall, M.S., Graph visualization and navigation in information visualization: a survey, IEEE transactions on visualization and computer graphics, 6, 1, 24-43, (2000)
[20] Kac, M., Can one hear the shape of a drum?, The American mathematical monthly, 73, 4, 1-23, (1966) · Zbl 0139.05603
[21] Kempe, D.; McSherry, F., A decentralized algorithm for spectral analysis, Journal of computer and system sciences, 74, 1, 70-83, (2008) · Zbl 1131.68074
[22] Kernighan, B.W.; Lin, S., A efficient heuristic procedure for partitioning graphs, The Bell system technical journal, 49, 291-307, (1970) · Zbl 0333.05001
[23] Kim, J. -H., West, M., Lall, S., Scholte, E., & Banaszuk, A. (2008b). Stochastic multiscale approaches to consensus problems. In Conference on decision and control.
[24] Kim, J. -H., West, M., Scholte, E., & Narayanan, S. (2008a). Multiscale consensus for decentralized estimation and its application to building systems. In American control conference.
[25] Klus, S.; Sahai, T.; Liu, C.; Dellnitz, M., An efficient algorithm for the parallel solution of high-dimensional differential equations, Journal of computational and applied mathematics, 235, 9, 3053-3062, (2011) · Zbl 1210.65145
[26] Kottak, C.P., Cultural anthropology, (1991), McGraw-Hill
[27] Lancichinetti, A.; Fortunato, S.; Radicchi, F., Benchmark graphs for testing community detection algorithms, Physical review E, 78, 046110, (2008)
[28] Luxburg, U. v., Bousquet, O., & Belkin, M. (2004). On the convergence of spectral clustering on random samples: the normalized case. In Proceedings of the 17th annual conference on learning theory. COLT (pp. 457-471). · Zbl 1078.68134
[29] Mathew, G., & Mezic, I. (2009). Spectral multiscale coverage: a uniform coverage algorithm for mobile sensor networks. In Proceedings of the conference on decision and control (pp. 7872-7877).
[30] Mohar, B. (1991). The Laplacian spectrum of graphs. Department of mathematics, Simon Fraser university. Tech. rep. Canada.
[31] Muhammad, A., & Jadbabaie, A. (2007). Distributed computation of homology groups by gossip. In Proceedings of the american control conference (pp. 3438-3443).
[32] Nadler, B.; Lafon, S.; Coifman, R.R.; Kevrekidis, I.G., Diffusion maps, spectral clustering and eigenfunctions of fokker – planck operators, Advances in neural information processing systems, 18, (2006)
[33] Nadler, B.; Lafon, S.; Coifman, R.R.; Kevrekidis, I.G., Diffusion maps, spectral clustering and reaction coordinates of dynamical systems, Applied and computational harmonic analysis, 21, 113-127, (2006), (special issue on) Diffusion maps and wavelets · Zbl 1103.60069
[34] Newman, M.E.J., Modularity and community structure in networks, Proceedings of the national Academy of sciences, 103, 8577-8582, (2006)
[35] Olfati-Saber, R. (2007). Distributed Kalman filtering for sensor networks. In IEEE conference on decision and control. · Zbl 1112.93369
[36] Paccanaro, A.; Casbon, J.A.; Saqi, M.A.S., Spectral clustering of protein sequences, Nucleic acids research, 34, 1571-1580, (2006)
[37] Palla, G.; Derényi, I.; Farkas, I.; Vicsek, T., Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435, 814-818, (2005)
[38] Porter, M.A.; Onnela, J.-P.; Mucha, P.J., Communities in networks, Notices of the American mathematical society, (2009) · Zbl 1188.05142
[39] Reichardt, J.; Burnholdt, S., Detecting fuzzy community structures with a Potts model, Physical review letters, 93, 218701, (2004)
[40] Rosvall, M.; Bergstrom, C.T., An information—theoretic framework for resolving community structure in complex networks, Proceedings of the national Academy of sciences, 104, 18, 7327-7331, (2007)
[41] Schmidt, R.O., Multiple emitter location and signal parameter estimation, IEEE transactions on antennas and propagation, AP-34, 3, 276-280, (1986)
[42] Selle, C., & West, M. (2009). Multiscale networks for distributed consensus algorithms. In IEEE conference on decision and control and Chinese control conference.
[43] Shah, D., Gossip algorithms, (2009), Now Publisher Inc. · Zbl 1185.68072
[44] Speranzon, A.; Fischione, C.; Johansson, K.H.; Sangiovanni-Vincentelli, A., A distributed minimum variance estimator for sensor networks, IEEE journal on selected areas in communications, 26, 609-621, (2008)
[45] Spielman, D. A., & Teng, S. -H. (2004). Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium on theory of computing (pp. 81-90). · Zbl 1192.65048
[46] Stoer, M.; Wagner, F., A simple MIN-cut algorithm, Journal of the ACM, 44, 4, 585-591, (1997) · Zbl 0891.68071
[47] Varigonda, S., Kalmar-Nagy, T., Labarre, B., & Mezic, I. (2004). Graph decomposition methods for uncertainty propagation in complex, nonlinear interconnected dynamical systems. In IEEE conference on decision and control. Vol. 2 (pp. 1794-1798).
[48] von Luxburg, U., A tutorial on spectral clustering, Statistics and computing, 17, 395-416, (2007)
[49] Wagner, D., & Wagner, F. (1993). Between min cut and graph bisection. In Proceedings of the 18th international symposium on mathematical foundations of computer science. MFCS (pp. 744-750). · Zbl 0925.05053
[50] Zachary, W.W., An information flow model for conflict and fission in small groups, Journal of anthropological research, 33, 452-473, (1977)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.