用sql写迭代算法-用spark sql划分连通图

一、问题描述

1.1 问题场景化描述

小时候你可能遇到过这种情况，一不小心在游戏厅惹到了别人，然后就约放学后校门口等着。

结果两人都找了一自己认识的小团体在校门口对峙，紧张的气氛中，有的人发现对面的团体中有认识的人，结果约架便成了约烧烤，两个团体都互相认识了。

如果每个人都有个标签，贴在身上，比如都叫“XX帮”，就能避免约架的流程是吧。

1.2 问题概念模型

上面的问题，我们用图来表示。图是由节点和边构成，点就是某个同学，边就代表是否认识。

给你一个图，将图中互相认识的人都打上同一个标签，也就是处于同一个连通图的节点打上同一个标签。

比如下图所示的一个图，有9个点，很多条边。

1.3 问题物理模型

在hive数据表relation中，存储两两的关系：

user:string , friend:string

比如1.2的图就可以表示成下表

问题就变成了生成一张表名为user_group，记录每个user的标签。

user:string , group:string

二、解决方案

2.1 场景化解决方案

为了解决这个问题：

首先第一天每个人都成立一个以自己为帮主的帮派，在自己肩上贴上帮主名字。

然后第二天大家都去上学，观察自己认识的人中都加入了哪些帮派，偷偷记下来。

放学回到家，就把记下来的帮主姓名按字母顺序排序，加入排第一个的帮派，第二天去上学的时候贴上帮主名字。

这样很多天之后，大家发现认识的人都统一了帮主。

约架时两帮人说出自己的帮主，帮主不一样大家肯定都互相不认识的，直接打就是。

2.2 解决方案概念模型

这就是社群发现，可以使用标签传播算法（LAP）：每一轮将标签按边的权值传播到临近节点，每个节点收到传播过来的标签后更新自己的标签，经过多轮传播直到收敛。

具体就不多说了，感兴趣的同学可以搜索一下。

2.3 sql物理实现

基于1.3的表我们有下面的解法:

由于是无向图，得把反向关系的数据补全，构造表all_relation:

spark.sql("""

select user,friend as group

from relation

union

select friend as user, user as group

from relation

""").registerTempTable("all_relation")

计算标签的更新路径

while True:

# 每个人把认识的人的帮主都记下来，选帮主

propagation_map = spark.sql("""

select distinct user as source,

least(user, min(group)) target,

count(1) c

from all_relation

group by user

having source!=target

""").cache()

#如果每个人认识的人中都只公认了只有一个帮主就不再计算

propagation_count = propagation_map.filter("c>1").count()

if(propagation_count==0):

break

propagation_map.registerTempTable("propagation_map")

# 更新认识的人的帮主

all_relation = spark.sql("""

select distinct all_relation.user,

nvl(propagation_map.target,all_relation.group) group

from all_relation

left join propagation_map

on all_relation.group=propagation_map.source

""").registerTempTable("all_relation")

结果就是 all_relation 这张表

三、一些思考

这个模式和比特币的共识模式很像，都是先建立一套规则让每个节点按照这个规则操作，最后能让所有节点达成共识。

sql这样的模式和一般的通用语言不一样，天生带有并行性。

对于本文的这种描述方式大家觉得咋样。

历史文章推荐：

折腾了一周的任务 带你了解大数据计算原理

文言文编程背后-语言的本质

嘿！产品&运营：你需要懂的数据分析入门

一问搞懂区块链基本原理

一文了解几十万年的科技史