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

A Two-Phase Method to Balance the Result of Distributed graph Repartitioning

IEEE TRANSACTIONS ON BIG DATA 2022年第6期8卷 1580-1591页

作者： Li, He Huang, Jianbin Yuan, Hang Cui, Jiangtao Ma, Xiaoke Qiao, Shaojie Wu, Xindong Xidian Univ Sch Comp Sci & Technol Xian 710126 Shaanxi Peoples R China Chengdu Univ Informat Technol Sch Software Engn Chengdu 610225 Sichuan Peoples R China Mininglamp Acad Sci Mininglamp Technol Beijing 100102 Peoples R China Hefei Univ Technol Key Lab Knowledge Engn Big Data Hefei 230009 Anhui Peoples R China

With the increase in popularity of graph structured data arising in different areas such as Web, social network, communication network, knowledge graph, etc., there is a growing need for partitioning and repartitioning large graph data in a distributed system. However, the existing graph repartitioning methods are known for poor efficiency in the distributed environment and most of them lack a balance mechanism between edge cut and load balance. In this article, we introduce a new two-phase method to improve the result of distributed graph repartitioning. We first design a local method to identify all the potential candidate vertices that could improve the graph repartitioning result in load balance and edge cut at once in each partition locally. After that, we propose to migrate the selected vertices among the given initial partitions to improve the result of graph repartitioning. During this procedure, we propose to adopt a synchronous vertex migration method to balance both the edge cuts and load balance problems. Extensive experimental results demonstrate that the proposed method is more efficient than the existing methods in several aspects such as communication cost, running time, edge cut, and load balance. We also run SSSP and PageRank applications based on the graph repartitioning result on Giraph to indicate the efficiency of the proposed method.

关键词： Social networking (online) Big Data Partitioning algorithms Interference Distributed databases Knowledge engineering Internet Large graph graph partitioning graph repartitioning graph management graph algorithm

来源：评论

学校读者我要写书评

暂无评论

graph Computing Systems and Partitioning Techniques: A Survey

引用

IEEE ACCESS 2022年 10卷 118523-118550页

作者： Ayall, Tewodros Alemu Liu, Huawen Zhou, Changjun Seid, Abegaz Mohammed Gereme, Fantahun Bogale Abishu, Hayla Nahom Yacob, Yasin Habtamu Zhejiang Normal Univ Dept Comp Sci Jinhua 321004 Zhejiang Peoples R China Dilla Univ Dept Comp Sci Dilla Ethiopia Shaoxing Univ Dept Comp Sci Shaoxing 312000 Zhejiang Peoples R China Hamad Bin Khalifa Univ Informat & Comp Technol Doha Qatar Univ Elect Sci & Technol China Inst Fundamental & Frontier Sci Chengdu 611731 Peoples R China Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China

graphs are a tremendously suitable data representations that model the relationships of entities in many application domains, such as recommendation systems, machine learning, computational biology, social network analysis, and other application domains. graphs with many vertices and edges have become quite prevalent in recent years. Therefore, graph computing systems with integrated various graph partitioning techniques have been envisioned as a promising paradigm to handle large-scale graph analytics in these application domains. However, scalable processing of large-scale graphs is challenging due to their high volume and inherent irregular structure of the real-world graphs. Hence, industry and academia have been recently proposing graph partitioning and computing systems to process and analyze large-scale graphs efficiently. The graph partitioning and computing systems have been designed to improve scalability issues and reduce processing time complexity. This paper presents an overview, classification, and investigation of the most popular graph partitioning and computing systems. The various methods and approaches of graph partitioning and diverse categories of graph computing systems are presented. Finally, we discuss main challenges and future research directions in graph partitioning and computing systems.

关键词： Distributed computing graph computing systems graph partitioning graph processing systems graph databases graph algorithm large-scale graph analysis

来源：评论

学校读者我要写书评

暂无评论

Efficient graph computation on hybrid CPU and GPU systems

引用

JOURNAL OF SUPERCOMPUTING 2015年第4期71卷 1563-1586页

作者： Zhang, Tao Zhang, Jingjie Shu, Wei Wu, Min-You Liang, Xiaoyao Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200240 Peoples R China Fudan Univ Dept Elect Engn Shanghai 200433 Peoples R China

graphs are used to model many real objects such as social networks and web graphs. Many real applications in various fields require efficient and effective management of large-scale, graph-structured data. Although distributed graph engines such as GBase and Pregel handle billion-scale graphs, users need to be skilled at managing and tuning a distributed system in a cluster, which is a non-trivial job for ordinary users. Furthermore, these distributed systems need many machines in a cluster in order to provide reasonable performance. Several recent works proposed non-distributed graph processing platforms as complements to distributed platforms. In fact, efficient non-distributed platforms require less hardware resource and can achieve better energy efficiency than distributed ones. graphChi is a representative non-distributed platform that is disk-based and can process billions of edges on CPUs in a single PC. However, the design drawbacks of graphChi on I/O and computation model have limited its parallelism and performance. In this paper, we propose a general, disk-based graph engine called ggraph to process billion-scale graphs efficiently by utilizing both CPUs and GPUs in a single PC. Ggraph exploits full parallelism and full overlap of computation and I/O processing as much as possible. Experiment results show that ggraph outperforms graphChi and Powergraph. In addition, ggraph achieves the best energy efficiency among all evaluated platforms.

