For input @math , let @math denote the set of outputs that are the "legal" answers for a computational problem @math . Suppose @math and members of @math are so large that there is not time to read them in their entirety. We propose a model of local computation algorithms which for a given input @math , support queries by a user to values of specified locations @math in a legal output @math . When more than one legal output @math exists for a given @math , the local computation algorithm should output in a way that is consistent with at least one such @math . Local computation algorithms are intended to distill the common features of several concepts that have appeared in various algorithmic subfields, including local distributed computation, local algorithms, locally decodable codes, and local reconstruction. We develop a technique, based on known constructions of small sample spaces of @math -wise independent random variables and Beck's analysis in his algorithmic approach to the Lov ' a sz Local Lemma, which under certain conditions can be applied to construct local computation algorithms that run in polylogarithmic time and space. We apply this technique to maximal independent set computations, scheduling radio network broadcasts, hypergraph coloring and satisfying @math -SAT formulas.
Recently, local algorithms have been demonstrated to be applicable for computations on the web graph. In @cite_20 @cite_41 @cite_24 @cite_38 @cite_34 , local algorithms are given which, for a given vertex @math in the web graph, computes an approximation to @math 's personalized PageRank vector and computes the vertices that contribute significantly to @math 's PageRank. In these algorithms, evaluations are made only to the nearby neighborhood of @math , so that the running time depends on the accuracy parameters input to the algorithm, but there is no running time dependence on the size of the web-graph. Local graph partitioning algorithms have been presented in @cite_31 @cite_38 which find subsets of vertices whose internal connections are significantly richer than their external connections. The running time of these algorithms depends on the size of the cluster that is output, which can be much smaller than the size of the entire graph.
@cite_38 @cite_41 @cite_24 @cite_31 @cite_34 @cite_20
2086254934 2952246906 2135512436 2106891910
A local graph partitioning algorithm finds a cut near a specified starting vertex, with a running time that depends largely on the size of the small side of the cut, rather than the size of the input graph. In this paper, we present a local partitioning algorithm using a variation of PageRank with a specified starting distribution. We derive a mixing result for PageRank vectors similar to that for random walks, and show that the ordering of the vertices produced by a PageRank vector reveals a cut with small conductance. In particular, we show that for any set C with conductance and volume k, a PageRank vector with a certain starting distribution can be used to produce a set with conductance O ( k ). We present an improved algorithm for computing approximate PageRank vectors, which allows us to find such a set in time proportional to its size. In particular, we can find a cut with conductance at most o , whose small side has volume at least 2b, in time O ( 2^b ^2 m o^2 ) where m is the number of edges in the graph. By combining small sets found by this local partitioning algorithm, we obtain a cut with conductance o and approximately optimal balance in time O ( m ^4 m o^2 ). Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research has shown that such algorithms show significant promise in computing structures like large independent sets in graphs locally. Indeed the promise led to a conjecture by Hatami, and Szegedy HatamiLovaszSzegedy that local algorithms may be able to compute maximum independent sets in (sparse) random @math -regular graphs. In this paper we refute this conjecture and show that every independent set produced by local algorithms is multiplicative factor @math smaller than the largest, asymptotically as @math . Our result is based on an important clustering phenomena predicted first in the literature on spin glasses, and recently proved rigorously for a variety of constraint satisfaction problems on random graphs. Such properties suggest that the geometry of the solution space can be quite intricate. The specific clustering property, that we prove and apply in this paper shows that typically every two large independent sets in a random graph either have a significant intersection, or have a nearly empty intersection. As a result, large independent sets are clustered according to the proximity to each other. While the clustering property was postulated earlier as an obstruction for the success of local algorithms, such as for example, the Belief Propagation algorithm, our result is the first one where the clustering property is used to formally prove limits on local algorithms. We study the design of local algorithms for massive graphs. A local graph algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster---a subset of vertices whose internal connections are significantly richer than its external connections---near a given vertex. The running time of our algorithm, when it finds a nonempty local cluster, is nearly linear in the size of the cluster it outputs. The running time of our algorithm also depends polylogarithmically on the size of the graph and polynomially on the conductance of the cluster it produces. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph.... Motivated by the problem of detecting link-spam, we consider the following graph-theoretic primitive: Given a webgraph G, a vertex v in G, and a parameter δ ∈ (0, 1), compute the set of all vertices that contribute to v at least a δ fraction of v's PageRank. We call this set the δ-contributing set of v. To this end, we define the contribution vector of v to be the vector whose entries measure the contributions of every vertex to the PageRank of v. A local algorithm is one that produces a solution by adaptively examining only a small portion of the input graph near a specified vertex. We give an efficient local algorithm that computes an Ɛ-approximation of the contribution vector for a given vertex by adaptively examining O(1 Ɛ) vertices. Using this algorithm, we give a local approximation algorithm for the primitive defined above. Specifically, we give an algorithm that returns a set containing the δ-contributing set of v and at most O(1 δ) vertices from the δ 2-contributing set of v, and which does so by examining at most O(1 δ) vertices. We also give a local algorithm for solving the following problem: If there exist k vertices that contribute a ρ-fraction to the PageRank of v, find a set of k vertices that contribute at least a (ρ-Ɛ)-fraction to the PageRank of v. In this case, we prove that our algorithm examines at most O(k Ɛ) vertices.