文摘

图形模式匹配是广泛应用于大数据的应用程序。然而,现实世界的图通常是巨大的和动态的。小变化数据图表或图案图可能会导致严重的计算成本。增量图匹配算法可以避免再计算在整个图和降低计算成本数据图或图表更新模式。PGC_IncGPM现有的增量算法可以有效地减少匹配时间不超过一半的边缘模式更新图。然而,随着改变了边缘的数量增加,提高PGC_IncGPM逐渐减少。为了解决这个问题,开发iDeltaP_IncGPM本文改进算法。对多个插入(分别地。,deletions) on pattern graphs, iDeltaP_IncGPM determines the nodes’ matching state detection sequence and processes them together. Experimental results show that iDeltaP_IncGPM has higher efficiency and wider application range than PGC_IncGPM.

1。介绍

图模式匹配是找到的所有子图给定模式的相同或相似的图在数据图 。广泛应用在许多应用程序中,例如,web文档分类,软件剽窃检测,蛋白质结构检测(1- - - - - -3]。

随着因特网的迅速发展,大量的图表数据每天都出现。例如,有关开放数据项目,旨在通过网络连接数据,直到2017年发表了1490亿年三元组(4]。此外,现实世界的图形是动态的(5]。通常是浪费时再计算匹配从零开始或是更新。增量匹配算法是必要的,其目的是为了减少不必要的重新计算,通过分析和计算匹配结果的变化更新(职责。)(职责。)。

例如,图1(一)是一个模式的图和图1 (b)是一个数据图 。组成的子图 , , , , ,以及它们之间的边缘(为简单起见,表示 )是唯一匹配子图。假设( , )和( , )从图模式,传统的验算算法计算新模式的匹配图对整个数据图。这是浪费时间。增量算法只会检查节点的一部分G,也就是说, , ,和添加新的匹配子图( , 最初的匹配结果。

目前,增量图模式匹配的研究仍处于起步阶段,现有的工作(6- - - - - -12)主要集中在数据图的更新。在我们之前的研究中,我们提出了一个增量图匹配算法叫PGC_IncGPM,用于场景数据图是常量和模式更新图表(13]。PGC_IncGPM可以有效地降低图像匹配的运行时只要改变了边缘的数量小于不变边的数量 。然而,PGC_IncGPM的改善效果逐渐增加改变了边缘的数量减少。本文的瓶颈PGC_IncGPM进一步分析。节点的优化方法的匹配状态检测提出了序列,和一种更有效的算法称为iDeltaP_IncGPM是设计和实现。

使用图1作为一个例子,假设(B, E)和(C, D)从模式中删除图。PGC_IncGPM算法将首先考虑删除(B, E),也就是说,检查B₂,一个₂B₃和一个₃,然后考虑删除(C, D),也就是说,检查C₂B₂,一个₂C₃B₃和一个₃。因此B₂,一个₂B₃和一个₃都检查两次。iDeltaP_IncGPM认为两个一起删除;C₂B₂,一个₂C₃B₃和一个₃都是只检查一次。

本文的其余部分组织如下。节2综述了相关工作。模型描述和定义部分3。节4,我们的算法。部分5实验结果和比较,部分6给出了结论。

2。相关工作

我们调查相关工作在两类:图模式匹配模型和增量算法对大规模图匹配图。

图模式匹配通常定义的子图同构(14,15]。然而,子图同构是一个np完全问题[16]。此外,子图同构是经常限制太多,因为它要求匹配子图完全相同的拓扑模式图。这些阻碍社交网络等新兴应用的适用性和犯罪检测。因此,模拟图(17和它的扩展18- - - - - -22)采用模式匹配。图模拟保存的标签和孩子关系的图形模式匹配。在实际应用程序中,图模拟非常松散,它可能会产生大量无用的匹配,可以大量有用的信息。双模拟(18)提高图形模拟征收额外的条件,保护儿童和父母的关系(向下和向上映射)。由于其良好的平衡度和高的实用价值的双重模拟响应时间和效率,图形模式匹配的定义是双重仿真。

目前,增量图模式匹配的研究仍处于起步阶段;现有的工作(6- - - - - -12)主要集中在数据图的更新。风扇等人提出了增量图仿真算法IncMatch [6,7]。太阳等人研究了最大小团体枚举问题动态图(8]。Stotz等人研究了增量不精确的子图同构问题9]。王、陈提出增量近似图匹配算法,改变了近似子图搜索到向量空间关系检测(10]。当插入或删除数据图,修改相关节点的向量和新的向量是否仍然包含模式的矢量图核对。Choudhury等人发明了一种快速匹配系统StreamWorks动态图(11]。系统可以实时检测可疑模式图形和早期警告高风险的数据传输模式在不断更新的网络图。Semertzidis和Pitoura提议的方法找到最持久的一个输入图形模式匹配图,随时间而变化12]。在[13),增量图匹配算法提出了更新的图形模式。

