尺寸约束的truss社群搜索方法及装置

1.本文件涉及图数据挖掘技术领域，尤其涉及一种尺寸约束的truss社群搜索方法及装置。


背景技术：

2.在图数据分析领域中，社区搜索一般在图网络的数据上搜索稠密子图，在团队组建、活动组织等方面有广泛应用，k-truss是一种网络中稠密子图的模型。
3.常见的社群搜索相关技术中，人们通常对自己参与的社群更感兴趣，再加上预算和容量的限制，往往会对社群进行尺寸约束。以上技术通常存在以下问题：搜索结果并非最优的稠密社群；稠密度的参数难以确定以及一些查询可能会返回空集结果。
4.综合上面该技术领域发展状况分析，现有的技术方案中尺寸约束社区搜索方案缺少能够准确搜索最优稠密社群的方法。


技术实现要素：

5.本发明的目的在于提供一种尺寸约束的truss社群搜索方法及装置，旨在解决现有技术中的上述问题。
6.根据本公开实施例的第一方面，提供一种尺寸约束的truss社群搜索方法，包括：
7.步骤1，利用启发式算法计算近似解h和最优解的min-trussness上界k*；
8.步骤2，用k'表示近似解h的min-trussness值，若k'等于k*，则确定近似解h为准确解，若k'不等于k*，执行步骤3；
9.步骤3，利用分支定界算法查找精确解。
10.根据本公开实施例的第二方面，提供一种尺寸约束的truss社群搜索装置，包括：
11.第一计算模块，用于利用启发式算法计算近似解h和最优解的min-trussness上界k*；
12.第二条件判断模块，用于以k'表示近似解h的min-trussness值，若k'等于k*，则确定近似解h为准确解，若k'不等于k*，调用第三计算模块；
13.第三计算模块，用于利用分支定界算法查找精确解。
14.根据本公开实施例的第三方面，提供一种电子设备，包括：存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，计算机程序被处理器执行时实现本公开第一方面提供的尺寸约束的truss社群搜索方法。
15.根据本公开实施例的第四方面，提供一种计算机可读存储介质，其上存储有信息传递的实现程序，程序被处理器执行时实现本公开第一方面提供的尺寸约束的truss社群搜索方法的步骤。
16.本公开的实施例提供的技术方案可以包括以下有益效果：使用有效的启发式算法初始化接近最优结果的高质量子图，针对当前部分解和候选集的顶点的预算—成本关系提出新的界定技术，大幅提高了搜索效率，有效地缩小搜索空间。
17.应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本公开。
附图说明
18.为了更清楚地说明本说明书一个或多个实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本说明书中记载的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。
19.图1是本发明实施例的尺寸约束的truss社群搜索方法的流程图；
20.图2是本发明实施例的启发式算法伪代码的示意图；
21.图3是本发明实施例的分支检查算法伪代码的示意图；
22.图4是本发明实施例的最优解查找算法伪代码的示意图；
23.图5是本发明实施例的尺寸约束的truss社群搜索装置的示意图；
24.图6是本发明实施例的整体流程伪代码的示意图；
25.图7是本发明实施例的电子设备的示意图。
具体实施方式
26.为了使本技术领域的人员更好地理解本说明书一个或多个实施例中的技术方案，下面将结合本说明书一个或多个实施例中的附图，对本说明书一个或多个实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本说明书的一部分实施例，而不是全部的实施例。基于本说明书一个或多个实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都应当属于本文件的保护范围。
27.方法实施例
28.根据本发明实施例，提供了一种尺寸约束的truss社群搜索方法，图1是本发明实施例的尺寸约束的truss社群搜索方法的示意图，如图1所示，根据本发明实施例的尺寸约束的truss社群搜索方法具体包括：
29.在步骤s110中，利用启发式算法计算近似解h和最优解的min-trussness上界k*，具体包括：
30.判断节点q的trussness值是否大于尺寸约束的上界h，若是，则设置k*即最优解的min-trussness上界为h，并用q初始化c作为种子子图；若不是，则设置k*为满足tq(k)的尺寸不小于l的最大k值，其中，tq(k)表示包含q的连通子图，其节点均由q开始遍历计算且其节点trussness值不小于k；
31.若tq(k)的尺寸不大于h时，即返回tq(k)作为解，否则以tq(k
*
+1)的节点集以及q初始化c作为种子子图；
32.以c的邻居中节点trussness值不小于且不在c中的节点初始化备选节点集r，递归地根据计分函数其中，k
max
是g中最大的节点trussness，依次将r中有希望的节点移动到c中，直到c的尺寸达到尺寸约束的上界h；
33.在所有由c生成的子图中满足尺寸不小于l的k-truss里，找到最大的k
′
，并返回该k
′-russ。
34.在步骤s120中，用k'表示近似解h的min-trussness值，若k'等于k*，则确定近似解h为准确解，若k'不等于k*，执行步骤s130。
35.在步骤s130中，利用分支定界算法查找精确解。分支定界算法具体包括：基于cost-budget的定界技术、备选集剪枝技术以及分支策略。
36.基于cost-budget的定界技术，首先用先进的truss maintenance算法更新c中每个节点的trussness值，然后初始化c中每个节点的cost和budget，将节点的访问标志设为否，如果节点的预算小于成本，则该分支没有希望，终止计算；否则分别用b
min
和c
max
记录所有节点中最小的预算值和最大的成本值，如果b
min
≥2
×cmax
，则确定当前分支有希望，否则访问c中的每个节点u，并且假定从r转移到c中一些节点后，u的节点trussness值达到k
′
+1，并且相应地更新受影响的节点的cost和budget，并在更新后重新判断cost和budget的大小关系，以决定是否终止该分支的计算。
37.基于备选集剪枝技术将r中没有希望的节点删除掉，并且在不违反尺寸约束的前提下将r中有希望的节点添加到c中，为了使解的min-trussness至少达到k'+1，如果把r中的一个节点转移到c中需要超过(h-|c|-1)个节点同时转移，则该节点是没有希望的，故将其从r中移除；对于c中的节点，若其在c并r中节点trussness值不小于k'+1的邻居数量为k'，则这些邻居都转移到c中。
38.根据分支策略，在分支访问顺序上，将加入c的节点依据计分函数得分进行排序，根据回溯算法，对于一个实例(c，r)，如果发现在当前分支中顶点u∈c不会存在与任何一个min-trussness值至少为k
′
+1的满足尺寸约束的连通子图中，则该分支是没有希望的，回溯到上面不包含该节点的分支上。
39.后续根据以上步骤得到的精确解查找一个包含查询节点q、节点数量至少为l至多为h，并且在所有连通子图中拥有最大min-trussness的连通子图。
40.需要说明的是，稠密子图模型k-truss常用于衡量子图结构的稠密程度，在一个k-truss子图中任意一条边都被至少k-2个三角形所包含。边的trussness是指包含该边的k-truss中最大的k值；而点的trussness是指以该点为端点的边中，最大的边的trussness值；图的min-trussness是指图中最小的节点的trussness值。
41.结合以下附图，对本发明实施例的上述技术方案进行举例说明。
42.图2是本发明实施例的启发式算法伪代码的示意图，如图2所示，利用启发式算法计算近似解h和最优解的min-trussness上界k*，包括以下步骤：
43.根据q节点trussness值与社群的尺寸约束的关系，确定最优解的min-trussness上界，若q节点trussness值违反尺寸约束的上界条件，则设置k
*
即最优解的min-trussness上界为h，并用q初始化c作为种子子图；若不违反，则设置k
*
为满足tq(k)的尺寸不小于l的最大k值，若tq(k)的尺寸恰好也不大于h时，即返回tq(k)作为解，否则以tq(k
*
+1)的节点集以及q初始化c作为种子子图。之后以初始化备选节点集r，递归地依据一个计分函数依次将r中有希望的节点移动到c中，直到c的尺寸达到尺寸约束的上界h。最后，在所有由c生成的子图中满足尺寸不小于l的k-truss里，找到最大的k
′
，并返回该k
′‑
truss，此结果即为满足尺寸约束条件、包含查询节点并且该节点密集参与的社群近似解。
44.图3是本发明实施例的分支检查算法伪代码的示意图，如图3所示，该算法在备选集不为空时进行，对于包含budget小于cost的节点的分支，应终止该分支的计算。
45.图4是本发明实施例的最优解查找算法伪代码的示意图，如图4所示，对于最优解的查找在近似解的基础上进行，若k
′
＝k
*
，则认为近似解已达到稠密程度的最优，终止算法，否则进行最优解的查找，若c已达到尺寸约束的上界或者备选集r为空，则更新k
′
、无希望点集φ和备选集r。
46.装置实施例
47.根据本发明实施例，提供了一种尺寸约束的truss社群搜索装置，图5是本发明实施例的尺寸约束的truss社群搜索装置的示意图，如图5所示，根据本发明实施例的本发明实施例的尺寸约束的truss社群搜索装置的示意图，具体包括：
48.第一计算模块50，用于利用启发式算法计算近似解h和最优解的min-trussness上界k*，具体包括：
49.判断节点q的trussness值是否大于尺寸约束的上界h，若是，则设置k*即最优解的min-trussness上界为h，并用q初始化c作为种子子图；若不是，则设置k*为满足tq(k)的尺寸不小于l的最大k值，其中，tq(k)表示包含q的连通子图，其节点均由q开始遍历计算且其节点trussness值不小于k；
50.若tq(k)的尺寸不大于h时，即返回tq(k)作为解，否则以tq(k
*
+1)的节点集以及q初始化c作为种子子图；
51.以c的邻居中节点trussness值不小于且不在c中的节点初始化备选节点集r，递归地根据计分函数其中，k
max
是g中最大的节点trussness，依次将r中有希望的节点移动到c中，直到c的尺寸达到尺寸约束的上界h；
52.在所有由c生成的子图中满足尺寸不小于l的k-truss里，找到最大的k
′
，并返回该k
′‑
truss。
53.第二条件判断模块52，用k
′
表示近似解h的min-trussness值，若k
′
等于k*，则确定近似解h为准确解，若k
′
不等于k*，调用第三计算模块54。
54.第三计算模块54，用于利用分支定界算法查找精确解。分支定界算法具体包括：基于cost-budget的定界技术、备选集剪枝技术以及分支策略。
55.基于cost-budget的定界技术，首先用先进的truss maintenance算法更新c中每个节点的trussness值，然后初始化c中每个节点的cost和budget，将节点的访问标志设为否，如果节点的预算小于成本，则该分支没有希望，终止计算；否则分别用b
min
和c
max
记录所有节点中最小的预算值和最大的成本值，如果b
min
≥2
×cmax
，则确定当前分支有希望，否则访问c中的每个节点u，并且假定从r转移到c中一些节点后，u的节点trussness值达到k
′
+1，并且相应地更新受影响的节点的cost和budget，并在更新后重新判断cost和budget的大小关系，以决定是否终止该分支的计算。
56.基于备选集剪枝技术将r中没有希望的节点删除掉，并且在不违反尺寸约束的前提下将r中有希望的节点添加到c中，为了使解的min-trussness至少达到k
′
+1，如果把r中的一个节点转移到c中需要超过(h-|c|-1)个节点同时转移，则该节点是没有希望的，故将
其从r中移除；对于c中的节点，若其在c并r中节点trussness值不小于k
′
+1的邻居数量为k
′
，则这些邻居都转移到c中。
57.根据分支策略，在分支访问顺序上，将加入c的节点依据计分函数得分进行排序，根据回溯算法，对于一个实例(c，r)，如果发现在当前分支中顶点u∈c不会存在与任何一个min-trussness值至少为k
′
+1的满足尺寸约束的连通子图中，则该分支是没有希望的，回溯到上面不包含该节点的分支上。
58.图6是本发明实施例的主算法伪代码示意图，如图6所示，该算法首先利用启发式算法计算近似解h和最优解的min-trussness上界k*；之后用k
′
表示近似解h的min-trussness值，若k
′
等于k*，则确定近似解h为准确解，若k
′
不等于k*，则利用分支定界算法查找精确解。
59.电子设备实施例
60.图7是本发明实施例的电子设备的示意图。电子设备600，可包括至少一个处理器610和存储器620。处理器610可以执行存储在存储器620中的指令。处理器610通过数据总线与存储器620通信连接。除存储器620外，处理器610还可通过数据总线与输入设备630、输出设备640、通信设备650通信连接。
61.处理器610可以是任何常规的处理器，诸如商业可获得的cpu。处理器还可以包括诸如图像处理器(graphic process unit，gpu)，现场可编程门阵列(field programmable gate array，fpga)、片上系统(system on chip，soc)、专用集成芯片(application specific integrated circuit，asic)或它们的组合。
62.存储器620可以由任何类型的易失性或非易失性存储设备或者它们的组合实现，如静态随机存取存储器(sram)，电可擦除可编程只读存储器(eeprom)，可擦除可编程只读存储器(eprom)，可编程只读存储器(prom)，只读存储器(rom)，磁存储器，快闪存储器，磁盘或光盘。
63.在本公开实施例中，存储器620中存储有可执行指令，处理器610可以从存储器620中读取可执行指令，并执行指令以实现上述示例性实施例中任一的尺寸约束的truss社群搜索方法的全部或部分步骤。
64.计算机可读存储介质实施例
65.除了上述方法和装置以外，本公开的示例性实施例还可以是计算机程序产品或存储有该计算机程序产品的计算机可读存储介质，该计算机产品中包括计算机程序指令，该计算机程序指令可被处理器执行，以实现上述示例性实施例中任一方法中描述的全部或部分步骤。
66.计算机程序产品可以以一种或多种程序设计语言的任意组合来编写用于执行本技术实施例操作的程序代码，程序设计语言包括面向对象的程序设计语言，诸如java、c++等，还包括常规的过程式程序设计语言，诸如“c”语言或类似的程序设计语言以及脚本语言(例如python)。程序代码可以完全地在用户计算设备上执行、部分地在用户设备上执行、作为一个独立的软件包执行、部分在用户计算设备上部分在远程计算设备上执行、或者完全在远程计算设备或服务器上执行。
67.计算机可读存储介质可以采用一个或多个可读介质的任意组合。可读介质可以是可读信号介质或者可读存储介质。可读存储介质例如可以包括但不限于电、磁、光、电磁、红
外线、或半导体的系统、装置或器件，或者任意以上的组合。可读存储介质的更具体的例子包括：具有一个或多个导线电连接的静态随机存取存储器(sram)，电可擦除可编程只读存储器(eeprom)，可擦除可编程只读存储器(eprom)，可编程只读存储器(prom)，只读存储器(rom)，磁存储器，快闪存储器，磁盘或光盘，或者上述的任意合适的组合。
68.最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。

