@article{DBLP:journals/jcss/KempeM08,
  abstract = {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.},
  added-at = {2012-01-25T07:56:31.000+0100},
  author = {Kempe, David and McSherry, Frank},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  biburl = {http://www.bibsonomy.org/bibtex/2ed42abde4535669c1bf2aeff272dd24d/monoid},
  doi = {10.1016/j.jcss.2007.04.014},
  interhash = {7b7293ee3d1a1b3b0cd1562376182fed},
  intrahash = {ed42abde4535669c1bf2aeff272dd24d},
  journal = {J. Comput. Syst. Sci.},
  keywords = {expanders},
  number = 1,
  pages = {70-83},
  title = {A decentralized algorithm for spectral analysis},
  volume = 74,
  year = 2008
}

@inproceedings{conf/iccS/GolubchikCDDGKOSSSZ06,
  added-at = {2012-01-15T00:00:00.000+0100},
  author = {Golubchik, Leana and Caron, David A. and Das, Abhimanyu and Dhariwal, Amit and Govindan, Ramesh and Kempe, David and Oberg, Carl and Sharma, Abhishek and Stauffer, Beth and Sukhatme, Gaurav S. and 0010, Bin Zhang},
  biburl = {http://www.bibsonomy.org/bibtex/2b71d5f3dfb046c1194f3981d0dc5faf8/dblp},
  booktitle = {International Conference on Computational Science (3)},
  crossref = {conf/iccS/2006-3},
  editor = {Alexandrov, Vassil N. and van Albada, G. Dick and Sloot, Peter M. A. and Dongarra, Jack},
  ee = {http://dx.doi.org/10.1007/11758532_68},
  interhash = {d8572572adae6dd9ab9f8e5d55cb2c0d},
  intrahash = {b71d5f3dfb046c1194f3981d0dc5faf8},
  isbn = {3-540-34383-0},
  keywords = {dblp},
  pages = {514-521},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {A Generic Multi-scale Modeling Framework for Reactive Observing Systems: An Overview.},
  url = {http://dblp.uni-trier.de/db/conf/iccS/iccS2006-3.html#GolubchikCDDGKOSSSZ06},
  volume = 3993,
  year = 2006
}

@inproceedings{conf/iccS/CaronDDGGKOSSSZ07,
  added-at = {2012-01-15T00:00:00.000+0100},
  author = {Caron, David A. and Das, Abhimanyu and Dhariwal, Amit and Golubchik, Leana and Govindan, Ramesh and Kempe, David and Oberg, Carl and Sharma, Abhishek and Stauffer, Beth and Sukhatme, Gaurav and 0010, Bin Zhang},
  biburl = {http://www.bibsonomy.org/bibtex/267df78ea253affbc86d9a245a8b21ec1/dblp},
  booktitle = {International Conference on Computational Science (1)},
  crossref = {conf/iccS/2007-1},
  editor = {Shi, Yong and van Albada, G. Dick and Dongarra, Jack and Sloot, Peter M. A.},
  ee = {http://dx.doi.org/10.1007/978-3-540-72584-8_131},
  interhash = {19635846f28cc4ba53d9b0e3ac42992d},
  intrahash = {67df78ea253affbc86d9a245a8b21ec1},
  isbn = {978-3-540-72583-1},
  keywords = {dblp},
  pages = {995-1001},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {AMBROSia: An Autonomous Model-Based Reactive Observing System.},
  url = {http://dblp.uni-trier.de/db/conf/iccS/iccS2007-1.html#CaronDDGGKOSSSZ07},
  volume = 4487,
  year = 2007
}

@article{journals/corr/abs-1112-3680,
  added-at = {2012-01-01T00:00:00.000+0100},
  author = {Chen, Po-An and de Keijzer, Bart and Kempe, David and Schäfer, Guido},
  biburl = {http://www.bibsonomy.org/bibtex/236195cb25eb0159bbd80446847089f2f/dblp},
  ee = {http://arxiv.org/abs/1112.3680},
  interhash = {b1808a86d2612d99fce831a94b0d5304},
  intrahash = {36195cb25eb0159bbd80446847089f2f},
  journal = {CoRR},
  keywords = {dblp},
  title = {The Robust Price of Anarchy of Altruistic Games},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr1112.html#abs-1112-3680},
  volume = {abs/1112.3680},
  year = 2011
}

@inproceedings{conf/acl/Kempe97,
  added-at = {2011-12-23T00:00:00.000+0100},
  author = {Kempe, André},
  biburl = {http://www.bibsonomy.org/bibtex/2229405b9593ea4258e23c5800fa576fb/dblp},
  booktitle = {ACL},
  crossref = {conf/acl/1997},
  editor = {Cohen, Philip R. and Wahlster, Wolfgang},
  ee = {http://aclweb.org/anthology-new/P/P97/},
  interhash = {4740e458b7631422703a345bbd3a096d},
  intrahash = {229405b9593ea4258e23c5800fa576fb},
  keywords = {dblp},
  pages = {460-467},
  publisher = {Morgan Kaufmann Publishers / ACL},
  title = {Finite State Transducers Approximating Hidden Markov Models.},
  url = {http://dblp.uni-trier.de/db/conf/acl/acl97.html#Kempe97},
  year = 1997
}

@inproceedings{conf/icml/DasK11,
  added-at = {2011-12-16T00:00:00.000+0100},
  author = {Das, Abhimanyu and Kempe, David},
  biburl = {http://www.bibsonomy.org/bibtex/275c48128e8b43ad8f1572be66cca54dd/dblp},
  booktitle = {ICML},
  crossref = {conf/icml/2011},
  editor = {Getoor, Lise and Scheffer, Tobias},
  interhash = {dccee451fad3530d1f27410ea351af21},
  intrahash = {75c48128e8b43ad8f1572be66cca54dd},
  keywords = {dblp},
  pages = {1057-1064},
  publisher = {Omnipress},
  title = {Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection.},
  url = {http://dblp.uni-trier.de/db/conf/icml/icml2011.html#DasK11},
  year = 2011
}

@article{journals/eccc/GavinskyKW06,
  added-at = {2011-12-07T00:00:00.000+0100},
  author = {Gavinsky, Dmitry and Kempe, Julia and de Wolf, Ronald},
  biburl = {http://www.bibsonomy.org/bibtex/2aaa7a6e7f0fafa3c65856a16d2283175/dblp},
  ee = {http://eccc.hpi-web.de/eccc-reports/2006/TR06-086/index.html},
  interhash = {7ab182c32ccb873f49a445942d79dc4e},
  intrahash = {aaa7a6e7f0fafa3c65856a16d2283175},
  journal = {Electronic Colloquium on Computational Complexity (ECCC)},
  keywords = {dblp},
  number = 086,
  title = {Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function.},
  url = {http://dblp.uni-trier.de/db/journals/eccc/eccc13.html#GavinskyKW06},
  volume = 13,
  year = 2006
}

@article{journals/corr/cs-CL-0110027,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Kempe, André},
  biburl = {http://www.bibsonomy.org/bibtex/2149b3ebae9e813f8ef4274080d57fb77/dblp},
  ee = {http://arxiv.org/abs/cs.CL/0110027},
  interhash = {0c3efed8a6e521ccb5b1e9861b73ca08},
  intrahash = {149b3ebae9e813f8ef4274080d57fb77},
  journal = {CoRR},
  keywords = {dblp},
  title = {Part-of-Speech Tagging with Two Sequential Transducers},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr0110.html#cs-CL-0110027},
  volume = {cs.CL/0110027},
  year = 2001
}

@article{journals/corr/cs-CL-0010030,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Kempe, André},
  biburl = {http://www.bibsonomy.org/bibtex/2df6cc57afd86c788036feab89cb487e9/dblp},
  ee = {http://arxiv.org/abs/cs.CL/0010030},
  interhash = {bf9bf1bb4dbe153925cc90adcbadc592},
  intrahash = {df6cc57afd86c788036feab89cb487e9},
  journal = {CoRR},
  keywords = {dblp},
  title = {Reduction of Intermediate Alphabets in Finite-State Transducer Cascades},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr0010.html#cs-CL-0010030},
  volume = {cs.CL/0010030},
  year = 2000
}

@article{journals/corr/abs-0912-3310,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Kempe, David and Salek, Mahyar and Moore, Cristopher},
  biburl = {http://www.bibsonomy.org/bibtex/28182b6a11b43389fe82382f9bf6f86b2/dblp},
  ee = {http://arxiv.org/abs/0912.3310},
  interhash = {37fe046e8e4555c6217bccd22d73bdaf},
  intrahash = {8182b6a11b43389fe82382f9bf6f86b2},
  journal = {CoRR},
  keywords = {dblp},
  title = {Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr0912.html#abs-0912-3310},
  volume = {abs/0912.3310},
  year = 2009
}

@article{journals/corr/quant-ph-0411051,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Gavinsky, Dmitry and Kempe, Julia and de Wolf, Ronald},
  biburl = {http://www.bibsonomy.org/bibtex/2be22b281137ca6e8de67dfe77ede6db9/dblp},
  ee = {http://arxiv.org/abs/quant-ph/0411051},
  interhash = {5390dd42651de539a5c4df046a127c15},
  intrahash = {be22b281137ca6e8de67dfe77ede6db9},
  journal = {CoRR},
  keywords = {dblp},
  title = {Quantum Communication Cannot Simulate a Public Coin},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr0411.html#quant-ph-0411051},
  volume = {quant-ph/0411051},
  year = 2004
}

@article{journals/corr/cmp-lg-9802001,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Kempe, André},
  biburl = {http://www.bibsonomy.org/bibtex/2b982dc25846d1a30f1c6db64047a6801/dblp},
  ee = {http://arxiv.org/abs/cmp-lg/9802001},
  interhash = {de9b183ae77c7d55242ab6f32f73d881},
  intrahash = {b982dc25846d1a30f1c6db64047a6801},
  journal = {CoRR},
  keywords = {dblp},
  title = {Look-Back and Look-Ahead in the Conversion of Hidden Markov Models into Finite State Transducers},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr9802.html#cmp-lg-9802001},
  volume = {cmp-lg/9802001},
  year = 1998
}

@article{journals/corr/abs-1106-2378,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Iwasaki, Atsushi and Kempe, David and Salek, Mahyar and Yokoo, Makoto},
  biburl = {http://www.bibsonomy.org/bibtex/222e342ced606a68d4c9b4c38161d021e/dblp},
  ee = {http://arxiv.org/abs/1106.2378},
  interhash = {b11dd7c76696671d5627f51f59d1f2cc},
  intrahash = {22e342ced606a68d4c9b4c38161d021e},
  journal = {CoRR},
  keywords = {dblp},
  title = {False-name-proof Mechanisms for Hiring a Team},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr1106.html#abs-1106-2378},
  volume = {abs/1106.2378},
  year = 2011
}

@article{journals/corr/abs-quant-ph-0603173,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Gavinsky, Dmitry and Kempe, Julia and de Wolf, Ronald},
  biburl = {http://www.bibsonomy.org/bibtex/2d779cfb8961e222c2faa3338524b4df0/dblp},
  ee = {http://arxiv.org/abs/quant-ph/0603173},
  interhash = {4df0d3750fa63231df4c012b91f2400e},
  intrahash = {d779cfb8961e222c2faa3338524b4df0},
  journal = {CoRR},
  keywords = {dblp},
  title = {Strengths and Weaknesses of Quantum Fingerprinting},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr0603.html#abs-quant-ph-0603173},
  volume = {abs/quant-ph/0603173},
  year = 2006
}

@article{journals/corr/abs-1101-3804,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Das, Abhimanyu and Kempe, David},
  biburl = {http://www.bibsonomy.org/bibtex/276a3a68fb7a03a5fe8acfe25fdd42eaf/dblp},
  ee = {http://arxiv.org/abs/1101.3804},
  interhash = {8318d93cc7e3f1e2cb22f83db1e087b5},
  intrahash = {76a3a68fb7a03a5fe8acfe25fdd42eaf},
  journal = {CoRR},
  keywords = {dblp},
  title = {Estimating the Average of a Lipschitz-Continuous Function from One Sample},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr1101.html#abs-1101-3804},
  volume = {abs/1101.3804},
  year = 2011
}

@article{journals/corr/abs-1104-5362,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Kempe, André},
  biburl = {http://www.bibsonomy.org/bibtex/2b3a5c7028682380e433d744831dc5834/dblp},
  ee = {http://arxiv.org/abs/1104.5362},
  interhash = {2e17a2b277b84e60f656830411a886d9},
  intrahash = {b3a5c7028682380e433d744831dc5834},
  journal = {CoRR},
  keywords = {dblp},
  title = {Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr1104.html#abs-1104-5362},
  volume = {abs/1104.5362},
  year = 2011
}

@article{journals/corr/abs-cond-mat-0503087,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Achlioptas, Dimitris and Clauset, Aaron and Kempe, David and Moore, Cristopher},
  biburl = {http://www.bibsonomy.org/bibtex/28303082cbd3175fa62b0ae074c288f24/dblp},
  ee = {http://arxiv.org/abs/cond-mat/0503087},
  interhash = {a35d213e53abefbad22a8472be4e9c18},
  intrahash = {8303082cbd3175fa62b0ae074c288f24},
  journal = {CoRR},
  keywords = {dblp},
  title = {On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr0503.html#abs-cond-mat-0503087},
  volume = {abs/cond-mat/0503087},
  year = 2005
}

@article{journals/corr/abs-0911-0201,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Kempe, Julia and Regev, Oded},
  biburl = {http://www.bibsonomy.org/bibtex/2ab31749c0c5ec3b94aa67e52619bce53/dblp},
  ee = {http://arxiv.org/abs/0911.0201},
  interhash = {fa0d8f74a70b9515248ded8f12eefed2},
  intrahash = {ab31749c0c5ec3b94aa67e52619bce53},
  journal = {CoRR},
  keywords = {dblp},
  title = {No Strong Parallel Repetition with Entangled and Non-signaling Provers},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr0911.html#abs-0911-0201},
  volume = {abs/0911.0201},
  year = 2009
}

@article{journals/corr/cs-CL-0406003,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Kempe, André and Guingne, Franck and Nicart, Florent},
  biburl = {http://www.bibsonomy.org/bibtex/2bfdb133b7aa13e444154903e361d323a/dblp},
  ee = {http://arxiv.org/abs/cs.CL/0406003},
  interhash = {1d6c16a3d5492457cae68cd835672e64},
  intrahash = {bfdb133b7aa13e444154903e361d323a},
  journal = {CoRR},
  keywords = {dblp},
  title = {Algorithms for weighted multi-tape automata},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr0406.html#cs-CL-0406003},
  volume = {cs.CL/0406003},
  year = 2004
}

@article{journals/corr/abs-1101-3884,
  added-at = {2011-12-05T00:00:00.000+0100},
  author = {Gharibian, Sevag and Kempe, Julia},
  biburl = {http://www.bibsonomy.org/bibtex/22bbc8ed88c6e980a62e52f2318b86e2a/dblp},
  ee = {http://arxiv.org/abs/1101.3884},
  interhash = {8cdc58839c8050b74e974d5bd9376247},
  intrahash = {2bbc8ed88c6e980a62e52f2318b86e2a},
  journal = {CoRR},
  keywords = {dblp},
  title = {Approximation algorithms for QMA-complete problems},
  url = {http://dblp.uni-trier.de/db/journals/corr/corr1101.html#abs-1101-3884},
  volume = {abs/1101.3884},
  year = 2011
}