在大数据时代23),图计算广泛应用于不同的领域,如社交网络(24),传感器网络(25,26,物联网27,28),和蜂窝网络29日]。因此,迫切要求改进的性能大图像处理,特别是图形模式匹配。

3所示。模型和定义

图形模式匹配模式的图形和数据图是有向图和标签。图中的每个节点都有一个独特的标签,它定义了节点的态度(如关键词、技能类、名称、和公司)。

定义1(图)。一个节点标示有向图(或只是一个图表)被定义为 ,在那里是一组有限的节点, 是一个有限集合的边缘,是一个函数映射每个节点在一个标签 ;也就是说,的属性是 。

定义2(图模式匹配)。给定一个图模式 和一个数据图 ,匹配如果有一个二元关系 ,这样(1)如果 ,然后 ;(2) ,存在一个节点在这样 (一) ,存在优势 这样 ;(b) ,存在优势 这样 。

条件(2)(a)确保匹配的节点让孩子的关系 ;(2)(b)保证条件维护父母的关系 。

对于任何和 ,存在一个唯一最大匹配关系 。图形模式匹配 ,结果图的子图可以代表 。

考虑到一个现实生活中的例子,招聘人员想找一个专业的软件开发团队从社交网络。图2(一个)的基本组织图是一个软件开发团队。身份的团队由以下人员组成:项目经理(PM),数据库工程师(DB),软件架构(SA)、业务流程分析(BA),用户界面设计师(UD),软件开发(SD)和软件测试人员(ST)。图中的每个节点代表一个人,和节点的标签意味着人的身份。边缘从节点到节点B意味着B行之有效的监督下一个社交网络如图2 (b)。在这个例子中,是(DB数据库₁),(点,点₁),(SA SA₁),(BA BA₁),(UD UD₁),(SD, SD₁),(SD, SD₂),(圣,圣₁),(圣,圣₂)}。因为英国航空公司₂没有一个孩子匹配UD和SA吗₂没有一个家长匹配DB,点₂不让孩子点关系。出于同样的原因,SD₃(职责。ST₃)不匹配SD(分别地。圣)。

定义3(增量图模式匹配模式图形变化)。给定一个数据图和图模式 ,的匹配结果为是 。假设变化 ,新模式图形表示为 。与批处理算法,再计算匹配从零开始,增量图匹配算法的目标是找到的变化来 为了应对这样 。
当很小,通常是小的,它是更少的成本比验算整个组匹配计算。换句话说,这说明我们计算比赛一旦通过batch-matching整个图算法,然后逐步确定新的匹配响应不支付的成本高复杂性的图形模式匹配。
为了得到很快,索引可以预先构建的基于所选择的数据图的特点在增量匹配来减少搜索空间。索引越多,时间越短和更大的空间来存储索引。对大规模数据图,响应时间和存储成本需要降低。考虑存储成本和响应时间的平衡,在这篇文章中,三种集生成的图匹配的过程中被用作索引。(1)首先是候选人匹配集萤石();为每个节点在 ,萤石(u)包括所有节点只有拥有相同的标签 。的节点萤石()被称为c节点。(2)第二个孩子匹配集sim卡();为每个节点在 ,sim卡(u)包括所有节点保护孩子的关系 。的节点sim卡()被称为年代节点。(3)第三个完成匹配集垫();为每个节点在 ,垫(u)包括所有节点保护孩子和父母的关系 。的节点垫()被称为米节点。

本文中使用的符号概念部分所示。

4所示。iDeltaP_IncGPM算法

在本节中,我们提出了改进的增量图模式匹配算法模式变化(图)。

4.1。的想法PGC_IncGPM算法

PGC_IncGPM[的基本框架13)如图3。

图形模式匹配算法(gpm)首先表现在整个数据图模式的图 。计算匹配结果图并创建索引所需的后续增量匹配。可能包括边缘插入()和边删除()。增量图形模式匹配算法PGC_IncGPM首先调用subalgorithm AddEdges得到和,然后调用subalgorithm SubEdges得到和 。 新匹配的结果吗 ,新索引,可以用于后续的增量匹配如果图模式改变了。

边缘插入(分别地。边删除)处理一个接一个的AddEdges(分别地。SubEdges)。例如,当删除多个边缘 ,处理PGC_IncGPM如下。

在第一步中,为每个执行以下操作删除边( ):为每一个 ,无论让孩子的关系在 检查。如果让孩子的关系u,然后从萤石(u)sim卡(u),的父母在萤石()处理。

在第二步中,每个节点sim卡()是反复过滤根据其父母和孩子;新生成的米节点被添加到垫()。

