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

SUBLINEAR algorithms FOR local GRAPH-CENTRALITY ESTIMATION

SIAM JOURNAL ON COMPUTING 2023年第4期52卷 968-1008页

作者： Bressan, Marco Peserico, Enoch Pretto, Luca Univ Milan Dipartimento Informat Via Celoria 18 I-20133 Milan Italy Univ Padua Dipartimento Ingn Informaz Via Gradenigo 6 I-35131 Padua Italy

We study the complexity of local graph-centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, which we apply to PageRank and Heat Kernel, for constructing a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of n nodes and m arcs, with probability (1 -delta) computes a multiplicative (1 +/-epsilon)-approximation of its score by examining only O(min(n(1/2)Delta(1/2),n(1/2)m(1/4))) nodes/arcs, where Delta is the maximum outdegree of the graph and poly(epsilon (-1)) and polylog(delta(-1)) factors are omitted for readability. A similar bound holds for computational cost. We also prove a lower bound of Omega (min(n(1/2)Delta(1/2), n(1/3)m(1/3))) for both query complexity and computational complexity. Moreover, in the jump-and-crawl graph -access model, our technique yields a O(min(n(1/2)Delta(1/2), n(2/3)))-queries algorithm;we show that this algorithm is optimal up to a logarithmic factor-in fact, sublogarithmic in the case of PageRank. These are the first algorithms with sublinear worst-case bounds for general directed graphs and any choice of the target node.

关键词： graph centrality sublinear algorithms local algorithms query complexity computational complexity random walks PageRank Heat Kernel

来源：评论

学校读者我要写书评

暂无评论

local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics

引用

ADVANCES IN MATHEMATICS 2023年第1期431卷

作者： Grebik, Jan Rozhon, Vaclav Masaryk Univ Fac Informat Botanicka 68A Brno 60200 Czech Republic UCLA Dept Math Los Angeles CA 90095 USA Univ Warwick Coventry Ireland Swiss Fed Inst Technol Zurich Switzerland

We present an intimate connection among the following fields: (a) distributed local algorithms: coming from the area of computer science, (b) finitary factors of iid processes: coming from the area of analysis of randomized processes, (c) descriptive combinatorics: coming from the area of combinatorics and measure theory. In particular, we study locally checkable problems on grids from all three perspectives. Most of our results are for perspective (b) where we prove time hierarchy theorems similar to those known in the field (a) Chang and Pettie (2017) [16]. This approach, which borrows techniques from fields (a) and (c), implies a number of results about the possible complexities of finitary factor solutions. Among others, it answers three open questions of Holroyd et al. (2017) [46] or the more general question of Brandt et al. Brandt (2017) [9] who asked for a formal connection between the fields (a) and (b). In general, we hope that our treatment will help to view all three perspectives as a part of a common theory of locality, in which we follow the insightful paper of Bernshteyn (2023) [6]. & COPY;2023 Elsevier Inc. All rights reserved.

关键词： Descriptive combinatorics local algorithms Finitary factors

来源：评论

学校读者我要写书评

暂无评论

local Hadwiger's Conjecture

引用

JOURNAL OF COMBINATORIAL THEORY SERIES B 2023年第1期162卷 154-183页

作者： Moore, Benjamin Postle, Luke Turner, Lise Charles Univ Prague Comp Sci Inst Prague Czech Republic Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada

We propose local versions of Hadwiger's Conjecture, where only balls of radius & omega;(log(v(G))) around each vertex are required to be Kt-minor-free. We ask: if a graph is locally-Ktminor-free, is it t-colourable? We show that the answer is yes when t & LE;5, even in the stronger setting of list-colouring, and we complement this result with a O(log v(G))-round distributed colouring algorithm in the local model. Further, we show that for large enough values of t, we can list-colour locally-Kt-minor-free graphs with 13 & BULL;max h(t), 1312 (t - 1)1}) colours, where h(t) is any value such that all Kt-minor-free graphs are h(t)-list-colourable. We again complement this with a O(log v(G))-round distributed algorithm. & COPY;2023 Published by Elsevier Inc.

关键词： Hadwiger's Conjecture Graph colouring Graph minors local algorithms

来源：评论

学校读者我要写书评

暂无评论

Errors are robustly tamed in cumulative knowledge processes

引用

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 2025年第5期122卷 e2416866122页

作者： Brandenberger, Anna Marcussen, Cassandra Mossel, Elchanan Sudan, Madhu MIT Dept Math Cambridge MA 02139 USA Harvard Univ Sch Engn & Appl Sci Comp Sci Boston MA 02134 USA

