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

Parallel algorithms for flexible pattern matching on big graphs

INFORMATION SCIENCES 2018年 436卷 418-440页

作者： Wang, Hongzhi Li, Ning Li, Jianzhong Gao, Hong Harbin Inst Technol Dept Comp Sci & Technol Harbin Heilongjiang Peoples R China

Strong simulation is a state-of-the-art approximate scheme in graph pattern matching. This scheme always finds high-quality results compared to other schemes. However, as the Web and social networks are increasingly used in human lives, the scale of the data grows extremely large. As a result, such big graphs are often stored in the distributed environment, in order to be managed efficiently. Unfortunately, current distributed algorithm for strong simulation is not efficient and cannot be applied to real applications. In this paper, we propose efficient parallel algorithms for strong simulation in the distributed setting. The contribution includes (1) We convert the calculation of strong simulation to calculating a relative small set of partial results for each partition of pattern suitable for distributed system. (2) We develop a method to reduce data shipment and time complexity of local computation in the distributed setting. (3) We split the distributed calculation of strong simulation into an offline redistribution algorithm and an online matching algorithm. The major data shipment is involved in the offline algorithm, while the online algorithm is highly parallel and much more efficient than current algorithms. (4) By experiments on both real and synthetic data, we verify the efficiency of our distributed algorithms and the effectiveness of our scheme without large intermediate results. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Graph query Graph simulation distributed algorithms Strong simulation

来源：评论

学校读者我要写书评

暂无评论

Approximate Projection Methods for Decentralized Optimization With Functional Constraints

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2018年第10期63卷 3248-3260页

作者： Lee, Soomin Zavlanos, Michael M. Yahoo Labs Sunnyvale CA 94089 USA Duke Univ Dept Mech Engn & Mat Sci Durham NC 27708 USA

We consider distributed convex optimization problems that involve a separable objective function and nontrivial functional constraints, such as linear matrix inequalities. We propose a decentralized and computationally inexpensive algorithm, which is based on the concept of approximate projections. Our algorithm is one of the consensus-based methods in that, at every iteration, each agent performs a consensus update of its decision variables followed by an optimization step of its local objective function and local constraints. Unlike other methods, the last step of our method is not a Euclidean projection onto the feasible set, but instead a subgradient step in the direction that minimizes the local constraint violation. We propose two different averaging schemes to mitigate the disagreements among the agents' local estimates. We show that the algorithms converge almost surely, i.e., every agent agrees on the same optimal solution, under the assumption that the objective functions and constraint functions are nondifferentiable and their subgradients are bounded. We provide simulation results on a decentralized optimal gossip averaging problem, which involves semidefinite programming constraints, to complement our theoretical results.

关键词： Decentralized optimization distributed algorithms multi-agent systems probabilistic robust design randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fair dynamic resource allocation in transit-based evacuation planning

引用

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 2018年 94卷 307-322页

作者： Aalami, Soheila Kattan, Lina Department of Civil Engineering Schulich School of Engineering University of Calgary Calgary AB Canada

Resource allocation in transit-based emergency evacuation is studied in this paper. The goal is to find a method for allocation of resources to communities in an evacuation process which is (1) fair, (2) reasonably efficient, and (3) able to dynamically adapt to the changes to the emergency situation. Four variations of the resource allocation problem, namely maximum rate, minimum clearance time, maximum social welfare, and proportional fair resource allocation, are modeled and compared. It is shown that the optimal answer to each problem can be found efficiently. Additionally, a distributed and dynamic algorithm based on the Lagrangian dual approach, called PFD(2)A, is developed to find the proportional fair allocation of resources and update the evacuation process in real time whenever new information becomes available. Numerical results for a sample scenario are presented.

关键词： Emergency evacuation Resource allocation Fairness Optimization distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

On the runtime of universal coating for programmable matter

引用

NATURAL COMPUTING 2018年第1期17卷 81-96页

作者： Daymude, Joshua J. Derakhshandeh, Zahra Gmyr, Robert Porter, Alexandra Richa, Andrea W. Scheideler, Christian Strothmann, Thim Arizona State Univ Comp Sci CIDSE Tempe AZ 85287 USA Paderborn Univ Dept Comp Sci Paderborn Germany

Imagine coating buildings and bridges with smart particles (also coined smart paint) that monitor structural integrity and sense and report on traffic and wind loads, leading to technology that could do such inspection jobs faster and cheaper and increase safety at the same time. In this paper, we study the problem of uniformly coating objects of arbitrary shape in the context of self-organizing programmable matter, i.e., programmable matter which consists of simple computational elements called particles that can establish and release bonds and can actively move in a self-organized way. Particles are anonymous, have constant-size memory, and utilize only local interactions in order to coat an object. We continue the study of our universal coating algorithm by focusing on its runtime analysis, showing that our algorithm terminates within a linear number of rounds with high probability. We also present a matching linear lower bound that holds with high probability. We use this lower bound to show a linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information, which implies that our algorithm is also optimal in a competitive sense. Simulation results show that the competitive ratio of our algorithm may be better than linear in practice.