在第一步中,当删除( )P中,一些节点萤石(u),萤石()(的是一个祖先)可能会改变c节点,年代节点。因此,当一个c- node成为年代- node,使用自底向上方法来找到自己的父母和祖先萤石()。如果( , )和( , 删除)和有一个共同的祖先 ,然后萤石()将访问两次。总之,有一个瓶颈PGC_IncGPM多个删除边。多个插入边缘有同样的问题。

4.2。优化匹配状态检测序列

因为PGC_IncGPM处理边缘插入(分别地。,deletions) one by one, the efficiency of it gradually decreases as the number of changed edges increases. To overcome the bottleneck of PGC_IncGPM, multiple edge insertions (resp., deletions) should be considered together. In this paper, the optimization method for nodes’ matching state detection sequence is proposed. The optimization can be applied to both insertions and deletions on 。

以SubEdges为例,优化方法如下。

首先,分析所有边删除确定哪些节点的候选人匹配集可能会改变。如果萤石(u)可能会改变被添加到集。

其次,由逆拓扑排序的序列 。可能会有一些强大的连接组件 。在这种情况下,我们首先找到强有力的连接组件P然后,收敛每个强连通分支成节点有向无环图并找到的逆拓扑序列 ;最后,我们强大的连接组件融合节点替换原始节点集。因此,近似逆拓扑序列是获得。

最后,为每个在 ,萤石(依次处理)。取决于是否有删除边 ,使用两个不同的过滤方法:(1)至少有一条边被删除,那么每个节点在吗萤石()很可能保持孩子的关系现在。所以是否保持孩子的关系应该检查;(2)如果没有一条边被删除,那么唯一的节点的一部分吗萤石()都需要检查。也就是说,一个节点萤石()将检查只有改变它至少有一个孩子c- node,年代- node。

一些候选人匹配集的访问时间可以减少通过以上优化。

4.3。iDeltaP_IncGPM算法

根据提出的优化方法4.2,提出了iDeltaP_IncGPM。它使用优化方法对多个边插入边和多个删除。边缘的优化算法删除算法所示1。在算法1,包含所有条边的节点删除。对于一个节点在 ,如果的变化可能会导致某些节点在吗萤石()成为年代节点,然后 。 由逆拓扑排序的序列((1)-(5)行)。如果有一条边删除, ,那么所有的节点萤石()需要检查他们是否保持孩子的关系u((7)-(12)行)。如果 和不在 ,只有一部分的节点萤石()检查。也就是说,如果有一个孩子和就是从萤石()sim卡()( ),那么是否仍然是一个年代- node将检查((14)-(20)行)。

这里我们用一个例子来说明PGC_IncGPM和iDeltaP_IncGPM的实现过程。图模式如图4,假设(E、H), (G,我)和删除(C、G)P。

PGC_IncGPM的过程如下。(1)删除处理(E、H),和每一个在萤石(E)检查它是否让孩子的关系在 。如果让孩子的关系 ,那么它的父母从成立萤石(B)(分别地。萤石(C))检查。如果这些节点B (resp保持孩子的关系。C),然后他们删除sim卡(B)(分别地。sim卡(C))。之后,他们的父母从成立萤石(一)检查;(2)删除处理(G, I),和节点萤石(G),萤石(C),萤石(D)萤石(一)依次检查;(3)删除处理(C、G),和节点萤石(C)和萤石(一)检查。从上面的步骤,可以看出萤石(C)和萤石(一)参观了三次,萤石(G),萤石(D),萤石(E)萤石(B)是访问一次。

iDeltaP_IncGPM过程如下:由于删除(E、H), (G, I),和(C、G),一些节点萤石(E),萤石(G),萤石(C),萤石(B),萤石(D)萤石(一)可能会年代节点。的节点萤石()检查订单G, E、D、C、B}。的节点萤石首先检查(G),节点萤石(一)检查。E、G和C都out-edges删除,所以所有节点在检查他们的候选人匹配集。节点的萤石(B),萤石(D)萤石(一个),如果他们有一个孩子从c- node,年代- node,他们将检查。因此,萤石(C),萤石(D),萤石(一),萤石(G),萤石(E)萤石(B)是只访问一次。换句话说,优化方案降低了访问的时候萤石()。

为多个边缘模式插入图,采用类似的优化方法。节点⁺包含所有的源节点插入的边缘。如果在某些节点sim卡()可能成为c节点由于边缘插入是在filtorder⁺。filtorder⁺由反向拓扑有序序列模式的图。节点⁺和filtorder⁺用于减少的访问时间吗sim卡(),垫()。

5。实验和结果分析

