基于强社交图的多约束信任图模式增量匹配算法

TRUST-ORIENTED GRAPH INCREMENTAL PATTERN MATCHING WITH MULTIPLE CONSTRAINTS BASED ON STRONG SOCIAL GRAPH

针对现有的图匹配方法没有考虑到社交背景下的多种约束以及在多约束图匹配中图结构的变化,提出一种多约束图模式匹配方法。为了提高多约束图模式匹配的效率,提出强社交图的概念及一种强社交图的索引结构来索引图的可达性、图模式和上下文背景信息,提出维护强社交图索引的算法INC-SSG和多约束图匹配的增量算法SSG-IncMGPM,当面对强社交图结构的变化时能快速有效地识别多约束图模式匹配结果。通过对五个真实社交图的实证研究,验证了该方法在效率和有效性方面的优越性。

The existing graph pattern matching(GPM)methods do not consider the multiple constraints of the social contexts in GPM or the changes of graph structure in GPM with multiple constraints,so we propose a multi-constrained graph pattern matching(MC-GPM)method.To improve the efficiency of MC-GPM in large social graphs,the concept of strong social graph(SSG)and an index structure of SSG were proposed to index the reachability,the graph patterns and the social contexts of social graphs.An incremental algorithm was proposed to maintain the SSG-index,which can greatly save the execution time when facing the change of the structures of SSGs.Moreover,with combing SSG-index,an incremental algorithm was developed,called SSG-IncMGPM,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.