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

导语

共同好友作为一种社交特征的典型代表,被广泛用于推荐、广告、游戏领域。当用户量达到海量的场景,通常是按月计算全量共同好友列表,时效性较低,甚至因为计算资源消耗过大而无法计算。相比而言,计算新增共同好友有着更大的价值。本文介绍一种千亿关系链下的日新增共同好友挖掘算法--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 条评论
登录 后参与评论

相关文章

来自专栏吉浦迅科技

DAY59:阅读 #pragma unroll

By default, the compiler unrolls small loops with a known trip count. The #pragm...

502
来自专栏技术沉淀

Pandas QQ聊天记录分析

1333
来自专栏数据小魔方

空间数据可视化笔记——simple features空间对象基础

是不是感觉被封面图和不明觉厉的题目给骗进来了哈哈哈,今天这篇是理论篇,没有多少案例,而且还很长,所以静不下心的小伙伴儿可以先收藏着,时间充裕了再看。 ---- ...

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

对于随机数的一些分析

多年前我朋友圈的一个朋友公司年会抽奖出现了下面的这样一幕:CTO现场review代码。本来带着一丝娱乐精神,结果被无限放大了。所以年会中大家都会很自然想revi...

3088
来自专栏用户画像

相似人群画像算法

由于TESLA集群无法直接操作MongoDB,需要将TDW里面的用户画像数据,通过洛子系统导出至HDFS,再与MongoDB中原有群画像进行合并。

3045
来自专栏斑斓

迪米特法则与重构

在面向对象设计的世界里,有一个寻常却又常常为人所忽略的原则——“迪米特(Law of Demeter)”法则。这个原则认为,任何一个对象或者方法,它应该只能调用...

836
来自专栏前端布道

JavaScript设计模式与开发实践 - 策略模式

引言 本文摘自《JavaScript设计模式与开发实践》 在现实中,很多时候也有多种途径到达同一个目的地。比如我们要去某个地方旅游,可以根据具体的实际情况来选择...

3618
来自专栏我是攻城师

Lucene+Solr+ElasticSearch查询匹配优化

2975
来自专栏跟着阿笨一起玩NET

浅谈数据库设计技巧(上)(转)

转一篇他人写的数据库设计技巧,感觉也不一定都正确,开拓一下思路吧。 说到数据库,我认为不能不先谈数据结构。1996年,在我初入大学学习计算机...

1191
来自专栏GreenLeaves

Oracle 中运用rollup和cube实现汇总运算

前言、看了很多的随笔博文内容都是关于rollup和cube的用法,发现一个问题,很多都是一样或者转载的,但这都不是重点,重点是,他们写的都太专业化了,直接给一个...

1827

扫码关注云+社区