As knowledge accumulates in science and society in a distributed fashion, erroneous derivations can be introduced into the corpus of knowledge. Such derivations can compromise the validity of any units of knowledge that rely on them in the future. Can societal knowledge maintain some level of integrity given simple distributed error- checking mechanisms? In this paper, we investigate the following formulation of the question: assuming that a constant fraction of the new derivations is wrong, is it possible for simple error-checking mechanisms that apply when a new unit of knowledge is derived to maintain the integrity of the corpus of knowledge? This question was introduced by Ben-Eliezer et al. ["Is this correct? Let's check!" in 14th Innovations in Theoretical Computer Science Conference (ITCS, 2023)], who gave a robust affirmative answer in a specific probabilistic model for knowledge accumulation. Namely, this model required that new units depend on just one existing unit and join the process according to a preferential attachment rule. In this work, we consider much more general families of processes of knowledge accumulation, where new units may depend on multiple existing units and join according to varied attachment mechanisms. We also consider models with a (random) fraction of insertions of adversarial nodes. We give a robust affirmative answer to the above question by showing that for all of these models, as long as many of the units follow simple local heuristics for checking a bounded number of units they depend on, all errors will be eventually eliminated.

关键词： knowledge accumulation error elimination local algorithms probabilistic models

来源：评论

学校读者我要写书评

暂无评论

A local updating algorithm for personalized PageRank via Chebyshev polynomials

引用

SOCIAL NETWORK ANALYSIS AND MINING 2022年第1期12卷 1-11页

作者： Bautista, Esteban Latapy, Matthieu Sorbonne Univ CNRS LIP6 F-75005 Paris France

The personalized PageRank algorithm is one of the most versatile tools for the analysis of networks. In spite of its ubiquity, maintaining personalized PageRank vectors when the underlying network constantly evolves is still a challenging task. To address this limitation, this work proposes a novel distributed algorithm to locally update personalized PageRank vectors when the graph topology changes. The proposed algorithm is based on the use of Chebyshev polynomials and a novel update equation that encompasses a large family of PageRank-based methods. In particular, the algorithm has the following advantages: (i) it has faster convergence speed than state-of-the-art alternatives for local personalized PageRank updating;and (ii) it can update the solution of recent extensions of personalized PageRank that rely on complex dynamical processes for which no updating algorithms have been developed. Experiments in a real-world temporal network of an autonomous system validate the effectiveness of the proposed algorithm.

关键词： PageRank Updating algorithms local algorithms Chebyshev polynomials Graph signal processing Semi-supervised learning

来源：评论

学校读者我要写书评

暂无评论

local Planar Domination Revisited 1

引用

29th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Heydt, Ozan Siebertz, Sebastian Vigny, Alexandre Univ Bremen Bremen Germany

ISBN: (数字)9783031099939

ISBN: (纸本)9783031099939;9783031099922

We show how to compute an (11 + epsilon) - approximation of a minimum dominating set in a planar graph in a constant number of rounds in the local model of distributed computing. This improves on the previously best known approximation factor of 52, which was achieved by an elegant and simple algorithm of Lenzen et al. Our algorithm combines ideas from the algorithm of Lenzen et al. with recent work of Czygrinow et al. and Kublenz et al. to reduce to the case of bounded degree graphs. We can then apply an LP-based approximation in a constant number of rounds. We also study a distributed version of the classical greedy algorithm, which however falls short of achieving the best approximation ratio.

关键词： Dominating set local algorithms Planar graphs

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A local algorithm and its percolation analysis of bipartite z-matching problem

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2023年第5期2023卷 053401-053401页

作者： Zhao, Jin-Hua South China Normal Univ Sch Data Sci & Engn Shanwei 516600 Peoples R China South China Normal Univ Inst Quantum Matter Guangdong Prov Key Lab Nucl Sci Guangzhou 510006 Peoples R China South China Normal Univ Southern Nucl Sci Comp Ctr Guangdong Hong Kong Joint Lab Quantum Matter Guangzhou 510006 Peoples R China