关键词： graph graph algorithm graph processing platform GPU

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration of maximum-weight b-matchings in a graph

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第2期37卷 454-464页

作者： Ito, Takehiro Kakimura, Naonori Kamiyama, Naoyuki Kobayashi, Yusuke Okamoto, Yoshio Tohoku Univ Grad Sch Informat Sci Sendai Miyagi Japan Keio Univ Dept Math Yokohama Kanagawa Japan Kyushu Univ Inst Math Ind Fukuoka Fukuoka Japan Univ Tsukuba Fac Engn Informat & Syst Tsukuba Ibaraki Japan Univ Electrocommun Dept Commun Engn & Informat Tokyo Japan RIKEN Ctr Adv Intelligence Project Tokyo Japan

Consider a graph such that each vertex has a nonnegative integer capacity and each edge has a positive integer weight. Then, a b-matching in the graph is a multi-set of edges (represented by an integer vector on edges) such that the total number of edges incident to each vertex is at most the capacity of the vertex. In this paper, we study a reconfiguration variant for maximum-weight b-matchings: For two given maximum-weight b-matchings in a graph, we are asked to determine whether there exists a sequence of maximum-weight b-matchings in the graph between them, with subsequent b-matchings obtained by removing one edge and adding another. We show that this reconfiguration problem is solvable in polynomial time for instances with no integrality gap. Such instances include bipartite graphs with any capacity function on vertices, and 2-matchings in general graphs. Thus, our result implies that the reconfiguration problem for maximum-weight matchings can be solved in polynomial time for bipartite graphs.

关键词： Combinatorial reconfiguration graph algorithm b-matching

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity of the list coloring reconfiguration problem with graph parameters

引用

THEORETICAL COMPUTER SCIENCE 2018年 739卷 65-79页

作者： Hatanaka, Tatsuhiko Ito, Takehiro Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Aoba Yama 6-6-05 Sendai Miyagi 9808579 Japan

Let G be a graph such that each vertex has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. For two given list colorings of G, we study the problem of transforming one into the other by changing only one vertex color assignment at a time, while at all times maintaining a list coloring. This problem is known to be PSPACE-complete even for bounded bandwidth graphs and a fixed constant k. In this paper, we study the fixed-parameter tractability of the problem when parameterized by several graph parameters. We first give a fixed-parameter algorithm for the problem when parameterized by k and the modular-width of an input graph. We next give a fixed-parameter algorithm for the shortest variant which computes the length of a shortest transformation when parameterized by k and the size of a minimum vertex cover of an input graph. As corollaries of these two results, we show that the problem for cographs and the shortest variant for split graphs are fixed-parameter tractable even when only k is taken as a parameter. On the other hand, we prove that the problem is Will-hard when parameterized only by the size of a minimum vertex cover of an input graph. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration graph algorithm List coloring Fixed-parameter algorithm W-hardness

来源：评论

学校读者我要写书评

暂无评论

Fast Subgraph Matching by Dynamic graph Editing

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2024年第5期17卷 2432-2443页

作者： Jiang, Zite Zhang, Shuai Liu, Boxiao Hou, Xingzhong Yuan, Mengting You, Haihang Chinese Acad Sci Inst Comp Technol SKLP Beijing 100045 Peoples R China Univ Chinese Acad Sci Sch Comp Sci & Technol Beijing 101408 Peoples R China Zhongguancun Lab Beijing 100190 Peoples R China Wuhan Univ Sch Comp Sci Wuhan 430072 Peoples R China

Subgraph matching is a challenging NP-complete problem that involves finding identical subgraphs of a query graph qq in a larger data graph G. It has numerous applications in diverse fields, including social and biological networks. However, existing subgraph matching algorithms assume that the graph structure is fixed, which limits their performance in solving more difficult matching cases. To address this issue, we propose a novel approach called Dynamic graph Editing (DGE), which dynamically edits the query graph to optimize the subgraph matching algorithm. Based on this approach, we introduce an efficient enumeration method called Dynamic graph Editing Enumeration, which significantly improves the performance of the algorithm. Our experimental results show that DGE outperforms current state-of-the-art algorithms in terms of computational efficiency and ability to solve more complex subgraph matching cases.

关键词： Heuristic algorithms Optimization Search problems Approximation algorithms Social networking (online) Pattern matching Constraint handling graph algorithm subgraph matching query processing optimization technique

来源：评论

学校读者我要写书评

暂无评论

On the Tractability of Covering a graph with 2-Clubs

引用

algorithmICA 2023年第4期85卷 992-1028页

作者： Dondi, Riccardo Lafond, Manuel Univ Bergamo Bergamo Italy Univ Sherbrooke Sherbrooke PQ Canada

