一种有向图中目标子图查方法及相关设备

1.本发明涉及图数据处理技术领域，特别涉及一种有向图中目标子图查方法及相关设备。

背景技术：

2.在实际应用中，很多数据都是稀疏的，例如社数据等，为了提升数据分析效率，需要在稀疏的数据中提取出尽可能多的相互关联性强的部分数据来进行分析。但是，在现有技术中还没有高效地在稀疏的数据中提取尽可能多的相互关联性强的部分数据的方法。
3.因此，现有技术还有待改进和提高。

技术实现要素：

4.针对现有技术的上述缺陷，本发明提供一种有向图中目标子图查方法，旨在解决现有技术中没有高效地在稀疏的数据中提取尽可能多的相互关联性强的部分数据的方法的问题。
5.为了解决上述技术问题，本发明所采用的技术方案如下：本发明的第一方面，提供一种有向图中目标子图查方法，所述方法包括：获取原始有向图，获取所述原始有向图中的所有顶点的出度和入度，根据所有顶点的出度和入度获取初始顶点集合，其中，所述初始顶点集合中的每个顶点的出度都不小于所述原始有向图对应的出度目标差值，所述初始顶点集合中的每个顶点的入度都不小于所述原始有向图对应的入度目标差值；根据所述初始顶点集合中的顶点个数在所述原始有向图中删除至少一个顶点或有向边，得到处理有向图；在所述处理有向图中获取目标子图，所述目标子图为所述原始有向图中满足目标条件的子图中包含的顶点数量最大的子图，所述目标条件为子图中的每个顶点的出度都不小于该子图对应的出度目标差值且每个顶点的入度都不小于该子图对应的入度目标差值；其中，图对应的出度目标差值为该图的顶点数量与预设出度阈值的差值，图对应的入度目标差值为该图的顶点数量与预设入度阈值的差值。
6.本发明的第二方面，提供一种有向图中目标子图查装置，包括：初始解生成模块，所述初始解生成模块用于获取原始有向图，获取所述原始有向图中的所有顶点的出度和入度，根据所有顶点的出度和入度获取初始顶点集合，其中，所述初始顶点集合中的每个顶点的出度都不小于所述原始有向图对应的出度目标差值，所述初始顶点集合中的每个顶点的入度都不小于所述原始有向图对应的入度目标差值；图预处理模块，所述图预处理模块用于根据所述初始顶点集合中的顶点个数在所述原始有向图中删除至少一个顶点或有向边，得到处理有向图；子图获取模块，所述子图获取模块用于在所述处理有向图中获取目标子图，所述目标子图为所述原始有向图中满足目标条件的子图中包含的顶点数量最大的子图，所述目
标条件为子图中的每个顶点的出度都不小于该子图对应的出度目标差值且每个顶点的入度都不小于该子图对应的入度目标差值；其中，图对应的出度目标差值为该图的顶点数量与预设出度阈值的差值，图对应的入度目标差值为该图的顶点数量与预设入度阈值的差值。
7.本发明的第三方面，提供一种终端，所述终端包括处理器、与处理器通信连接的计算机可读存储介质，所述计算机可读存储介质适于存储多条指令，所述处理器适于调用所述计算机可读存储介质中的指令，以执行实现上述任一项所述的有向图中目标子图查方法的步骤。
8.本发明的第四方面，提供一种计算机可读存储介质，所述计算机可读存储介质存储有一个或者多个程序，所述一个或者多个程序可被一个或者多个处理器执行，以实现上述任一项所述的有向图中目标子图查方法的步骤。
9.与现有技术相比，本发明提供了一种有向图中目标子图查方法及相关设备，本发明提供的有向图中目标子图查方法中，将从稀疏数据中提取尽可能多的相互关联性强的部分数据的问题转化为从有向图中查满足每个顶点的出度都不小于子图对应的出度目标差值且每个顶点的入度都不小于子图对应的入度目标差值的最大子图问题，并采用了预处理的手法，提升了子图查的效率，实现了高效地从稀疏数据中查尽可能多的相互关联性强的部分数据的效果。
附图说明
10.图1为本发明提供的有向图中目标子图查方法的实施例的流程图；图2为有向图的示意图；图3为本发明提供的有向图中目标子图查方法的实施例中整体算法伪代码示意图；图4为本发明提供的有向图中目标子图查方法的实施例中在处理有向图中查目标子图的算法伪代码示意图；图5为本发明提供的有向图中目标子图查装置的实施例的结构原理图；图6为本发明提供的终端的实施例的原理示意图。
具体实施方式
11.为使本发明的目的、技术方案及效果更加清楚、明确，以下参照附图并举实施例对本发明进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。
12.本发明提供的有向图中目标子图查方法，可以应用于具有计算能力的终端中，终端可以执行本发明提供的有向图中目标子图查方法获取目标子图，终端可以但不限于是各种计算机、移动终端、智能家电、可穿戴式设备等。
13.实施例一如图1所示，所述有向图中目标子图查方法的一个实施例中，包括步骤：s100、获取原始有向图，获取所述原始有向图中的所有顶点的出度和入度，根据所有顶点的出度和入度获取初始顶点集合，其中，所述初始顶点集合中的每个顶点的出度都
不小于所述原始有向图对应的出度目标差值，所述初始顶点集合中的每个顶点的入度都不小于所述原始有向图对应的入度目标差值。
14.所述原始有向图可以根据待分析的原始稀疏数据生成的有向图，所述原始有向图中的每个顶点可以是所述原始稀疏数据中的某一个数据点，所述原始有向图中的每个有向边可以是所述原始稀疏数据中两个数据点之间的关系，例如对于社数据对应的有向图来说，有向图中的顶点可以是社中的每个用户，有向图中的有向边可以是社的用户之间的社交媒体关注关系等，再例如，对于生物蛋白质分子数据对应的有向图来说，有向图中的顶点可以是原子，有向图中的有向边可以是分子之间的化学键等。
15.一个简单的有向图可以如图2所示，具体地，一个有向图g可以用来表示，其中表示有向图g中的顶点集合，表示有向图g中的边集合。
16.在本实施例中，将从原始稀疏数据中提取尽可能多地相互关联性强的问题转化为从原始有向图中查目标子图的问题，所述目标子图满足目标条件，所述目标条件为：子图中的每个顶点的出度都不小于该子图对应的出度目标差值且每个顶点的入度都不小于该子图对应的入度目标差值。
17.图对应的出度目标差值为该图的顶点数量与预设出度阈值的差值，图对应的入度目标差值为该图的顶点数量与预设入度阈值的差值。子图中的每个顶点的出度和入度都大于预设的差值，说明子图的顶点之间的关联性强。为了方便表示，将所述目标子图称为最大-plex，其中，为所述预设出度阈值，为所述预设入度阈值，也就是说，在一个顶点数为n的有向图中，若图中任意一个顶点都满足出度大于等于，入度大于等于，则称该有向图为一个有向-plex。如图2中的原始有向图，导出子图{0,1,2}是一个(1，1)-plex。
18.在本实施例提供的方法中，如图3所示，为了查到所述原始有向图中的目标子图，首先求取下界解，利用下界解进行图数据预处理，再进行精确查。
19.具体地，所述根据所述顶点的出度和入度获取初始顶点集合的过程可以为：将所述原始有向图中的所有顶点按出度由小到大排列得到第一集合，将所述原始有向图中的所有顶点按入度由小到大排列得第二集合；依次删除所述第一集合中的顶点直至所述第一集合中出度最小的顶点不小于所述原始有向图对应的出度目标差值，依次删除所述第二集合中的顶点直至所述第二集合中入度最小的顶点不小于所述原始有向图对应的入度目标差值；对所述第一集合和所述第二集合取并集，得到所述初始顶点集合。
20.得到所述初始顶点集合后，利用所述初始顶点集合对所述原始有向图进行预处理，即对所述原始有向图进行缩减，提升后续精确查的效率。即本实施例提供的方法，还包括步骤：s200、根据所述初始顶点集合中的顶点个数在所述原始有向图中删除至少一个顶点或有向边，得到处理有向图。
21.所述根据所述初始顶点集合中的顶点个数在所述原始有向图中删除至少一个顶点或有向边，包括：
获取目标值，所述目标值为第一值与所述初始顶点集合中的顶点个数值中的最大值，其中，所述第一值为预设出度阈值和预设入度阈值中的最小值；基于所述目标值，采用第一方式在所述原始有向图中删除至少一个顶点；和/或采用第二方式在所述原始有向图中删除至少一个有向边。
22.在本实施例提供的方法，可以采用两种方式对所述原始有向图进行预处理以实现对所述原始有向图的缩减，这两种方式可以分别单独实施，也可以一同实施。
23.所述采用第一方式在所述原始有向图中删除至少一个顶点，包括：对于所述原始有向图中的一个目标顶点，若所述目标顶点的出度小于所述目标值和所述预设出度阈值之间的差值或者，所述目标顶点的入度小于所述目标值和所述预设入度阈值之间的差值，则在所述原始有向图中删除所述目标顶点。
24.所述第一方式为弱缩减方式，设，弱缩减方法依据的理论为：给定一个有向图和一个顶点，如果的出度小于或者入度小于，那么顶点不可能出现在一个大小大于的有向-plex中，因此，可以将顶点从所述原始有向图中删除而不影响最终的目标子图查结果。
25.所述采用第二方式在所述原始有向图中删除至少一个有向边，包括：对于所述原始有向图中的每个顶点，分别获取对应的目标出度集合和目标入度集合，其中，在所述原始有向图中存在目标顶点到所述目标顶点对应的所述目标出度集合中的每个顶点的有向边，在所述原始有向图中存在所述目标顶点对应的所述目标入度集合中的每个顶点到所述目标顶点的有向边；获取所述原始有向图中的第一目标顶点和第二目标顶点之间的出度交集和入度交集，其中，所述出度交集为所述第一目标顶点和所述第二目标顶点分别对应的所述目标出度集合的交集，所述入度交集为所述第一目标顶点和所述第二目标顶点分别对应的所述目标入度集合的交集；根据所述出度交集和所述入度交集中顶点的数量在所述原始有向图中删除至少一个有向边。
26.所述第一目标顶点和所述第二目标顶点是所述原始有向图中的任意两个不同的顶点，所述根据所述出度交集和所述入度交集中顶点的数量在所述原始有向图中删除至少一个有向边，包括：若所述原始有向图中存在所述第一目标顶点到所述第二目标顶点的有向边和所述第二目标顶点到所述第一目标顶点的有向边，并且，所述出度交集中顶点的数量不大于第一差值或所述入度交集中顶点的数量不大于第二差值，则在所述原始有向图中删除所述第一目标顶点和所述第二目标顶点之间的连接边；其中，所述第一差值为所述目标值与所述预设出度阈值的两倍的差值，所述第二差值为所述目标值与所述预设入度阈值预设入度阈值的两倍的差值；若所述原始有向图的所述第一目标顶点和所述第二目标顶点之间的连接边为单向连接边，并且，所述出度交集中顶点的数量不大于第三差值或所述入度交集中顶点的数
量不大于第四差值，则在所述原始有向图中删除所述第一目标顶点和所述第二目标顶点之间的连接边；其中，所述第三差值为所述第一差值加1，所述第四差值为所述第二差值加1。
27.所述第二方式为强缩减方式，设，强缩减方法依据的理论为：令：给定一个有向图和两个顶点，如果：1.有向边有向边且或者，那么不可能同时出现在一个大小大于的有向-plex中。
28.2.有向边有向边或者，且或者，那么不可能同时出现在一个大小大于的有向-plex中。
29.在经过所述步骤s200后，所述原始有向图中部分顶点和边被删除，得到所述处理有向图，在所述处理有向图中查所述目标子图，即还包括步骤：s300、在所述处理有向图中获取目标子图，所述目标子图为所述原始有向图中满足目标条件的子图中包含的顶点数量最大的子图，所述目标条件为子图中的每个顶点的出度都不小于所述原始有向图对应的出度目标差值且每个顶点的入度都不小于所述原始有向图对应的入度目标差值。
30.在一种可能的实现方式中，可以采用经典整数线性规划法求解所述目标子图，其中构建如下约束函数：
式中，，当时，表示顶点出现在解中，否则表示不出现，,当时，表示，否则表示，是一个足够大的整数，使用时可以取。
31.在本实施例提供的方法中，如图4所示，基于分支限界法的思想在所述处理有向图中查所述目标子图。具体包括：将所述处理有向图中所有的顶点加入至候选集中，并设置扩张解集为空集；在每个分支图中选取一个顶点作为根节点，根据所述根节点所在的集合生成至少一个分支并更新所述扩张解集，每个分支中包括一个分支图；当目标分支图中的所有节点的出度都不小于所述原始有向图对应的出度目标差值且所有节点的入度都不小于所述原始有向图对应的入度目标差值时，不再在所述目标分支图中选取顶点作为根节点，否则继续在所述目标分支图中选取一个顶点作为根节点；在所有的所述目标分支图中选取顶点个数最大的图作为所述目标子图；其中，初始分支图为所述处理有向图。
32.所述根据所述根节点所在的集合生成至少一个分支并更新所述扩张解集，包括：当所述根节点在所述扩张解集时，获取所述根节点对应的第一出度集合、第二出度集合和第一入度集合、第二入度集合，其中，所述第一出度集合中的顶点都属于所述扩张解集，且所述扩张解集对应的子图中不存在所述根节点到所述根节点对应的所述第二出度集合中每个顶点的有向边，所述第二出度集合中的顶点都属于所述候选集且所述候选集对应的子图中不存在所述根节点到所述根节点对应的所述第二出度集合中的每个顶点的有向边，所述第一入度集合中的顶点都属于所述扩张解集，且所述扩张解集对应的子图中不存在所述根节点对应的所述第二入度集合中每个顶点到所述根节点的有向边，所述第二入度集合中的顶点都属于所述候选集，且所述候选集对应的子图中不存在所述根节点对应的所述第二入度集合中的每个顶点到所述根节点的有向边；若所述根节点的出度小于所述原始有向图对应的出度目标差值，则获取所述根节点对应的第一参数，所述第一参数为预设出度阈值与所述第一出度集合中顶点的个数的差值；
根据所述第一参数和所述第二出度集合生成个出度分支并将所述第二出度集合中的前个顶点加入至所述扩张解集中，其中，为所述第一参数，前个所述出度分支的分支图由从所述根节点所在的分支图中分别删除所述第二出度集合中的前个顶点而产生，第个所述出度分支的分支图由从所述根节点所在的分支图中删除所述第二出度集合中前个顶点之外的顶点而产生；若所述根节点的入度小于所述原始有向图对应的入度目标差值，则获取所述根节点对应的第二参数，所述第二参数为预设入度阈值与所述第一入度集合中顶点的个数的差值；根据所述第一参数和所述第二入度集合生成个入度分支并将所述第二入度集合中的前个顶点加入至所述扩张解集中，其中，为所述第二参数，前个所述入度分支的分支图由从所述根节点所在的分支图中分别删除所述第二入度集合中的前个顶点而产生，第个所述入度分支的分支图由从所述根节点所在的分支图中删除所述第二入度集合中前个顶点之外的顶点而产生；当所述根节点在所述候选集时，生成两个第三分支并将所述根节点加入至所述扩张解集中，其中一个所述第三分支为从所述根节点所在的分支图中删除所述根节点，另一个所述第三分支为所述根节点所在的分支图。
33.具体地，若图中一个顶点满足出度大于等于，则称该顶点为-satisfied的，否则称为-unsatisfied。同理，若一个顶点入度大于等于，则称该顶点为-satisfied的，否则称为-unsatisfied的。在每个分支递归中，算法会寻当前实例出度最小的顶点和入度最小的顶点，假设至少有个顶点是假设至少有个顶点是unsatisfied的（否则算法因为到了-plex已经不再在这个分支上产生新的分支）。通过判断该顶点在扩张解集合还是在候选集中，有两种分支方法。
34.假设下面对在两个集合中的分支方法进行介绍，值的说明的是，下文中的g指的是需要产生下一代分支图的分支图，即通过下文中的分支规则产生分支图g的分支图。
35.分支规则一：在中分支假设顶点是集合中的-unsatisfied顶点（-unsatisfied同理），令
由于顶点是-unsatisfied的，所以。再令：，其中的顺序任意。
36.分支规则一将会产生个分支：分支1：从图中删去顶点分支2：令，并从图中删去顶点分支3：令，并从图中删去顶点
…
分支：令，并从图中删去顶点分支：令，并从图中删去顶点。
37.分支规则二：在中分支假设顶点是集合中的-unsatisfied顶点（-unsatisfied同理）,则分支规则二将产生2个分支：分支1：从图中删去顶点分支2：令。
38.对于每个新生成的分支图，若该分支图中已经无法再加入任何节点到所述扩张解中，那么不再对该分支图进行分支，称该分支图为目标分支图。每次产生新的目标分支图时，将其与已存储的目标分支图进行比较，选取其中包含节点个数较大的一个保留，另一个删除。
39.在分支过程中，若分支图中的节点数量小于当前已存在的所述目标分支图，即使该分支图中仍存在unsatisfied顶点，也可以不再对其进行分支。
40.获取最终的所述目标分支图作为所述目标子图，得到所述目标子图后，可以根据所述目标子图在所述原始稀疏数据中提取相应的数据作为待分析数据进行分析。
41.综上所述，本实施例提供一种有向图中目标子图查方法，将从稀疏数据中提取尽可能多的相互关联性强的部分数据的问题转化为从有向图中查满足每个顶点的出度都不小于所述原始有向图对应的出度目标差值且每个顶点的入度都不小于所述原始有向图对应的入度目标差值的最大子图问题，并采用了预处理的手法，提升了子图查的效率，实现了高效地从稀疏数据中查尽可能多的相互关联性强的部分数据的效果。
42.应该理解的是，虽然本发明说明书附图中给出的的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，流程图中的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段
并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。
43.本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取计算机可读存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本发明所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器（rom）、可编程rom（prom）、电可编程rom（eprom）、电可擦除可编程rom（eeprom）或闪存。易失性存储器可包括随机存取存储器（ram）或者外部高速缓冲存储器。作为说明而非局限，ram以多种形式可得，诸如静态ram（sram）、动态ram（dram）、同步dram（sdram）、双数据率sdram（ddrsdram）、增强型sdram（esdram）、同步链路（synchlink） dram（sldram）、存储器总线（rambus）直接ram（rdram）、直接存储器总线动态ram（drdram）、以及存储器总线动态ram（rdram）等。
44.实施例二基于上述实施例，本发明还相应提供了一种有向图中目标子图查装置，如图5所示，所述有向图中目标子图查装置包括：初始解生成模块，所述初始解生成模块用于获取原始有向图，获取所述原始有向图中的所有顶点的出度和入度，根据所有顶点的出度和入度获取初始顶点集合，其中，所述初始顶点集合中的每个顶点的出度都不小于所述原始有向图对应的出度目标差值，所述初始顶点集合中的每个顶点的入度都不小于所述原始有向图对应的入度目标差值，具体如实施例一中所述；图预处理模块，所述图预处理模块用于根据所述初始顶点集合中的顶点个数在所述原始有向图中删除至少一个顶点或有向边，得到处理有向图，具体如实施例一中所述；子图获取模块，所述子图获取模块用于所述处理有向图中获取目标子图，所述目标子图为所述原始有向图中满足目标条件的子图中包含的顶点数量最大的子图，所述目标条件为子图中的每个顶点的出度都不小于所述原始有向图对应的出度目标差值且每个顶点的入度都不小于所述原始有向图对应的出度目标差值，具体如实施例一中所述。
45.实施例三基于上述实施例，本发明还相应提供了一种终端，如图6所示，所述终端包括处理器10以及存储器20。图6仅示出了终端的部分组件，但是应理解的是，并不要求实施所有示出的组件，可以替代的实施更多或者更少的组件。
46.所述存储器20在一些实施例中可以是所述终端的内部存储单元，例如终端的硬盘或内存。所述存储器20在另一些实施例中也可以是所述终端的外部存储设备，例如所述终端上配备的插接式硬盘，智能存储卡（smart media card, smc），安全数字（secure digital, sd）卡，闪存卡（flash card）等。进一步地，所述存储器20还可以既包括所述终端的内部存储单元也包括外部存储设备。所述存储器20用于存储安装于所述终端的应用软件及各类数据。所述存储器20还可以用于暂时地存储已经输出或者将要输出的数据。在一实施例中，存储器20上存储有有向图中目标子图查程序30，该有向图中目标子图查程序
30可被处理器10所执行，从而实现本技术中有向图中目标子图查方法。
47.所述处理器10在一些实施例中可以是一中央处理器（central processing unit, cpu），微处理器或其他芯片，用于运行所述存储器20中存储的程序代码或处理数据，例如执行所述有向图中目标子图查方法等。
48.在一实施例中，当处理器10执行所述存储器20中有向图中目标子图查程序30时实现以下步骤：获取原始有向图，获取所述原始有向图中的所有顶点的出度和入度，根据所有顶点的出度和入度获取初始顶点集合，其中，所述初始顶点集合中的每个顶点的出度都不小于所述原始有向图对应的出度目标差值，所述初始顶点集合中的每个顶点的入度都不小于所述原始有向图对应的入度目标差值；根据所述初始顶点集合中的顶点个数在所述原始有向图中删除至少一个顶点或有向边，得到处理有向图；在所述处理有向图中获取目标子图，所述目标子图为所述原始有向图中满足目标条件的子图中包含的顶点数量最大的子图，所述目标条件为子图中的每个顶点的出度都不小于所述原始有向图对应的出度目标差值且每个顶点的入度都不小于所述原始有向图对应的入度目标差值。
49.所述根据所述初始顶点集合中的顶点个数在所述原始有向图中删除至少一个顶点或有向边，包括：获取目标值，所述目标值为第一值与所述初始顶点集合中的顶点个数值中的最小值，其中，所述第一值为预设出度阈值和预设入度阈值中的最小值，所述预设出度阈值为所述原始有向图中所有顶点的数量与所述原始有向图对应的出度目标差值之间的差值，所述预设入度阈值为所述原始有向图中所有顶点的数量与所述原始有向图对应的入度目标差值之间的差值；基于所述目标值，采用第一方式在所述原始有向图中删除至少一个顶点；和/或采用第二方式在所述原始有向图中删除至少一个有向边。
50.所述采用第一方式在所述原始有向图中删除至少一个顶点，包括：对于所述原始有向图中的一个目标顶点，若所述目标顶点的出度小于所述目标值和所述预设出度阈值之间的差值或者，所述目标顶点的入度小于所述目标值和所述预设入度阈值之间的差值，则在所述原始有向图中删除所述目标顶点。
51.所述采用第二方式在所述原始有向图中删除至少一个有向边，包括：对于所述原始有向图中的每个顶点，分别获取对应的目标出度集合和目标入度集合，其中，在所述原始有向图中存在目标顶点到所述目标顶点对应的所述目标出度集合中的每个顶点的有向边，在所述原始有向图中存在所述目标顶点对应的所述目标入度集合中的每个顶点到所述目标顶点的有向边；获取所述原始有向图中的第一目标顶点和第二目标顶点之间的出度交集和入度交集，其中，所述出度交集为所述第一目标顶点和所述第二目标顶点分别对应的所述目标出度集合的交集，所述入度交集为所述第一目标顶点和所述第二目标顶点分别对应的所述目标入度集合的交集；根据所述出度交集和所述入度交集中顶点的数量在所述原始有向图中删除至少
一个有向边。
52.所述根据所述出度交集和所述入度交集中顶点的数量在所述原始有向图中删除至少一个有向边，包括：若所述原始有向图中存在所述第一目标顶点到所述第二目标顶点的有向边和所述第二目标顶点到所述第一目标顶点的有向边，并且，所述出度交集中顶点的数量不大于第一差值或所述入度交集中顶点的数量不大于第二差值，则在所述原始有向图中删除所述第一目标顶点和所述第二目标顶点之间的连接边；其中，所述第一差值为所述目标值与所述预设出度阈值的两倍的差值，所述第二差值为所述目标值与所述预设入度阈值的两倍的差值；若所述原始有向图的所述第一目标顶点和所述第二目标顶点之间的连接边为单向连接边，并且，所述出度交集中顶点的数量不大于第三差值或所述入度交集中顶点的数量不大于第四差值，则在所述原始有向图中删除所述第一目标顶点和所述第二目标顶点之间的连接边；其中，所述第三差值为所述第一差值加1，所述第四差值为所述第二差值加1。
53.所述在所述处理有向图中获取目标子图，包括：将所述处理有向图中所有的顶点加入至候选集中，并设置扩张解集为空集；在每个分支图中选取一个顶点作为根节点，根据所述根节点所在的集合生成至少一个分支并更新所述扩张解集，每个分支中包括一个分支图；当目标分支图中的所有节点的出度都不小于所述目标分支图对应的出度目标差值且所有节点的入度都不小于所述目标分支图对应的入度目标差值时，不再在所述目标分支图中选取顶点作为根节点；在所有的所述目标分支图中选取顶点个数最大的图作为所述目标子图；其中，初始分支图为所述处理有向图。
54.所述根据所述根节点所在的集合生成至少一个分支并更新所述扩张解集，包括：当所述根节点在所述扩张解集时，获取所述根节点对应的第一出度集合、第二出度集合和第一入度集合、第二入度集合，其中，所述第一出度集合中的顶点都属于所述扩张解集，且所述扩张解集对应的子图中不存在所述根节点到所述根节点对应的所述第一出度集合中每个顶点的有向边，所述第二出度集合中的顶点都属于所述候选集且所述候选集对应的子图中不存在所述根节点到所述根节点对应的所述第二出度集合中的每个顶点的有向边，所述第一入度集合中的顶点都属于所述扩张解集，且所述扩张解集对应的子图中不存在所述根节点对应的所述第一入度集合中每个顶点到所述根节点的有向边，所述第二入度集合中的顶点都属于所述候选集，且所述候选集对应的子图中不存在所述根节点对应的所述第二入度集合中的每个顶点到所述根节点的有向边；若所述根节点的出度小于所述根节点所在的分支图对应的出度目标差值，则获取所述根节点对应的第一参数，所述第一参数为预设出度阈值与所述第一出度集合中顶点的个数的差值；根据所述第一参数和所述第二出度集合生成个出度分支并将所述第二出度集合中的前个顶点加入至所述扩张解集中，其中，为所述第一参数，前
个所述出度分支的分支图由从所述根节点所在的分支图中分别删除所述第二出度集合中的前个顶点而产生，第个所述出度分支的分支图由从所述根节点所在的分支图中删除所述第二出度集合中前个顶点之外的顶点而产生；若所述根节点的入度小于所述根节点所在的分支图对应的入度目标差值，则获取所述根节点对应的第二参数，所述第二参数为预设入度阈值与所述第一入度集合中顶点的个数的差值；根据所述第一参数和所述第二入度集合生成个入度分支并将所述第二入度集合中的前个顶点加入至所述扩张解集中，其中，为所述第二参数，前个所述入度分支的分支图由从所述根节点所在的分支图中分别删除所述第二入度集合中的前个顶点而产生，第个所述入度分支的分支图由从所述根节点所在的分支图中删除所述第二入度集合中前个顶点之外的顶点而产生；当所述根节点在所述候选集时，生成两个第三分支并将所述根节点加入至所述扩张解集中，其中一个所述第三分支为从所述根节点所在的分支图中删除所述根节点，另一个所述第三分支为所述根节点所在的分支图。
55.实施例四本发明还提供一种计算机可读存储介质，其中，存储有一个或者多个程序，所述一个或者多个程序可被一个或者多个处理器执行，以实现如上所述的有向图中目标子图查方法的步骤。
56.最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