关键词： distributed algorithms Programmable matter Self-organization Self-organizing systems Coating

来源：评论

学校读者我要写书评

暂无评论

Online Leader Selection for Improved Collective Tracking and Formation Maintenance

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2018年第1期5卷 3-13页

作者： Franchi, Antonio Giordano, Paolo Robuffo Univ Toulouse CNRS LAAS CNRS F-31400 Toulouse France Irisa CNRS Campus Beaulieu F-35042 Rennes France Inria Rennes Bretagne Atlantique Campus Beaulieu F-35042 Rennes France

The goal of this paper is to propose an extension of the popular leader-follower framework for multiagent collective tracking and formation maintenance in the presence of a time-varying leader. In particular, the leader is persistently selected online in order to optimize the tracking performance of an exogenous collective velocity command while also maintaining a desired formation via a (possibly time-varying) communication-graph topology. The effects of a change in the leader identity are theoretically analyzed and exploited for defining a suitable error metric that is able to capture the tracking performance of the multiagent group. Both the group performance and the metric design are found to depend upon the spectral properties of a special directed graph induced by the identity of the chosen leader. By exploiting these results, as well as distributed estimation techniques, we are then able to detail a fully decentralized adaptive strategy that is able to periodically select online the best leader among the neighbors of the current leader. Numerical simulations show that the application of the proposed technique results in an improvement of the overall performance of the group behavior with regard to other possible strategies.

关键词： Decentralized control distributed agent systems distributed algorithms mobile agents multiagent systems

来源：评论

学校读者我要写书评

暂无评论

A tutorial on modeling and analysis of dynamic social networks. Part II

引用

ANNUAL REVIEWS IN CONTROL 2018年 45卷 166-190页

作者： Proskurnikov, Anton V. Tempo, Roberto Delft Univ Technol Delft Ctr Syst & Control Delft Netherlands Russian Acad Sci Inst Problems Mech Engn St Petersburg Russia ITMO Univ St Petersburg Russia Politecn Torino CNR IEIIT Turin Italy

Recent years have witnessed a significant trend towards filling the gap between Social Network Analysis (SNA) and control theory. This trend was enabled by the introduction of new mathematical models describing dynamics of social groups, the development of algorithms and software for data analysis and the tremendous progress in understanding complex networks and multi-agent systems (MAS) dynamics. The aim of this tutorial is to highlight a novel chapter of control theory, dealing with dynamic models of social networks and processes over them, to the attention of the broad research community. In its first part (Proskurnikov & Tempo, 2017), we have considered the most classical models of social dynamics, which have anticipated and to a great extent inspired the recent extensive studies on MAS and complex networks. This paper is the second part of the tutorial, and it is focused on more recent models of social processes that have been developed concurrently with MAS theory. Future perspectives of control in social and techno-social systems are also discussed. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Social network Opinion dynamics Multi-agent systems distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

A Faster Exact-Counting Protocol for Anonymous Dynamic Networks

引用

ALGORITHMICA 2018年第11期80卷 3023-3049页

作者： Chakraborty, Maitri Milani, Alessia Mosteiro, Miguel A. Kean Univ Dept Comp Sci Union NJ USA Univ Bordeaux LABRI INP Bordeaux France Pace Univ Comp Sci Dept New York NY 10038 USA

We study the problem of Counting the number of nodes in Anonymous Dynamic Network: nodes do not have identifiers and the network topology changes frequently. Counting is a fundamental task in distributed computing, for instance, to decide termination. Knowing what is the cost of anonymity is of paramount importance to understand what is feasible for future generations of Dynamic Networks, where the lack of nodes identifiers might facilitate mass production. Previous upper bounds to compute the exact network size are double-exponential. Strikingly, only linear complexity lower bounds are known, leaving open the question of whether efficient Counting protocols for Anonymous Dynamic Networks exist or not. In this work, we achieve an exponential speedup presenting Incremental Counting (IC), a distributed Counting protocol for Anonymous Dynamic Networks that has exponential time complexity and computes the exact size of the system. We complement the theoretical study evaluating IC experimentally. We tested a variety of network topologies that may appear in practice, including extremal cases such as trees, paths, and continuously changing topologies. Our simulations showed that IC is polynomial for all the inputs tested, paving the way to use it in practical applications where the network topology is predictable.

