检索结果-内蒙古大学图书馆

An Optimization Approach to locally-Biased Graph algorithms

PROCEEDINGS OF THE IEEE 2017年第2期105卷 256-272页

作者： Fountoulakis, Kimon Gleich, David F. Mahoney, Michael W. Univ Calif Berkeley Int Comp Sci Inst Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

locally-biased graph algorithms are algorithms that attempt to find local or small-scale structure in a large data graph. In some cases, this can be accomplished by adding some sort of locality constraint and calling a traditional graph algorithm;but more interesting are locally-biased graph algorithms that compute answers by running a procedure that does not even look at most of the input graph. This corresponds more closely to what practitioners from various data science domains do, but it does not correspond well with the way that algorithmic and statistical theory is typically formulated. Recent work from several research communities has focused on developing locally-biased graph algorithms that come with strong complementary algorithmic and statistical theory and that are useful in practice in downstream data science applications. We provide a review and overview of this work, highlighting commonalities between seemingly different approaches, and highlighting promising directions for future work.

关键词： Clustering graph algorithms local algorithms network flow partitioning semi-supervised learning spectral graph theory

来源：评论

学校读者我要写书评

暂无评论

Energy-efficient strategies for building short chains of mobile robots locally

引用

THEORETICAL COMPUTER SCIENCE 2013年 509卷 97-112页

作者： Brandes, Philipp Degener, Bastian Kempkes, Barbara der Heide, Friedhelm Meyer Auf Univ Paderborn CS Dept Heinz Nixdorf Inst D-33098 Paderborn Germany

