背景与思路

  对于大多数场景,通常都会将(共同好友数)作为衡量用户亲密度的重要依据。然而,共同好友本身的挖掘有更大的意义。这里共同好友的挖掘是指计算用户三角形(如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。< p="">

  算法实现

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

  


  图: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。< p="">

  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三角形。具体过程为:

  新增关系链集合Sn join Sn, 找到两边(A-B, A-C)在Sn中的三角形序列集合St

  对St进行map操作,转换为非新增关系链B-C为主键形式((B,C), A)

  转换后的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))。< p="">

  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 graphs[C]//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 graphs[C]//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 guarantees[C]//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 Listing[C]//Data Mining (ICDM), 2016 IEEE 16th International Conference on. IEEE, 2016: 101-110.

 

 作者:mecoolyang, chainyang