An efficient method for top-k graph based node matching

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.