We are given a winding chain of n mobile robots between two stations in the plane, each of them having a limited viewing range. It is only guaranteed that each robot can see its two neighbors in the chain. The goal is to let the robots converge to the line between the stations. The robots are modeled as points in the plane which cannot collide. We use a discrete and synchronous time model, but we restrict the movement of each mobile robot to a distance of 8 in each round. This restriction fills the gap between the previously used discrete time model with an unbounded step length and the continuous time model which was introduced in [Bastian Degener, Barbara Kempkes, Peter Kling, Friedhelm Meyer auf der Heide, A continuous, local strategy for constructing a short chain of mobile robots, in: SIROCCO'10: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, 2010, pp. 168-182]. We adapt the Go-To-The-Middle strategy by Dynia, Kutylowski, Lorek and Meyer auf der Heide (BICC 2006): In each round, each robot first observes the positions of its neighbors and then moves towards the midpoint between them until it reaches the point or has moved a distance of B. The main energy consumers in this scenario are the number of observations of positions of neighbors, which equals the number of rounds, and the distance to be traveled by the robots. We analyze the strategy with respect to both quality measures and provide asymptotically tight bounds. We show that the best choice for 8 for this strategy is 8 E e(D, since this minimizes (up to constant factors) both energy consumers, the number of rounds as well as the maximum traveled distance, at the same time. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Mobile robots local algorithms Dynamics Robot formation problems Convergence speed Distributed algorithms Geometric networks

来源：评论

学校读者我要写书评

暂无评论

On the computational tractability of statistical estimation on amenable graphs

引用

PROBABILITY THEORY AND RELATED FIELDS 2021年第4期181卷 815-864页

作者： El Alaoui, Ahmed Montanari, Andrea Cornell Univ 1176 Comstock Hall Ithaca NY 14850 USA Stanford Univ 390 Serra Mall Stanford CA 94305 USA

We consider the problem of estimating a vector of discrete variables theta = (theta(1), ..., theta(n)), based on noisy observations Y-uv of the pairs (theta(u), theta(v)) on the edges of a graph G = ([n], E). This setting comprises a broad family of statistical estimation problems, including group synchronization on graphs, community detection, and low-rank matrix estimation. A large body of theoretical work has established sharp thresholds for weak and exact recovery, and sharp characterizations of the optimal reconstruction accuracy in such models, focusing however on the special case of Erdos-Renyitype random graphs. An important finding of this line of work is the ubiquity of an information-computation gap. Namely, for many models of interest, a large gap is found between the optimal accuracy achievable by any statistical method, and the optimal accuracy achieved by known polynomial-time algorithms. Moreover, it is expected in many situations that this gap is robust to small amounts of additional side information revealed about the theta(i)'s. How does the structure of the graph G affect this picture? Is the information-computation gap a general phenomenon or does it only apply to specific families of graphs? We prove that the picture is dramatically different for graph sequences converging to amenable graphs (including, for instance, d-dimensional grids). We consider a model in which an arbitrarily small fraction of the vertex labels is revealed, and show that a linear-time local algorithm can achieve reconstruction accuracy that is arbitrarily close to the information-theoretic optimum. We contrast this to the case of random graphs. Indeed, focusing on group synchronization on random regular graphs, we prove that local algorithms are unable to have non-trivial performance below the so-called Kesten-Stigum threshold, even when a small amount of side information is revealed.

关键词： Statistical estimation local algorithms Processes on graphs Information-computation tradeoffs

来源：评论

学校读者我要写书评

暂无评论

Distributed maximal independent set computation driven by finite-state dynamics

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2023年第1期38卷 85-97页

作者： Goles, Eric Leal, Laura Montealegre, Pedro Rapaport, Ivan Rios-Wilson, Martin Univ Adolfo Ibanez Fac Ingn & Ciencias Penalolen Chile Univ Chile Dept Ingn Matemat Santiago Chile Univ Chile DIM CMM UMI CNRS 2807 Santiago Chile

A Maximal Independent Set (MIS) is an inclusion maximal set of pairwise non-adjacent vertices. The computation of an MIS is one of the core problems in distributed computing. In this article, we introduce and analyze a finite-state distributed randomized algorithm for computing a Maximal Independent Set (MIS) on arbitrary undirected graphs. Our algorithm is self-stabilizing (reaches a correct output on any initial configuration) and can be implemented on systems with very scarce conditions. We analyze the convergence time of the proposed algorithm, showing that in many cases the algorithm converges in logarithmic time with high probability.

关键词： Maximal independent set local algorithms distributed algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Compositional systems over reducible networks

引用

FUNDAMENTA INFORMATICAE 2007年第3-4期79卷 265-282页

作者： Mazurkiewicz, Antoni Polish Acad Sci Inst Comp Sci PL-01237 Warsaw Poland

In the paper two notions related to local (distributed) computations are identified and discussed. The first one is the notion of reducible graphs. A graph is reducible if it can be reduced to a singleton by successive removing its removable nodes;the removing procedure should be local in the sense that to decide whether a node is removable or not it is sufficient to inspect its neighbor-hood. The second is the notion of compositional systems, consisting of a set of objects together with a composition operation which to each pair of local objects (like local votes, partial trees, partial orderings, local consensus, local processes etc.) assigns their possible compositions;a sequence of such composition operations leads to a global object (like a global vote, a full spanning tree, a total ordering, a global consensus, a synchronized process, etc). Combining these two notions gives rise to a generic distributed algorithm for composing different local objects assigned to nodes of a reducible graph into one global object assigned to all nodes. Correctness of the composing algorithm, i.e its proper termination and its impartiality is proved.

关键词： local algorithms distributed data computation networks distributed computing

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Super-Fast t-Ruling Sets 14

Brief Announcement: Super-Fast t-Ruling Sets

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Bisht, Tushar Kothapalli, Kishore Pemmaraju, Sriram, V Int Inst Informat Technol Hyderabad 500032 India Univ Iowa Dept Comp Sci Iowa City IA 52242 USA

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.

关键词： Distributed algorithms local algorithms Maximal Independent Sets Ruling Sets Symmetry Breaking

来源：评论

学校读者我要写书评

暂无评论

Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching 58

Deterministic Distributed Edge-Coloring via Hypergraph Maxim...

引用

58th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Fischer, Manuela Ghaffari, Mohsen Kuhn, Fabian Swiss Fed Inst Technol Dept Comp Sci CH-8092 Zurich Switzerland Univ Freiburg Dept Comp Sci D-79110 Freiburg Germany

ISBN: (纸本)9781538634646

We present a deterministic distributed algorithm that computes a (2 Delta - 1)-edge-coloring, or even list-edgecoloring, in any n-node graph with maximum degree Delta, in O(log(8) Delta . log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e.g., Open Problem 4 in the Distributed Graph Coloring book of Barenboim and Elkin. The previous best round complexities were 2(O(root log n)) by Panconesi and Srinivasan [STOC' 92] and (O) over tilde (root Delta) + O(log* n) by Fraigniaud, Heinrich, and Kosowski [FOCS' 16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of (2 Delta - 1)-edgecoloring to poly(log log n) rounds. The key technical ingredient is a deterministic distributed algorithm for hypergraph maximal matching, which we believe will be of interest beyond this result. In any hypergraph of rank r - where each hyperedge has at most r vertices - with n nodes and maximum degree Delta, this algorithm computes a maximal matching in O(r(5) log(6+log r) Delta . log n) rounds. This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmic-time deterministic distributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkin's book, a ((log Delta/epsilon)(O(log 1/epsilon)) - round deterministic algorithm for (1 + epsilon)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting lambda-arboricity graphs with out-degree at most inverted right perpendicular (1 + epsilon)lambda inverted left perpendicular, for any constant epsilon > 0, hence partially answering Open Problem 10 of Barenboim and Elkin's book.

关键词： distributed graph algorithms local algorithms deterministic distributed algorithms edge-coloring hypergraph maximal matching rounding linear programs

来源：评论

学校读者我要写书评

暂无评论

Strong localization in Personalized PageRank Vectors 12th

Strong Localization in Personalized PageRank Vectors

引用

12th International Workshop on algorithms and Models for the Web-Graph (WAW)

作者： Nassar, Huda Kloster, Kyle Gleich, David F. Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Purdue Univ Dept Math W Lafayette IN 47907 USA

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.

关键词： PageRank Diffusion local algorithms

来源：评论

学校读者我要写书评

暂无评论

On the Power of Preprocessing in Decentralized Network Optimization

On the Power of Preprocessing in Decentralized Network Optim...

引用

IEEE Conference on Computer Communications (IEEE INFOCOM)

作者： Foerster, Klaus-Tycho Hirvonen, Juho Schmid, Stefan Suomela, Jukka Univ Vienna Fac Comp Sci Vienna Austria Aalto Univ Dept Comp Sci Helsinki Finland

ISBN: (纸本)9781728105154

As communication networks are growing at a fast pace, the need for more scalable approaches to operate such networks is pressing. Decentralization and locality are key concepts to provide scalability. Existing models for which local algorithms are designed fail to model an important aspect of many modern communication networks such as software-defined networks: the possibility to precompute distributed network state. We take this as an opportunity to study the fundamental question of how and to what extent local algorithms can benefit from preprocessing. In particular, we show that preprocessing allows for significant speedups of various networking problems. A main benefit is the precomputation of structural primitives, where purely distributed algorithms have to start from scratch. Maybe surprisingly, we also show that there are strict limitations on how much preprocessing can help in different scenarios. To this end, we provide approximation bounds for the maximum independent set problem which however show that our obtained speedups are asymptotically optimal. Even though we show that physical link failures in general hinder the power of preprocessing, we can still facilitate the precomputation of symmetry breaking processes to bypass various runtime harriers. We believe that our model and results are of interest beyond the scope of this paper and apply to other dynamic networks as well.

关键词： Decentralization local algorithms Software-defined networks

来源：评论

学校读者我要写书评

暂无评论

On the locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition 21

On the Locality of Nash-Williams Forest Decomposition and St...

引用

40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Harris, David G. Su, Hsin-Hao Vu, Hoa T. Univ Maryland College Pk MD 20742 USA Boston Coll Chestnut Hill MA 02167 USA San Diego State Univ San Diego CA 92182 USA

ISBN: (纸本)9781450385480

Given a graph G = (V, E) with arboricity alpha, we study the problem of decomposing the edges of G into (1 + epsilon)alpha disjoint forests in the distributed local model. While there is a polynomial time centralized algorithm for alpha-forest decomposition (e.g. [Imai, J. Operation Research Soc. of Japan '83]), it remains an open question how close we can get to this exact decomposition in the local model. Barenboim and Elkin [PODC '08] developed a local algorithm to compute a (2 + epsilon)alpha-forest decomposition in O(log n/epsilon) rounds. Ghaffari and Su [SODA '17] made further progress by computing a (1 + epsilon)alpha-forest decomposition in O(log(3) n/epsilon(4)) rounds when epsilon alpha = Omega (root alpha log n), i.e., the limit of their algorithm is an (alpha + Omega (root alpha log n))-forest decomposition. This algorithm, based on a combinatorial construction of Alon, McDiarmid & Reed [Combinatorica '92], in fact provides a decomposition of the graph into star-forests, i.e., each forest is a collection of stars. Our main goal is to reduce the threshold of epsilon alpha in (1 + epsilon)alpha-forest decomposition. We obtain the following main results: An O(Delta(rho) log(4 )n/epsilon)-round algorithm when epsilon alpha = Omega(rho) (1) in simple graphs and multigraphs, where rho > 0 is any arbitrary constant. An O(log(4) n log Delta/epsilon )-round algorithm when epsilon alpha = Omega(log Delta / log log Delta) in simple graphs and multigraphs. An O(log(4 )n/epsilon)-round algorithm when epsilon alpha = Omega (log n) in simple graphs and multigraphs. This also covers an extension of the forest-decomposition problem to list-edge-coloring. An O(log(3) n/epsilon)-round algorithm for star-forest decomposition for epsilon alpha = Omega(root log Delta + log alpha) in simple graphs. When epsilon alpha >= Q (log Delta), this also covers a list-edge-coloring variant. Our techniques also give an algorithm for (1 + epsilon)alpha-outdegree-orientation in O (log(3)

关键词： forest decompositions local algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：