A z-matching on a bipartite graph is a set of edges, among which each vertex of two types of the graph is adjacent to at most 1 and at most z (>= 1) edges, respectively. The z-matching problem concerns finding z-matchings with the maximum size. Our approach to this combinatorial optimization problem is twofold. From an algorithmic perspective, we adopt a local algorithm as a linear approximate solver to find z-matchings on any graph instance, whose basic component is a generalized greedy leaf removal procedure in graph theory. From a theoretical perspective, on uncorrelated random bipartite graphs, we develop a mean-field theory for the percolation phenomenon underlying the local algorithm, leading to an analytical estimation of z-matching sizes on random graphs. Our analytical theory corrects the prediction by belief propagation algorithm at zero-temperature limit in (*** ' c and Bianconi 2019 ***. 126 028001). Besides, our theoretical framework extends a core percolation analysis of kappa-XORSAT problems to a general context of uncorrelated random hypergraphs with arbitrary degree distributions of factor and variable nodes.

关键词： random graphs combinatorial optimization local algorithms percolation theory

来源：评论

学校读者我要写书评

暂无评论

The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots

引用

THEORETICAL COMPUTER SCIENCE 2021年 852卷 29-40页

作者： Li, Shouwei Heide, Friedhelm Meyer auf der Podlipyan, Pavel Paderborn Univ Heinz Nixdorf Inst Furstenallee 11 D-33102 Paderborn Germany Paderborn Univ Dept Comp Sci Furstenallee 11 D-33102 Paderborn Germany

In this paper, we reconsider the well-known discrete, round-based Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita [2] for gathering n autonomous mobile robots with limited viewing range in the plane. Remarquably, this algorithm exploits the fact that during its execution, many collisions of robots occur. Such collisions are interpreted as a success because it is assumed that such collided robots behave the same from now on. This is acceptable under the assumption that each robot is represented by a single point. Otherwise, collisions should be avoided. In this paper, we consider a continuous Go-To-The-Center algorithm in which the robots continuously observe the positions of their neighbors and adapt their speed (assuming a speed limit) and direction. Our first results are time bounds of O(n(2)) for gathering in two dimensions Euclidean space, and O(n) for the one dimension. Our main contribution is the introduction and evaluation of a continuous algorithm which performs Go-To-The-Center considering only the neighbors of a robot with respect to the Gabriel subgraph of the visibility graph, i.e. Go-To-The-Gabriel-Center algorithm. We show that this modification still correctly executes gathering in one and two dimensions, with the same time bounds as above. Simulations exhibit a severe difference of the behavior of the Go-To-The-Center and the Go-To-The-Gabriel-Center algorithms: Whereas lots of collisions occur during a run of the Go-To-The-Center algorithm, typically only one, namely the final collision occurs during a run of the Go-To-The-Gabriel-Center algorithm. We can prove this "collisionless property" of the Go-To-The-Gabriel-Center algorithm for one dimension. In two-dimensional Euclidean space, we conjecture that the "collisionless property" holds for almost every initial configuration. We support our conjecture with measurements obtained from the simulation where robots execute both continuous Go-To-The-Center and Go-To-The-Gabriel-Center alg

关键词： local algorithms Distributed algorithms Collisionless gathering Mobile robots Multiagent system

来源：评论

学校读者我要写书评

暂无评论

A continuous strategy for collisionless gathering

引用

THEORETICAL COMPUTER SCIENCE 2021年 852卷 41-60页

作者： Li, Shouwei Markarian, Christine Heide, Friedhelm Meyer Auf Der Podlipyan, Pavel Paderborn Univ Heinz Nixdorf Inst Paderborn Germany Paderborn Univ Dept Comp Sci Paderborn Germany Univ Dubai Dept Engn & Informat Technol Dubai U Arab Emirates

Over the past decades, the Gathering problem, which asks to gather a group of robots in finite time given some restrictions, has been intensively studied. In this paper, we are given a group of n autonomous, dimensionless, deterministic, and anonymous robots, with bounded viewing range. Assuming a continuous time model, the goal is to gather these robots into one point in finite time. We introduce a simple convergence criterion that defines a new class of algorithms which perform gathering in O (nd) time, where d is the diameter of the initial robot configuration. We show that some gathering algorithms in the literature belong to this class and propose two new algorithms that belong to this class and have quadratic running time, namely, Go-To-The-Relative-Center algorithm (GTRC) and Safe-Go-To-The-Relative-Center algorithm (S-GTRC). We prove that the latter can perform gathering without collision by using a slightly more complex robot model: non oblivious, chiral, and luminous (i.e. robots have observable external memory, as in [8]). We also consider a variant of the Gathering problem, the Near-Gathering problem, in which robots must get close to each other without colliding. We show that S-GTRC solves the Near-Gathering problem in quadratic time and assumes a weaker robot model than the one assumed in the current state-of-the-art. (C) 2020 Elsevier B.V. All rights reserved.

关键词： local algorithms Distributed algorithms Collisionless gathering Mobile robots Multiagent system

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：