Strong social graph based trust-oriented graph pattern matching with multiple constraints

Guanfeng Liu*, Yurong Wang, Bolong Zheng, Zhixu Li, Kai Zheng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


Online social network is popular and graph pattern matching (GPM) has been significant in many social network based applications, such as experts finding and social position detection. However, the existing GPM methods do not consider the multiple constraints of the social contexts in GPM, which are commonly found in various applications, or they do not consider the changes of graph structure in the index maintenance of GPM, leading to low efficiency. In this paper, we first propose a multi-constrained simulation based on the bounded graph simulation, and propose a multi-constrained graph pattern matching (MC-GPM) problem. To improve the efficiency of MC-GPM in large social graphs, we propose a new concept, strong social graph (SSG), that contains the users who have strong social connections. Then, we propose an SSG-index method to index the reachability, the graph patterns, and the social contexts of social graphs. Finally, we propose an incremental algorithm to maintain the SSG-index, which can greatly save the execution time when faced with the change of the structures of SSGs. Moreover, by combining SSG-index, we develop a heuristic algorithm, called SSG-MGPM, to identify MC-GPM results effectively and efficiently. An empirical study over five real-world social graphs has demonstrated the superiority of our approach in terms of efficiency and effectiveness.

Original languageEnglish
Pages (from-to)675-685
Number of pages11
JournalIEEE Transactions on Emerging Topics in Computational Intelligence
Issue number5
Publication statusPublished - Oct 2020


  • graph pattern matching
  • social network
  • Trust


Dive into the research topics of 'Strong social graph based trust-oriented graph pattern matching with multiple constraints'. Together they form a unique fingerprint.

Cite this