分布式环境下动态图结构匹配的方法
分布式环境下动态图结构匹配的方法
【技术领域】
[0001]本发明涉及增量图结构匹配、分布式计算技术领域，具体涉及一种分布式环境下动态图结构匹配的方法。
【背景技术】
[0002]近年来，社交网络、社交媒体的流行，导致其数据量呈现爆炸式增长，对社交网络大数据的分析、研究也因而成为业界研究的热点问题。由于社交网络可以抽象为图结构一一用户可被视为图的顶点，用户之间的关系可被看作图的边，因此，基于图结构匹配的分析技术已成为社交网络分析的主要技术之一。
[0003]基于不同的应用场景，人们提出了多种图结构匹配语义，其中“子图同构”语义得到了广泛的应用，也成为本发明所采用的查询语义。然而，(1)基于“子图同构”语义的图结构匹配属于一类极难解决的问题一一NP完全问题；(2)社交网络的数据往往是分布式存储的，在分布式环境下，各站点间不得不通过传递数据来帮助求解，从而导致分布式环境下的图结构匹配计算十分复杂。
[0004]此外，社交网络是动态变化的，例如，不断有新边在网络中出现(新增的边被关联上时间戳，表明其出现的时刻)。为了对动态社交网络进行实时监控，一个重要且亟待解决的问题是:给定一个动态图G，模式图Q和时间窗口切，计算在tw时间区间内，G中所有与Q同构的子图g。如果把g中最早和最晚出现的边的时间差定义为i(g)，则T(g)〈 = tw。直观上看，该问题的一个解决方法为:对更新后的图GeAG反复进行子图同构计算，然而，考虑到(1)子图同构计算开销大；(2)计算请求十分频繁，因此该方法并不适用。此外，在动态网络环境下，人们往往对某一时间段内的匹配结果感兴趣，而非全部的，基于历史数据的匹配结果。
[0005]为了有效的克服以上困难，更加高效、便捷地对动态社交网络进行分析，我们提出了分布式环境下动态图结构匹配技术来有效解决以上问题。
【发明内容】
[0006]本发明克服了现有技术的不足，提供一种高效、便捷地对动态社交网络进行分析的分布式环境下动态图结构匹配的方法。
[0007]考虑到现有技术的上述问题，根据本发明公开的一个方面，本发明采用以下技术方案:
[0008]—种分布式环境下动态图结构匹配的方法，它包括:
[0009](a)建立由一个主机端和多个工作站点组成的支持支持全双工通信和多线程计算的分布式计算框架；
[0010](b)主机端向工作站点传递信息，并协调工作站点的工作；
[0011 ] (c)工作站点根据主机端传递的信息，计算本地匹配结果M1;
[0012](d)主机端回收各工作站点返回的部分结果Μ,，并汇总得到匹配结果Μ。
[0013]为了更好地实现本发明，进一步的技术方案是:
[0014]根据本发明的一个实施方案，所述主机端执行的步骤包括:
[0015]i)将模式图Q视为无向图，并计算直径d;
[0016]ii)对于每一个工作站点Si，主机端将对应的更新ΔΕ,*送到工作站点S1;
[0017]m)主机端汇总各工作站As,返回的结果吣，得到匹配结果μ。
[0018]根据本发明的另一个实施方案，所述工作站ASi执行的步骤包括:
[0019]i)声明空集合S;空图数据Gs;
[0020]? )对于一个工作站点Si对应的更新AEi中的每条边e= (u，u’)；
[0021]??)计算本地图Fi的子图Gsub (e)，Fi为对应的工作站点Si中的数据；
[0022 ]iv )将子图Gsub (e)中尚未包含在空集合S中的虚拟节点v_v放入空集合S中；
[0023]V )子图将Gsub(e)并入空图数据Gs中；
[0024]vi)对于空集合S中的所有虚拟节点V，向所有虚拟节点V所在的工作站点Sj请求信息;
[0025]vii)工作站点Si接收从工作站点Sj返回的子图G(v)，并与Gs合并；
[0026]vi)当所有请求得到返回后，对子图Gs，工作站点&调用VF2计算得到本地匹配结果Μι；
[0027]k)返回Μ至主机端。
[0028]根据本发明的另一个实施方案，所述工作站AS,执行的步骤还包括:
[0029]i)计算模式图Q中各节点u的拓扑排序；
[0030]? )选择模式图Q中与虚拟节点V标签相同且拓扑排序最大的节点u,构造点对(u,ν)；
[0031 ]iii )以(u，ν)为起始，遵循模式图Q的拓扑结构及节点标签，在Fi中进行宽度优先遍历，^为对应的工作站点&中的数据，并将遍历到的点与边放入子图G(v);
[0032]力)返回6(丫)。
[0033]本发明还可以是:
[0034]根据本发明的另一个实施方案，整个分布式计算采用UDP协议。
[0035]与现有技术相比，本发明的有益效果之一是:
[0036]本发明的一种分布式环境下动态图结构匹配的方法，支持全双工通信的分布式计算架构，以及各站点支持多线程计算，满足多任务运算的要求，使得计算高度并行化，实现了动态环境下高效率的分布式计算;从而更加高效、便捷地对动态社交网络进行分析。
【附图说明】
[0037]为了更清楚的说明本申请文件实施例或现有技术中的技术方案，下面将对实施例或现有技术的描述中所需要使用的附图作简单的介绍，显而易见地，下面描述中的附图仅是对本申请文件中一些实施例的参考，对于本领域技术人员来讲，在不付出创造性劳动的情况下，还可以根据这些附图得到其它的附图。
[0038]图1示出了根据本发明一个实施例的分布式环境下动态图结构匹配框图。
【具体实施方式】
[0039]下面结合实施例对本发明作进一步地详细说明，但本发明的实施方式不限于此。
[0040]在分布式环境下，高效率的对动态社交网络进行基于子图同构语义的结构匹配计算，其包括:(a)分布式计算框架；(b)基于动态网络图的分布式匹配计算。
[0041 ] (a)分布式计算框架:一个主-从(Master-Worker)结构，支持全双工通信的分布式计算架构。同时，各站点支持多线程计算，满足多任务运算的要求，使得计算高度并行化。
[0042](b)基于动态网络图的分布式匹配计算:主机(Master)端与工作站(Worker)端的算法，实现动态环境下高效率的分布式计算。
[0043]本方案具体如下:
[0044](一)分布式计算框架
[0045]分布式环境下，社交网络图G被存储在多个不同的站点，每个站点Si维护当前站点的数据F,。为了维持各片段间数据的连通性，对于跨站点的边e=(v，v’)(v属于FhV’属于FJ，在F冲保留了节点ν’的一个副本，并将其称为“虚拟节点”。通过“虚拟节点ν’”，可以向V’所在站点发送请求，来帮助当前站点获取必要的信息，并在本地进行结构匹配计算。
[0046]为了有效支持分布式环境下的运行计算，我们采用了如下计算框架。通过该框架，实现了站点间消息的异步传递，从而实现了图结构匹配的并行计算。具体框架结构如下:
[0047]计算框架由一个Master站点和多个Worker站点组成。其中，Master站点主要负责:
(1)向Worker站点传递消息，并协调Worker站点的工作；(2)回收各Worker站点返回的部分结果，并汇总。各Worker站点主要执行:(1)本地运算；(2)协同其它站点计算。此外，整个分布式计算采用UDP协议，实现了全双工通信。
[0048](二)基于动态网络图的分布式匹配计算
[0049]在上述计算框架下，我们设计了如下算法，在分布式环境下开展动态图结构匹配计算:
[0050]进程EvaMatch(在Master站点执行)
[0051 ]输入:时间窗口 tw，批量更新ΛΕ，模式图Q;
[0052]输出:匹配结果Μ;
[0053]1.将模式图Q视为无向图，并计算直径d(任意两点间最短距离的最大值)；
[0054]2.对于每一个Worker站点Si;
[0055]3.将对应的更新AEi发送到Worker站点Si ；
[0056]4.站点Si调用进程LocalEval (ΔΕι，Fi，Q，d，tw)计算本地匹配结果Mi ；
[OO57 ] 5.汇总各Worker站点返回的结果Mi ； [0058]6.返回Μ。
[0059]进程LocalEval(在Worker站点Si执行):
[0060]输入:本地更新AEi，本地图数据Fi，模式图Q及其直径d，Q时间窗口切。
[0061 ] 输出:本地匹配结果Mi。
[0062]1.声明空集合S;空图数据Gs;
[0063]2.对于AEi中的每条边e=(u，u，)；
[0064]3.计算本地图Fi的子图Gsub(e);
[0065]4.将Gsub (e)中尚未包含在S中的虚拟节点v_v放入S中；
[0066]5.将Gsub(e)并入 Gs;
[0067]6.对于S中的所有虚拟节点ν，向ν所在站点Sj请求信息；
[0068]7.接收从Sj返回的子图G(v)，并与Gs合并；
[0069]8.当所有请求得到返回后，对子图Gs，调用VF2计算本地匹配结果Μ;
[0070]9.返回Μ至Master。
[0071 ]进程Findlnfo(在Worker站点Si执行):
[0072 ]输入:节点ν，本地图数据Fi，模式图Q及其直径d，时间窗口 tw。
[0073]输出:子图G(v)。
[0074]1.计算Q中各节点u的拓扑排序；
[0075]2.选择Q中与ν标签相同且拓扑排序最大的节点u,构造点对(u，v)；
[0076]3.以(u，v)为起始，遵循Q的拓扑结构及节点标签，在Fi中进行宽度优先遍历，并将遍历到的点与边放入G (ν);
[0077]4.返回 G(v)。
[0078]参见图1所示，以下对上述算法进行进一步说明Jaster站点首先执行EvaMatch来启动计算。考虑到边e更新所造成的影响范围不超过Q中最长的两点间距离(将Q视为无向图)，因此，EvaMatch首先计算无向图Q的直径d。随后，Master站点将更新AEi发送至对应的Worker站点Si，同时触发站点Si的LocalEval进程。当收集到所有的Worker站点返回的部分匹配结果跑后，Master将结果进行合并，并返回最终结果M。
[0079]Worker站点采用多线程的方式开展工作。具体而言，它通过线程T1来响应Master站点的请求，执行LocalEval计算。具体而言，LocalEval首先声明一个空集合S，用于存放“虚拟节点”，以及一个空图Gs(第1行)。随后，对于每条待更新的边e = (u，u’)，LocalEval计算受e更新而影响的子图Gsub(e)，S卩:在当前片段Fi*，分别以u，u’为起点进行宽度优先搜索，搜索的最大距离为d，搜索过程中访问到的所有节点所导出的子图即为Gsub。与此同时，对于遍历过程中访问到的“虚拟节点” v_v，如果S中尚未包含v_v，则将其加入S;同时，将Gsub
(e)与Gs合并。不难发现，当处理完所有待更新的边后，(a)S包含一组不重复的“虚拟节点”，当前Worker站点将通过这些虚拟节点向它所在站点请求必要的信息用于计算；(b)Gs即为本地站点受AEi影响的最大范围。随后，对于S中的每个“虚拟节点” ν，当前站点向ν所在站点请求信息，并在收到返回的子图G(v)后将其与Gs合并。当Worker接收到所有返回的结果后，调用算法VF2计算本地匹配结果M，并将Μ返回至Master站点。
[0080]除了T1线程，Worker同时启用T2线程响应其他Worker站点。当接收到来自其它站点的请求后，T2线程执行Findlnfo来计算子图G(v)。具体而言，FindInfo首先计算Q中节点的拓扑排序。其中，拓扑排序的定义如下:(a)r(u)=0,如果s(u)是Qs。。中的叶节点；(b)r(u)
=max{(l+r(u')) | (s(u)，s(u’))\in Escc}，其中Qscc= (Vscc，ESCC)是Q的强连通图--即强连通组件收缩为单一节点而形成的图结构，u是其强连通组件所对应节点s(u)内的节点。对于接收到的来自邻居站点的节点v，FindInf ο选择Q中与其标签相同且拓扑排序最大的节点u，随后，分别在Q和当前片段中，以u，v为起始点，沿Q的拓扑结构，并遵循节点标签约束进行宽度优先遍历，得到子图G(v)，并将其返回请求站点。
[0081]本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其它实施例的不同之处，各个实施例之间相同相似部分相互参见即可。
[0082]在本说明书中所谈到的“一个实施例”、“另一个实施例”、“实施例”、等，指的是结合该实施例描述的具体特征、结构或者特点包括在本申请概括性描述的至少一个实施例中。在说明书中多个地方出现同种表述不是一定指的是同一个实施例。进一步来说，结合任一实施例描述一个具体特征、结构或者特点时，所要主张的是结合其他实施例来实现这种特征、结构或者特点也落在本发明的范围内。
[0083]尽管这里参照本发明的多个解释性实施例对本发明进行了描述，但是，应该理解，本领域技术人员可以设计出很多其他的修改和实施方式，这些修改和实施方式将落在本申请公开的原则范围和精神之内。更具体地说，在本申请公开和权利要求的范围内，可以对主题组合布局的组成部件和/或布局进行多种变型和改进。除了对组成部件和/或布局进行的变型和改进外，对于本领域技术人员来说，其他的用途也将是明显的。
【主权项】
1.一种分布式环境下动态图结构匹配的方法，其特征在于它包括: (a)建立由一个主机端和多个工作站点组成的支持支持全双工通信和多线程计算的分布式计算框架； (b)主机端向工作站点传递信息，并协调工作站点的工作； (c)工作站点根据主机端传递的信息，计算本地匹配结果M1; (d)主机端回收各工作站点返回的部分结果跑，并汇总得到匹配结果Μ。2.根据权利要求1所述的分布式环境下动态图结构匹配的方法，其特征在于所述主机端执行的步骤包括: i)将模式图Q视为无向图，并计算直径d; ? )对于每一个工作站点Si，主机端将对应的更新AEi发送到工作站点Si; m)主机端汇总各工作站点&返回的结果跑，得到匹配结果μ。3.根据权利要求1所述的分布式环境下动态图结构匹配的方法，其特征在于所述工作站点Si执行的步骤包括: i)声明空集合S;空图数据Gs; ? )对于一个工作站点Si对应的更新AEi中的每条边e= (u，u’)； m)计算本地图F,的子图匕也⑷上为对应的工作站点S冲的数据； iv )将子图Gsub(e)中尚未包含在空集合S中的虚拟节点v_v放入空集合S中； V )子图将Gsub(e)并入空图数据Gs中； vi)对于空集合S中的所有虚拟节点V，向所有虚拟节点V所在的工作站点Sj请求信息； vii)工作站点Si接收从工作站点Sj返回的子图G(V)，并与Gs合并； vi)当所有请求得到返回后，对子图Gs，工作站AS,通过计算得到本地匹配结果跑； ix)返回Μ至主机端。4.根据权利要求1所述的分布式环境下动态图结构匹配的方法，其特征在于所述工作站点Si执行的步骤还包括: i)计算模式图Q中各节点u的拓扑排序； ? )选择模式图Q中与虚拟节点V标签相同且拓扑排序最大的节点u，构造点对(u，V); iii)以(u，V)为起始，遵循模式图Q的拓扑结构及节点标签，在Fi中进行宽度优先遍历，Fi为对应的工作站点Si*的数据，并将遍历到的点与边放入子图G(v); iv)返回G(v) ο5.根据权利要求1所述的分布式环境下动态图结构匹配的方法，其特征在于整个分布式计算采用UDP协议。
【专利摘要】本发明公开了一种分布式环境下动态图结构匹配的方法，它包括：(a)建立由一个主机端和多个工作站点组成的支持支持全双工通信和多线程计算的分布式计算框架；(b)主机端向工作站点传递信息，并协调工作站点的工作；(c)工作站点根据主机端传递的信息，计算本地匹配结果Mi；(d)主机端回收各工作站点返回的部分结果Mi，并汇总得到匹配结果M。本发明使得计算高度并行化，实现了动态环境下高效率的分布式计算，从而更加高效、便捷地对动态社交网络进行分析。
【IPC分类】G06F17/50
【公开号】CN105488289
【申请号】CN201510908818
【发明人】王欣, 郝妙, 于成业, 杜彤, 赵亮, 钟吉英, 刘传银
【申请人】四川长虹电器股份有限公司
【公开日】2016年4月13日
【申请日】2015年12月9日
【技术领域】
[0001]本发明涉及增量图结构匹配、分布式计算技术领域，具体涉及一种分布式环境下动态图结构匹配的方法。
【背景技术】
[0002]近年来，社交网络、社交媒体的流行，导致其数据量呈现爆炸式增长，对社交网络大数据的分析、研究也因而成为业界研究的热点问题。由于社交网络可以抽象为图结构一一用户可被视为图的顶点，用户之间的关系可被看作图的边，因此，基于图结构匹配的分析技术已成为社交网络分析的主要技术之一。
[0003]基于不同的应用场景，人们提出了多种图结构匹配语义，其中“子图同构”语义得到了广泛的应用，也成为本发明所采用的查询语义。然而，(1)基于“子图同构”语义的图结构匹配属于一类极难解决的问题一一NP完全问题；(2)社交网络的数据往往是分布式存储的，在分布式环境下，各站点间不得不通过传递数据来帮助求解，从而导致分布式环境下的图结构匹配计算十分复杂。
[0004]此外，社交网络是动态变化的，例如，不断有新边在网络中出现(新增的边被关联上时间戳，表明其出现的时刻)。为了对动态社交网络进行实时监控，一个重要且亟待解决的问题是:给定一个动态图G，模式图Q和时间窗口切，计算在tw时间区间内，G中所有与Q同构的子图g。如果把g中最早和最晚出现的边的时间差定义为i(g)，则T(g)〈 = tw。直观上看，该问题的一个解决方法为:对更新后的图GeAG反复进行子图同构计算，然而，考虑到(1)子图同构计算开销大；(2)计算请求十分频繁，因此该方法并不适用。此外，在动态网络环境下，人们往往对某一时间段内的匹配结果感兴趣，而非全部的，基于历史数据的匹配结果。
[0005]为了有效的克服以上困难，更加高效、便捷地对动态社交网络进行分析，我们提出了分布式环境下动态图结构匹配技术来有效解决以上问题。
【发明内容】
[0006]本发明克服了现有技术的不足，提供一种高效、便捷地对动态社交网络进行分析的分布式环境下动态图结构匹配的方法。
[0007]考虑到现有技术的上述问题，根据本发明公开的一个方面，本发明采用以下技术方案:
[0008]—种分布式环境下动态图结构匹配的方法，它包括:
[0009](a)建立由一个主机端和多个工作站点组成的支持支持全双工通信和多线程计算的分布式计算框架；
[0010](b)主机端向工作站点传递信息，并协调工作站点的工作；
[0011 ] (c)工作站点根据主机端传递的信息，计算本地匹配结果M1;
[0012](d)主机端回收各工作站点返回的部分结果Μ,，并汇总得到匹配结果Μ。
[0013]为了更好地实现本发明，进一步的技术方案是:
[0014]根据本发明的一个实施方案，所述主机端执行的步骤包括:
[0015]i)将模式图Q视为无向图，并计算直径d;
[0016]ii)对于每一个工作站点Si，主机端将对应的更新ΔΕ,*送到工作站点S1;
[0017]m)主机端汇总各工作站As,返回的结果吣，得到匹配结果μ。
[0018]根据本发明的另一个实施方案，所述工作站ASi执行的步骤包括:
[0019]i)声明空集合S;空图数据Gs;
[0020]? )对于一个工作站点Si对应的更新AEi中的每条边e= (u，u’)；
[0021]??)计算本地图Fi的子图Gsub (e)，Fi为对应的工作站点Si中的数据；
[0022 ]iv )将子图Gsub (e)中尚未包含在空集合S中的虚拟节点v_v放入空集合S中；
[0023]V )子图将Gsub(e)并入空图数据Gs中；
[0024]vi)对于空集合S中的所有虚拟节点V，向所有虚拟节点V所在的工作站点Sj请求信息;
[0025]vii)工作站点Si接收从工作站点Sj返回的子图G(v)，并与Gs合并；
[0026]vi)当所有请求得到返回后，对子图Gs，工作站点&调用VF2计算得到本地匹配结果Μι；
[0027]k)返回Μ至主机端。
[0028]根据本发明的另一个实施方案，所述工作站AS,执行的步骤还包括:
[0029]i)计算模式图Q中各节点u的拓扑排序；
[0030]? )选择模式图Q中与虚拟节点V标签相同且拓扑排序最大的节点u,构造点对(u,ν)；
[0031 ]iii )以(u，ν)为起始，遵循模式图Q的拓扑结构及节点标签，在Fi中进行宽度优先遍历，^为对应的工作站点&中的数据，并将遍历到的点与边放入子图G(v);
[0032]力)返回6(丫)。
[0033]本发明还可以是:
[0034]根据本发明的另一个实施方案，整个分布式计算采用UDP协议。
[0035]与现有技术相比，本发明的有益效果之一是:
[0036]本发明的一种分布式环境下动态图结构匹配的方法，支持全双工通信的分布式计算架构，以及各站点支持多线程计算，满足多任务运算的要求，使得计算高度并行化，实现了动态环境下高效率的分布式计算;从而更加高效、便捷地对动态社交网络进行分析。
【附图说明】
[0037]为了更清楚的说明本申请文件实施例或现有技术中的技术方案，下面将对实施例或现有技术的描述中所需要使用的附图作简单的介绍，显而易见地，下面描述中的附图仅是对本申请文件中一些实施例的参考，对于本领域技术人员来讲，在不付出创造性劳动的情况下，还可以根据这些附图得到其它的附图。
[0038]图1示出了根据本发明一个实施例的分布式环境下动态图结构匹配框图。
【具体实施方式】
[0039]下面结合实施例对本发明作进一步地详细说明，但本发明的实施方式不限于此。
[0040]在分布式环境下，高效率的对动态社交网络进行基于子图同构语义的结构匹配计算，其包括:(a)分布式计算框架；(b)基于动态网络图的分布式匹配计算。
[0041 ] (a)分布式计算框架:一个主-从(Master-Worker)结构，支持全双工通信的分布式计算架构。同时，各站点支持多线程计算，满足多任务运算的要求，使得计算高度并行化。
[0042](b)基于动态网络图的分布式匹配计算:主机(Master)端与工作站(Worker)端的算法，实现动态环境下高效率的分布式计算。
[0043]本方案具体如下:
[0044](一)分布式计算框架
[0045]分布式环境下，社交网络图G被存储在多个不同的站点，每个站点Si维护当前站点的数据F,。为了维持各片段间数据的连通性，对于跨站点的边e=(v，v’)(v属于FhV’属于FJ，在F冲保留了节点ν’的一个副本，并将其称为“虚拟节点”。通过“虚拟节点ν’”，可以向V’所在站点发送请求，来帮助当前站点获取必要的信息，并在本地进行结构匹配计算。
[0046]为了有效支持分布式环境下的运行计算，我们采用了如下计算框架。通过该框架，实现了站点间消息的异步传递，从而实现了图结构匹配的并行计算。具体框架结构如下:
[0047]计算框架由一个Master站点和多个Worker站点组成。其中，Master站点主要负责:
(1)向Worker站点传递消息，并协调Worker站点的工作；(2)回收各Worker站点返回的部分结果，并汇总。各Worker站点主要执行:(1)本地运算；(2)协同其它站点计算。此外，整个分布式计算采用UDP协议，实现了全双工通信。
[0048](二)基于动态网络图的分布式匹配计算
[0049]在上述计算框架下，我们设计了如下算法，在分布式环境下开展动态图结构匹配计算:
[0050]进程EvaMatch(在Master站点执行)
[0051 ]输入:时间窗口 tw，批量更新ΛΕ，模式图Q;
[0052]输出:匹配结果Μ;
[0053]1.将模式图Q视为无向图，并计算直径d(任意两点间最短距离的最大值)；
[0054]2.对于每一个Worker站点Si;
[0055]3.将对应的更新AEi发送到Worker站点Si ；
[0056]4.站点Si调用进程LocalEval (ΔΕι，Fi，Q，d，tw)计算本地匹配结果Mi ；
[OO57 ] 5.汇总各Worker站点返回的结果Mi ； [0058]6.返回Μ。
[0059]进程LocalEval(在Worker站点Si执行):
[0060]输入:本地更新AEi，本地图数据Fi，模式图Q及其直径d，Q时间窗口切。
[0061 ] 输出:本地匹配结果Mi。
[0062]1.声明空集合S;空图数据Gs;
[0063]2.对于AEi中的每条边e=(u，u，)；
[0064]3.计算本地图Fi的子图Gsub(e);
[0065]4.将Gsub (e)中尚未包含在S中的虚拟节点v_v放入S中；
[0066]5.将Gsub(e)并入 Gs;
[0067]6.对于S中的所有虚拟节点ν，向ν所在站点Sj请求信息；
[0068]7.接收从Sj返回的子图G(v)，并与Gs合并；
[0069]8.当所有请求得到返回后，对子图Gs，调用VF2计算本地匹配结果Μ;
[0070]9.返回Μ至Master。
[0071 ]进程Findlnfo(在Worker站点Si执行):
[0072 ]输入:节点ν，本地图数据Fi，模式图Q及其直径d，时间窗口 tw。
[0073]输出:子图G(v)。
[0074]1.计算Q中各节点u的拓扑排序；
[0075]2.选择Q中与ν标签相同且拓扑排序最大的节点u,构造点对(u，v)；
[0076]3.以(u，v)为起始，遵循Q的拓扑结构及节点标签，在Fi中进行宽度优先遍历，并将遍历到的点与边放入G (ν);
[0077]4.返回 G(v)。
[0078]参见图1所示，以下对上述算法进行进一步说明Jaster站点首先执行EvaMatch来启动计算。考虑到边e更新所造成的影响范围不超过Q中最长的两点间距离(将Q视为无向图)，因此，EvaMatch首先计算无向图Q的直径d。随后，Master站点将更新AEi发送至对应的Worker站点Si，同时触发站点Si的LocalEval进程。当收集到所有的Worker站点返回的部分匹配结果跑后，Master将结果进行合并，并返回最终结果M。
[0079]Worker站点采用多线程的方式开展工作。具体而言，它通过线程T1来响应Master站点的请求，执行LocalEval计算。具体而言，LocalEval首先声明一个空集合S，用于存放“虚拟节点”，以及一个空图Gs(第1行)。随后，对于每条待更新的边e = (u，u’)，LocalEval计算受e更新而影响的子图Gsub(e)，S卩:在当前片段Fi*，分别以u，u’为起点进行宽度优先搜索，搜索的最大距离为d，搜索过程中访问到的所有节点所导出的子图即为Gsub。与此同时，对于遍历过程中访问到的“虚拟节点” v_v，如果S中尚未包含v_v，则将其加入S;同时，将Gsub
(e)与Gs合并。不难发现，当处理完所有待更新的边后，(a)S包含一组不重复的“虚拟节点”，当前Worker站点将通过这些虚拟节点向它所在站点请求必要的信息用于计算；(b)Gs即为本地站点受AEi影响的最大范围。随后，对于S中的每个“虚拟节点” ν，当前站点向ν所在站点请求信息，并在收到返回的子图G(v)后将其与Gs合并。当Worker接收到所有返回的结果后，调用算法VF2计算本地匹配结果M，并将Μ返回至Master站点。
[0080]除了T1线程，Worker同时启用T2线程响应其他Worker站点。当接收到来自其它站点的请求后，T2线程执行Findlnfo来计算子图G(v)。具体而言，FindInfo首先计算Q中节点的拓扑排序。其中，拓扑排序的定义如下:(a)r(u)=0,如果s(u)是Qs。。中的叶节点；(b)r(u)
=max{(l+r(u')) | (s(u)，s(u’))\in Escc}，其中Qscc= (Vscc，ESCC)是Q的强连通图--即强连通组件收缩为单一节点而形成的图结构，u是其强连通组件所对应节点s(u)内的节点。对于接收到的来自邻居站点的节点v，FindInf ο选择Q中与其标签相同且拓扑排序最大的节点u，随后，分别在Q和当前片段中，以u，v为起始点，沿Q的拓扑结构，并遵循节点标签约束进行宽度优先遍历，得到子图G(v)，并将其返回请求站点。
[0081]本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其它实施例的不同之处，各个实施例之间相同相似部分相互参见即可。
[0082]在本说明书中所谈到的“一个实施例”、“另一个实施例”、“实施例”、等，指的是结合该实施例描述的具体特征、结构或者特点包括在本申请概括性描述的至少一个实施例中。在说明书中多个地方出现同种表述不是一定指的是同一个实施例。进一步来说，结合任一实施例描述一个具体特征、结构或者特点时，所要主张的是结合其他实施例来实现这种特征、结构或者特点也落在本发明的范围内。
[0083]尽管这里参照本发明的多个解释性实施例对本发明进行了描述，但是，应该理解，本领域技术人员可以设计出很多其他的修改和实施方式，这些修改和实施方式将落在本申请公开的原则范围和精神之内。更具体地说，在本申请公开和权利要求的范围内，可以对主题组合布局的组成部件和/或布局进行多种变型和改进。除了对组成部件和/或布局进行的变型和改进外，对于本领域技术人员来说，其他的用途也将是明显的。
【主权项】
1.一种分布式环境下动态图结构匹配的方法，其特征在于它包括: (a)建立由一个主机端和多个工作站点组成的支持支持全双工通信和多线程计算的分布式计算框架； (b)主机端向工作站点传递信息，并协调工作站点的工作； (c)工作站点根据主机端传递的信息，计算本地匹配结果M1; (d)主机端回收各工作站点返回的部分结果跑，并汇总得到匹配结果Μ。2.根据权利要求1所述的分布式环境下动态图结构匹配的方法，其特征在于所述主机端执行的步骤包括: i)将模式图Q视为无向图，并计算直径d; ? )对于每一个工作站点Si，主机端将对应的更新AEi发送到工作站点Si; m)主机端汇总各工作站点&返回的结果跑，得到匹配结果μ。3.根据权利要求1所述的分布式环境下动态图结构匹配的方法，其特征在于所述工作站点Si执行的步骤包括: i)声明空集合S;空图数据Gs; ? )对于一个工作站点Si对应的更新AEi中的每条边e= (u，u’)； m)计算本地图F,的子图匕也⑷上为对应的工作站点S冲的数据； iv )将子图Gsub(e)中尚未包含在空集合S中的虚拟节点v_v放入空集合S中； V )子图将Gsub(e)并入空图数据Gs中； vi)对于空集合S中的所有虚拟节点V，向所有虚拟节点V所在的工作站点Sj请求信息； vii)工作站点Si接收从工作站点Sj返回的子图G(V)，并与Gs合并； vi)当所有请求得到返回后，对子图Gs，工作站AS,通过计算得到本地匹配结果跑； ix)返回Μ至主机端。4.根据权利要求1所述的分布式环境下动态图结构匹配的方法，其特征在于所述工作站点Si执行的步骤还包括: i)计算模式图Q中各节点u的拓扑排序； ? )选择模式图Q中与虚拟节点V标签相同且拓扑排序最大的节点u，构造点对(u，V); iii)以(u，V)为起始，遵循模式图Q的拓扑结构及节点标签，在Fi中进行宽度优先遍历，Fi为对应的工作站点Si*的数据，并将遍历到的点与边放入子图G(v); iv)返回G(v) ο5.根据权利要求1所述的分布式环境下动态图结构匹配的方法，其特征在于整个分布式计算采用UDP协议。
【专利摘要】本发明公开了一种分布式环境下动态图结构匹配的方法，它包括：(a)建立由一个主机端和多个工作站点组成的支持支持全双工通信和多线程计算的分布式计算框架；(b)主机端向工作站点传递信息，并协调工作站点的工作；(c)工作站点根据主机端传递的信息，计算本地匹配结果Mi；(d)主机端回收各工作站点返回的部分结果Mi，并汇总得到匹配结果M。本发明使得计算高度并行化，实现了动态环境下高效率的分布式计算，从而更加高效、便捷地对动态社交网络进行分析。
【IPC分类】G06F17/50
【公开号】CN105488289
【申请号】CN201510908818
【发明人】王欣, 郝妙, 于成业, 杜彤, 赵亮, 钟吉英, 刘传银
【申请人】四川长虹电器股份有限公司
【公开日】2016年4月13日
【申请日】2015年12月9日
最新回复(0)