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

24th International Conference on World Wide Web (WWW)

作者： Saltz, Matthew Prat-Perez, Arnau Dominguez-Sal, David Univ Politecn Cataluna DAMA UPC E-08028 Barcelona Spain

ISBN: (纸本)9781450334730

Community detection has become an extremely active area of research in recent years, with researchers proposing various new metrics and algorithms to address the problem. Recently, the Weighted Community Clustering (WCC) metric was proposed as a novel way to judge the quality of a community partitioning based on the distribution of triangles in the graph, and was demonstrated to yield superior results over other commonly used metrics like modularity. The same authors later presented a parallel algorithm for optimizing WCC on large graphs. In this paper, we propose a new distributed, vertex-centric algorithm for community detection using the WCC metric. Results are presented that demonstrate the algorithm's performance and scalability on up to 32 worker machines and real graphs of up to 1.8 billion edges. The algorithm scales best with the largest graphs, finishing in just over an hour for the largest graph, and to our knowledge, it is the first distributed algorithm for optimizing the WCC metric.

关键词： Community detection distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed maximum matching verification in congest 34

Distributed maximum matching verification in congest

引用

34th International Symposium on distributed Computing, DISC 2020

作者： Ahmadi, Mohamad Kuhn, Fabian University of Freiburg Germany

ISBN: (纸本)9783959771689

We study the maximum cardinality matching problem in a standard distributed setting, where the nodes V of a given n-node network graph G = (V, E) communicate over the edges E in synchronous rounds. More specifically, we consider the distributed CONGEST model, where in each round, each node of G can send an O(log n)-bit message to each of its neighbors. We show that for every graph G and a matching M of G, there is a randomized CONGEST algorithm to verify M being a maximum matching of G in time O(|M|) and disprove it in time O(D + '), where D is the diameter of G and ' is the length of a shortest augmenting path. We hope that our algorithm constitutes a significant step towards developing a CONGEST algorithm to compute a maximum matching in time Õ(s∗), where s∗ is the size of a maximum matching. © Mohamad Ahmadi and Fabian Kuhn;licensed under Creative Commons License CC-BY 34th International Symposium on distributed Computing (DISC 2020).

关键词： Augmenting paths distributed graph algorithms distributed matching

来源：评论

学校读者我要写书评

暂无评论

Efficient load-balancing through distributed token dropping 21

Efficient load-balancing through distributed token dropping

引用

33rd ACM Symposium on Parallelism in algorithms and Architectures, SPAA 2021

作者： Brandt, Sebastian Keller, Barbara Rybicki, Joel Suomela, Jukka Uitto, Jara ETH Zurich Zurich Switzerland Aalto University Helsinki Finland IST Austria Klosterneuburg Austria

ISBN: (纸本)9781450380706

We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(^5) rounds in graphs of maximum degree , while we improve it to O(^4) and also prove a lower bound of ω(). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S);here C and S are the maximum degrees of customers and servers, respectively. © 2021 ACM.

关键词： semi-matching distributed graph algorithms stable orientations load balancing

来源：评论

学校读者我要写书评

暂无评论

Compact distributed Certification of Planar graphs 20

Compact Distributed Certification of Planar Graphs

引用

39th Symposium on Principles of distributed Computing

作者： Feuilloley, Laurent Fraigniaud, Pierre Montealegre, Pedro Rapaport, Ivan Remila, Eric Todinca, Ioan Univ Chile Dept Ingn Ind Santiago Chile Univ Paris Paris France CNRS Paris France Univ Adolfo Ibanez Fac Ingn & Ciencias Santiago Chile Univ Chile DIM CMM UMI 2807 CNRS Santiago Chile UJM St Etienne GATE Lyon St Etienne CNRS UMR 5824 St Etienne France Univ dOrleans LIFO Orleans France INSA Ctr Val de Loire Blois Loir & Cher France

ISBN: (纸本)9781450375825

Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a distributed interactive proof for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM protocol), and uses small certificates, on O(logn) bits in n-node networks. We show that a single interaction from the prover suffices, and randomization is unecessary, by providing an explicit description of a proof-labeling scheme for planarity, still using certificates on just O(logn) bits. We also show that there are no proof-labeling schemes - in fact, even no locally checkable proofs - for planarity using certificates on o(logn) bits.

关键词： distributed graph algorithms communication networks fault-tolerance

来源：评论

学校读者我要写书评

暂无评论

Deterministic Near-Optimal distributed Listing of Cliques 22

Deterministic Near-Optimal Distributed Listing of Cliques

引用

41st ACM Symposium on Principles of distributed Computing, PODC 2022

作者： Censor-Hillel, Keren Leitersdorf, Dean Vulakh, David Technion - Israel Institute of Technology Haifa Israel Massachusetts Institute of Technology CambridgeMA United States

ISBN: (纸本)9781450392624

The importance of classifying connections in large graphs has been the motivation for a rich line of work on distributed subgraph finding that has led to exciting recent breakthroughs. A crucial aspect that remained open was whether deterministic algorithms can be as efficient as their randomized counterparts, where the latter are known to be tight up to polylogarithmic factors. We give deterministic distributed algorithms for listing cliques of size p in n1 - 2/p + o(1) rounds in the Congest model. For triangles, our n1/3+o(1) round complexity improves upon the previous state of the art of n2/3+o(1) rounds [Chang and Saranurak, FOCS 2020]. For cliques of size p ≥ 4, ours are the first non-trivial deterministic distributed algorithms. Given known lower bounds, for all values p ≥ 3 our algorithms are tight up to a no(1) subpolynomial factor, which comes from the deterministic routing procedure we use. © 2022 ACM.

