TY - JOUR
T1 - Strong social graph based trust-oriented graph pattern matching with multiple constraints
AU - Liu, Guanfeng
AU - Wang, Yurong
AU - Zheng, Bolong
AU - Li, Zhixu
AU - Zheng, Kai
PY - 2020/10
Y1 - 2020/10
N2 - 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.
AB - 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.
KW - graph pattern matching
KW - social network
KW - Trust
UR - http://www.scopus.com/inward/record.url?scp=85087500234&partnerID=8YFLogxK
U2 - 10.1109/TETCI.2019.2920404
DO - 10.1109/TETCI.2019.2920404
M3 - Article
AN - SCOPUS:85087500234
SN - 2471-285X
VL - 4
SP - 675
EP - 685
JO - IEEE Transactions on Emerging Topics in Computational Intelligence
JF - IEEE Transactions on Emerging Topics in Computational Intelligence
IS - 5
ER -