千亿关系链下的新增共同好友计算

导语

共同好友作为一种社交特征的典型代表,被广泛用于推荐、广告、游戏领域。当用户量达到海量的场景,通常是按月计算全量共同好友列表,时效性较低,甚至因为计算资源消耗过大而无法计算。相比而言,计算新增共同好友有着更大的价值。本文介绍一种千亿关系链下的日新增共同好友挖掘算法--NTE算法。该算法基于分治的思想,将新增共好友计算问题,转换为更易于运算与实现的三角形计算问题。该算法也可十分便捷的移植到其他需要计算新增共同好友的场景。

作者:mecoolyang, chainyang

背景与思路

对于大多数场景,通常都会将(共同好友数)作为衡量用户亲密度的重要依据。然而,共同好友本身的挖掘有更大的意义。这里共同好友的挖掘是指计算用户三角形(如A,B有共同好友C,则存在好友三角形A-B-C)。在社交化推荐中,根据场景用户A,B的偏好,能够为非场景用户C提供推荐依据;在广告场景中,共同好友间A,B,C会经常查看动态和互动,覆盖到三者中的一个可以起到推广到三者的目的;在游戏场景,稳定关系的A,B,C可能会经常开黑,当A,B入坑王者荣耀后,为C推荐这款游戏应该有不错效果。

可见,无论是推荐场景、广告场景还是社交运营场景,共同好友都有极其重要的意义。在用户量关系到达百亿甚至千亿的时候,共同好友计算需要消耗大量资源,通常都是按月例行。这样无法发挥新增关系的时效性。在这类场景中,计算新增共同好友的挖掘计算更为重要。

模型介绍

计算新增共同好友的过程,实际上可看作是一个计算新增三角形的过程。例如,用户A和B,都新添加好友C,实质是新增三角形A-B-C。

这里,我们设计了一种新增三角形挖掘算法(New Triangle Enumeration, 简称NTE算法)。该算法根据新增边的个数,将新增三角形分成new1三角形(1条新增边),new2三角形(2条新增边),new3三角形(3条新增边)。然后分别采用不同的计算模式,计算不同类型新增三角形。这里三角形的新增边实际是业务新增关系链,非新增边是业务已有的历史全量关系链。整个计算模式如下图所示。

图:NTE计算模型

为了减少三角形的重复存储和计算,我们计算的新增三角形都是有序三角形,即id值A<B<C。

算法实现

Part1 : new3三角形计算

new3三角形的三条新增边都来自新增关系链,计算量是三类新增三角形中最小的。这里我们采用基于GraphX的GTE(Graph based Triangle Enumeration)算法,计算新增关系链所形成网络结构中的new3三角形。具体过程为:

1. 收集邻居信息

首先需要读取新增关系链数据作为边,建立初始图(如下图左侧所示)。简单起见,可以直接将关系链两端点的场景用户index_id作为点id。这里用A,B,C,D,E,F表示顶点id(id值A<B<C<D<E<F)。完成建初始图操作后,遍历图中各点,收集邻居信息存于顶点属性(如下图右侧所示)。

图:GTE聚合邻居信息

这里我们用圈表示顶点,用矩形表示顶点属性。如顶点A有邻居B、C、E、F, 则B、C、E、F存于A的顶点属性。

2. 计算共同好友

完成邻居信息的收集后,就可以进行共同好友的计算。这里我们遍历图各边,比较边两端点的属性值,计算其中的共现index_id,即为共同好友。

图: GTE计算共同好友

如图所示,计算边A-E时,A的属性值(B,C,E,F)和E的属性值A无交集,表示A与E没有共同好友(这里用null表示);计算边B-C时,B的属性值(A,C,D)和C的属性值(A,B,D)有交集A、D,则表示B和C有2个共同好友A、D。

3. 计算好友三角形

为了避免同一条形成的相同好友三角形被多少统计。共同好友计算完成后,将计算的共同好友和边端点组成有序三角形,发送给id值较小的顶点。

图:GTE计算好友三角形

