An efficient method for top-k graph based node matching

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

Research output: Contribution to journalArticleResearchpeer-review

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.

LanguageEnglish
Pages945-966
Number of pages22
JournalWorld Wide Web
Volume22
Issue number3
DOIs
Publication statusPublished - 15 May 2019

Fingerprint

Pattern matching
Labels
Monte Carlo methods

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
Liu, Guanfeng ; Shi, Qun ; Zheng, Kai ; Liu, An ; Li, Zhixu ; Zhou, Xiaofang. / An efficient method for top-k graph based node matching. In: World Wide Web. 2019 ; Vol. 22, No. 3. pp. 945-966.
@article{9b11bd8fd2ba497c8b6a1abda4864557,
title = "An efficient method for top-k graph based node matching",
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.",
keywords = "Node matching, Social graph, Top-k",
author = "Guanfeng Liu and Qun Shi and Kai Zheng and An Liu and Zhixu Li and Xiaofang Zhou",
year = "2019",
month = "5",
day = "15",
doi = "10.1007/s11280-018-0577-y",
language = "English",
volume = "22",
pages = "945--966",
journal = "World Wide Web",
issn = "1386-145X",
publisher = "Springer",
number = "3",

}

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, vol. 22, no. 3, pp. 945-966. https://doi.org/10.1007/s11280-018-0577-y

An efficient method for top-k graph based node matching. / Liu, Guanfeng; Shi, Qun; Zheng, Kai; Liu, An; Li, Zhixu; Zhou, Xiaofang.

In: World Wide Web, Vol. 22, No. 3, 15.05.2019, p. 945-966.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - An efficient method for top-k graph based node matching

AU - Liu, Guanfeng

AU - Shi, Qun

AU - Zheng, Kai

AU - Liu, An

AU - Li, Zhixu

AU - Zhou, Xiaofang

PY - 2019/5/15

Y1 - 2019/5/15

N2 - 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.

AB - 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.

KW - Node matching

KW - Social graph

KW - Top-k

UR - http://www.scopus.com/inward/record.url?scp=85047439243&partnerID=8YFLogxK

U2 - 10.1007/s11280-018-0577-y

DO - 10.1007/s11280-018-0577-y

M3 - Article

VL - 22

SP - 945

EP - 966

JO - World Wide Web

T2 - World Wide Web

JF - World Wide Web

SN - 1386-145X

IS - 3

ER -