王钰蓉 丁鹏飞 刘 安

(苏州大学计算机科学与技术学院 江苏 苏州 215006)

0 引 言

图模式匹配(GPM)在许多基于社交网络的应用中发挥了重要的作用，如专家发现[1]和社交社区挖掘[2]。GPM通常是根据子图同构来定义的，其中模式图和数据图之间需要节点和边的精确匹配。子图同构是一个经典的NP完全问题，计算量大。此外，对于一些社交应用程序来说，点和边的精确匹配过于严格。因此，提出了图模拟[3]的概念。在图模拟中，如果数据图中路径的起点和终点分别与模式图中的边的两顶点具有相同的标签，则该路径被视为模式边的匹配。然而，对于一些实际应用而言，图模拟有时仍然过于严格[4-5]。然后，提出了有界模拟[6]的概念。在有界模拟中，每个顶点都被标记为特定的类别，每个边都可以用常数k或*标记。k和*分别代表匹配的最大路径长度的约束不大于k以及不限制该路径长度。有界模拟不执行边到边的映射，而是通过有界长度将模式图中的边与数据图中的路径匹配[6]。根据有界模拟的性质，基于有界模拟的GPM试图找到最小直径的子图。

然而，上下文社交网络中[7]具有许多与顶点和边相关联的上下文信息，例如特定领域中用户的社会角色(例如，AI的顶级专家)，以及用户之间的社会关系(例如，同事关系)和用户之间的信任度。在基于社交网络的各种应用中，如众包旅游[8]、研究团队选择(classroomsalon.com)和社交网络中的专家发现[7]，人们通常愿意对GPM中用户之间的亲密社交关系和用户之间的强信任关系设置一些约束。……