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

导语

共同好友作为一种社交特征的典型代表，被广泛用于推荐、广告、游戏领域。当用户量达到海量的场景，通常是按月计算全量共同好友列表，时效性较低，甚至因为计算资源消耗过大而无法计算。相比而言，计算新增共同好友有着更大的价值。本文介绍一种千亿关系链下的日新增共同好友挖掘算法--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条新增边)。然后分别采用不同的计算模式，计算不同类型新增三角形。这里三角形的新增边实际是业务新增关系链，非新增边是业务已有的历史全量关系链。整个计算模式如下图所示。

[1505959211989_8020_1505959212176.jpg]

图：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)。完成建初始图操作后，遍历图中各点，收集邻居信息存于顶点属性(如下图右侧所示)。

[1505959267005_4640_1505959267144.jpg]

图：GTE聚合邻居信息

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

2. 计算共同好友

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

[1505959293246_9400_1505959293373.jpg]

图： 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值较小的顶点。

[1505959319152_2632_1505959319369.jpg]

图：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的顶点，可能在多个边形成好友三角形。按边计算完好友三角形后，需要按顶点聚合所在不同边的三角形。

[1505959341433_2196_1505959341527.jpg]

图：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)。

[1505959394834_8773_1505959394934.jpg]

图：STE单向边连接

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

2.有序过滤

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

[1505959417041_8269_1505959417126.jpg]

图： STE有序过滤

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

3.主键转换

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

[1505959526816_6209_1505959527227.jpg]

图：STE主键转换

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

4.三角形计算

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

[1505959553000_2857_1505959553112.jpg]

图：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.