面向超图的极大团搜索算法.pdf

2023 08 10计算机应用,Journal of Computer Applications2023,43(8):2319-2324ISSN 10019081CODEN JYIIDUhttp：/面向超图的极大团搜索算法徐兰天1，李荣华1*，戴永恒2，王国仁1（1.北京理工大学 计算机学院，北京 100081；2.电科云（北京）科技有限公司，北京 100041）（通信作者电子邮箱）摘要：现实世界中的实体关系大多不能用简单的二元关系来表示，而超图能很好地表示实体间的多元关系。因此，提出超图团和极大团的定义，并给出了搜索超图极大团的精确算法和近似算法。首先，分析了现有的普通图上的极大团搜索算法无法直接应用到超图上的原因。然后，基于超图的特性和极大团的定义，提出了一种新颖的保存超点间邻接关系的数据结构，并提出了一种超图上的精确极大团搜索算法。由于精确算法的速度较慢，因此结合支撑点（pivot）的剪枝思想，削减递归层数，提出了一种超图上的近似极大团搜索算法。在多个真实超图数据集上的实验结果显示，所提近似算法在找到大多数极大团的前提下，提高了搜索速度，当在3-uniform超图上，测试超图团的点数为22时，加速比达到了1 000以上。关键词：超图；极大团；集合枚举；近似算法；支撑点中图分类号：TP311.1 文献标志码：AMaximal clique searching algorithm for hypergraphsXU Lantian1，LI Ronghua1*，DAI Yongheng2，WANG Guoren1（1.School of Computer Science and Technology，Beijing Institute of Technology，Beijing 100081，China；2.Diankeyun（Beijing）Technology Company Limited，Beijing 100041，China）Abstract:Most of entity relationships in the real world cannot be represented by simple binary relations，and hypergraph can represent the n-ary relations among entities well.Therefore，definitions of hypergraph clique and maximal clique were proposed，and the exact algorithm and approximation algorithm for searching hypergraph maximal clique were given.First，the reason why the existing maximal clique searching algorithms on ordinary graphs cannot be applied to hypergraphs directly was analyzed.Then，based on the characteristics of hypergraph and the definition of maximal clique，a novel data structure for preserving the adjacency relations among hyperpoints was proposed，and an accurate maximal clique searching algorithm on hypergraph was proposed.As the running of the exact algorithm is slow，the pruning idea of pivots was combined with，the number of recursive layers was reduced，and an approximation maximal clique searching algorithm on hypergraph was proposed.Experimental results on multiple real hypergraph datasets show that under the premise finding most maximal cliques，the proposed approximation algorithm improves the search speed.When the number of test hypergraph cliques on 3-uniform hypergraph is 22，the acceleration ratio reaches over 1 000.Key words:hypergraph;maximal clique;set enumeration;approximation algorithm;pivot0 引言 随着大数据技术的发展，越来越多的数据挖掘需求以从现实世界中抽象出来的图数据集为基础，而现实世界中各种图的信息量巨大，其中包含大量的信息模式。在现实世界中很多领域都能应用图网络，如社交网络1、化学分析2和图像处理3等。极大团搜索作为一个基本的图数据挖掘问题，应用场景非常多，因此对现实世界的图进行极大团枚举具有重要的现实意义。极大团枚举在很多应用场景中都有使用，比如 k-clique community、蛋白质分析、社区搜索、机器学习因子分解等4。这些应用大多针对真实的图数据集，可能被构建为超图等与传统图结构不同的结构，因此极大团算法也需要考虑超图等真实世界的图特征；而且极大团算法主要用于预计算或处理，它们的性能会影响整个应用程序的性能，因此如何更快地对超图进行极大团搜索是当前图算法领域的一个关键问题。在现实世界中，许多数据的关系本身就是多元的，因此用二元关系表达多元关系是不适合的。如学者协作网络中，多位作者共同完成一篇文章，此时用普通图表示作者间的两两合作关系不如超图的表示确切。超图与普通图最大的不同在于每条边不仅关联两个点，而可能关联更多的点。此时原有的普通图上的一些基础定义和极大团定义等需要在超图上重新诠释，有如下几个问题文章编号：1001-9081（2023）08-2319-06DOI：10.11772/j.issn.1001-9081.2022091334收稿日期：20220906；修回日期：20220923；录用日期：20221008。基金项目：国家自然科学基金资助项目（62072034）；国家重点研发计划课题（2021YFB3301301）。作者简介：徐兰天（1997），男，河北唐山人，硕士研究生，主要研究方向：图数据挖掘；李荣华（1985），男，北京人，教授，博士，CCF会员，主要研究方向：图数据挖掘；戴永恒（1983），男，北京人，工程师，博士，主要研究方向：领域建模、专家知识结构化、融合的机器学习；王国仁（1966），男，北京人，教授，博士，CCF会员，主要研究方向：数据挖掘。第 43 卷计算机应用要解决：1）如何定义超图上的团和极大团；2）如何定义超图上的邻居关系，并用适宜的数据结构来表达；3）如何改造普通图上的极大团算法使之适合超图上的社区搜索。1 相关工作极大团算法是图挖掘领域的一个经典问题。极大团是一个NP-Hard问题，目前研究人员已经提出了许多在普通图上搜索极大团的有效算法。Bron和Kerbosch提出了一种经典的递归算法来解决极大团问题，这种算法也被称为 Bron-Kerbosch 算法5。Tomita 等6证明了对于一个有 n个顶点的图，极大团算法最坏情况下的时间复杂度为O（3n/3）。这是一个关于n的函数，因为在一个有n个顶点的图中，最多存在3n/3个极大团。Tomita等6还改进了Bron-Kerbosch算法，提出了一种pivot算法。Tomita等6发现当Bron-Kerbosch算法递归到一中间状态时，对于候选集和禁止集中的任何点u，任何后续找到的极大团至少包含一个不是点u的邻居的节点。关于团的挖掘，主要有k-团挖掘（即搜索指定大小为k的团）、极大团挖掘、最大团挖掘和带权团挖掘等7-8。由于团问题是NP-hard问题，针对团的研究也分为精确算法和近似算法。具体的精确算法可以分为两大类：基于非排序的算法和基于排序的算法。两种典型的基于非排序的算法是经典的Chiba-Nishizeki算法9和MACE算法10；基于排序的算法包括基于度排序的算法11和基于退化排序的算法12，这两种算法是目前最先进的 k-clique 枚举算法。而在近似算法方面，k-clique枚举通常可以采用智能采样的技术，例如现有的基于排序的算法可以通过一种基于颜色的修剪技术进行优化，从而得到一组基于颜色排序的算法。此外现有的近似算法还包括Turn-Shadow算法13和ERS算法14等。2 基础知识 普通图中的团定义为点集中的点两两之间都有边相连。然而超图中边的大小一般大于等于2，两两邻接关系不再适合应用在超图中，不能充分利用超图中所承载的信息。虽然一些数学领域的研究人员已经提出了关于超图团的一些相关定义15，但只是进行了超图上最大可能出现的团的数量的证明，而目前超图上的团和极大团算法还没有有效的社区搜索算法出现。结合数学领域的超图团的定义，下面给出本文中的在r-uniform超图（指超图中所有超边都只包含r个点）上的超图团和极大团定义。定义1 超图团和极大团。超团hclique是r-uniform超图G中的一个超点子集，使超团中任意r个不同的超点都可以组成超图G中的一条边。如果一个超团不被其他任一超团所包含，即它不是其他任一超团的真子集，则称该团为r-uniform超图G的一个极大超团（maximal hclique）。若一个超团中包含k个点，则该超团被称为k-hclique。如图1所示，本文展示了一个在3-uniform图上的4-超团（4-hclique）。图中共有4个点（A，B，C，D）和4条超边（A，B，C ，A，B，D ，A，C，D ，B，C，D ）。从图1中可以看出，该4-hclique 的 4 个点中任意三点都是超图中的一条边。类似地，在一个r-uniform超图上的k-hclique要求其中的k个点中任意r个点都能组成这个r-uniform超图中的一条边。3 面向超图的极大团搜索算法设计 3.1对普通图极大团搜索算法的分析普通图和超图的特征、普通图和超图上极大团的定义均不相同，因此现有的 Bron-Kerbosch 算法无法直接应用于超图。下面具体分析将Bron-Kerbosch算法推广到超图的主要挑战。1）普通图中邻接关系是二元的，即若(u，v)E，则点u与点v相邻，点u是点v的邻居，点u应存在点v的邻接表中；反之点v是点u的邻居，点v也应存在点u的邻接表中。然而，对超图中的超边（u，v，w），简单地把点v加入点u的邻接表是不确切的，因为本质上点u同时与点v和点w相邻，如果不考虑点w而只讨论另两点互为邻居会损失超图信息。例如在图1中，假如只有（A，B，C）和（A，C，D）两条超边，若以二元关系来考虑，则A的邻接表中会保存B、C、D三个点，然而点C与点A同时参与构成了两条超边，点B和D分别只与点A同时参与构成了一条超边，但这3个点在二元关系邻接表中保存为了相同的状态。显然二元关系的邻接表不能充分诠释超图中的关系，造成了信息丢失。2）普通图极大团Bron-Kerbosch算法中涉及结果集、候选集和禁止集3个集合，如何合理地结合超图和超图极大团的定义、推广Bron-Kerbosch算法的思想，对这3个集合赋予新的意义也是一个需要解决的主要问题。3.2超图团的数据结构本文提出了一种新的模式来定义邻接关系，首先定义一个超点组和超点组的邻接关系。定义2 超点组。对于r-uniform超图上的一条超边e，它包含的 r 个点中任取r-1个点可以组成一个超点组，也称hgroup。定义3 超点组的邻居。对于r-uniform超图上的一条超边e，其中包含r个超点组，则对于一个超点组h，超点组的邻居定义为超边中的另一点 u，即 eh，可表示为超点组 h 邻接于点u。定义4 超点组的度。对于一个超点组h，它所有邻居点的个数称为超点组h的度，可表示为Degree（h）。例如，如图1所示的3-uniform超图中的4-hclique中，对于超边 A，B，C ，其中包含 A，B 、A，C 、B，C 3个超点组。对于超点组 A，C ，它邻接于 B ；同理，超点组 A，C 和 B，C 分别邻接于 B 和 A 。整个图中共有6个超点组，即 A，B 、A，C 、A，D 、B，C 、B，D 和 C，D ，它们的邻接关系如图2所示。此时的 hgroup邻接表比较完整地保存了超图中的原有信息。与二元关系保存的邻接表相比，hgroup充分保留了超图中的多元关系，对于不同邻接状态可以在hgroup邻接表中存储为图14-超团Fig.1Four-hclique2320第 8 期徐兰天等：面向超图的极大团搜索算法不同的形态，比较好地解决了二元邻接表中邻接关系不同，但储存的邻接表结构相同的问题。3.3面向超图团的改进Bron-Kerbosch算法基于前文中的数据结构和超图极大团的定义，以及对普通图Bron-Kerbosch算法的分析，本文提出了Bron-Kerbosch算法面向超图团的改进策略。普通图Bron-Kerbosch算法的输入参数主要是结果集、候选集和禁止集，分别表示为R、P和X，其中P初始化为原图G中的 所 有 节 点，而 R、X 则 初 始 化 为 空 集。此 后，普 通 图Bron-Kerbosch算法会把集合P中的点逐个加入集合R中。然而在超图极大团算法中却并不能采用这样的方法，因为本文定义的超图的邻接表结构是基于hgroup-vertex的key-value关系，这使求超图极大团的算法在启动时应采取不同的设计形式。本文算法将超图 Bron-Kerbosch算法分为算法启动模块和算法递归模块两个模块。算法启动模块如算法1所示，需要算法启动模块的主要原因是，在超图极大团算法中第一轮加入集合R的不是一个超点，而是一个超点组hgroup。在算法中，首先遍历hgroup的邻接表hgneibour中的所有key值，即所有超图G中存在的hgroup，对每一个初始化一个标记位，并将其置为false。这里的标志位flag表示标记目前还没有枚举包含这个hgroup的所有超图极大团。然后，再次遍历hgneibour中的所有hgroup，并调用算法BKH（R，P，X）（或算法 BKHpivot（R，P，X），每次将一个 hgroup存入集合 R，将这个hgroup在hgneibour中的所有邻接点集合作为集合P，再传一个空集合X作为BKH（R，P，X）的三个参数。当BKH（R，P，X）执行结束并返回时，算法已经枚举了包含这个hgroup的所有超图极大团。此时，算法将R集合清空，并将hgflaghg 置为true，标志包含hg的极大团搜索完毕，在以后的递归过程中，若hg再次出现，则可直接跳过，否则找到的超图极大团就会出现重复枚举的情况。算法1 BKHinit。输入 超图G中关于hgroup的邻接表hgneibour；输出 超图G的极大团。1）hgflag是一个map，key值为hgroup，value值为bool，R=，X=2）/为所有hg初始化状态为false3）for hg hgneibour do4）hgflaghg=flase5）/遍历hgneibour中的hg，调用BKH算法（可替换为BKHpivot/算法）6）for hg hgneibour do7）R hg8）BKH（R，hgneibourhg，X）9）R.clear()10）hgflaghg=true11）return NULL算法递归模块如算法2所示。首先判断输入参数集合P和集合X是否均为空集，若二者均为空集，即P X=，则当前的集合R中的所有超点组成一个极大超团；否则当前输入的集合R并不能在本轮输出为一个极大团，还需要继续递归验证。此时计算集合R中的所有超点，从中寻找所有大小为r-2的超点组，此处称之为hgless。寻找hgless的原因是，由于当前集合R还有继续扩展的空间，之后还要继续向R集合中尝试加入集合P中的超点，然而由于R集合是一个由若干hgroup组成的集合，而集合P是一个由若干单个超点组成的集合，所以从P集合中取点后需要转化为hgroup后再加入集合R。算法从第6）行开始逐个遍历集合P中的候选超点，为了避免初始的R、P、X被修改而影响下一轮循环，算法用Rnow、Pnow和Xnow三个集合分别保存本轮循环中的R、P、X。对于每一个P集合中的超点u，所有R集合中的hgless加上这个超点就可以组成一个超点组hgroup。此时向集合R中加入一个超点，本质是加入了一组 hgroup。与 普 通 图 算 法 类 似，也 要 执 行Pnow=Pnow hgneibour hg 和Xnow=Xnow hgneibour hg 来削减下一层递归的候选集和禁止集。此外，值得注意的是，若新组成的超点组的hgflag为true，则当前超点u无须再加入R集合，因为如果超点u加入R集合，则新的R集合中一定包含这个hgflag为true的hg，而由BKHinit算法可知，所有包含这个hg的极大超团已被枚举，所以此时可以直接跳过超点u，继续从集合P中枚举下一个超点。最后，从候选集合P中去掉超点u并将它加入到禁止集X中，算法结束。算法2 BKH（R，P，X）。输入 从BKHinit函数获得的R、P、X；输出 在P和R中的极大团。1）if P X=do2）将R中所有超点输出为一个极大团3）返回上一层递归函数4）Rnode代表R中所有hgroup组成的集合5）hgless是Rnode中所有大小为r-1的集合6）for u P do7）Pnow=P，Rnow=R，Xnow=X8）flag=09）for hgl hgless do10）/用hgl和超点u取并集，形成新hgroup11）hg=hgl u12）/检查包含hg的极大团是否已被枚举13）if hgflag hg =true then14）flag=true15）break16）/加入hg后，更新Rnow、Pnow、Xnow17）Rnow=Rnowhg18）Pnow=Pnow hgneibour hg 19）Xnow=Xnow hgneibour hg 20）/若存在已枚举过的hg，跳出循环21）if flag=true then22）continue23）/递归调用24）BKH（Rnow，Pnow，Xnow）25）P=P-u26）X=X u27）/待下一层递归函数输出28）return NULL图1所示3-uniform超图的递归算法流程如图3所示，图中每一行代表一次递归过程。在第一层递归中，输入参数 R 集合中只有一个 hgroupA，图2超点组的邻接关系Fig.2Adjacency relationships in hgroup2321第 43 卷计算机应用B ，P集合中则包含了hgneibour A，B ，即C、D两个超点，而X集合初始为。首先枚举P集合中的点，假如本次枚举的是超点C，则将超点C加入R集合中。然而R集合中的hgless（大小为r-2的超点组，本例中r=3）只有 A 和 B 两个。则加入超点C后，新产生 A，C ，B，C 两个hgroup。此时集合P=C，D 和集合X=，它们都需要与 hgneibour A，C =B，D 和hgneibour B，C =A，D 两个集合均取交集，得到第二轮的P集合为P=D，X集合为X=。在下一轮子递归中，再次枚举集合P中的点，选取点D加入R集合中，则结合R集合中的hgless，加入超点D后，新产生A，D ，B，D ，C，D 三个hgroup。然后再用集合P和集合X与hgneibourA，D=B，C，hgneibourB，D=A，C 和hgneibour C，D =A，B 三个集合均取交集，得到下一轮的P集合为，集合X也为。此时再在下一轮的子递归中，由于集合P和集合X已同时为空集，满足P X=的条件，说明当前R集合符合极大超团输出条件，则将输出此时集合R=A，B ，A，C ，B，C ，A，D ，B，D ，C，D 中的所有单超点 A，B，C，D 。在第二层递归中，再次枚举集合P中的点，此时点C已被枚举，此轮则选取点D加入R集合中，则结合R集合中的hgless，加入超点D后，新产生 A，D ，B，D 两个hgroup；然后再用集合P=D 和X=C 与 hgneibourA，D =B，C 和hgneibour B，D =A，C 两个集合均取交集，得到下一轮的P集合为空集，集合X=C。在第二轮递归的下一轮子递归中，由于集合P=但集合X ，说明当前的R集合的极大超团已被搜索过，不符合极大超图的输出条件，且此时集合P为空集，不能再从中取点加入集合R中，则此轮递归结束，不输出任何极大超团。3.4面向超图团的改进BKHpivot算法在上述BKH算法的基础上，本文继续根据pivot算法的剪枝思想提出BKHpivot算法，如算法3所示。算法3 BKHpivot（R，P，X）。输入 从BKHinit函数获得的R、P、X；输出 在P和R中的极大团。1）if P X=then2）将R中所有超点输出为一个极大团3）返回上一层递归函数4）Rnode代表R中所有hgroup组成的集合5）hgless是Rnode中所有大小为r-1的集合6）从P X中选择一个pivot点w，N=7）/求若加入w新产生hgroup的邻接点的交集8）for hgl hgless do9）hgw=hgl w10）if N=then11）N=hgneibour hgw12）else13）N=N hgneibour hgw14）/减少P中需要遍历的超点15）for u PN do16）Pnow=P，Rnow=R，Xnow=X17）flag=018）for hgl hgless do19）/用hgl和超点u取并集，形成新hgroup20）hg=hgl u21）/检查包含hg的极大团是否已被枚举22）if hgflag hg =true then23）flag=true24）break25）/加入hg后，更新Rnow，Pnow，Xnow26）Rnow=Rnowhg27）Pnow=Pnow hgneibour hg 28）Xnow=Xnow hgneibour hg 29）/若存在已枚举过的hg，跳出循环30）if flag=true then31）continue32）/递归调用33）BKHpivot（Rnow，Pnow，Xnow）34）P=P-u 35）X=X u 36）/待下一层递归函数输出37）return NULLBKHpivot算法与BKH算法的主要区别在于BKHpivot算法在第6）13）行使用了pivot的剪枝思想进行剪枝。当算法枚举到一个中间状态时，对于P X中的任何一点u，倘若将点u加入集合R，本质是将点u和hgless中的大小为r-2的点集取交集产生的hgroup加入R。若超点u可以加入集合R，则这些新产生的hgroup的邻接点可以在超点u加入R集合之后再遍历；若超点u不能加入集合R，算法并不能保证在超点u加入集合X后还能枚举到所有的新hgroup的邻接点。BKHpivot算法在遍历集合P中的超点时，其实只需要遍历其中的一部分，而不用全部遍历，极大地改善BKH算法的运行效率，但是有可能会少搜索到一部分的超图极大团。4 面向超图的极大团算法分析 首先，在BKHinit算法中要遍历所有的r-uniform超图G中的 hgroup，加入超图中的超边共有 m 条，而超图中最大可能的hgroup数量为rm。在极大团算法中，每轮循环都会遍历集合P中的超点，而集合P初始化为一个hgroup的邻居节点，则集合的大小不超过hg的最大邻居数，记为dmax。无论在BKH算法还是BKHpivot算法中，都需要计算加入一个超点后集合R中新产生的hgroup，对于每个hgroup，集合P和X要与新产生的hgroup的邻居依次求交集。每次新产生的hgroup数由本轮集合中的hgless数决定，最大为()rdmax，则需要()rdmax+1个长度不超过dmax的集合取交集。整个算法是递归结构，最多将dmax个点加入集合R，则算法最多递归dmax层。值得注意BKHpivot算法能减少部图3BKH算法的R，P，X集合Fig.3R，P，X sets of BKH algorithm2322第 8 期徐兰天等：面向超图的极大团搜索算法分重复枚举，但在时空复杂度上，与BKH并无区别。综上，超图极大团时间复杂度为O(rm()rdmaxd2max)dmax)。前文给出了r-uniform超图上的团和极大团的定义，实际上本文的定义也可以推广到普通超图，即超边大小任意的超图上。下面给出普通超图团和极大超图团的定义：定义5 普通超图团和极大超图团。普通超图团hclique是超图G中的一个超点子集，使得超图团中的任意r个不同的超点都可以参与组成超图G中的同一条边。如果一个超图团不被其他任一超图团所包含，即它不是其他任一超图团的真子集，则称该团为超图G的一个极大超图团。若一个超图团中包含K个点，则该超图团被称为K，r-hclique。超图团的这种推广主要是基于普通超图的边分解的思路。如图4所示，一条超边大小为d的超边可以转化为()rd条大小为r的超边。若在整个普通超图中求r-hclique，则可直接删除普通超图中所有大小小于r的超边，将大于r的超边转化为若干r大小的超边再搜索，此时原来的普通超图就会转化为r-uniform超图，就可以在新图上应用BKH算法和BKHpivot算法等来计算极大超图团。5 实验与结果分析 本 文 实 验 环 境 硬 件 为 Intel Xeon Gold 5218R CPU 2.10 GHz，内存为96 GB，硬盘为500 GB，操作系统为Ubuntu 9.4.0，开发软件为g+，开发语言为C/C+。本文首先在不同规模大小的超图团上测试了BKH算法和BKHpivot算法，结果如表1所示。表1中r表示测试超图为r-uniform超图，K表示测试超图的点数，edge表示测试超图的边数。例如一个数据集K=12，r=3表示该数据是一个超点数为12的r-uniform超图团，即图中有12个超点，且这12个点中任意3个点都存在一条超边。对于一个K=12，r=3的超图团，其中共包含()312，即220条超边。从表1中可知，对于K的增长，超图极大团算法的搜索时间呈现指数增长。对于K=12，3-uniform超图BKH算法的运行时间为0.07 s，而K=22，3-uniform超图BKH算法的运行时间达到了123.08 s，而超图的超边数只扩大了7倍。同时，对于相同的K值，r值越高，超图极大团算法的搜索时间也越长。对于r=4的超图极大团，算法的搜索时间普遍是r=3的24倍。以上结果符合前文中时间复杂度的分析。可以发现，在超图团这种比较特殊的数据集上，近似算法BKHpivot与精确算法BKH一样，都可以输出精确的超图极大团，但所需的时间远小于BKH算法。K值越大，加速比越大：在K=12时，算法BKHpivot对BKH的加速比只有7倍左右；在K=22时，无论r=3时，加速比都达到了 1000以上。这主要是因为 K越大，所需总递归层数越多，BKHpivot算法越有机会能减掉更多的递归层数，使算法越来越快。由于目前未找到公开的标准r-uniform超图数据集，为了在更大规模的超图数据集上测试两个算法，本文选取了contact-primary-school、contact-high-school 和 email-Eu 三个数据集16，它们的基本信息如表2所示，其中|E|=m表示边数，|V|=n表示点数。本文采用上文的超边分解的方法，分别以r=3和r=4处理了这3个数据集，即删除低于r的超边，将size大于r的超边转化为若干大小为r的超边；然后用BKH算法和BKHpivot算法分别在各数据集上搜索极大团，结果如表3所示。表3中，num为找到的极大团数，time表示极大团完成搜索所需的时间，memory表示内存占用情况。图4d大小超边r化Fig.4d-edge to r-edges表1超图极大团搜索算法的运行时间比较Tab.1Comparison of running time of hypergraph maximal clique searching algorithmsK121416182022r343434343434edge2204953641 0015601 8208163 0601 1404 8451 5407 315搜索K，r超图团的时间/sBKH0.070.140.260.491.032.885.1114.4925.7387.75123.08438.73BKHpivot0.010.070.030.210.050.310.041.070.041.750.096.79加速比7.002.008.672.3320.609.29127.7513.54643.2550.141 367.5664.61表2数据集基本信息Tab.2Basic information about dataset数据集contact-primary-schoolcontact-high-schoolemail-Eu|E|=m106 879172 035234 760|V|=n2423271 005表3超图极大团的搜索结果比较Tab.3Comparison of search results of hypergraph maximal cliquer34数据集contact-primary-schoolcontact-high-schoolemail-Eucontact-primary-schoolcontact-high-schoolemail-Euedge5 1392 370160 605381238714 535BKHnum3 4691 6336 3303452102 750time/s0.0400.02542 905.0000.0080.006226 458.000memory/KB4 8044 50013 2484 0723 78861 576BKHpivotnum3 0851 4833 8063402052 392time/s0.0300.0201.4880.0080.00716.899memory/KB4 8084 35213 3044 0284 07261 4842323第 43 卷计算机应用从表3中可以看出BKHpivot算法在email-Eu数据集上优势明显，r=3时，BKHpivot可以在1.5 s内找到绝大多数的极大团，而BKH算法完成搜索则需要42 905 s；而r=4时，BKH算法的用时极久，已超出可承受范围，而BKHpivot可在17 s内完成搜索。虽然BKH和BKHpivot算法在较为稠密的email-Eu 数据集上的用时差异极大，但在较为稀疏的 contact-primary-school 和 contact-high-school 数据集上的用时则差不多。这是由于稀疏图上的极大团的K值较小时，K=3或4的情况很多，几乎没有大K值的情况，使得BKHpivot算法减少递归次数的优势没有充分体现，反而在计算pivot点的运算中消耗了时间；而内存占用上，各参数下BKH和BKHpivot算法基本相同，也印证了前文的时空复杂度分析。图 5具体展示了 email-Eu数据集上的r=3和r=4处理图上进行两种极大团搜索后，在高K值部分极大团数的对比，K值最高分别为26和25。高K值部分极大团是图中最重要也是最稠密的部分。从图5中可以看出，BKHpivot算法虽然并没有找到所有的极大团，但这并不是主要以损失大量高K值部分极大团为代价，在高K值极大团的搜索上，BKHpivot算法依然保持了较高的效率。图5两种算法的超图极大团数Fig.5Number of hypergraph maximal cliques for two algorithms结合前文超图团数据的搜索实验，可以发现在大规模超图数据上，由于图的稀疏程度不同，BKHpivot算法的加速能力存在差异。在稀疏的图上，由于更多的极大团的K值较小，所需搜索的递归层数也少，难以发挥 BKHpivot 算法的优势，BKHpivot算法更适合在更稠密的超图数据集中搜索超图极大团，而且极大团的K值越高，效果越明显。6 结语 本文给出了r-uniform超图上的团和极大团的定义，重新定义了超图中的邻接关系并设计了相应的数据结构，给出了普通超图上极大团搜索的算法思路。基于大规模数据集验证了超图极大团算法的效率和有效性。在下一步的工作中，希望可以进一步改进 pivot算法的结构，在提高搜索速度的基础上保证能枚举到所有的超图极大团。参考文献（References）1 HAO F，LI S，MIN G Y，et al.An efficient approach to generating location-sensitive recommendations in ad-hoc social network environmentsJ.IEEE Transactions on Services Computing，2015，8（3）：520-533.2 SHANG H L，TAO Y D，GAO Y，et al.An improved invariant for matching molecular graphs based on VF2 algorithmJ.IEEE Transactions on Systems，Man，and Cybernetics：Systems，2015，45（1）：122-128.3 LIU J Z，LEE Y T.Graph-based method for face identification from a single 2D line drawing J.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（10）：1106-1119.4 LI R H，GAO S，QIN L，et al.Ordering heuristics for k-clique listing J.Proceedings of the VLDB Endowment，2020，13（12）：2536-2548.5 BRON C，KERBOSCH J.Algorithm 457：finding all cliques of an undirected graph J.Communications of the ACM，1973，16（9）：575-577.6 TOMITA E，TANAKA A，TAKAHASHI H.The worst-case time complexity for generating all maximal cliques and computational experimentsJ.Theoretical Computer Science，2006，363（1）：28-42.7 MITZENMACHER M，PACHOCKI J，PENG R，et al.Scalable large near-clique detection in large-scale networks via samplingC/Proceedings of the 21st ACM Special I