腾讯QQ社交网络的四度分离(2)
2017-05-23 编辑：
对于每个用户都存储“通讯录”是不现实的，因为到最后，每个用户的通讯录都会增长到十亿级别，导致需要存储“十亿乘以十亿”的数据。为了解决这个问题 HyperANF 使用了 HyperLogLog 计数器来表示这个集合。这个计数器能够看做是一个表示集合的数据结构。我们可以简单认为它是一个有三个方法的类：
HyperLogLog 计数器得到的只是近似值，但好处在于只需要定长存储，不会随着加入元素的增多而耗费更多的存储。算法只需给每个用户初始化一个定长的 HyperLogLog 计数器，然后进行传播就能够统计到 B(t)。使得能够在有限存储的情况下计算 QQ 千亿关系链的平均距离。
而为了求一个准确的社交平均距离，我们采取的方法是运行算法多次，以均值作为算法的最终结果。
Spark图计算
除了存储，另一个需要解决的瓶颈在于迭代次数。HyperANF 算法一般需要数百甚至上千次迭代才能停止。每一次迭代都需要遍历整个网络，如果都需要从磁盘中载入千亿 QQ 关系链会十分耗时。
为此我们引入 Spark 图计算框架，把网络结构缓存到内存中，从而节省重复磁盘 I/O 时间。
在实践中，我们还做了更细致的优化，在算法迭代的时候我们只更新有变化的节点。因此统计发现网络的大部分用户在迭代十轮以后“通讯录”已经不再变化。理论推导表明此时也不会影响好友的“通讯录”更新。因此可以不必再给自己的好友发送数据。如此优化能够有效减少网络通信负载，实际数据表明，在千亿关系链的情况下，优化后的算法在十轮以后的单次迭代耗时能够压缩到 1 分钟。
另一个在图计算中需要考虑的优化点是定期缓存中间结果到硬盘中。过长的迭代次数会增加计算失败的风险，而在 Spark 上，当出现节点故障导致当前计算的数据丢失时，系统会自动根据数据的依赖关系重算。但在图计算场景下，每次重算可能需要重做历史数百轮的迭代，同时也可能在追根溯源之后发现需要重新加载所有原始数据才能恢复当前丢失的少量数据。因此有必要在迭代一定次数之后，把中间结果缓存到一个硬盘中，斩断对更早迭代数据的依赖。
尾记
社交平均距离的计算，让我们明白社交网络的“小世界现象”：我们的网络很大，有 10 亿+ 用户。我们的网络也很稀疏，平均每个用户只有不到 150 个好友，但平均只需要 4 个中间人，我们就能够让任意两个用户互相认识。这个数字相比起 50 年前那位美国社会学家得到的结论，还少了 2 个中间人，我们可以猜测是互联网让社会变得更紧密了，也让这个世界更小了。而相比起外国的社交网络，中国的社交网络虽然稀疏，但仍依旧紧密，我们认为这是中国社交网络的结构特殊之处，能够以更少的人均好友，获得同样高的信息传播效率。
参考说明：
[1]Milgram S. The small world problem[J].Psychology today, 1967, 2(1): 60-67.
[2]实际上 Milgram 挑选的志愿者并不完全随机, 而是分成三组: 100个同城组(住在波士顿), 100个同职业组(同是股票经纪人)和96个随机志愿者. 而实验的结果显示同城组平均只需要4.4个中间人就能够联系上目标.
[3]Leskovec J, Horvitz E. Planetary-scale views on a large instant-messaging network[C]//Proceedings of the 17th international conference on World Wide Web. ACM, 2008: 915-924.
[4]Backstrom L, Boldi P, Rosa M, et al. Four degrees of separation[C]//Proceedings of the 4th Annual ACM Web Science Conference. ACM, 2012: 33-42.
[5]因为这里选取的网络都是双向关系, 因此一对用户有两条单向关系链.
[6]一个网络最多拥有的边的数目为”用户数*(用户数-1)”, 用它去除真实的关系链数, 越大意味着越接近关系链的上限, 也即是越稠密.
[7]QQ 社交网络来源于腾讯即时通讯工具 QQ 在2014年11月的用户关系链. 为了去掉网络中已经不再使用的账号, 我们限制参与计算的用户必须在当月有登录. 同时, 为了获得真正的相互间的QQ好友关系, 我们去掉了关系链中的单向关系.
[8]Facebook的网络来源于Facebook的好友关系链. 其选取了2011年5月份有登录行为的7.21亿用户, 然后提取用户之间的好友关系作为用户关系.
[9]MSN 的网络来源于微软 MSN 2006年6月的用户发消息数据. 他们共有2.42亿的用户有登录, 但只有1.8亿的用户有消息行为.
[10]如果一个用户没有加好友, 那么自然没有人能够通过中间人联系上他. 因此我们这里统计的前提是所有能够通过中间人介绍的人. 实际上根据我们的统计, 如果一个用户有至少一个好友, 那么有99%的可能性是能够联系上网络中的大部分人.
[11]因为我们使用的 HyperANF 算法得到的只是距离分布的估计值, 根据算法逻辑 401 只是整个网络直径的下确界, 即是说有可能有两个用户的距离大于401, 不过这里我们使用它作为估计的直径.
[12]Boldi P, Rosa M, Vigna S. HyperANF: Approximating the neighbourhood function of very large graphs on a budget[C]//Proceedings of the 20th international conference on World wide web. ACM, 2011: 625-634.
作者简介
黄俊，腾讯QQ社交网络事业群数据挖掘工程师，主导或参与过社交关系链挖掘，LBS挖掘，推荐系统等多个项目。负责对千亿QQ社交关系链的计算、分析和挖掘工作，历经腾讯图计算从Hive到Spark的演变。
本文为《程序员》原创文章，未经允许不得转载，更多精彩文章请点击「阅读原文」订阅《程序员》。
相关阅读：
相关推荐：
