Impact Vertices-Aware Diffusion Walk Algorithm for Efficient Subgraph Pattern Matching in Massive Graphs

Abstract

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.

Keywords

• Distributed algorithms
• graph theory
• optimal matching
• subgraph matching