.png){kind=icon}
返回
Impact Vertices-Aware Diffusion Walk Algorithm for Efficient Subgraph Pattern Matching in Massive Graphs
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2019.2908930.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Subgraph pattern matching is a basic building block for many applications. Where to commence the pattern matching task and how to proceed are fundamental issues in massive graphs. In this paper, we propose the most impact vertices in view of a query graph and diffusion walk on data graph. We present a novel impact vertices-aware diffusion walk algorithm, a distributed algorithm named DiffWalk, for subgraph pattern matching. Our algorithm employs the most impact vertices from a query graph to locate the initial search position and then proceeds to traverse a large-scale data graph by diffusion walk. We give theoretical analyses based on probability inference and spectral graph, which prove that graph pattern matching beginning at the most impact vertices could prevent comparison overhead by low-probability events first, also prove that diffusion walk could traverse graph efficiently. We have performed a range of experiments that demonstrate our algorithm efficiency both in running time and communication size.
Keyword:
Distributed algorithms
graph theory
optimal matching
subgraph matching
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。