如图所示,A-B边计算出的共同好友C与端点A,B组成有序三角形(A,B,C) (顶点值大小A<B<C),并发送给顶点值较小的端点A;B-C边计算出的共同好友A和D,与端点B,C组成有序三角形(A,B,C)和(B,C,D)发送给顶点值较小的端点B。

4. 聚合好友三角形

度大于1的顶点,可能在多个边形成好友三角形。按边计算完好友三角形后,需要按顶点聚合所在不同边的三角形。

图:GTE聚合好友三角形

如同所示,B会收到B-C形成的三角形(A,B,C)和(B,C,D)和B-D边形成的三角形(B,C,D)。在顶点B对信息进行合并去重后,将有效三角形序列(A,B,C)和(B,C,D)存于B的顶点属性。

值得注意的是这里好友三角形,依然存在重复存储(B点和C点都存有三角形(A,B,C))。最终按顶点输出好友三角形后需要做去重操作(由于已经是有序三角形了,去重操作的计算量会大大减少)。

GTE算法不仅可以用于新增三角形计算,对于场景内关系链量级在百亿以内的场景,都可以直接用于三角形计算,从而计算共同好友列表。并且在计算共同好友列表的过程中,可以同时计算共同好友数。

Part2 : new2三角形计算

new2三角形由2条新增边和1条全量边组成。它的特殊在于需要计算全量关系链,建图较为困难;但又不涉及全量链之间的join操作。因此我们采用基于新增链join的JTE(Join Based Triangle Enumeration)算法计算新增边与全量边组成的new2三角形。具体过程为:

  1. 新增关系链集合Sn join Sn, 找到两边(A-B, A-C)在Sn中的三角形序列集合St
  2. 对St进行map操作,转换为非新增关系链B-C为主键形式((B,C), A)
  3. 转换后的St join Sa, Sa为最近一次更新的全量关系链, 找出B-C在Sa中的三角形(A,B,C)

JTE算法的计算过程较为简单,这里不作过多描述。

Part3 : new1三角形计算

new1由1条新增边和2条全量边组成,是三类三角形中计算量最大的。为了减少计算量,这里采用新增边join全量边的结果,再去join一次全量边的整体思路。由于计算过程中边端点在join前后都需要保持有序,因此我们采用基于sort的STE(Sort Based Triangle Enumeration)算法计算新增边与全量边组成的new3三角形。具体过程为:

1.连接单向边

读取新增关系链集合Sn和历史全量关系链集合Sa,筛选单向关系链(srcId < dstId)。

图:STE单向边连接

如图所示,从新增关系链取有序边A-B与全量关系链取的有序边A-C做连接,得到以A为主键的元组(A,(B,C))。

2.有序过滤

由于最终计算的是有序三角形,这里先根据元组的非主键部分,进行筛选过滤,保证非组件部分成有序。

图: STE有序过滤

这里筛选非主键部分B<C的元组,得到(A,(D,E))。从而不仅确保了元组中三个单元的大小关系,而且对于输入集合有交集的扩展场景(存在B=C),可以去除B=C的元组(A,(B,C))。

3.主键转换

为了判定边D-E是否在全量关系链中,需要将上述结果与Sa集合做连接操作。在join之前需要对元组进行主键转换,让D-E成为主键。

图:STE主键转换

这里以D-E为主键相当于为D-E添加一条虚链(不确定是否存在)。

4.三角形计算

最终将第3步的结果集St与Sa进行连接,从而筛选出D-E边在Sa中的元组。对该元组进行转换操作即可得到有序的new1三角形。

图:STE三角形计算

由于根据前面的过滤筛选,已经得知了A,D,E三者的大小关系。在St与Sa连接得到D-E边在Sa中的元组((D,E),A)后,经过简单的转换操作,即可得到有序三角形(A,D,E)。

算法调优

这里列举几个实现过程中值得注意的地方

1.读表后先repartition再处理

考虑到直接从tdw读取的数据可能存在分布不均匀。load tdw表中的数据后,先进行repartition 或 partitionBy 操作,可以在一定程度上解决数据倾斜问题。

2.充分利用cpu和内存

