1.本发明涉及图计算技术领域,特别是涉及图的极大团枚举技术领域,尤其涉及一种基于分布式系统的极大团枚举方法和装置。
背景技术:
2.近年来,随着信息技术的发展,各种大数据普遍存在实际应用中,例如:社交网络,web网络,生物网络等等。这些各种各样的大数据系统可以表示为图。例如,web网络是有超链接互联的网页构成的图;社交网络图中可将人作为顶点、他们的关系作为边;生物网络图中可将生物化学分子作为顶点、它们之间的反应作为边。从这些网络的图中提取出隐含的稠密子结构是网络分析中的一个基本问题,例如:从社交网络中挖掘出社交圈子,在web网络中发现关键重要的网站,以及在生物网络找出蛋白络合物等等。目前人们在网络图挖掘的领域中提出了许多模型来提取网络中的稠密子图,其中比较经典的模型为极大团模型,极大团表示图中的极大完全图,也就是说每两个点之间都要有边相连。
3.由于目前要处理的图越来越大,越来越复杂,单机系统的算法已经不足以满足当前的图处理需求。现在主要有三种类型的算法来处理极大团枚举问题,第一种是线性的内存算法,第二种是线性的外存算法,第三种是分布式的并行算法。由于线性的内存算法和线性的外存算法计算比较慢,且不适用于大图,因此针对大的图,目前大多采用分布式的并行算法。但是很多现有的分布式并行算法要求在每台机器上各存储一份完整的图,还可能由于节点度数的差异存在负载不均衡的问题。针对这种情况,yanyan xu等人提出了一种基于mapreduce的分布式算法,该基于mapreduce的分布式算法系统中,需要有一台机器作为主节点(master),而其他都是从节点(worker)。在算法执行时,首先要赋予每个顶点互不相同的id值,该id值可以用多种方式来定义,如度数或degeneracy序等。在任意一个极大团里,必然有一个顶点拥有该团中最小的id值,算法以此为理论基础,对每个顶点搜索以它为最小id值的极大团。
4.这个算法一共分为两个阶段。第一阶段,进行数据分发阶段(map阶段),该阶段处理顶点的id和邻接表信息,这是为了获得顶点v以及顶点v的邻居中id值比顶点v大的那些顶点信息。主节点将任务分发给从节点,所有的从节点分别将自己活得的所有信息写进预先指定好的中间文件或者本地磁盘中等待下一步的操作。第二阶段,在节点上进行极大团的搜索(reduce阶段),从节点首先等待主节点分配任务,然后分别远程读取第一阶段中所存储下来的顶点信息,并利用它们来进行搜索。具体而言,以每个顶点v的id,邻接表,以及id比顶点v大的顶点的邻居顶点作为搜索的初始信息,通过搜索树来寻找极大团。其中,每个顶点通过只对比自己id大的节点进行搜索来防止重复搜索,同时,算法通过一定的数据结构来记录已经搜索过并且可以加入当前团的顶点,用来判断当前团是不是极大的。
5.在整个算法运行的过程中,由主节点来负责整个算法的调度,它将顶点的任务简单地平分到每个从节点上。从节点无法直接进行信息交互,信息交互只发生在主节点和从节点之间,因此需要有一个主节点来进行资源的调度与管理,当处理算法的集群较小时,这
会造成资源的浪费,且主节点的存在大大增加的系统的维护代价。
6.此外,该基于mapreduce的分布式算法需要进行大量的磁盘io/远程拷贝,不利于实时计算,这常常还带来巨大的通信代价,在通信上占据较多的时间,且对带宽的要求较高。该算法的执行效率有待于进一步提高。
技术实现要素:
7.鉴于现有技术中存在的问题,本发明实施例提供了一种基于分布式系统的极大团枚举方法和装置,以大大提高了极大团枚举的执行效率,并降低了网络开销。
8.本发明的技术方案如下:
9.一种基于分布式系统的极大团枚举方法,该方法包括以下步骤:
10.基于无向无权图中顶点的属性或位置进行编号,使得属性或位置相近的节点编号相邻;
11.将重新编号后的顶点集合按照编号分为多个连续的编号区间;
12.将所述各个连续的区间对应的顶点集合分配给各个节点,使得每个节点对应一个编号区间;
13.确定无向无权图中各顶点的id值;
14.在图计算过程中,在主副本所在的节点和对应镜像副本所在的节点间进行信息传递,以使得各节点基于传递的信息获得各主副本的第一邻居列表,所述第一邻居列表包括当前主副本的、id比当前主副本自身id大的邻居的列表;
15.各节点获得各个主副本顶点的邻接表,基于获得的邻接表信息利用搜索树进行极大团的枚举。
16.在本发明一实施例中,所述在主副本所在的节点和对应镜像副本所在的节点间进行信息传递,以使得各节点基于传递的信息获得各主副本的第一邻居列表,包括:确定当前活跃边集处于稀疏状态还是稠密状态;在活跃边集处于稀疏状态的情况下,所述由所述镜像副本对应的主副本所在的节点向所述镜像副本所在的节点推送主副本信息,所述镜像副本所在的节点基于接收的主副本信息更新所述镜像副本所在节点上的主副本的第一邻居列表;在活跃边集处于稠密状态的情况下,镜像副本所在的节点统计该节点中镜像副本的所有第一邻居列表,并将生成的邻居列表传递给对应的主副本。
17.在本发明一实施例中,利用多点接口mpi在主副本所在的节点和对应镜像副本所在的节点间进行信息传递。
18.在本发明一实施例中,所述利用多点接口mpi在主副本所在的节点和对应镜像副本所在的节点间进行信息传递,包括:使用专门线程来利用多点接口mpi在主副本所在的节点和对应镜像副本所在的节点间进行信息传递;所述各节点获得各个顶点的邻接表,基于获得的邻接表信息利用搜索树进行极大团的枚举,包括:对于节点中的任一顶点,如果该节点已经获得了对该任一顶点进行枚举所需的完整信息,则就该顶点进行极大团的枚举。
19.在本发明一实施例中,所述基于获得的邻接表信息利用搜索树进行极大团的枚举的步骤包括:
20.各节点针对所拥有的每一个主副本,从候选顶点集合中选择一个顶点,所述候选集合包括针对当前主副本尚未被搜索过的、既是当前主副本的邻居、id又比当前主副本大
的顶点;
21.如果选择的顶点与当前正在被枚举的团中的每一个顶点都有边相连的顶点,则将该选择的顶点加入到当前正在被枚举的团中;
22.将候选顶点集合与选择的顶点的邻居当中既是当前主副本的邻居其id又比当前主副本大的顶点集合进行交操作,并将交操作的结果加入当前正在被枚举的团中;
23.将已经被搜索过并且可以被加入到当前正在被枚举的团的第二顶点集合与选择的顶点的邻居当中既是当前主副本的邻居其id又比当前主副本大的顶点集合进行交操作,基于交操作的结果更新所述第二顶点集合。
24.在本发明一实施例中,所述方法还包括:利用主元(pivot)进行剪枝操作,该步骤包括:选择一个顶点作为主元;在所述候选顶点集合中去掉所选择的顶点的邻居中既是当前主副本的邻居、其id又比当前主副本大的顶点集合。
25.在本发明一实施例中,所述选择一个顶点作为主元包括:对当前候选顶点集合中的顶点,先选取该候选顶点集合中既是当前主副本的邻居、其id又比当前主副本大的顶点集合;对选取的集合进行贪心着色,选择着色最多的交集对应的顶点u作为主元。
26.在本发明一实施例中,所述方法还包括:使用位图(bitmap)来进行顶点的记录。
27.本发明的另一方面,还提供一种基于分布式系统的极大团枚举装置,该装置包括处理器和存储器,所述存储器中存储有计算机指令,所述处理器用于执行所述存储器中存储的计算机指令,当所述计算机指令被处理器执行时该装置实现如前所述方法的步骤。
28.本发明的另一方面,还提供一种计算机可读存储介质,其上存储有计算机程序,该计算机程序被处理器执行时实现如前所述方法的步骤。
29.本发明的基于分布式系统的极大团枚举方法和系统,充分考虑到了顶点的局部性等信息,减少了大量信息传递,提高了分布式团枚举算法的效率,能根据图数据快速计算出结果;并且,算法不需要多余的调度服务器来进行任务分配,在读图的过程中就自动进行了图的分割。
30.更进一步的,本发明的方法和系统可利用双模式引擎寻找比顶点v大的顶点列表,能够大大减少主副本更新时的数据竞争,减小了为了维护并发修改正确性导致的开销。
31.本发明的附加优点、目的,以及特征将在下面的描述中将部分地加以阐述,且将对于本领域普通技术人员在研究下文后部分地变得明显,或者可以根据本发明的实践而获知。本发明的目的和其它优点可以通过在书面说明及其权利要求书以及附图中具体指出的结构实现到并获得。
32.本领域技术人员将会理解的是,能够用本发明实现的目的和优点不限于以上具体所述,并且根据以下详细说明将更清楚地理解本发明能够实现的上述和其他目的。
附图说明
33.此处所说明的附图用来提供对本发明的进一步理解,构成本技术的一部分,并不构成对本发明的限定。
34.图1为本发明实施例的基于分布式系统的极大团枚举方法的流程示意图。
35.图2为本发明实施例中基于双模式引擎来在节点间信息传递,由节点获得各顶点的邻居列表的流程示意图。
36.图3为本发明实施例中采用双模式引擎在节点间进行信息传递的示意图。
37.图4为有8个顶点的无向无权图的示例。
具体实施方式
38.为使本发明的目的、技术方案和优点更加清楚明白,下面结合实施方式和附图,对本发明做进一步详细说明。在此,本发明的示意性实施方式及其说明用于解释本发明,但并不作为对本发明的限定。
39.在此,还需要说明的是,为了避免因不必要的细节而模糊了本发明,在附图中仅仅示出了与根据本发明的方案密切相关的结构和/或处理步骤,而省略了与本发明关系不大的其他细节。
40.应该强调,术语“包括/包含”在本文使用时指特征、要素、步骤或组件的存在,但并不排除一个或更多个其它特征、要素、步骤或组件的存在或附加。
41.现有的基于mapreduce的分布式算法不仅需要进行大量的磁盘io/远程拷贝,不利于实时计算、通信代价高、对带宽的要求较高,而且,该分部式算法需要有一个主节点来进行资源的调度与管理,当处理算法的集群较小时,这会造成资源的浪费,且主节点的存在大大增加的系统的维护代价。进一步地,该分部式算法没有充分考虑和利用到顶点的局部性。
42.处理大图数据是目前比较热门的问题,因此高效的处理算法对图数据分析是至关重要的。本发明针对现有的基于mapreduce的极大团枚举算法的不足之处,提出了一种新的基于分布式系统的极大团枚举方法。优选地,为了信息传递的高效性,考虑到不同的边的密集程度,本发明实施例还利用双模式引擎来进行一部分信息的传递。同时,本发明在设计算法时充分考虑到了节点的局部性,在存储和计算上将其局部性的优势最大化,尽可能地减少信息传递。在本发明实施例的算法实施过程中,每个服务器都处于平等的地位,不需要一个主(master)服务器来对资源进行调度。
43.图1为本发明实施例的基于分布式系统的极大团枚举方法的流程示意图,用于针对一个给定的图g=(v,e),计算其所有的极大团。如图1所示,该方法包括以下步骤:
44.步骤s110,基于无向无权图中顶点的属性或位置进行重新编号,使得属性或位置相近的节点编号相邻。
45.给定一个无向无权图,例如用g=(v,e)表示,其中v和e分别表示图中顶点和边的集合。对于图中的每一个顶点v,需要赋予一个独一无二的id(v),例如,可以简单地基于顶点的度(d)或degeneracy序来获得id(v),但本发明并不限于此。对于v中的任意顶点v,其邻居表示如下:
46.(1)如果顶点u和顶点v在图g上有边相连,那么顶点u就被称为顶点v的邻居,顶点v的邻居可以表示为:adj(v)={u:(u,v)∈e}。
47.(2)如果顶点u是顶点v的邻居,并且顶点u的id值小于顶点v的id值,那么顶点u就被称为秩小于顶点v的邻居。顶点v的邻居中秩小于顶点v的邻居表示为:adj(<v)={u:u∈adj(v),id(u)<id(v)}。
48.(3)如果顶点u是顶点v的邻居,并且顶点u的id值大于顶点v的id值,那么顶点u就被称为秩大于顶点v的邻居。顶点v的邻居中秩大于顶点v的邻居表示为:adj(>v)={u:u∈adj(v),id(u)>id(v)}。
49.本发明若用m(g)来表示图g中的所有极大团,用mv来表示m(g)中以顶点v为id值最小的顶点的一系列极大团,则mv={c:c∈m(g),v=argmin
u∈c
id(u)},其中,c为mv中的任何一个极大团,
″
v=argmin
u∈c
id(u)
″
表示顶点v属于c并且顶点v为极大团c的所有顶点中id值最小的顶点,即id(v)=min{id(u):u∈c}。
50.在本发明一实施例中,图g中各个节点的id值可以在步骤s110之前就计算出了,也可以在后面的s130中再进行计算。
51.本发明采用分布式的方式对图信息进行存储。由于许多现实世界的大规模图具有天然的局部性,如图中顶点的语义属性、顶点位置等具有局部性,因此,本发明实施例中,考虑节点的局部性,将图进行预处理,将基于图g中顶点的属性或位置进行重新编号,如利用搜索等方式将图g中顶点的属性或位置相近的顶点重新赋予相邻的顶点编号,使得属性或位置相近的节点编号相邻。在重新编号后,会使得邻接的顶点很可能在编号上也十分接近。其中,顶点的属性例如可以是顶点的局部语义属性,但本发明并不限于此。顶点的位置例如可以是顶点在整个图中处于的位置(边缘或中心)。
52.步骤s120,将重新编号后的顶点集合按照编号分为多个连续的编号区间,并将各个连续的编号区间对应的顶点集合分配给各个节点,使得每个节点对应一个编号区间。
53.本步骤中,将重新编号后的顶点集合按照步骤s110中得到的新编号划分为若干连续的编号区间(或称连续的块),能有效地在每个编号区间构成的子图上保有原图的局部性。
54.在将顶点集合v划分成若干个连续的编号区间后,将各编号区间对应的顶点集合分配给各个节点。本发明实施例中,在划分区间时并不仅仅以顶点个数作为考量,为了保证负载均衡,还考虑了每个顶点的边数,使所有顶点均衡地分布到所有节点上。这样的块式划分能以极小的代价实现系统的可扩展性。也就是说,当算法要处理的数据量大大增加时,完全可以通过增加机器(节点)来进行处理更大的数据,块式划分依然可以有效地对总体任务进行划分。由于块式划分会将一段连续编号的顶点分配到一个节点上,因此本发明只需要在每个节点上记录一些简单的数据,比如分配顶点区间的起始顶点编号和分配的顶点总数,就可以完成顶点宿主查询等一系列经常调用的基本操作。
55.在各个节点存储顶点信息时,一个顶点会以两种方式出现:主副本或镜像副本。如果顶点a被分配到一个节点a(即该节点a拥有该顶点a),那么在该节点a上,这个顶点a被称为主副本,相应节点a负责维护该主副本顶点a的状态和数据;而如果这个顶点a与被分配到其他节点b的其他顶点b之间有相邻的边存在,那么这个其他节点b上就会存在这个顶点a的镜像副本。同样,顶点b在节点b上被称为主副本,在节点a上被称为镜像副本。在已有方案中,每个从节点(worker)读取自己要进行处理的数据,而不与其他的从节点相互,将中间结果全部写入到中间件(或本地磁盘)中,再由从节点重新读取这些结果进行下一步搜索操作,由于主节点的调度,对一个顶点进行第二阶段搜索的从节点和对其进行第一阶段处理的从节点可能并不是同一个,所以图数据并不是在整个过程中都被存储在内存中,而需要多次进行读取,这常常带来巨大的通信代价。
56.而本发明实施例中,在存储和计算上将其局部性的优势最大化,能尽可能地减少信息传递。
57.步骤s130,确定无向无权图中各顶点的id值。
58.在本发明其他实施例中,确定顶点id的步骤也可以在步骤s110分割顶点之前进行,即在顶点重新分割并编号之前就已经确定了各个节点的id值。
59.步骤s140,在图计算过程中,在主副本所在的节点和对应镜像副本所在的节点间进行信息传递,以使得各节点基于传递的信息获得各主副本的第一邻居列表。
60.对于一个无向图g=(v,e),搜索极大团的任务会被分为很多子任务分配到各个节点上,让每个节点以自身拥有的主副本搜索极大团。但是由于图g并不是在每个节点上都完全存储的,每个节点上只存储了一部分的图信息,因此不同节点之间必须进行交互来完成一部分信息传输的目的。
61.本发明不利用远程读取这样的方式来进行信息交互,因此避免了速度缓慢的磁盘io。在本发明的一示例中,可利用使用多点接口(mpi)在节点之间直接进行信息传递,由于顶点的局部性,每个节点所需的大多数信息其实就存储于自身的机器上,不需要向其他节点获取,仅传输每个节点所需的小部分信息,这就避免了大量的信息传递。因此,在进行搜索前,需要先计算出每个节点各自需要的信息有哪些。下面说明每个节点需要的信息。
62.由于各节点要基于自己拥有的主副本来进行极大团搜索,即自身拥有的主副本都将是枚举的极大团中id最小的,因此,本发明实施例中,各主副本的第一邻居列表将包括当前主副本的、id比当前主副本自身id大的邻居的列表。例如,对于主副本顶点v,其第一邻居列表可表示为:adj(>v)={u:u∈adj(v),id(u)>id(v)}。
63.更具体地,在本步骤中,通过节点间信息的传递,可使得镜像副本获得对应的主副本信息并根据对应的主副本信息更新镜像副本所在节点上的主副本的第一邻居列表;或者可使得镜像副本获得所在节点上镜像副本的第一邻居列表并传递给对应的主副本。
64.本步骤中,可以采用双模式引擎来在节点间信息传递,由节点获得所拥有的各顶点的第一邻居列表。具体可包括:
65.步骤s141,确定当前活跃边集处于稀疏状态还是稠密状态。
66.活跃边集存在稀疏和稠密两种状态。在图计算过程的某个给定时刻,可根据活跃边集大小(即所有活跃顶点的度之和)与总边数|e|的比例,确定当前活跃边集处于稀疏和稠密两种状态。在本发明实施例中,不同状态的活跃边集采用不同的更新传递模型。
67.步骤s142,在活跃边集处于稀疏状态的情况下,由一个节点的主副本向对应的镜像副本所在的其他节点推送所述主副本的信息,对应镜像副本所在的节点基于接收的主副本信息更新所述镜像副本所在节点上的主副本的第一邻居列表。
68.具体而言,当活跃边集处于稀疏状态时,本发明的分布式系统更适合使用推送的处理模式,简称推送模式。在推送模式下,节点会将其拥有的主副本的信息推送给对应的镜像副本所在的其他节点,然后由所述其他节点基于接收的信息更新自己的主副本的信息,例如,接收到别的节点推送的主副本信息(如主副本编号id)的各节点基于接收的主副本信息更新自己的主副本的第一邻居列表。在稀疏状态下,系统中活跃的边数量较少。当一个节点从其他节点接收到其镜像副本对应的主副本推送来的信息之后,可以基于推送的信息更新当前节点所拥有的主副本的邻居列表,该邻居列表包括当前主副本的、id比当前主副本自身id大的邻居的列表。由于这个邻居的数量较小,因此开销较低。
69.图3为采用双模式引擎在节点间进行信息传递的示例。如图3所示,黑色表示该顶点为镜像副本,白色表示该顶点为主副本。虚线表示的是节点之间发生的信息传递,而实线
则只是在节点内发生的工作。在稀疏模式中,如图3的左侧部分所示,镜像副本v与两个未示出编号的其他顶点的主副本位于同一个节点上。拥有主副本v的节点通过稀疏信号(sparsesignal)将该主副本v的顶点编号vtx和顶点id,也就是(vtx,id(vtx)),作为要传递的消息推送给对应的镜像副本v所在的节点,拥有对应镜像副本的节点收到消息之后,通过稀疏间隙(稀疏响应)(sparseslot)对节点上存储的邻居信息进行遍历,比较两者的id信息,如果周围的主副本id比收到的id(vtx)小,那么就将vtx写入到该主副本拥有的邻居队列表里。在此例中,主副本v将自己的编号和id值,也就是(vtx,id(vtx)作为消息发送给它的镜像副本v,镜像副本v在收到这个消息之后,遍历自己的两个邻居,如果发现自己的id比邻居的id大,就把自己加入到其邻居(主副本)的第一id列表adj(>v)里,该第一邻居列表包括该主副本的邻居当中、id比当前主副本自身id大的邻居。
70.步骤s143,在活跃边集处于稠密状态的情况下,镜像副本所在的节点统计该节点中镜像副本的所有第一邻居列表,并将生成的邻居列表传递给对应的主副本。
71.当活跃边集处于密集状态时,本发明的分布式系统采用拉取的处理模式,简称拉取模式。稠密状态的活跃边集能从拉取模式获得更高的收益,在拉取模式下,节点针对每个镜像副本,都是从邻居处收集信息来完成自身状态和数据的更新,然后由镜像副本对应的主副本拉取这个更新的信息来完成对主副本的更新。由于一个主副本很可能有多个镜像副本,在存在多个镜像副本更新主副本时会产生数据竞争,不可避免地会使用数据锁,而数据锁在一定程度上会降低效率。但在拉取模式下,由于一个主副本拥有的镜像副本数最多与节点数量相同,因此大大减少了更新时的数据竞争,减小了为了维护并发修改正确性导致的开销。
72.在拉取模式中,如图3的右侧部分所示,每个镜像副本通过密集信号(densesignal)统计在该节点中拥有的所有id值比自身大的顶点列表,然后通过密集间隙(denseslot)将这个列表发送给它的主副本,由各个镜像副本从所在节点获得而来的顶点的列表的集合组成了主副本v的第一邻居列表adj(>v)。如图3所示,镜像副本所在的节点首先通过遍历该镜像副本的邻居完成对镜像副本的更新,也就是收集邻居中所有id比镜像副本v大的顶点编号,在收集完之后,镜像副本所在节点将镜像副本收集到的部分信息通过节点间信息传递发送给对应主副本所在的节点,由主副本所在的节点进行整理汇合,得到主副本的第一邻居列表adj(>v)。
73.本发明实施例在双模式引擎的基础上来统计顶点v的比顶点v的id值大的邻居,用于下一步获得顶点的邻接表的操作。
74.步骤s150,各节点获得各个主副本顶点的邻接表,基于获得的邻接表信息利用搜索树进行极大团的枚举。
75.对于mv中的任何一个极大团c,由于v都是团中id最小的,所有c\{v}以外的顶点都应该属于adj(>v)。为了计算极大团c,需要知道对于团中的任意两个顶点,边(u,w)是否属于边集e。因此,需要获得u∈adj(>v)的所有adj(u)。在验证极大团时,需要完整的adj(u)和adj(v)信息,这是因为,一些顶点w(w∈adj(u)并且w∈adj(v),id(w)<id(v))会被用来判断极大性。例如,假设{u,v}的超集{w,u,v}是一个团,如果没有顶点w的信息,算法就会错认为{v,u}是一个极大团。
76.在通过前述步骤s140得知了节点上主副本的第一邻居列表adj(>v)之后,下一步
就是要获得这些顶点的邻接表。mv需要的邻接表为:
77.{(u,adj(u)):u∈adj(>v)}∪{(v,adj(v))}。
78.本发明实施例中,由于顶点分布的局部性,团中的一大部分顶点可能都位于同一台服务器上,对于这些顶点,可以很方便的直接获得它们的邻接表,免去服务器之间邻接表传递的花销。对于不得不进行的信息传递,本发明可使用多点接口(mpi)来使用专门的线程实现邻接表的发送和接收。在发送和接收信息的同时,已经获得全部邻接表信息的顶点节点便可以开始进行搜索,进行极大团的枚举。而此时其他顶点的信息收集工作就与枚举工作发生了重叠。相较于现有线性的处理方式(先收集全部信息,再依次进行枚举),这样的调度方式隐藏了一部分的通信代价。本发明实施例中,通过创建一个进程来进行信息接收,另一个进程来进行信息发送。如果一个顶点所需的全部邻接表信息都已经获得,那么这个顶点所在的节点就可以直接利用已经获得的信息基于该顶点开始进行团枚举。
79.基于获得的邻接表信息利用搜索树进行极大团的枚举可以采用现有的极大团枚举方法来实现,优选使用搜索树在进行极大团的枚举。搜索树是一种简单的树形枚举方式,通过不断地递归搜索来进行查找。
80.由于对mv中的任何一个团c,都有因此,要枚举mv中的极大团,需要求图g中的顶点u邻居adj(u)与id值大于顶点v的id值的顶点v的邻居adj(>v)的交集,即adj(u)∩adj(>v)。本发明实施例中,用adj
>v
[u]表示顶点u的邻居中即是v的邻居同时id比v大的顶点。此外,为了判断团的极大性,还需要计算adj(u)∩adj(v),本发明用adjv[u]表示u的邻居中也是v的邻居的顶点。以上信息作为搜索的初始信息被传入搜索函数中。
[0081]
在搜索过程中,用c来代表当前正在被枚举的团信息,用“candidates”来代表可以被加入当前团的候选顶点集合,用“prev”来代表之前已经被搜索过并且可以被加入到当前团的顶点集合。那么一开始c里仅包含一个顶点v,candidates集合中包含了adj(>v)的所有顶点。然后算法重复下面的步骤直到candidates集合为空:从candidates集合里取一个顶点u,如果确定顶点u和c中的每一个顶点都有边相连,则将顶点u加入集合c中。当candidate集合为空并且prev节点也为空时就说明算法找到了一个极大团。
[0082]
当算法把顶点u加入当前团c时,需要更新candidates。将candidates集合与adj
>v
[u]进行交操作。与此同时,通过把prev和adjv[u]进行交操作来更新prev集合,这是因为如果存在另一个极大团c
″
存在,它使c
′
无法成为极大团,这就说明(c
″
\c
′
)一定是adjv[u]的子集。
[0083]
由于mv是以v为最小顶点的所有极大团,那么m(g)就是所有mv的并集,即m(g)=∪
v∈vmv
。
[0084]
通过如上步骤,便获得了无向无权图的所有极大团。
[0085]
为了进一步进行优化,本发明还可利用主元(pivot)进行剪枝。pivot剪枝要求选定一个顶点u
p
作为pivot,然后在candidates里去掉adj
>v
[u
p
],使candidates的范围大大缩小,以此来减少搜索范围。pivot的选择对于剪枝效果的体现起到尤为重要的作用,本发明实施例采用了如下方式来选择pivot:对于当前的candidates集合里的顶点u,先取candidates中每个顶点的u的adj
>v
[u]。接下来对这个集合进行贪心着色,选择着色数最多的交集对应的顶点u作为这一轮的pivot。由于pivot剪枝技术已经在现有极大团搜索过程中使用,再次不再赘述。
[0086]
下面结合具体的示例来描述本发明实施例的基于分布式系统的极大团枚举方法。
[0087]
给定一个无向无权图g,整个算法总体分为两步,首先通过双模式获得所有顶点v的adj(>v),并获取对应的邻接表;然后,利用以上信息进行搜索。该算法的输入为图g,输出为所有极大团。
[0088]
在执行本发明的方法之前,可先部署一个集群,以具备代码运行的环境以及mpi和openmp的运行条件,其中,mpi是为了在机器之间进行发送和接收,而openmp是为了实现单台机器上上的多线程运行,加快运算效率。由于集群中每一台机器都处于相等的地位,可在每台机器上运行同样的代码。
[0089]
在集群部署完毕后,可执行如下操作:
[0090]
第一步:每个节点分别读取部分图信息,并记录自己的主节点区间以及主节点的邻接表信息,做好图的预处理工作。
[0091]
在每个节点(每台机器)上都执行一样的图读取工作,图读取工作首先读取全图并且记录下每个顶点的度数信息,记录度数信息是为了之后的节点分割工作,保证负载均衡。接下来各节点基于顶点的属性或位置将顶点进行分割,使得属性或位置相近的节点编号相邻,得到分割后的顶点对应的编号区间,并记录下哪些顶点位于自己这个节点中。如果一个节点包含多路处理器,还可对位于自己这个节点中的顶点再一次进行分割,得到多个连续的编号区间。例如,在一个包含s路处理器的节点上,可将顶点区间划分成s个更小的区间,并且将这些区间与每个处理器一一对应。这样的操作可以适当地分配计算数据到特定的处理器上,就能进一步提升计算的性能。
[0092]
第二步:每个顶点上的节点分别计算自己的id值。
[0093]
读图工作完成后,要进行顶点数据分发和收集工作。在进行完成数据分发和收集工作之前,需先计算每个顶点的id值,顶点的id值例如可以是基于顶点的度或degeneracy序来计算得到。在本发明实施例中,可在每个节点中使用openmp来计算每个顶点的id值,openmp用于多线程并行操作,可以加速程序的计算速度,帮助算法更快地计算出顶点id。计算完id之后,把id值收集到每个节点。
[0094]
在本发明另一些实施例中,计算顶点id的步骤也可以在分割顶点之前进行,即在顶点重新分割并编号之前就已经确定了各个节点的id值。
[0095]
第三步:接下来各节点利用双模式引擎来寻找比顶点v大的顶点列表。在稀疏状态下采用推送的方式,在密集状态下采用拉取的方式。
[0096]
每个节点通过双模式引擎获得它所拥有的顶点的所有邻居顶点的id信息,并获得每个顶点v的adj(>v)。
[0097]
第五步:服务器间发送邻接表信息。
[0098]
获得顶点列表后,可创建两个线程,使用mpi命令,一个用来接收邻接表,一个用来发送邻接表。
[0099]
第六步:利用搜索树进行搜索。其中,对于不同顶点,第五步和第六步时间上有一定程度的交叠。
[0100]
每个节点上要进行枚举的次数与其拥有的顶点个数有关。对于每一个节点上的顶点v,首先计算出adj
>v
[u]和adjv[u],候选集合等一系列值。利用这些值进行递归的搜索。在搜索的过程中,首先通过candidates集合和prev集合来判断是否已经找到了极大团。如果
candidates集合中还有顶点,则进一步将该顶点加入到当前团中,更新adj,candidates和prev等信息,用作下一步的搜索。
[0101]
由于在搜索的过程中,需要频繁地利用集合的交操作来更新一些数据结构,这是其中非常耗时的一部分,为了快速地判断顶点是否存在,本发明实施例使用bitmap来进行顶点的记录,这样节约了时间和空间。
[0102]
下面以图4中的顶点a为例,详细描述第六步操作的细节:
[0103]
输入:每个顶点v,顶点v的邻接表,adj(>v)的邻接表。针对图4所示的图,简单地以节点的度(d)来作为获得id的标准,如图4所示,d(a)=4,d(b)=6,d(c)=3,d(d)=4,d(e)=7,d(f)=3,d(g)=5,d(h)=2。以d小的id小为原则(如果d一样则顶点标号小的id更小)。可以得到id(h)=1,id(c)=2,id(f)=3,id(a)=4,i(d)=5,id(g)=6,id(b)=7,id(e)=8。从图上可得adj(a)={d,g,b,e},由于这些邻居的id全都大于a,因此adj(>a)={d,g,b,e}。极大团搜索过程如下:
[0104]
(1)对每个顶点u∈adj(>v),节点计算adj
>v
[u]和adjv[u]。adjv[u]表示顶点u的邻居中同时也为顶点v的邻居的顶点。以顶点b为例,顶点b的邻居顶点a,d,g,e,f,c,其中的d,g,e也为顶点a的邻居,因此adja[b]={d,g,e},而adj
>v
[u]表示顶点u的邻居中同时也为顶点v的邻居,并且id比顶点v大的顶点。显然,adj
>a
[b]={d,g,e}。同理可以得到其他顶点的adj
>a
[u]和adja[u]。
[0105]
(2)定义初始的团c={v},候选集合candidates,以及用于判断是否是极大团的prev集合。此时c={a},候选集合为adj(>a),即candidates={d,g,b,e}。prev集合为空集。
[0106]
(3)如果candidates集合和prev集合都为空,则说明找到了一个极大团。在第一层递归中,candidates集合大小为4,prev集合为空,因此搜索不会停止。
[0107]
(4)如果candidates不为空,则选择一个pivot顶点u
p
,定义集合u=candidates/adj
>vup
]。在第一层递归中,算法将在candidates={d,g,b,e}中寻找一个点作为pivot。先取candidates中每个顶点u的adj
>a
[u]。接下来对这个集合进行贪心着色,选择着色数最多的集合对应的顶点u作为这一轮的pivot。比如d的adj
>a
[d]里一共有{b,g,e}这三个点,经过贪心着色,着色数集合里一共有三个颜色,在此例中,d,g,b,e这四个顶点的着色数相同,因此随机选择顶点b作为pivot。根据定义集合u=candidates/adj
>v
|u
p
|,由于adj
>a
[b]={d,g,e},因此u={b}。
[0108]
(5)按照|adj
>v
[u]|从大到小的顺序对集合u中的顶点u进行排序。此例中,此时集合u中只剩下一个顶点b。
[0109]
(6)对于集合u中的每一个顶点u,创建一个新的candidates集合cand
′
,并且更新adj
>v
[u]为adj
′
>v
[u]。由于顶点u是未来要加入到团中的候选节点,因此,新的候选节点集合应该都为u的邻居。此例中u=b,因此对顶点b来说,cand
′
的值应当是candidates和adj
>a
[b]的交集,即cand
′
={d,g,e}。接下来更新adj
>v
[u],由于之后的搜索范围会限制在cand
′
中,因此可以通过将这个数据与cand
′
做交操作,来排除一些与cand
′
无关的数据。此时cand
′
中一共有三个顶点{d,g,e},最后从adj
>a
[d]={b,g,e}中得到adj
′
>a
[d]={g,e}。
[0110]
(7)利用新得到的信息进行递归搜索。在这一步中,算法步骤回到步骤(3),而递归的层数增加了一层。
[0111]
(8)在prev集合中加入顶点u。当在步骤(6)中以顶点b开始进行的搜索结束时,程序回退到这一步,并且将b加入prev集合。
[0112]
根据计算结果,可得到g中一共有三个极大团,分别是{a,b,d,e,g},{b,c,e,f},{e,g,h}。用mv,来表示以v为最小节点的一系列极大团,可以得到,mh={e,g,h},mc={b,c,e,f},ma={a,b,d,e,g}。
[0113]
本发明的基于分布式的极大团枚举算法,结合双模式引擎,可实现节点内和节点间的并行处理。本发明技术可用于大图数据分析领域,例如社交网络分析,web网络挖掘等。
[0114]
本发明的基于分布系统的极大团枚举算法,由于充分考虑到了节点的局部性等信息,减少了大量信息传递,因此还具有如下的效果:
[0115]
(1)只要提供需要的图数据就可以快速计算出结果;
[0116]
(2)不需要多余的调度服务器来进行任务分配,在读图的过程中就自动进行了图的分割。
[0117]
(3)本发明充分考虑到了顶点的局部性,减少了信息的传输量,提高了分布式团枚举算法的效率。
[0118]
与前述方法相应地本发明还提供一种基于分布系统利用双模式引擎的极大团枚举装置,该装置包括处理器和存储器,所述存储器中存储有计算机指令,该处理器用于执行所述存储器中存储的计算机指令,当所述计算机指令被处理器执行时该装置实现如前所述方法的步骤。
[0119]
本发明还涉及存储介质,其上可以存储有计算机程序代码,当程序代码被执行时可以实现本发明的方法的各种实施例,该存储介质可以是有形存储介质,诸如光盘、随机存储器(ram)、内存、只读存储器(rom)、电可编程rom、电可擦除可编程rom、寄存器、硬盘、可移动磁盘、cd-rom或技术领域内所公知的任意其它形式的有形存储介质。
[0120]
需要明确的是,本发明并不局限于上文所描述并在图中示出的特定配置和处理。为了简明起见,这里省略了对已知方法的详细描述。在上述实施例中,描述和示出了若干具体的步骤作为示例。但是,本发明的方法过程并不限于所描述和示出的具体步骤,本领域的技术人员可以在领会本发明的精神后,作出各种改变、修改和添加,或者改变步骤之间的顺序。
[0121]
本领域普通技术人员应该可以明白,结合本文中所公开的实施方式描述的各示例性的组成部分、系统和方法,能够以硬件、软件或者二者的结合来实现。具体究竟以硬件还是软件方式来执行,取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能,但是这种实现不应认为超出本发明的范围。当以硬件方式实现时,其可以例如是电子电路、专用集成电路(asic)、适当的固件、插件、功能卡等等。当以软件方式实现时,本发明的元素是被用于执行所需任务的程序或者代码段。程序或者代码段可以存储在机器可读介质中,或者通过载波中携带的数据信号在传输介质或者通信链路上传送。“机器可读介质”可以包括能够存储或传输信息的任何介质。机器可读介质的例子包括电子电路、半导体存储器设备、rom、闪存、可擦除rom(erom)、软盘、cd-rom、光盘、硬盘、光纤介质、射频(rf)链路,等等。代码段可以经由诸如因特网、内联网等的计算机网络被下载。
[0122]
还需要说明的是,本发明中提及的示例性实施例,基于一系列的步骤或者装置描
述一些方法或系统。但是,本发明不局限于上述步骤的顺序,也就是说,可以按照实施例中提及的顺序执行步骤,也可以不同于实施例中的顺序,或者若干步骤同时执行。
[0123]
本发明中,针对一个实施方式描述和/或例示的特征,可以在一个或更多个其它实施方式中以相同方式或以类似方式使用,和/或与其他实施方式的特征相结合或代替其他实施方式的特征。
[0124]
以上所述仅为本发明的优选实施例而已,并不用于限制本发明,对于本领域的技术人员来说,本发明实施例可以有各种更改和变化。凡在本发明的精神和原则之内,所作的任何修改、等同替换、改进等,均应包含在本发明的保护范围之内。
技术特征:
1.一种基于分布式系统的极大团枚举方法,其特征在于,所述方法包括以下步骤:基于无向无权图中顶点的属性或位置进行编号,使得属性或位置相近的节点编号相邻;将重新编号后的顶点集合按照编号分为多个连续的编号区间,将所述各个连续的区间对应的顶点集合分配给各个节点,使得每个节点对应一个编号区间;确定无向无权图中各顶点的id值;在图计算过程中,在主副本所在的节点和对应镜像副本所在的节点间进行信息传递,以使得各节点基于传递的信息获得各主副本的第一邻居列表,所述第一邻居列表包括当前主副本的、id比当前主副本自身id大的邻居的列表;各节点获得各个主副本顶点的邻接表,基于获得的邻接表信息利用搜索树进行极大团的枚举。2.根据权利要求1所述的方法,其特征在于,所述在主副本所在的节点和对应镜像副本所在的节点间进行信息传递,以使得各节点基于传递的信息获得各主副本的第一邻居列表,包括:确定当前活跃边集处于稀疏状态还是稠密状态;在活跃边集处于稀疏状态的情况下,所述由所述镜像副本对应的主副本所在的节点向所述镜像副本所在的节点推送主副本信息,所述镜像副本所在的节点基于接收的主副本信息更新所述镜像副本所在节点上的主副本的第一邻居列表;在活跃边集处于稠密状态的情况下,镜像副本所在的节点统计该节点中镜像副本的所有第一邻居列表,并将生成的邻居列表传递给对应的主副本。3.根据权利要求1所述的方法,其特征在于,利用多点接口mpi在主副本所在的节点和对应镜像副本所在的节点间进行信息传递。4.根据权利要求3所述的方法,其特征在于,所述利用多点接口mpi在主副本所在的节点和对应镜像副本所在的节点间进行信息传递,包括:使用专门线程来利用多点接口mpi在主副本所在的节点和对应镜像副本所在的节点间进行信息传递;所述各节点获得各个顶点的邻接表,基于获得的邻接表信息利用搜索树进行极大团的枚举,包括:对于节点中的任一顶点,如果该节点已经获得了对该任一顶点进行枚举所需的完整信息,则对该顶点进行极大团的枚举。5.根据权利要求1所述的方法,其特征在于,所述基于获得的邻接表信息利用搜索树进行极大团的枚举的步骤包括:各节点针对所拥有的每一个主副本,从候选顶点集合中选择一个顶点,所述候选集合包括针对当前主副本尚未被搜索过的、既是当前主副本的邻居、id又比当前主副本大的顶点;如果选择的顶点与当前正在被枚举的团中的每一个顶点都有边相连的顶点,则将该选择的顶点加入到当前正在被枚举的团中;将候选顶点集合与选择的顶点的邻居当中既是当前主副本的邻居其id又比当前主副本大的顶点集合进行交操作,并将交操作的结果加入当前正在被枚举的团中;将已经被搜索过并且可以被加入到当前正在被枚举的团的第二顶点集合与选择的顶
点的邻居当中既是当前主副本的邻居其id又比当前主副本大的顶点集合进行交操作,基于交操作的结果更新所述第二顶点集合。6.根据权利要求5所述的方法,其特征在于,所述方法还包括:利用主元进行剪枝操作,该步骤包括:选择一个顶点作为主元;在所述候选顶点集合中去掉所选择的顶点的邻居中既是当前主副本的邻居、其id又比当前主副本大的顶点集合。7.根据权利要求6所述的方法,其特征在于,所述选择一个顶点作为主元包括:对当前候选顶点集合中的顶点,先选取该候选顶点集合中既是当前主副本的邻居、其id又比当前主副本大的顶点集合;对选取的集合进行贪心着色,选择着色最多的交集对应的顶点作为主元。8.根据权利要求1所述的方法,其特征在于,所述方法还包括:使用位图来进行顶点的记录。9.一种基于分布式系统的极大团枚举装置,该装置包括处理器和存储器,其特征在于,所述存储器中存储有计算机指令,所述处理器用于执行所述存储器中存储的计算机指令,当所述计算机指令被处理器执行时该装置实现如权利要求1-8中任意一项所述方法的步骤。10.一种计算机可读存储介质,其上存储有计算机程序,其特征在于,该程序被处理器执行时实现如权利要求1至9中任意一项所述方法的步骤。
技术总结
本发明提供一种基于分布式系统的极大团枚举方法和装置,所述方法包括:基于无向无权图中顶点的属性或位置进行重新编号,使得属性或位置相近的节点编号相邻;将重新编号后的顶点集合按照编号分为多个连续的块;将多个连续的块分别分配给多个节点,使得每个节点对应一个块;确定无向无权图中各顶点的ID值;在主副本所在的节点和对应镜像副本所在的节点间进行信息传递,以使得各节点基于传递的信息获得各主副本的第一邻居列表,第一邻居列表包括ID比主副本ID大的主副本的邻居的列表;各节点获得各个主副本顶点的邻接表,基于获得的邻接表信息利用搜索树进行极大团的枚举。本发明考虑到了顶点的局部性等信息,减少了信息传递,提高了搜索效率。高了搜索效率。高了搜索效率。
技术研发人员:潘敏佳 李荣华 田群 戴永恒 刘学谦
受保护的技术使用者:电科云(北京)科技有限公司
技术研发日:2020.11.23
技术公布日:2022/5/25
转载请注明原文地址:https://tc.8miu.com/read-15008.html