Covering a graph with cohesive subgraphs is a classical problem in theoretical computer science, for example when the cohesive subgraph model considered is a clique. In this paper, we consider as a model of cohesive subgraph the 2-clubs, which are induced subgraphs of diameter at most 2. We prove new complexity results on the Min 2-Club Cover problem, a variant recently introduced in the literature which asks to cover the vertices of a graph with a minimum number of 2-clubs. First, we answer an open question on the decision version of Min 2-Club Cover that asks if it is possible to cover a graph with at most two 2-clubs, and we prove that it is W[1]-hard when parameterized by the distance to a 2-club. Then, we consider the complexity of Min 2-Club Cover on some graph classes. We prove that Min 2-Club Cover remains NP-hard on subcubic planar graphs, W[2]-hard on bipartite graphs when parameterized by the number of 2-clubs in a solution, and fixed-parameter tractable on graphs having hounded treewidth.

关键词： graph algorithm Cohesive subgraphs 2-Clubs Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

FBSgraph: Accelerating Asynchronous graph Processing via Forward and Backward Sweeping

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2018年第5期30卷 895-907页

作者： Zhang, Yu Liao, Xiaofei Jin, Hai Gu, Lin Zhou, Bing Bing Huazhong Univ Sci & Technol Serv Comp Technol & Syst Lab Cluster & Grid Comp Lab Sch Comp Sci & Technol Wuhan 430074 Hubei Peoples R China Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

graph algorithm is pervasive in many applications ranging from targeted advertising to natural language processing. Recently, Asynchronous graph Processing (AGP) is becoming a promising model to support graph algorithm on large-scale distributed computing platforms because it enables faster convergence speed and lower synchronization cost than the synchronous model for no barrier between iterations. However, existing AGP methods still suffer from poor performance for inefficient vertex state propagation. In this paper, we propose an effective and low-cost forward and backward sweeping execution method to accelerate state propagation for AGP, based on a key observation that states in AGP can be propagated between vertices much faster when the vertices are processed sequentially along the graph path within each round. Through dividing graph into paths and asynchronously processing vertices on each path in an alternative forward and backward way according to their order on this path, vertex states in our approach can be quickly propagated to other vertices and converge in a faster way with only little additional overhead. In order to efficiently support it over distributed platforms, we also propose a scheme to reduce the communication overhead along with a static priority ordering scheme to further improve the convergence speed. Experimental results on a cluster with 1,024 cores show that our approach achieves excellent scalability for large-scale graph algorithms and the overall execution time is reduced by at least 39.8 percent, in comparison with the most cutting-edge methods.

关键词： graph algorithm synchronous/asynchronous convergence cascade effect

来源：评论

学校读者我要写书评

暂无评论

graph model for optimal OVSF code placement strategies

引用

INTERNATIONAL JOURNAL OF AD HOC AND UBIQUITOUS COMPUTING 2012年第3期9卷 133-141页

作者： Ouyang, Wen Yu, Chang Wu Liu, Meng-Ti Chang, Yu-Wei Chung Hua Univ Dept Comp Sci & Informat Engn Hsinchu 30012 Taiwan

The code utilisation of OVSF-CDMA systems are significantly impacted by the code placement and replacement schemes which have been studied by many researchers as independent problems. We formally define the placement optimality and present a novel graph model, CIDP, which is proved to be NP-complete for general graphs where the CIDP graphs reduced from the OVSF code placement problem are trivial perfect graphs. A unified algorithm UCMS-1, provided to firstly address both OVSF code placement and replacement jointly, achieves placement optimality in linear time complexity. It shows that OVSF code placement optimality problem is in P.

关键词： graph algorithm OVSF-CDMA code blocking code placement constrained independent dominating set

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration of list L(2,1)-labelings in a graph

引用

THEORETICAL COMPUTER SCIENCE 2014年第C期544卷 84-97页

作者： Ito, Takehiro Kawamura, Kazuto Ono, Hirotaka Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Kyushu Univ Fac Econ Higashi Ku Fukuoka 8128581 Japan

For an integer k >= 0, suppose that each vertex v of a graph G has a set C(v) subset of {0, 1,..., k} of labels, called a list of v. A list L(2, 1)-labeling of G is an assignment of a label in C(v) to each vertex v of G such that every two adjacent vertices receive labels which differ by at least 2 and every two vertices of distance two receive labels which differ by at least 1. In this paper, we study the problem of reconfiguring one list L(2, 1)-labeling of a graph into another list L(2, 1)-labeling of the same graph by changing only one label assignment at a time, while at all times maintaining a list L(2, 1)-labeling. First we show that this decision problem is PSPACE-complete, even for bipartite planar graphs and k >= 6. In contrast, we then show that the problem can be solved in linear time for general graphs if k <= 4. We finally consider the problem restricted to trees, and give a sufficient condition for which any two list L(2, 1)-labelings of a tree can be transformed into each other. (C) 2014 Elsevier B.V. All rights reserved.

关键词： graph algorithm L(2,1)-labeling PSPACE-complete Reachability on solution space

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：