技术特征：
1.一种尺寸约束的truss社群搜索方法，其特征在于，包括：步骤1，利用启发式算法计算近似解h和最优解的min-trussness上界k*；步骤2，用k'表示近似解h的min-trussness值，若k'等于k*，则确定近似解h为准确解，若k'不等于k*，执行步骤3；步骤3，利用分支定界算法查找精确解。2.根据权利要求1所述的方法，其特征在于，所述方法进一步包括：步骤4，根据精确解查找一个包含查询节点q、节点数量至少为l至多为h，并且在所有连通子图中拥有最大min-trussness的连通子图。3.根据权利要求2所述的方法，其特征在于，所述步骤1具体包括：判断节点q的trussness值是否大于尺寸约束的上界h，若是，则设置k*即最优解的min-trussness上界为h，并用q初始化c作为种子子图；若不是，则设置k*为满足t
q
()的尺寸不小于l的最大k值，其中，t
q
()表示包含q的连通子图，其节点均由q开始遍历计算且其节点trussness值不小于k；若t
q
()的尺寸不大于h时，即返回t
q
()作为解，否则以t
q
(
*
+1)的节点集以及q初始化c作为种子子图；以c的邻居中节点trussness值不小于k
*
，且不在c中的节点初始化备选节点集r，递归地根据计分函数其中，k
max
是g中最大的节点trussness，依次将r中有希望的节点移动到c中，直到c的尺寸达到尺寸约束的上界h；在所有由c生成的子图中满足尺寸不小于l的k-truss里，找到最大的k
′
，并返回该k
′-russ。4.根据权利要求2所述的方法，其特征在于，所述分支定界算法具体包括：基于cost-budget的定界技术、备选集剪枝技术以及分支策略。5.根据权利要求3所述的方法，其特征在于，所述步骤3具体包括：基于cost-budget的定界技术，首先用先进的truss maintenance算法更新c中每个节点的trussness值，然后初始化c中每个节点的cost和budget，将节点的访问标志设为否，如果节点的预算小于成本，则该分支没有希望，终止计算；否则分别用b
min
和c
max
记录所有节点中最小的预算值和最大的成本值，如果b
min
≥2
×
c
max
，则确定当前分支有希望，否则访问c中的每个节点u，并且假定从r转移到c中一些节点后，u的节点trussness值达到k
′
+1，并且相应地更新受影响的节点的cost和budget，并在更新后重新判断cost和budget的大小关系，以决定是否终止该分支的计算。6.根据权利要求5所述的方法，其特征在于，所述步骤3具体包括：基于备选集剪枝技术将r中没有希望的节点删除掉，并且在不违反尺寸约束的前提下将r中有希望的节点添加到c中，为了使解的min-trussness至少达到k'+1，如果把r中的一个节点转移到c中需要超过(h-|c|-1)个节点同时转移，则该节点是没有希望的，故将其从r中移除；对于c中的节点，若其在c并r中节点trussness值不小于k'+1的邻居数量为k'，则这些邻居都转移到c中。
7.根据权利要求6所述的方法，其特征在于，所述步骤3具体包括：根据分支策略，在分支访问顺序上，将加入c的节点依据计分函数得分进行排序，根据回溯算法，对于一个实例(c,r)，如果发现在当前分支中顶点u∈c不会存在与任何一个min-trussness值至少为k
′
+1的满足尺寸约束的连通子图中，则该分支是没有希望的，回溯到上面不包含该节点的分支上。8.一种尺寸约束的truss社群搜索装置，其特征在于，包括：第一计算模块，用于利用启发式算法计算近似解h和最优解的min-trussness上界k*；第二条件判断模块，用于以k'表示近似解h的min-trussness值，若k'等于k*，则确定近似解h为准确解，若k'不等于k*，调用第三计算模块；第三计算模块，用于利用分支定界算法查找精确解。9.一种电子设备，其特征在于，包括：存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序，所述计算机程序被所述处理器执行时实现如权利要求1至7中任一项所述的尺寸约束的truss社群搜索方法的步骤。10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有信息传递的实现程序，所述程序被处理器执行时实现如权利要求1至7中任一项所述的尺寸约束的truss社群搜索方法的步骤。

技术总结
本公开提供了一种尺寸约束的truss社群搜索方法及装置，其中，方法包括：步骤1，利用启发式算法计算近似解H和最优解的min-trussness上界k*；步骤2，用k'表示近似解H的min-trussness值，若k'等于k*，则确定近似解H为准确解，若k'不等于k*，执行步骤3；步骤3，利用分支定界算法查找精确解。本公开的分支定界算法首先使用启发式算法获得一个接近最优解的k'，其可以大幅减少准确解的搜索空间；并且设计了针对当前中间结果解和候选集顶点的界限策略——预算成本下界策略，其可以安全删除没有希望的搜索分支，进而提高准确解搜索效率。进而提高准确解搜索效率。进而提高准确解搜索效率。


技术研发人员：张帆 李利彬 郭海城
受保护的技术使用者：广州大学
技术研发日：2023.05.17
技术公布日：2023/8/6