面向超图的极大团搜索算法.pdf
《面向超图的极大团搜索算法.pdf》由会员分享,可在线阅读,更多相关《面向超图的极大团搜索算法.pdf(6页珍藏版)》请在咨信网上搜索。
1、2023 08 10计算机应用,Journal of Computer Applications2023,43(8):2319-2324ISSN 10019081CODEN JYIIDUhttp:/面向超图的极大团搜索算法徐兰天1,李荣华1*,戴永恒2,王国仁1(1.北京理工大学 计算机学院,北京 100081;2.电科云(北京)科技有限公司,北京 100041)(通信作者电子邮箱)摘要:现实世界中的实体关系大多不能用简单的二元关系来表示,而超图能很好地表示实体间的多元关系。因此,提出超图团和极大团的定义,并给出了搜索超图极大团的精确算法和近似算法。首先,分析了现有的普通图上的极大团搜索算法无
2、法直接应用到超图上的原因。然后,基于超图的特性和极大团的定义,提出了一种新颖的保存超点间邻接关系的数据结构,并提出了一种超图上的精确极大团搜索算法。由于精确算法的速度较慢,因此结合支撑点(pivot)的剪枝思想,削减递归层数,提出了一种超图上的近似极大团搜索算法。在多个真实超图数据集上的实验结果显示,所提近似算法在找到大多数极大团的前提下,提高了搜索速度,当在3-uniform超图上,测试超图团的点数为22时,加速比达到了1 000以上。关键词:超图;极大团;集合枚举;近似算法;支撑点中图分类号:TP311.1 文献标志码:AMaximal clique searching algorithm
3、 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 r
4、epresented 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 reas
5、on 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 p
6、roposed,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 propos
7、ed.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
8、words:hypergraph;maximal clique;set enumeration;approximation algorithm;pivot0 引言 随着大数据技术的发展,越来越多的数据挖掘需求以从现实世界中抽象出来的图数据集为基础,而现实世界中各种图的信息量巨大,其中包含大量的信息模式。在现实世界中很多领域都能应用图网络,如社交网络1、化学分析2和图像处理3等。极大团搜索作为一个基本的图数据挖掘问题,应用场景非常多,因此对现实世界的图进行极大团枚举具有重要的现实意义。极大团枚举在很多应用场景中都有使用,比如 k-clique community、蛋白质分析、社区搜索、机器学习因
9、子分解等4。这些应用大多针对真实的图数据集,可能被构建为超图等与传统图结构不同的结构,因此极大团算法也需要考虑超图等真实世界的图特征;而且极大团算法主要用于预计算或处理,它们的性能会影响整个应用程序的性能,因此如何更快地对超图进行极大团搜索是当前图算法领域的一个关键问题。在现实世界中,许多数据的关系本身就是多元的,因此用二元关系表达多元关系是不适合的。如学者协作网络中,多位作者共同完成一篇文章,此时用普通图表示作者间的两两合作关系不如超图的表示确切。超图与普通图最大的不同在于每条边不仅关联两个点,而可能关联更多的点。此时原有的普通图上的一些基础定义和极大团定义等需要在超图上重新诠释,有如下几个
10、问题文章编号:1001-9081(2023)08-2319-06DOI:10.11772/j.issn.1001-9081.2022091334收稿日期:20220906;修回日期:20220923;录用日期:20221008。基金项目:国家自然科学基金资助项目(62072034);国家重点研发计划课题(2021YFB3301301)。作者简介:徐兰天(1997),男,河北唐山人,硕士研究生,主要研究方向:图数据挖掘;李荣华(1985),男,北京人,教授,博士,CCF会员,主要研究方向:图数据挖掘;戴永恒(1983),男,北京人,工程师,博士,主要研究方向:领域建模、专家知识结构化、融合的机器
11、学习;王国仁(1966),男,北京人,教授,博士,CCF会员,主要研究方向:数据挖掘。第 43 卷计算机应用要解决:1)如何定义超图上的团和极大团;2)如何定义超图上的邻居关系,并用适宜的数据结构来表达;3)如何改造普通图上的极大团算法使之适合超图上的社区搜索。1 相关工作极大团算法是图挖掘领域的一个经典问题。极大团是一个NP-Hard问题,目前研究人员已经提出了许多在普通图上搜索极大团的有效算法。Bron和Kerbosch提出了一种经典的递归算法来解决极大团问题,这种算法也被称为 Bron-Kerbosch 算法5。Tomita 等6证明了对于一个有 n个顶点的图,极大团算法最坏情况下的时间
12、复杂度为O(3n/3)。这是一个关于n的函数,因为在一个有n个顶点的图中,最多存在3n/3个极大团。Tomita等6还改进了Bron-Kerbosch算法,提出了一种pivot算法。Tomita等6发现当Bron-Kerbosch算法递归到一中间状态时,对于候选集和禁止集中的任何点u,任何后续找到的极大团至少包含一个不是点u的邻居的节点。关于团的挖掘,主要有k-团挖掘(即搜索指定大小为k的团)、极大团挖掘、最大团挖掘和带权团挖掘等7-8。由于团问题是NP-hard问题,针对团的研究也分为精确算法和近似算法。具体的精确算法可以分为两大类:基于非排序的算法和基于排序的算法。两种典型的基于非排序的算
13、法是经典的Chiba-Nishizeki算法9和MACE算法10;基于排序的算法包括基于度排序的算法11和基于退化排序的算法12,这两种算法是目前最先进的 k-clique 枚举算法。而在近似算法方面,k-clique枚举通常可以采用智能采样的技术,例如现有的基于排序的算法可以通过一种基于颜色的修剪技术进行优化,从而得到一组基于颜色排序的算法。此外现有的近似算法还包括Turn-Shadow算法13和ERS算法14等。2 基础知识 普通图中的团定义为点集中的点两两之间都有边相连。然而超图中边的大小一般大于等于2,两两邻接关系不再适合应用在超图中,不能充分利用超图中所承载的信息。虽然一些数学领域的
14、研究人员已经提出了关于超图团的一些相关定义15,但只是进行了超图上最大可能出现的团的数量的证明,而目前超图上的团和极大团算法还没有有效的社区搜索算法出现。结合数学领域的超图团的定义,下面给出本文中的在r-uniform超图(指超图中所有超边都只包含r个点)上的超图团和极大团定义。定义1 超图团和极大团。超团hclique是r-uniform超图G中的一个超点子集,使超团中任意r个不同的超点都可以组成超图G中的一条边。如果一个超团不被其他任一超团所包含,即它不是其他任一超团的真子集,则称该团为r-uniform超图G的一个极大超团(maximal hclique)。若一个超团中包含k个点,则该超
15、团被称为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 算法无法
16、直接应用于超图。下面具体分析将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同时参与构成了一
17、条超边,但这3个点在二元关系邻接表中保存为了相同的状态。显然二元关系的邻接表不能充分诠释超图中的关系,造成了信息丢失。2)普通图极大团Bron-Kerbosch算法中涉及结果集、候选集和禁止集3个集合,如何合理地结合超图和超图极大团的定义、推广Bron-Kerbosch算法的思想,对这3个集合赋予新的意义也是一个需要解决的主要问题。3.2超图团的数据结构本文提出了一种新的模式来定义邻接关系,首先定义一个超点组和超点组的邻接关系。定义2 超点组。对于r-uniform超图上的一条超边e,它包含的 r 个点中任取r-1个点可以组成一个超点组,也称hgroup。定义3 超点组的邻居。对于r-unif
18、orm超图上的一条超边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所示
19、。此时的 hgroup邻接表比较完整地保存了超图中的原有信息。与二元关系保存的邻接表相比,hgroup充分保留了超图中的多元关系,对于不同邻接状态可以在hgroup邻接表中存储为图14-超团Fig.1Four-hclique2320第 8 期徐兰天等:面向超图的极大团搜索算法不同的形态,比较好地解决了二元邻接表中邻接关系不同,但储存的邻接表结构相同的问题。3.3面向超图团的改进Bron-Kerbosch算法基于前文中的数据结构和超图极大团的定义,以及对普通图Bron-Kerbosch算法的分析,本文提出了Bron-Kerbosch算法面向超图团的改进策略。普通图Bron-Kerbosch算法的
20、输入参数主要是结果集、候选集和禁止集,分别表示为R、P和X,其中P初始化为原图G中的 所 有 节 点,而 R、X 则 初 始 化 为 空 集。此 后,普 通 图Bron-Kerbosch算法会把集合P中的点逐个加入集合R中。然而在超图极大团算法中却并不能采用这样的方法,因为本文定义的超图的邻接表结构是基于hgroup-vertex的key-value关系,这使求超图极大团的算法在启动时应采取不同的设计形式。本文算法将超图 Bron-Kerbosch算法分为算法启动模块和算法递归模块两个模块。算法启动模块如算法1所示,需要算法启动模块的主要原因是,在超图极大团算法中第一轮加入集合R的不是一个超点
21、,而是一个超点组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)执行结束并返回时,算法已经枚
22、举了包含这个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算法(可替换为BKHp
23、ivot/算法)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中的超点,
24、然而由于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 hgnei
25、bour 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)Rnod
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 面向 超图 极大 搜索 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。