Distributed Algorithms for Finding Local Clusters Using Heat Kernel Pagerank

Autor:	Fan Chung, Olivia Simpson
Rok vydání:	2015
Předmět:	Theoretical computer science Speedup PageRank law Distributed algorithm Computer science Distributed element model Computation Cluster (physics) Random walk Algorithm Heat kernel law.invention
Zdroj:	Lecture Notes in Computer Science ISBN: 9783319267838 WAW
DOI:	10.1007/978-3-319-26784-5_14
Popis:	We consider the problem of computing local clusters in large graphs distributed across nodes in a network using two different models of distributed computation. We give a distributed algorithm that computes a local cluster in time that depends only logarithmically on the size of the graph in the CONGEST model. In particular, when the conductance of the optimal local cluster is known, the algorithm runs in time entirely independent of the size of the graph and depends only on error bounds for approximation. We also show that the local cluster problem can be computed in the k-machine distributed model in sublinear time. The speedup of our local cluster algorithms is mainly due to the use of our distributed algorithm for heat kernel pagerank.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::eb36349a24267fba15ab5dccd9ea7117 https://doi.org/10.1007/978-3-319-26784-5_14 Zobrazit plný text záznamu