An efficient method for top-k graph based node matching

Guanfeng Liu, Qun Shi, Kai Zheng*, An Liu, Zhixu Li, Xiaofang Zhou

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Graph Pattern Matching (GPM) is to find those subgraphs that match a given pattern graph. In many applications, users are interested in the top-k nodes that matches the label of a specific node, (named as the designated node v d ) included in a given pattern graph, rather than the entire set of matching. This is called Graph Pattern based Node Matching (GPNM) problem. However, the existing GPM methods for matching the designated node v d in social graphs do not consider the social contexts like the social relationships, the social trust and the social positions which commonly exist in real applications, like the experts recommendation in social graphs, leading to deliver low quality designated nodes. In this paper, we first propose the conText-Aware Graph pattern based Top-K designed nodes finding problem (TAG-K), which involves the NP-Complete Multiple Constrained GPM problem, and thus it is NP-Complete. To address the efficiency and effectiveness issues of TAG-K in large-scale social graphs, we propose two indices, MA-Tree and SSC-Index, which can help efficiently find the Top-K matching. Furthermore, we propose a probabilistic algorithm based on the Monte Carlo Method, called MC-TAG-K. Based on the experimental results on five real social graphs, we have demonstrated that MC-TAG-K outperforms the existing methods in both efficiency and effectiveness.

Original languageEnglish
Pages (from-to)945-966
Number of pages22
JournalWorld Wide Web
Volume22
Issue number3
DOIs
Publication statusPublished - 15 May 2019

    Fingerprint

Keywords

  • Node matching
  • Social graph
  • Top-k

Cite this

Liu, G., Shi, Q., Zheng, K., Liu, A., Li, Z., & Zhou, X. (2019). An efficient method for top-k graph based node matching. World Wide Web, 22(3), 945-966. https://doi.org/10.1007/s11280-018-0577-y