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 2039191721 2033252376 2045107949 2106891910 2069153192
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 ). We introduce a novel bookmark-coloring algorithm (BCA) that computes authority weights over the web pages utilizing the web hyperlink structure. The computed vector (BCV) is similar to the PageRank vector defined for a page-specific teleportation. Meanwhile, BCA is very fast, and BCV is sparse. BCA also has important algebraic properties. If several BCVs corresponding to a set of pages (called hub) are known, they can be leveraged in computing arbitrary BCV via a straightforward algebraic process and hub BCVs can be efficiently computed and encoded. Personalized PageRank expresses link-based page quality around user selected pages. The only previous personalized PageRank algorithm that can serve on-line queries for an unrestricted choice of pages on large graphs is our Monte Carlo algorithm [WAW 2004]. In this paper we achieve unrestricted personalization by combining rounding and randomized sketching techniques in the dynamic programming algorithm of Jeh and Widom [WWW 2003]. We evaluate the precision of approximation experimentally on large scale real-world data and find significant improvement over previous results. As a key theoretical contribution we show that our algorithms use an optimal amount of space by also improving earlier asymptotic worst-case lower bounds. Our lower bounds and algorithms apply to the SimRank as well; of independent interest is the reduction of the SimRank computation to personalized PageRank. We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy e in time linear in their number of non-zeros and log (κ f (A) e), where κ f (A) is the condition number of the matrix defining the linear system. Our algorithm applies the preconditioned Chebyshev iteration with preconditioners designed using nearly-linear time algorithms for graph sparsification and graph partitioning. 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. Recent web search techniques augment traditional text matching with a global notion of "importance" based on the linkage structure of the web, such as in Google's PageRank algorithm. For more refined searches, this global notion of importance can be specialized to create personalized views of importance--for example, importance scores can be biased according to a user-specified set of initially-interesting pages. Computing and storing all possible personalized views in advance is impractical, as is computing personalized views at query time, since the computation of each view requires an iterative computation over the web graph. We present new graph-theoretical results, and a new technique based on these results, that encode personalized views as partial vectors. Partial vectors are shared across multiple personalized views, and their computation and storage costs scale well with the number of views. Our approach enables incremental computation, so that the construction of personalized views from partial vectors is practical at query time. We present efficient dynamic programming algorithms for computing partial vectors, an algorithm for constructing personalized views from partial vectors, and experimental results demonstrating the effectiveness and scalability of our techniques.