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

Subgraph isomorphism in graph classes

DISCRETE MATHEMATICS 2012年第21期312卷 3164-3173页

作者： Kijima, Shuji Otachi, Yota Saitoh, Toshiki Uno, Takeaki Kobe Univ Grad Sch Engn Kobe Hyogo 6578501 Japan Kyushu Univ Grad Sch Informat Sci & Elect Engn Fukuoka 8190395 Japan Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan Natl Inst Informat Tokyo 1018430 Japan

We investigate the computational complexity of the following restricted variant of SUBgraph ISOMORPHISM: given a pair of connected graphs G = (V-G, E-G) and H = (V-H, E-H), determine if H is isomorphic to a spanning subgraph of G. The problem is NP-complete in general, and thus we consider cases where G and H belong to the same graph class such as the class of proper interval graphs, of trivially perfect graphs, and of bipartite permutation graphs. For these graph classes, several restricted versions of SUBgraph ISOMORPHISM such as HAMILTONIAN PATH, CLIQUE, BANDWIDTH, and graph ISOMORPHISM can be solved in polynomial time, while these problems are hard in general. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Subgraph isomorphism graph class NP-completeness graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Maintaining the classes of 4-edge-connectivity in a graph on-line

引用

algorithmICA 1998年第3期20卷 242-276页

作者： Dinitz, Y Westbrook, J Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel AT&T Bell Labs Res Florham Pk NJ 07932 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA

Two vertices of an undirected graph are called k-edge-connected if there exist k edge-disjoint paths between them (equivalently, they cannot be disconnected by the removal of less than k edges from the graph). Equivalence classes of this relation are called classes of k-edge-connectivity or k-edge-connected components. This paper describes graph structures relevant to classes of 4-edge-connectivity and traces their transformations as new edges are inserted into the graph. Data structures and an algorithm to maintain these classes incrementally are given. Starting with the empty graph, any sequence of q Same-4-Class? queries and it Insert-Vertex and lit Insert-Edge updates can be performed in O(q + m + ii log n total time. Each individual query requires O(1) time in the worst-case. In addition, an algorithm for maintaining the classes of k-edge-connectivity (k arbitrary) in a (k-1)-edge-connected graph is presented. Its complexity is O(q + m + n). with O(M + k(2)n log(n/k)) preprocessing, where M is the number of edges initially in the graph and n is the number of its vertices.

关键词： dynamic algorithm dynamic data structure graph algorithm edge-connectivity connectivity class component analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Automata for the verification of monadic second-order graph properties

引用

JOURNAL OF APPLIED LOGIC 2012年第4期10卷 368-409页

作者： Courcelle, Bruno Durand, Irene Univ Bordeaux Labri CNRS F-33405 Talence France

The model-checking problem for monadic second-order logic on graphs is fixed-parameter tractable with respect to tree-width and clique-width. The proof constructs finite automata from monadic second-order sentences. These automata recognize the terms over fixed finite signatures that define graphs satisfying the given sentences. However, this construction produces automata of hyper-exponential sizes, and is thus impossible to use in practice in many cases. To overcome this difficulty, we propose to specify the transitions of automata by programs instead of tables. Such automata are called fly-automata. By using them, we can check certain monadic second-order graph properties with limited quantifier alternation depth, that are nevertheless interesting for graph Theory. We give explicit constructions of automata relative to graphs of bounded clique-width, and we report on experiments. (C) 2012 Elsevier B.V. All rights reserved.

关键词： graph algorithm Automaton Monadic second-order logic Clique-width Fixed-parameter tractability Fly-automaton

来源：评论

学校读者我要写书评

暂无评论

An Explainable Recommendation Based on Acyclic Paths in an Edge-Colored graph 34th

An Explainable Recommendation Based on Acyclic Paths in an E...

引用

34th Australasian Joint Conference on Artificial Intelligence (AI)

作者： Chinone, Kosuke Nakamura, Atsuyoshi Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido Japan

ISBN: (纸本)9783030975463;9783030975456

We propose a novel recommendation algorithm based on acyclic paths in an edge-colored graph. In our method, all the objects including users, items to recommend, and other things usable to recommendation are represented as vertices in an edge-colored directed graph, in which edge color represents relation between the objects of its both ends. By setting each edge weight appropriately so as to reflect how much the object corresponding to its one end is preferred by people who prefer the object corresponding to its other end, the probability of an s-t path, which is defined as the product of its component edges' weights, can be regarded as preference degree of item t (item corresponding to vertex t) by user s (user corresponding to vertex s) in the context represented by the path. Given probability threshold theta, the proposed algorithm recommends user s to item t that has high sum of the probabilities of all the acyclic s-t paths whose probability is at least theta. For item t recommended to user s, the algorithm also shows high probability color sequences of those s-t paths, from which we can know main contexts of the recommendation of item t for user s. According to our experiments using real-world datasets, the recommendation performance of our method is comparable to the non-explainable state-of-the-art recommendation methods.

关键词： Recommender system Explainablity graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Exploring Network Optimizations for Large-Scale graph Analytics 15

Exploring Network Optimizations for Large-Scale Graph Analyt...

引用

International Conference for High Performance Computing, Networking, Storage and Analysis (SC)

作者： Que, Xinyu Checconi, Fabio Petrini, Fabrizio Liu, Xing Buono, Daniele IBM Corp TJ Watson Res Ctr Yorktown Hts NY 10598 USA

ISBN: (纸本)9781450337236

graph analytics are arguably one of the most demanding workloads for high-performance systems and interconnection networks. graph applications often display all-to-all, fine-grained, high-rate communication patterns that expose the limits of the network protocol stacks. Load and communication imbalance generate hard-to-predict network hot-spots, and may require computational steering due to unpredictable data distributions. In this paper we present a lightweight communication library, implemented "on the metal" of BlueGene/Q and POWER7 IH that we have used to support large-scale graph algorithms up to 96K processing nodes and 6 million threads. With this library we have explored several optimization techniques, including overlapped communication, non-blocking collectives, message aggregation, and computation in the network for special collective communication patterns, such as parallel prefix. The experimental results show significant performance improvements, ranging from 5X to 10X, when compared to equally optimized MPI implementations.

关键词： Network Performance graph algorithm POWER7 IH BlueGene/Q

来源：评论

学校读者我要写书评

暂无评论

Manipulating Structural graph Clustering 38

Manipulating Structural Graph Clustering

引用

38th IEEE International Conference on Data Engineering (ICDE)

作者： Li, Wentao Gao, Min Wen, Dong Zhou, Hongwei Ke, Cai Qin, Lu Univ Technol Sydney FEIT AAII Ultimo Australia Chongqing Univ Chongqing Peoples R China Univ New South Wales Sydney NSW Australia

ISBN: (数字)9781665408837

ISBN: (纸本)9781665408837

Structural graph clustering (SCAN) is a popular clustering technique. Using the concept of is an element of-neighborhood, SCAN defines the core vertices that uniquely determine the clusters of a graph. Most existing studies assume that the graph processed by SCAN contains no controlled edges. Few studies, however, have focused on manipulating SCAN by injecting edges. Manipulation of SCAN can be used to assess its robustness and lay the groundwork for developing robust clustering algorithms. To fill this gap and considering the importance of the is an element of-neighborhood for SCAN, we propose a problem, denoted as MN, for manipulating SCAN. The MN problem aims to maximize the is an element of-neighborhood of the target vertex by inserting some edges. On the theoretical side, we prove that the MN problem is both NP-hard and APX-hard, and also is non-submodular and non-monotonic. On the algorithmic side, we design an algorithm by focusing on how to select vertices to join is an element of neighborhood and thus avoid enumerating edges to report a solution. As a result, our algorithm bypasses the non-monotonicity nature of the MN problem. Extensive experiments on real-world graphs show that our algorithm can effectively solve the proposed MN problem.

关键词： Structural graph clustering Manipulation graph algorithm NP-Hard

来源：评论

学校读者我要写书评

暂无评论

A Biologically Plausible graph Structure for AGI 15th

A Biologically Plausible Graph Structure for AGI

引用

15th International Conference on Artificial General Intelligence (AGI)

作者： Simon, Charles J. Future AI Washington DC 20036 USA

ISBN: (纸本)9783031199066;9783031199073;9783031199066

graph structures have shown to represent a viable approach to developingAGI. This paper describes howa knowledge graph could be represented in neurons and introduces theUniversal Knowledge Store (UKS), an open-source implementation, which could form one component of AGI. Unlike backpropagationrelated systems which have only the most tenuous biological relationship, graph structures can be built from basic biological neuron models.

关键词： Artificial general intelligence graph algorithm Biological neuron Leaky-integrate-and-fire Hebbian synapse

来源：评论

学校读者我要写书评

暂无评论

Dynamic graph Repartitioning: From Single Vertex to Vertex Group 25th

Dynamic Graph Repartitioning: From Single Vertex to Vertex G...

引用

25th International Conference on Database Systems for Advanced Applications (DASFAA)

作者： Li, He Yuan, Hang Huang, Jianbin Cui, Jiangtao Yoo, Jaesoo Xidian Univ Sch Comp Sci & Technol Xian Shaanxi Peoples R China Chungbuk Natl Univ Dept Informat & Commun Engn Cheongju Chungbuk South Korea

ISBN: (纸本)9783030594152;9783030594169

With the increase of large graph data arising in applications like Web, social network, knowledge graph, and so on, there is a growing need for partitioning and repartitioning large graph data in graph data systems. However, the existing graph repartitioning methods are known for poor efficiency in the dynamic environment. In this paper, we devise an efficient lightweight method to identify and move the candidate vertices to achieve graph repartitioning in the dynamic environment. Different from previous approaches that just focus on the case of moving a single vertex as a basic unit, we show that the movement of some closely connected vertices as a group can further improve the quality of graph repartitioning result. We conduct experiments on a large set of real and synthetic graph data sets, and the results showed that the proposed method is more efficient comparing with existing method in several aspects.

关键词： graph repartitioning Large graph data graph algorithm Lightweight method

来源：评论

学校读者我要写书评

暂无评论

An Efficient Indexing Method for Dynamic graph kNN 35th

An Efficient Indexing Method for Dynamic Graph kNN

引用

35th International Conference on Database and Expert Systems Applications (DEXA)

作者： Matsugu, Shohei Kobayashi, Suomi Shiokawa, Hiroaki Univ Tsukuba Ctr Computat Sci Tsukuba Ibaraki Japan Univ Tsukuba Grad Sch Sci & Technol Tsukuba Ibaraki Japan

ISBN: (纸本)9783031683084;9783031683091

k-nearest neighbor (kNN) search is a fundamental problem in graph mining. This search finds the k most relevant nodes to a given query node. The increased use of social network services and map applications due to the proliferation of mobile devices has necessitated faster searches. Although pre-constructing an index using graphs can accelerate a kNN search, existing methods struggle handling dynamic graph updates. Herein we propose an efficient index update method for dynamic graphs that utilizes a core-tree structure to efficiently update the index in response to dynamic changes in the graph. Our experimental analysis using real-world data demonstrated that the proposed method can construct indexes more efficiently than the state-of-the-art method.

关键词： graph algorithm kNN search dynamic graph

来源：评论

学校读者我要写书评

暂无评论

Augmenting graph Convolution with Distance Preserving Embedding for Improved Learning 22

Augmenting Graph Convolution with Distance Preserving Embedd...

引用

22nd IEEE International Conference on Data Mining (ICDM)

作者： Cong, Guojing Lim, Seung-Hwan Young, Steven Oakridge Natl Lab Oakridge TN 37830 USA

ISBN: (纸本)9798350346091

graph convolution incorporates topological information of a graph into learning. Message passing corresponds to traversal of a local neighborhood in classical graph algorithms. We show that incorporating additional global structures, such as shortest paths, through distance preserving embedding can improve performance. Our approach, Gavotte, significantly improves the performance of a range of popular graph neural networks such as GCN, GAT,graphSAGE, and GCNII for transductive learning. Gavotte also improves the performance of graph neural networks for full-supervised tasks, albeit to a smaller degree. As high-quality embeddings are generated by Gavotte as a by-product, we leverage clustering algorithms on these embeddings to augment the training set and introduce Gavotte+. Our results of Gavotte+ on datasets with very few labels demonstrate the advantage of augmenting graph convolution with distance preserving embedding.

关键词： citation network GNN graph algorithm shortest path transductive learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：