Home // ACCSE 2017, The Second International Conference on Advances in Computation, Communications and Services // View article

An Efficient Reachability Queries Approach for Large Graph Based on Cluster Structure

Authors:
Yale Chai
Yao Ge
Chunyao Song
Peng Nie

Keywords: Reachability queries; Graph cluster; Search method

Abstract:
Reachability query is a fundamental operation on graphs that finds the connection between vertices. Although plenty of techniques have been proposed for reachability queries, most of them are designed for directed graphs. Existing techniques for undirected graphs cannot handle large volumes of data. In this paper, we propose an undirected graph reachability (UGR) query algorithm by integrating graph clustering algorithm with traditional search methods. We first find core vertices by partitioning them into clusters, and then cluster non-core vertices according to their adjacent core vertices. After clustering, we take each cluster as a new vertex and compute transitive closure. Experimental results demonstrate the effectiveness and scalability of the proposed methods for the reachability query problem.

Pages: 51 to 53

Copyright: Copyright (c) IARIA, 2017

Publication date: June 25, 2017

Published in: conference

ISSN: 2519-8459

ISBN: 978-1-61208-570-8

Location: Venice, Italy

Dates: from June 25, 2017 to June 29, 2017