Context-aware graph pattern based top-k designated nodes finding in social graphs

Guanfeng Liu*, Qun Shi, Kai Zheng, Zhixu Li, An Liu, Jiajie Xu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


Graph Pattern Matching (GPM) plays a significant role in many real applications, where many applications often need to find Top-K matches of a specific node, (named as the designated node v(d)) based on a pattern graph, rather than the entire set of matching. 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 an approximation algorithm, A-TAG-K. Using real social network datasets, we experimentally verify that A-TAG-K outperforms the existing methods in both efficiency and effectiveness for solving the TAG-K problem.

Original languageEnglish
Pages (from-to)751-770
Number of pages20
JournalWorld Wide Web
Issue number2
Publication statusPublished - 15 Mar 2019
Externally publishedYes


  • Graph pattern matching
  • Social graph


Dive into the research topics of 'Context-aware graph pattern based top-k designated nodes finding in social graphs'. Together they form a unique fingerprint.

Cite this