以下实验评估我们的算法。运行时作为一个关键的评估算法。此外,为了显示增量算法在视觉上的有效性,提出了改进的比率(IR),运行时被增量的比值匹配算法的运行时再计算算法。两个真实数据集(Epinions这样和Slashdot (30.)用于实验。75879年前是一个信任的网络节点和508837边缘。后者是一个社交网络,82168个节点和948464个边缘。在以往的研究中,我们尝试用正常大小和大尺寸图形模式,分别和结果表明,增量匹配算法的复杂性和有效性不受大小的图形模式。因此,在本文中,默认情况下,节点的数量P(||)是9,原始的边缘P(||)8(分别地。,16)为在年代ertions (resp., deletions) and 9 for both insertions and deletions.

为了评估算法的改进,iDeltaP_IncGPM PGC_IncGPM,验算都Epinions这样和Slashdot上执行在不同的设置。每个实验进行了5次图有不同的模式,这里的平均结果报告。实验结果如图所示5。直方图表示算法的运行时和折线图代表了改进的比率iDeltaP_IncGPM PGC_IncGPM验算。

图5(一个)(职责。图5 (b))显示了三种算法的运行时超过Epionions(分别地。图,Slashdot)插入模式。的设在代表的插入P“+ 2”表示,两条边插入P+ 4”代表四个边缘插入P,等等。图告诉我们如下:(一)插入不超过10时,运行时PGC_IncGPM和iDeltaP_IncGPM明显比验算,短和iDeltaP_IncGPM最短的运行时;(b)当插入12(新插入的边边的占60% ),运行时PGC_IncGPM长于验算,而iDeltaP_IncGPM仍然得到最短的运行时;(c)的改善比iDeltaP_IncGPM和PGC_IncGPM减少边缘插入的增加,但iDeltaP_IncGPM更小的减少。插入的边缘,越多越好iDeltaP_IncGPM PGC_IncGPM。12的边缘插入的时候出现 ,的红外iDeltaP_IncGPM平均是40%,平均PGC_IncGPM的红外是33%。因此,iDeltaP_IncGPM比PGC_IncGPM要好。原因是PGC_IncGPM进程插入的边缘。因此,随着插入的增加,它的运行时几乎线性增长。然而,iDeltaP_IncGPM集成了所有插入的边缘,分析匹配集的影响,并以适当的顺序处理它们。这将防止某些匹配集反复处理,这将缩短运行时间。

图5 (c)(职责。图5 (d))显示了三种算法的运行时超过Epionions(分别地。图,Slashdot)删除模式。的设在代表的删除 ,“−2”表示,两条边被删除 ,“−4”表示四个边被删除 ,等等。可以看出,(a)当删除更改从2到12日,所有三个算法的运行时增加,iDeltaP_IncGPM总是最短的运行时;(b)作为删除增加,红外PGC_IncGPM减少和IR iDeltaP_IncGPM缓慢增加。12删除,红外PGC_IncGPM平均减少7%,而iDeltaP_IncGPM红外平均增加到78%。原因在于,当删除增加时,再计算运行时的增加显著,而运行时iDeltaP_IncGPM增加一点。鸡眼iDeltaP_IncGPM比PGC_IncGPM因为它过程删除边缘和其运行时并不随着删除边数量的增加呈线性增加。

图5 (e)(职责。图5 (f))显示了三种算法的运行时超过Epionions(分别地。,Slashdot) for both insertions and deletions on pattern graph. The设在代表的插入和删除P,“+ 2−2”意味着两条边插入和其他两条边被移除 ,等等。如图,iDeltaP_IncGPM总是比其他人更短的运行时。

总之,iDeltaP_IncGPM有效改善PGC_IncGPM通过优化策略的效率。同样的 ,iDeltaP_IncGPM比较短,运行时和增加,运行时增加更少;红外的减少也更温和。因此,iDeltaP_IncGPM可以应用到更大的变化模式的图,和它有广泛的应用。

6。结论

在本文中,我们分析PGC_IncGPM找到它的效率瓶颈,提出一个更高效的增量iDeltaP_IncGPM匹配算法。多个插入(分别地。,deletions) are considered together and the optimization method for nodes’ matching state detection sequence is used. Experimental results on real data sets show that iDeltaP_IncGPM has higher efficiency and wider application range than PGC_IncGPM.

接下来,我们将研究分布式增量图匹配算法。现实生活中的图形快速增长的规模和hyper-massive数据图不能集中存储在一个数据中心,需要分布在多个数据中心。是非常值得研究,如何使高效的增量匹配在分布式大型图表。

符号

:	模式图像/数据图
:	节点
:	节点
:	的变化
:	的变化
:	新格局图
:	节点同样的标签但不要让孩子的关系
:	节点只有保持孩子的关系
:	节点让孩子和父母的关系
指数:	集包括 , 和
:	在这样
:	最大的比赛为
:	结果图,子图表示 。

的利益冲突

作者宣称没有利益冲突有关的出版。