The personalized PageRank diffusion is a fundamental tool in network analysis tasks like community detection and link prediction. It models the spread of a quantity from a set of seed nodes, and it has been observed t...
详细信息
ISBN:
(纸本)9783319267845;9783319267838
The personalized PageRank diffusion is a fundamental tool in network analysis tasks like community detection and link prediction. It models the spread of a quantity from a set of seed nodes, and it has been observed to stay localized near this seed set. We derive an upper-bound on the number of entries necessary to approximate a personalized PageRank vector in graphs with skewed degree sequences. This bound shows localization under mild assumptions on the maximum and minimum degrees. Experimental results on random graphs with these degree sequences show the bound is loose and support a conjectured bound.
Over the last fifteen years, a large group of algorithms emerged which compute various predicates from distributed data with a focus on communication efficiency. These algorithms are often called "communication-e...
详细信息
ISBN:
(纸本)9781450336178
Over the last fifteen years, a large group of algorithms emerged which compute various predicates from distributed data with a focus on communication efficiency. These algorithms are often called "communication-efficient", "geometric-monitoring", or "local" algorithms. We jointly call them distributed convex thresholding algorithms, for reasons which will be explained in this work. Distributed convex thresholding algorithms have found their applications in domains in which bandwidth is a scarce resource, such as wireless sensor networks and peer-to-peer systems, or in scenarios in which data rapidly streams to the different processors but outcome of the predicate rarely changes. Common to all of these algorithms is the use of a data dependent criteria to determine when further messaging is required. This work presents two very simple yet exceedingly general theorems from which the correctness of all distributed convex thresholding algorithms can be elicited, and demonstrates that for key examples. Because the theorems are general, they extend the range of predicates which can be computed in a communication efficient manner beyond what is currently known. Unlike the previous correction proofs given to these algorithms, the proofs of the theorems presented here do not depend on the communication infrastructure. So the correctness of any distributed convex thresholding algorithm is immediately extended from broadcast enabled networks or from cycle free networks to general networks. Inspecting existing algorithms in light of the new theorems reveals that they contain redundant requirements, which cause them to send messages when indeed none are needed.
We consider the self-deployment problem in mobile sensor networks with the objective of providing focused coverage for a point of interest (POI) such that the maximum area around it is covered by sensors without sensi...
详细信息
ISBN:
(纸本)9781479999644
We consider the self-deployment problem in mobile sensor networks with the objective of providing focused coverage for a point of interest (POI) such that the maximum area around it is covered by sensors without sensing holes. We present a local greedy algorithm, called TTGREEDY, that solves this problem in at most R + 2 . (n - 1) time steps, where R is the distance to the farthest initial sensor position from the POI and n is the number of sensors. This is a significant improvement over the best previously known O(D) time step algorithm of Blazovics and Lukovszki, where D is the sum of the initial distances to the sensors from the POI. The main idea is to synchronously drive mobile sensors along a locally-computed triangle tessellation avoiding collisions of sensors. We also show that there are initial configurations of n sensors in this problem where at least R+ (n-1)/2 time steps are needed by any greedy algorithm. These results provide the first tight runtime (within a small constant factor) solution to this problem.
We demonstrate how to leverage a system's capability for all-to-all communication to achieve an exponential speed-up of local algorithms despite bandwidth and memory restrictions. More precisely, if a network comp...
详细信息
ISBN:
(纸本)9781605588889
We demonstrate how to leverage a system's capability for all-to-all communication to achieve an exponential speed-up of local algorithms despite bandwidth and memory restrictions. More precisely, if a network comprises n nodes with all-to-all bandwidth n(epsilon) (epsilon > 0 constant) and nodes know their input and neighborhood with respect to a graph problem instance of polylogarithmic maximum degree, any local algorithm for this problem with running time r is an element of O(log n) and reasonably small states can be simulated within O(log r) rounds.
local algorithms are common tools for estimating intrinsic volumes from black-and-white digital images. However, these algorithms are typically biased in the design based setting, even when the resolution tends to inf...
详细信息
local algorithms are common tools for estimating intrinsic volumes from black-and-white digital images. However, these algorithms are typically biased in the design based setting, even when the resolution tends to infinity. Moreover, images recorded in practice are most often blurred grey-scale images rather than black-and-white. In this paper, an extended definition of local algorithms, applying directly to grey-scale images without thresholding, is suggested. We investigate the asymptotics of these new algorithms when the resolution tends to infinity and apply this to construct estimators for surface area and integrated mean curvature that are asymptotically unbiased in certain natural settings.
A t-ruling set of a graph G = (V;E) is a vertex-subset S subset of V that is independent and satisfies the property that every vertex v is an element of V is at a distance of at most t hops from some vertex in S. A ma...
详细信息
ISBN:
(纸本)9781450329446
A t-ruling set of a graph G = (V;E) is a vertex-subset S subset of V that is independent and satisfies the property that every vertex v is an element of V is at a distance of at most t hops from some vertex in S. A maximal independent set (MIS) is a 1-ruling set. Extending results from Kothapalli et al. (FSTTCS 2012) this note presents a randomized algorithm for computing, with high probability, a t-ruling set in O(t . log(1/t-1) n) rounds for 2 <= t <= root log log n and in exp(O(root log log n)) rounds for t > root log log n.
The context of this work is the online characterization of errors in large scale systems. In particular, we address the following question: Given two successive configurations of the system, can we distinguish massive...
详细信息
ISBN:
(纸本)9781479922338
The context of this work is the online characterization of errors in large scale systems. In particular, we address the following question: Given two successive configurations of the system, can we distinguish massive errors from isolated ones, the former ones impacting a large number of nodes while the second ones affect solely a small number of them, or even a single one? The rationale of this question is twofold. First, from a theoretical point of view, we characterize errors with respect to their neighbourhood, and we show that there are error scenarios for which isolated and massive errors are indistinguishable from an omniscient observer point of view. We then relax the definition of this problem by introducing unresolved configurations, and exhibit necessary and sufficient conditions that allow any node to determine the type of errors it has been impacted by. These conditions only depend on the close neighbourhood of each node and thus are locally computable. We present algorithms that implement these conditions, and show through extensive simulations, thier performances. Now from a practical point of view, distinguishing isolated errors from massive ones is of utmost importance for networks providers. For instance, for Internet service providers that operate millions of home gateways, it would be very interesting to have procedures that allow gateways to self distinguish whether their dysfunction is caused by network-level errors or by their own hardware or software, and to notify the service provider only in the latter case.
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 algo...
详细信息
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. Using the partitioning algorithm of this paper, we have designed a nearly linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearly linear time algorithm for solving linear systems in symmetric, diagonally dominant matrices. The linear system solver also leads to a nearly linear time algorithm for approximating the second-smallest eigenvalue and corresponding eigenvector of the Laplacian matrix of a graph. These other results are presented in two companion papers.
Datacenter networks should support high network utilization. Yet today's routing is typically load agnostic, so large flows can starve other flows if routed through overutilized links. Even recent proposals like c...
详细信息
ISBN:
(纸本)9781450321013
Datacenter networks should support high network utilization. Yet today's routing is typically load agnostic, so large flows can starve other flows if routed through overutilized links. Even recent proposals like centralized scheduling or end-host multi-pathing give suboptimal throughput, and they suffer from poor scalability and other limitations. We present a simple, switch-local algorithm called localFlow that is optimal (under standard assumptions), scalable, and practical. Although localFlow may split an individual flow (this is necessary for optimality), it does so infrequently by considering the aggregate flow per destination and allowing slack in distributing this flow. We use an optimization decomposition to prove localFlow's optimality when combined with unmodified end hosts' TCP. Splitting flows presents several new technical challenges that must be overcome in order to interact efficiently with TCP and work on emerging standards for programmable, commodity switches. Since localFlow acts independently on each switch, it is highly scalable, adapts quickly to dynamic workloads, and admits flexible deployment strategies. We present detailed packet-level simulations comparing localFlow to a variety of alternative schemes, on real datacenter workloads.
A class of minimization algorithms for Boolean functions that involve conjunctions from a reduced disjunctive normal form and first-order neighborhoods of such conjunctions is investigated. A particular algorithm is s...
详细信息
A class of minimization algorithms for Boolean functions that involve conjunctions from a reduced disjunctive normal form and first-order neighborhoods of such conjunctions is investigated. A particular algorithm is selected that is the best in the class in many cases.
暂无评论