Publication Type

Journal Article

Version

acceptedVersion

Publication Date

6-2020

Abstract

Node similarity search on graphs has wide applications in recommendation, link prediction, to name just a few. However, existing studies are insufficient due to two reasons: (i) the scale of the real-world graph is growing rapidly, and (ii) vertices are always associated with complex attributes. In this paper, we propose an efficiently distributed framework to support node similarity search on massive graphs, which considers both graph structure correlation and node attribute similarity in metric spaces. The framework consists of preprocessing stage and query stage. In the preprocessing stage, a parallel KD-tree construction (KDC) algorithm is developed to form a newly defined graph so-called hybrid graph, in order to integrate node attribute similarity into the original graph. To equally divide graph vertices into subsets, KDC adopts the KD-tree partitioning after the pivot mapping. In addition, two metric pruning rules and an optimized allocation strategy are presented to reduce communication and computation costs. In the query stage, based on the formed hybrid graph, we develop similarity search methods using random walk with restart (RWR) to measure node similarity. To boost efficiency, we derive tight bounds to rapidly shrink the search region. Extensive experiments with three real massive graphs are conducted to verify the effectiveness, efficiency, and scalability of our proposed techniques.

Keywords

Graph, Node similarity search, Distributed processing, Algorithm

Discipline

Computer Engineering | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

World Wide Web

First Page

1

Last Page

29

ISSN

1386-145X

Identifier

10.1007/s11280-020-00819-6

Publisher

Springer (part of Springer Nature): Springer Open Choice Hybrid Journals

Additional URL

https://doi.org/10.1007/s11280-020-00819-6

Download

Share

COinS