关键词： Anonymous dynamic networks Counting distributed algorithms Time-varying graphs

来源：评论

学校读者我要写书评

暂无评论

Greedy Sparse Learning Over Network

引用

IEEE TRANSACTIONS ON SIGNAL AND INFORMATION PROCESSING OVER NETWORKS 2018年第3期4卷 424-435页

作者： Zaki, Ahmed Venkitaraman, Arun Chatterjee, Saikat Rasmussen, Lars Kildehoj KTH Royal Inst Technol Sch Elect Engn S-11428 Stockholm Sweden KTH Royal Inst Technol ACCESS Linneaus Ctr S-11428 Stockholm Sweden

In this paper, we develop a greedy algorithm for solving the problem of sparse learning over a right stochastic network in a distributed manner. The nodes iteratively estimate the sparse signal by exchanging a weighted version of their individual intermediate estimates over the network. We provide a restricted-isometry-property (RIP)-based theoretical performance guarantee in the presence of additive noise. In the absence of noise, we show that under certain conditions on the RIP-constant of measurement matrix at each node of the network, the individual node estimates collectively converge to the true sparse signal. Furthermore, we provide an upper bound on the number of iterations required by the greedy algorithm to converge. Through simulations, we also show that the practical performance of the proposed algorithm is better than other state-of-the-art distributed greedy algorithms found in the literature.

关键词： Adaptive estimation compressed sensing convergence distributed algorithms greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

Renewable Energy-Aware Joint Caching and Routing for Green Communication Networks

引用

IEEE SYSTEMS JOURNAL 2018年第1期12卷 768-777页

作者： Khreishah, Abdallah Salameh, Haythem Bany Khalil, Issa Gharaibeh, Ammar New Jersey Inst Technol Dept Elect & Comp Engn Newark NJ 07102 USA Yarmouk Univ Dept Telecommun Engn Irbid 21163 Jordan Hamad Bin Khalifa Univ Qatar Comp Res Inst Doha 00974 Qatar

The Internet is one of the fastest increasing contributors to carbon emission. Content distribution as video on demand constitutes the majority of the Internet traffic. In order to reduce the Internet's carbon footprint, we propose greener mechanisms for content delivery that utilize the use of renewable energy and content caching concept. If renewable energy is not enough to satisfy a given user's demand, we use brown energy to satisfy the demand. Specifically, we consider the joint routing and caching problem with the objective of minimizing the brown energy usage while satisfying the users' requests. We formulate the problem as a mixed integer-linear program (MILP) and prove that it is NP-hard. Accordingly, we present two relaxation techniques to find an efficient solution in a polynomial time (within 10% of the optimal). The first technique is based on relaxation and rounding. The other one is a near-optimal solution based on sequential fixing, where the binary variables are determined iteratively by solving a sequence of linear programs. Then, we develop a gradient-based distributed algorithm that can adapt to the changes in traffic and renewable energy conditions. Finally, we show that by utilizing network coding, the problem can be formulated using linear programming, which has polynomial-time complexity. Simulation results are provided, which verify the effectiveness of our optimization framework and demonstrate the significant energy saving achieved (up to 90%) over the nonenergy-aware shortest path-routing method.

关键词： Approximation algorithms communication networks distributed algorithms joint caching and routing renewable energy network coding

来源：评论

学校读者我要写书评

暂无评论

Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane

引用

INFORMATION AND COMPUTATION 2018年 263卷 57-74页

作者： D'Emidio, Mattia Di Stefano, Gabriele Frigioni, Daniele Navarra, Alfredo Univ Aquila Dipartimento Ingn & Sci Informaz & Matemat Via Vetoio I-67100 Laquila Italy Univ Perugia Dipartimento Matemat & Informat Via Vanvitelli 1 I-06123 Perugia Italy Gran Sasso Sci Inst Laquila Italy

In this paper we study the computational power of mobile robots without global coordination. A comprehensive evaluation of the computational power of robots moving within the Euclidean plane has been proposed by Das et al. in 2016. In their work, the authors study the relations between classic synchronization models, namely fully synchronous, semi-synchronous, and asynchronous, and variations of them where robots are endowed with a visible light, i.e. they are luminous. Here we are interested in similar settings but for robots moving on graphs. In particular, we first prove computational relationships among classic models on graphs. To this respect, we investigate the gathering problem and disprove conjectures previously posed in the literature. Second, we compare classic models against luminous models. Third, we highlight the differences among different luminous models. Finally, we compare our results with those holding in the Euclidean plane. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Mobile robots Computational complexity distributed algorithms Luminous robots

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：