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

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.