每周学点大数据 | No.48 计算子图同构

No.48期

计算子图同构

Mr. 王:我们再来看一个例子——计算子图同构。这个问题给定(节点有标签)数据图G和查询图P,找到G 中和P 同构的子图。这是一个经典的NP 完全问题。

小可:那求解岂不是很困难?

Mr. 王:在实际情况下,虽然数据图G 会比较大,可能有上G 个节点,但查询图P 一般会比较小,因为查询图一般是由查询需求表现出来的,查询需求往往没有那么大。

小可:如果依然利用Pregel 平台的思想来解决问题,要怎么做呢?

Mr. 王:考虑到Pregel 平台具有面向节点编程的思想,我们就要考虑在比较大的图中较小的相邻结构。因为在每一轮迭代处理中,每一个节点也就只能和与其相邻的结构进行通信,所以我们使用一种叫作STwig 的结构,这种结构就是只有两层的一棵“小”树。

小可:嗯,只有两层的树的确可以很有效地表示某一个节点的所有邻居。

Mr. 王:我们要将整个大图拆分成Stwig 结构,这样做的效率比匹配点和边显然要高得多。然后我们按照P 中的STwig 到G 中去搜索相同的结构。经过数次迭代之后,将查询出的STwig 再重新join 成原来要查询的图结构就可以了。总结起来就是:拆分、查询、join。

小可:还是有点抽象,具体是怎么做的呢?

Mr. 王:好,我用一种具体的图模式来演示这种思想的具体步骤。

第1 步:划分。对查询图P 进行分解。比如上面的图abcdef 是想要查询的图模式。我们将其分解成多个STwig,也就是大小只有两层的树。当然,分解方法是不唯一的,而且求解最佳的分解方法也是NP 完全的,好在图模式的大小比较小,相对来讲比较容易求解。比如图中的q 和q’ 就是两种不同的划分方法,当我们完成划分之后,这一次查询Q(或者说查询图P)就可以表示成q1q2q3q4 或者q1’q2’q3’。

第2 步:搜索。在搜索时,我们先选取一种模式,比如q1,然后到数据图G 去搜索子模式q1。

这个搜索过程可以很好地利用Pregel 的思想。因为我们要寻找的模式都是两层的小树,所以在搜索q1 这种模式时,只需要让每一个节点检查自己是不是a,然后再让每一个a 去与其邻居联系,看看它们是不是b 和c,如果其邻居中同时有b 和c,那么就上报说明自己这里有q1。

小可:这样确实可以很好地利用“把自己当作一个节点”的思想。无须关注图的其他部分,也不用从整体上去寻找这种模式,而是每一个节点自己出发去检查其邻居是不是和自己构成了一个P 中存在的STwig 结构。

Mr. 王:这里还有一个小技巧。我们不难注意到,在要进行搜索的这些STwig 中,会存在一些公共的节点,比如q1 和q3 就有公共节点b。我们可以做一个缓存,记录下来在搜索q1 时找到的所有的b。当进行q3 搜索时,我们无须去搜索所有的b,而是只搜索q1 时找到的那些b就可以了。你想想看这是为什么?

小可想了一下,说:能够匹配模式P 的G 的子图必然同时匹配q1 和q3。如果进行q1 搜索时并没有将某一个b 搜索出来,则意味着符合q3 的子模式不符合q1,因为它的b 不连着a 或者它连着的a 不连着c。如果是这样,即使它真的能够匹配q3,那么到最后组合起来,也会由于不含q1 不可能构成P。

Mr. 王笑着说:非常好,你的逻辑思维很严谨。这样做的好处是,可以大大减少我们在每一轮搜索过程中需要处理的节点。

第3 步:对查找到的这些子模式进行一个join 操作,将小的STwig 合并成更加接近原图P的结构,以求能够返回最终结果。这个join 操作相对会麻烦一些,因为图的连接并不是一个符合“以节点为核心”思想的操作,这里就需要所涉及的每一台机器都要加载一些中间结果,让这些中间结果在自己这里进行连接。

下期精彩预告:

经过学习,我们学习了一个经典的NP 完全问题,计算子图同构。在下一期中,我们将了解众包算法。更多精彩内容,敬请关注灯塔大数据,每周五不见不散呦!

内容来源:灯塔大数据 文章编辑:柯一

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2017-08-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LET

CPU SIMD简介

之前的两篇文章,分别介绍了CPU和CPU Cache两个话题,性能是永恒的核心。我们也谈到了优化CPU性能面临的三堵墙:

1523
来自专栏怀英的自我修炼

怀英漫谈3-百度Echarts中日期控件的使用总结

你好, 今天下午在用百度的Echarts做一个日历图的效果,其中跌跌碰碰遇到了几个问题,好在最终都解决了,今天想跟你聊聊这几个问题。 本篇偏编程,可以跳至最后看...

3909
来自专栏杨建荣的学习笔记

任务调度的并行算法

如果串行是肯定不行的。我们可以考虑并行策略,但是开了并行,怎么能够充分利用资源比较好呢。

1493
来自专栏追不上乌龟的兔子

JupyterLab——更具生产力的Jupyter环境

Jupyter源于Ipython Notebook,是使用Python(也有R、Julia、Node等其他语言的内核)进行代码演示、数据分析、可视化、教学的很好...

8.8K4
来自专栏数据派THU

独家 | 一文读懂PySpark数据框(附实例)

本文中我们将探讨数据框的概念,以及它们如何与PySpark一起帮助数据分析员来解读大数据集。

851
来自专栏编舟记

生成式测试(Generative Testing)

满足需求是所有软件存在的必要条件,单元测试一定是为它服务的。从这一点出发,我们可以总结出写单元测试的两个动机:驱动(如:TDD)和验证功能实现。另外,软件需求易...

1553
来自专栏Java架构

分布式超大规模数据的实时快速排序算法

3198
来自专栏数说工作室

3行代码实现 Python 并行处理,速度提高6倍!

原标题:Here’s how you can get a 2–6x speed-up on your data pre-processing with Pyth...

3585
来自专栏nimomeng的自我进阶

Swift 4.2新特性——WWDC2018 Session401笔记

厨子今年的演讲很不给力。不过既然是软件开发者大会嘛,焦点自然应该放在软件功能上。 所以我看了下今年的Session401,也就是Swift4.2新特性介绍,做...

3152
来自专栏数据分析

[数据清洗]- Pandas 清洗“脏”数据(二)

概要 了解数据 分析数据问题 清洗数据 整合代码 了解数据 在处理任何数据之前,我们的第一任务是理解数据以及数据是干什么用的。我们尝试去理解数据的列/行、记录、...

3414

扫码关注云+社区