论文部分内容阅读
图是一种用于描述实体间复杂关联关系的通用数据结构,而异构图是一种带标签的特殊图结构,在多种不同实体组成的复杂数据建模中被广泛应用,例如信息网络、生物网络等实际应用领域。在异构数据图中如何进行有效的子图匹配成为近些年的研究热点。子图匹配是用户给定查询图,从大数据图中找到与查询图的结构相同且节点标签相同的所有子图。但在实际应中,人们往往关注兴趣度比较高的匹配结果,因此引出更具针对性的Top-K兴趣子图匹配问题。Top-K兴趣子图匹配主要分为两个部分,一是根据查询图在数据图中找到所有的匹配子图;二是将所有的匹配子图根据兴趣度排名获得兴趣度最大的K个兴趣子图。本文针对异构图中的Top-K兴趣子图匹配问题进行研究发现,目前已有方法存在若干问题,如仅涉及静态图上中针对无权查询图的匹配问题,没有考虑用户的个性化需求,即对有权查询图的匹配处理;在实际应用中,随着时间推移、实际应用语义的改变,图将发生拓扑结构的变化,即图的动态演进,对图的动态演进过程中的Top-K兴趣子图匹配研究关注很少。因此,为解决上述问题,本文考虑用户的个性化需求,提出一种高效的针对有权查询图的静态Top-K兴趣子图匹配方法;同时,针对图的动态演进过程中Top-K兴趣子图匹配问题展开研究,提出一种有效的基于增量的动态Top-K兴趣子图匹配方法。主要内容如下:(1)提出一种高效的静态Top-K兴趣子图匹配方法(ERWM)。首先,根据异构图的特性,提出一种类邻接表的储存结构存储异构数据图;其次,建立两种新异的索引:节点的拓扑结构特性索引(NTFI)、边特性索引(EFI),充分利用它们提供的节点和边的信息,在查询检索阶段过滤掉不合格(不匹配)的节点和边,获得相对较少的候选集,避免了匹配阶段进行不必要的节点、边连通性检测,从而减少了算法的冗余匹配步骤;最后,提出查询图边的标签设定方法,利用其确定查询边进行子图匹配验证的顺序,同时引入RWM算法的边匹配边排序的思想,从而提高图的子图匹配效率,减少冗余的子图匹配步骤。(2)提出一种有效的动态Top-K兴趣子图匹配方法(DRWM)。该方法在ERWM算法基础上进行动态扩展。首先,利用滑动窗口模型处理动态异构图的局部动态变化数据;其次,利用滑动窗口的思想,实现基于图的增量变化动态更新的Top-K兴趣子图匹配。(3)在模拟数据集和真实数据上,将本文提出的方法与现有的RAM和RWM方法进行对比,分别对算法索引构建、Top-K子图匹配的实验结果进行比较和分析,验证了本文提出的Top-K兴趣子图匹配方法在模拟和现实网络上,都具有较好的查询匹配能力,Top-K兴趣子图匹配的效率得到了极大的提高。