这里三角形计算Spark任务对内存消耗较大,较容易出现应用组内存资源不足,cpu负载未满的情况。为了充分利用cpu和内存(数平规定,二者负载都满了,才能追加资源啊),可以根据需要将executor_cores 设置为3或4.

3.边分区策略代替点分区策略

当边数量太大的时候,采用GraphX默认的点分区策略,计算代价都非常高。因此这里采用边分区策略EdgePartition2D建图。

4.Spark大任务拆分成多个小任务

这里主要是针对单任务迭代过程可能由于shuffle量大,导致内存溢出。遇到类似问题,可以考虑采用分治的思想,将任务拆分成若干小任务。

附录

三角形计算

  • Elenberg E R, Shanmugam K, Borokhovich M, et al. Beyond triangles: A distributed framework for estimating 3-profiles of large graphsC//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2015: 229-238.
  • Kim J, Han W S, Lee S, et al. OPT: a new framework for overlapped and parallel triangulation in large-scale graphsC//Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM, 2014: 637-648.
  • Park H M, Silvestri F, Kang U, et al. Mapreduce triangle enumeration with guaranteesC//Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. ACM, 2014: 1739-1748.
  • Cui Y, Xiao D, Loguinov D. On Efficient External-Memory Triangle ListingC//Data Mining (ICDM), 2016 IEEE 16th International Conference on. IEEE, 2016: 101-110.

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

杨光的专栏

1 篇文章1 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏進无尽的文章

如何建立一款App的配色方案

当我们评价一款app时,配色应该是仅次于其功能性的另一主要因素。现如今人机交互主要通过GUI来实现,色彩在交互过程中扮演着重要的角色。良好的色彩搭配会帮助用户发...

884
来自专栏CDA数据分析师

7 款 Python 数据图表工具的比较

Python 的科学栈相当成熟,各种应用场景都有相关的模块,包括机器学习和数据分析。数据可视化是发现数据和展示结果的重要一环,只不过过去以来,相对于 R 这样的...

25610
来自专栏Spark学习技巧

第3篇:更新异常与规范化设计

第三篇:更新异常与规范化设计 前言 在前两篇中,主要讲了ER建模和关系建模。在具体分析如何用数据库管理软件RDBMS(Relational Database M...

3387
来自专栏专知

无从下手落地问答系统?实用百度开源框架了解一下

【导读】智能问答系统,近两年被炒得热火朝天。然而,刨除花式 PPT以及论文里的各种黑科技,我们最想知道的其实是:这东西到底怎么落地?近日,百度开源了他们的主要面...

920
来自专栏Crossin的编程教室

【每周一坑】图像的指纹:数字水印 + 【解答】鸡兔同笼

曾经有过这样的新闻:某公司的员工将内网论坛上的言论截屏发布到互联网上,引发了热议。于是公司通过截图定位到了员工的身份,将其开除。

552
来自专栏PPV课数据科学社区

电商评论情感分析

? 随着网上购物的流行,各大电商竞争激烈,为了提高客户服务质量,除了打价格战外,了解客户的需求点,倾听客户的心声也越来越重要,其中重要的方式 就是对消费者的文...

4367
来自专栏CDA数据分析师

案例 | R语言数据挖掘实战:电商评论情感分析

随着网上购物的流行,各大电商竞争激烈,为了提高客户服务质量,除了打价格战外,了解客户的需求点,倾听客户的心声也越来越重要,其中重要的方式 就是对消费者的文本评论...

3319
来自专栏大数据挖掘DT机器学习

python数据挖掘:能不能找出吃货最佳住宿点?

这次我爬出了哈尔滨市TOP285家好吃的店,包括烧烤的TOP,饺子的TOP,酱骨的TOP等等等等,在地图上显示,规划热点,再用聚类算法计算下能不能找出吃货最佳的...

3325
来自专栏python开发者

[验证码识别技术]字符验证码杀手--CNN

字符验证码杀手--CNN 1 abstract  目前随着深度学习,越来越蓬勃的发展,在图像识别和语音识别中也表现出了强大的生产力。对于普通的深度学习爱好者来说...

3218
来自专栏逍遥剑客的游戏开发

LowPloy风格的模型导入

3204

扫码关注云+社区