关键词： congest distributed graph algorithms cliques

来源：评论

学校读者我要写书评

暂无评论

Efficient CONGEST algorithms for the lovász local lemma 35

Efficient CONGEST algorithms for the lovász local lemma

引用

35th International Symposium on distributed Computing, DISC 2021

作者： Maus, Yannic Uitto, Jara Technion Haifa Israel Aalto University Espoo Finland

ISBN: (纸本)9783959772105

We present a poly log log n time randomized CONGEST algorithm for a natural class of Lovász Local Lemma (LLL) instances on constant degree graphs. This implies, among other things, that there are no LCL problems with randomized complexity between Ω(log n) and poly log log n. Furthermore, we provide extensions to the network decomposition algorithms given in the recent breakthrough by Rozhoň and Ghaffari [STOC2020] and the follow up by Ghaffari, Grunau, and Rozhoň [SODA2021]. In particular, we show how to obtain a large distance separated weak network decomposition with a negligible dependency on the range of unique identifiers. © Yannic Maus and Jara Uitto;licensed under Creative Commons License CC-BY 4.0

关键词： CONGEST distributed graph algorithms Locally checkable labelings Lovász Local Lemma

来源：评论

学校读者我要写书评

暂无评论

Message reduction in the LOCAL model is a free lunch 33

Message reduction in the LOCAL model is a free lunch

引用

33rd International Symposium on distributed Computing, DISC 2019

作者： Bitton, Shimon Emek, Yuval Izumi, Taisuke Kutten, Shay Technion – Israel Institute of Technology Haifa Israel Nagoya Institute of Technology Japan

ISBN: (纸本)9783959771269

A new spanner construction algorithm is presented, working under the LOCAL model with unique edge IDs. Given an n-node communication graph, a spanner with a constant stretch and O(n1+Ε) edges (for an arbitrarily small constant Ε > 0) is constructed in a constant number of rounds sending O(n1+Ε) messages whp. Consequently, we conclude that every t-round LOCAL algorithm can be transformed into an O(t)-round LOCAL algorithm that sends O(t · n1+Ε) messages whp. This improves upon all previous message-reduction schemes for LOCAL algorithms that incur a logΩ(1) n blow-up of the round complexity. © Shimon Bitton, Yuval Emek, Taisuke Izumi, and Shay Kutten.

关键词： distributed graph algorithms LOCAL model Message complexity Spanner

来源：评论

学校读者我要写书评

暂无评论

Barriers due to Congestion and Two Ways to Deal With Them 18

Barriers due to Congestion and Two Ways to Deal With Them

引用

37th ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing (PODC)

作者： Censor-Hillel, Keren Technion Dept Comp Sci Haifa Israel

ISBN: (纸本)9781450357951

Restricting the bandwidth in models of distributed graph computations naturally introduces challenges that arise due to communication bottlenecks. In this talk, I will survey techniques for proving lower bounds on the complexity of fundamental graph problems under limited bandwidth. For some problems, allowing relaxed solutions can significantly reduce the required amount of communication, enabling efficient computations. Two successful approaches for overcoming provable barriers, namely, approximations and testing, will be exemplified and discussed in the context of distributed computing.

关键词： distributed graph algorithms Limited Bandwidth Lower bounds Approximations Testing

来源：评论

学校读者我要写书评

暂无评论

The energy complexity of diameter and minimum cut computation in bounded-genus networks

引用

THEORETICAL COMPUTER SCIENCE 2024年 982卷

作者： Chang, Yi-Jun Natl Univ Singapore Singapore Singapore

This paper investigates the energy complexity of distributed graph problems in multi-hop radio networks, where the energy cost of an algorithm is measured by the maximu m number of awake rounds of a vertex. Recent works revealed that some problems, such as broadcast, breadth-first search, and maximal matching, can be solved with energy-ecient algorithms that consume only poly log n energy. However, there exist some problems, such as computing the diameter of the graph, that requir e Omega(n) energy to solve. To improve energ y eciency for these problems, we focus on a special graph class: bounded-genus graphs. We present algorithms for computin g the exact diameter, the exact global minimum cut size , and a (1 +/- epsilon)-approximate s-t minimum cut root size with O( root n) energy for bounded-genus graphs. Our approach is based on a generic framework that divides the vertex set into high-degree and low-degree parts and leverages the structural properties of bounded-genus graphs to control the number of certain connected components in the subgraph induced by the low-degree part.

关键词： distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Synchronous t-resilient consensus in arbitrary graphs

引用

INFORMATION AND COMPUTATION 2023年 292卷

作者： Castaneda, Armando Fraigniaud, Pierre Paz, Ami Rajsbaum, Sergio Roy, Matthieu Travers, Corentin Univ Nacl Autonoma Mexico Inst Matemat Mexico City Mexico CNRS IRIF Paris France Univ Paris Cite Paris France CNRS LISN Paris France Univ Paris Saclay Paris France CNRS LAAS Toulouse France Univ Aix Marseille LIS Marseille France

We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius(G, t), that extends the standard graph theoretical notion of radius, for considering all the ways in which t nodes may crash, and we present an algorithm that solves consensus in radius(G, t) rounds. Then we derive a lower bound showing that, among oblivious algorithms, our algorithm is optimal for a large family of graphs including all vertex-transitive graphs.(c) 2023 Elsevier Inc. All rights reserved.

关键词： Crash failures Consensus Combinatorial topology distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：