BibSonomy publications for /author/KempeWed Jan 25 07:56:31 CET 2012J. Comput. Syst. Sci.170-83A decentralized algorithm for spectral analysis742008expanders 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(τmixlog2n) 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 linearly on the degree of the node, polynomially on k, but not at all on the (typically much larger) number n of nodes. To achieve independence of n, the coordinates of the computed eigenvectors are held locally by the nodes to which they correspond, enabling many eigenanalyses without distributing complete global state.Sun Jan 15 00:00:00 CET 2012International Conference on Computational Science (3)conf/iccS/2006-3514-521Lecture Notes in Computer ScienceA Generic Multi-scale Modeling Framework for Reactive Observing Systems: An Overview.39932006dblp Sun Jan 15 00:00:00 CET 2012International Conference on Computational Science (1)conf/iccS/2007-1995-1001Lecture Notes in Computer ScienceAMBROSia: An Autonomous Model-Based Reactive Observing System.44872007dblp Sun Jan 01 00:00:00 CET 2012CoRRThe Robust Price of Anarchy of Altruistic Gamesabs/1112.36802011dblp Fri Dec 23 00:00:00 CET 2011ACLconf/acl/1997460-467Finite State Transducers Approximating Hidden Markov Models.1997dblp Fri Dec 16 00:00:00 CET 2011ICMLconf/icml/20111057-1064Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection.2011dblp Wed Dec 07 00:00:00 CET 2011Electronic Colloquium on Computational Complexity (ECCC)086Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function.132006dblp Mon Dec 05 00:00:00 CET 2011CoRRPart-of-Speech Tagging with Two Sequential Transducerscs.CL/01100272001dblp Mon Dec 05 00:00:00 CET 2011CoRRReduction of Intermediate Alphabets in Finite-State Transducer Cascadescs.CL/00100302000dblp Mon Dec 05 00:00:00 CET 2011CoRRFrugal and Truthful Auctions for Vertex Covers, Flows, and Cutsabs/0912.33102009dblp Mon Dec 05 00:00:00 CET 2011CoRRQuantum Communication Cannot Simulate a Public Coinquant-ph/04110512004dblp Mon Dec 05 00:00:00 CET 2011CoRRLook-Back and Look-Ahead in the Conversion of Hidden Markov Models into Finite State Transducerscmp-lg/98020011998dblp Mon Dec 05 00:00:00 CET 2011CoRRFalse-name-proof Mechanisms for Hiring a Teamabs/1106.23782011dblp Mon Dec 05 00:00:00 CET 2011CoRRStrengths and Weaknesses of Quantum Fingerprintingabs/quant-ph/06031732006dblp Mon Dec 05 00:00:00 CET 2011CoRREstimating the Average of a Lipschitz-Continuous Function from One Sampleabs/1101.38042011dblp Mon Dec 05 00:00:00 CET 2011CoRRSelected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machinesabs/1104.53622011dblp Mon Dec 05 00:00:00 CET 2011CoRROn the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphsabs/cond-mat/05030872005dblp Mon Dec 05 00:00:00 CET 2011CoRRNo Strong Parallel Repetition with Entangled and Non-signaling Proversabs/0911.02012009dblp Mon Dec 05 00:00:00 CET 2011CoRRAlgorithms for weighted multi-tape automatacs.CL/04060032004dblp Mon Dec 05 00:00:00 CET 2011CoRRApproximation algorithms for QMA-complete problemsabs/1101.38842011dblp