MCS-GPM: multi-constrained simulation based graph pattern matching in contextual social graphs

Guanfeng Liu, Yi Liu, Kai Zheng, An Liu, Zhixu Li, Yan Wang, Xiaofang Zhou

Research output: Contribution to journalArticlepeer-review

46 Citations (Scopus)


Graph Pattern Matching (GPM) has been used in lots of areas, like biology, medical science, and physics. With the advent of Online Social Networks (OSNs), recently, GPM has been playing a significant role in social network analysis, which has been widely used in, for example, finding experts, social community mining, and social position detection. Given a query which contains a pattern graph GQ and a data graph GD, a GPM algorithm finds those subgraphs, GM, that match GQ in GD. However, the existing GPM methods do not consider the multiple end-to-end constraints of the social contexts, like social relationships, social trust, and social positions on edges in GQ, which are commonly found in various applications, such as crowdsourcing travel, social network based ecommerce, and study group selection, etc. In this paper, we first conceptually extend Bounded Simulation to Multi-Constrained Simulation (MCS), and propose a novel NP-Complete Multi-Constrained Graph Pattern Matching (MC-GPM) problem. Then, to address the efficiency issue in large-scale MC-GPM, we propose a new concept called Strong Social Component (SSC), consisting of participants with strong social connections. We also propose an approach to identifying SSCs, and propose a novel index method and a graph compression method for SSC. Moreover, we devise a multithreading heuristic algorithm, called M-HAMC, to bidirectionally search the MC-GPM results in parallel without decompressing graphs. An extensive empirical study over five real-world large-scale social graphs has demonstrated the effectiveness and efficiency of our approach.
Original languageEnglish
Pages (from-to)1050-1064
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number6
Publication statusPublished - 1 Jun 2018


  • graph pattern matching
  • social graph


Dive into the research topics of 'MCS-GPM: multi-constrained simulation based graph pattern matching in contextual social graphs'. Together they form a unique fingerprint.

Cite this