技术特征：

1.一种有向图中目标子图查方法，其特征在于，所述方法包括：获取原始有向图，获取所述原始有向图中的所有顶点的出度和入度，根据所有顶点的出度和入度获取初始顶点集合，其中，所述初始顶点集合中的每个顶点的出度都不小于所述原始有向图对应的出度目标差值，所述初始顶点集合中的每个顶点的入度都不小于所述原始有向图对应的入度目标差值；根据所述初始顶点集合中的顶点个数在所述原始有向图中删除至少一个顶点或有向边，得到处理有向图；在所述处理有向图中获取目标子图，所述目标子图为所述原始有向图中满足目标条件的子图中包含的顶点数量最大的子图，所述目标条件为子图中的每个顶点的出度都不小于该子图对应的出度目标差值且每个顶点的入度都不小于该子图对应的入度目标差值；其中，图对应的出度目标差值为该图的顶点数量与预设出度阈值的差值，图对应的入度目标差值为该图的顶点数量与预设入度阈值的差值。2.根据权利要求1所述的有向图中目标子图查方法，其特征在于，所述根据所述初始顶点集合中的顶点个数在所述原始有向图中删除至少一个顶点或有向边，包括：获取目标值，所述目标值为第一值与所述初始顶点集合中的顶点个数值中的最大值，其中，所述第一值为所述预设出度阈值和所述预设入度阈值中的最小值；基于所述目标值，采用第一方式在所述原始有向图中删除至少一个顶点；和/或采用第二方式在所述原始有向图中删除至少一个有向边。3.根据权利要求2所述的有向图中目标子图查方法，其特征在于，所述采用第一方式在所述原始有向图中删除至少一个顶点，包括：对于所述原始有向图中的一个目标顶点，若所述目标顶点的出度小于所述目标值和所述预设出度阈值之间的差值，或者，所述目标顶点的入度小于所述目标值和所述预设入度阈值之间的差值，则在所述原始有向图中删除所述目标顶点。4.根据权利要求2所述的有向图中目标子图查方法，其特征在于，所述采用第二方式在所述原始有向图中删除至少一个有向边，包括：对于所述原始有向图中的每个顶点，分别获取对应的目标出度集合和目标入度集合，其中，在所述原始有向图中存在目标顶点到所述目标顶点对应的所述目标出度集合中的每个顶点的有向边，在所述原始有向图中存在所述目标顶点对应的所述目标入度集合中的每个顶点到所述目标顶点的有向边；获取所述原始有向图中的第一目标顶点和第二目标顶点之间的出度交集和入度交集，其中，所述出度交集为所述第一目标顶点和所述第二目标顶点分别对应的所述目标出度集合的交集，所述入度交集为所述第一目标顶点和所述第二目标顶点分别对应的所述目标入度集合的交集；根据所述出度交集和所述入度交集中顶点的数量在所述原始有向图中删除至少一个有向边。5.根据权利要求4所述的有向图中目标子图查方法，其特征在于，所述根据所述出度交集和所述入度交集中顶点的数量在所述原始有向图中删除至少一个有向边，包括：若所述原始有向图中存在所述第一目标顶点到所述第二目标顶点的有向边和所述第二目标顶点到所述第一目标顶点的有向边，并且，所述出度交集中顶点的数量不大于第一
差值或所述入度交集中顶点的数量不大于第二差值，则在所述原始有向图中删除所述第一目标顶点和所述第二目标顶点之间的连接边；其中，所述第一差值为所述目标值与所述预设出度阈值的两倍的差值，所述第二差值为所述目标值与所述预设入度阈值的两倍的差值；若所述原始有向图的所述第一目标顶点和所述第二目标顶点之间的连接边为单向连接边，并且，所述出度交集中顶点的数量不大于第三差值或所述入度交集中顶点的数量不大于第四差值，则在所述原始有向图中删除所述第一目标顶点和所述第二目标顶点之间的连接边；其中，所述第三差值为所述第一差值加1，所述第四差值为所述第二差值加1。6.根据权利要求1所述的有向图中目标子图查方法，其特征在于，所述在所述处理有向图中获取目标子图，包括：将所述处理有向图中所有的顶点加入至候选集中，并设置扩张解集为空集；在每个分支图中选取一个顶点作为根节点，根据所述根节点所在的集合生成至少一个分支并更新所述扩张解集，每个分支中包括一个分支图；当目标分支图中的所有节点的出度都不小于所述目标分支图对应的出度目标差值且所有节点的入度都不小于所述目标分支图对应的入度目标差值时，不再在所述目标分支图中选取顶点作为根节点；在所有的所述目标分支图中选取顶点个数最大的图作为所述目标子图；其中，初始分支图为所述处理有向图。7.根据权利要求6所述的有向图中目标子图查方法，其特征在于，所述根据所述根节点所在的集合生成至少一个分支并更新所述扩张解集，包括：当所述根节点在所述扩张解集时，获取所述根节点对应的第一出度集合、第二出度集合和第一入度集合、第二入度集合，其中，所述第一出度集合中的顶点都属于所述扩张解集，且所述扩张解集对应的子图中不存在所述根节点到所述根节点对应的所述第一出度集合中每个顶点的有向边，所述第二出度集合中的顶点都属于所述候选集且所述候选集对应的子图中不存在所述根节点到所述根节点对应的所述第二出度集合中的每个顶点的有向边，所述第一入度集合中的顶点都属于所述扩张解集，且所述扩张解集对应的子图中不存在所述根节点对应的所述第一入度集合中每个顶点到所述根节点的有向边，所述第二入度集合中的顶点都属于所述候选集，且所述候选集对应的子图中不存在所述根节点对应的所述第二入度集合中的每个顶点到所述根节点的有向边；若所述根节点的出度小于所述根节点所在的分支图对应的出度目标差值，则获取所述根节点对应的第一参数，所述第一参数为预设出度阈值与所述第一出度集合中顶点的个数的差值；根据所述第一参数和所述第二出度集合生成个出度分支并将所述第二出度集合中的前个顶点加入至所述扩张解集中，其中，为所述第一参数，前个所述出度分支的分支图由从所述根节点所在的分支图中分别删除所述第二出度集合中的前个顶点而产生，第个所述出度分支的分支图由从所述根节点所在的分支图中删除所述第二出度集合中前个顶点之外的顶点而产生；
若所述根节点的入度小于所述根节点所在的分支图对应的入度目标差值，则获取所述根节点对应的第二参数，所述第二参数为预设入度阈值与所述第一入度集合中顶点的个数的差值；根据所述第一参数和所述第二入度集合生成个入度分支并将所述第二入度集合中的前个顶点加入至所述扩张解集中，其中，为所述第二参数，前个所述入度分支的分支图由从所述根节点所在的分支图中分别删除所述第二入度集合中的前个顶点而产生，第个所述入度分支的分支图由从所述根节点所在的分支图中删除所述第二入度集合中前个顶点之外的顶点而产生；当所述根节点在所述候选集时，生成两个第三分支并将所述根节点加入至所述扩张解集中，其中一个所述第三分支为从所述根节点所在的分支图中删除所述根节点，另一个所述第三分支为所述根节点所在的分支图。8.一种有向图中目标子图查装置，其特征在于，包括：初始解生成模块，所述初始解生成模块用于获取原始有向图，获取所述原始有向图中的所有顶点的出度和入度，根据所有顶点的出度和入度获取初始顶点集合，其中，所述初始顶点集合中的每个顶点的出度都不小于所述原始有向图对应的出度目标差值，所述初始顶点集合中的每个顶点的入度都不小于所述原始有向图对应的入度目标差值；图预处理模块，所述图预处理模块用于根据所述初始顶点集合中的顶点个数在所述原始有向图中删除至少一个顶点或有向边，得到处理有向图；子图获取模块，所述子图获取模块用于在所述处理有向图中获取目标子图，所述目标子图为所述原始有向图中满足目标条件的子图中包含的顶点数量最大的子图，所述目标条件为子图中的每个顶点的出度都不小于该子图对应的出度目标差值且每个顶点的入度都不小于该子图对应的入度目标差值；其中，图对应的出度目标差值为该图的顶点数量与预设出度阈值的差值，图对应的入度目标差值为该图的顶点数量与预设入度阈值的差值。9.一种终端，其特征在于，所述终端包括：处理器、与处理器通信连接的计算机可读存储介质，所述计算机可读存储介质适于存储多条指令，所述处理器适于调用所述计算机可读存储介质中的指令，以执行实现上述权利要求1-7任一项所述的有向图中目标子图查方法的步骤。10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储有一个或者多个程序，所述一个或者多个程序可被一个或者多个处理器执行，以实现如权利要求1-7任一项所述的有向图中目标子图查方法的步骤。

技术总结

本发明公开了一种有向图中目标子图查方法及相关设备。方法包括：根据原始有向图中所有顶点的出度和入度获取初始顶点集合，初始顶点集合中的每个顶点的出度都不小于原始有向图对应的出度目标差值，初始顶点集合中的每个顶点的入度都不小于原始有向图对应的入度目标差值；根据初始顶点集合中的顶点个数在原始有向图中删除至少一个顶点或有向边，得到处理有向图；在处理有向图中获取目标子图，目标子图为原始有向图中满足目标条件的子图中包含的顶点数量最大的子图。本发明可以实现高效地从稀疏数据中查尽可能多的相互关联性强的部分数据。的部分数据。的部分数据。