文档介绍：关于图计算和graphx的一些思考
时间2013-12-03 15:51:04 淘宝技术部相似文章(0) 原文  http://rdc./?p=1927 添加到推刊
收藏到推刊创建推刊
收藏取消
已收藏到推刊!
请填写推刊名
描述不能大于100个字符!
权限设置: 公开仅自己可见
创建取消
“全世界的网络连接起来,英特纳雄耐尔就一定要实现。”受益于这个时代,互联网从小众的角落走到了历史的中心舞台。如果无远弗届的互联网将把会整个世界转化成了一个巨型网络,那么就让这一切首先从淘宝开始吧。
最近我们试图将淘宝的交易记录中的物品和人组成一个对分网络(work)。对于这个网络的,我们有许多有趣的问题:这个网络中节点的度分布会是什么样?在这个网络中,是否也存在“权威节点”?是否也有所谓的“小世界现象”。工欲善其事必先利其器,在回答这个问题前,如何存储这个图(上亿个节点,几十亿条边),如何快速地将图算法应用到这个图上是我们小组在遇到的不可回避的问题。
通过搜索和查新,我们知道基于spark的graphX和spark原生的bagel都提供了对于图操作的API。我们使用pageRank做了两者的性能比较,发现只要图中节点的边数呈现幂律分布,当节点数比较大时(3000W以上),在graphx上的pageRank每次超步(superstep)的时间可以稳定地低于基于spark的原生图算法框架bagel。为了知其所以然,我们花了2天时间,阅读了两篇文章和其他的相关材料,动手写了代码,做了测试,结合网上的查找和自己的思考,对于背后的原因做了一些了解和思考。
幂律分布和自然图(natural graph)
这段主要来自: tent/10/0124/11/
现实生活中存在各种不同的现象,可用不同的数学上的分布来描述它。
比如我们以身高为横坐标,以取得此身高的人数为纵坐标,可画出一条钟形分布曲线,这种曲线两边衰减地极快,特别高的人和特别矮的人都是比较少见的;这种分布可以用正态分布或泊松分布来描述它。如左上图的泊松分布
但是有些分布的差距记为悬殊,比如收入为横坐标,以不低于该收入值的个体数或概率为纵坐标,可绘出一条向右偏斜得很厉害的曲线(包括梧苇在内的大多数人都在横轴接近0的地方无语飘过,囧)。这种“长尾”分布表明,绝大多数个体的尺度很小,而只有少数个体的尺度很大(想想胡润财富榜),而且相当大个体的尺度可以在很宽的范围内变化(比如资产亿元已经可以算是巨富,但是往上,还有资产十亿,百亿,千亿的富豪),这种波动往往可以跨越多个数量级。
上面说的这个现象可以用数学语言描述为:不小于某个特定值x的概率与x的常数次幂亦存在简单的反比关系,它的公式为:P[X≥k]~x^(-k),这就是所谓的Pareto定律。这是一种幂律分布,还有很多其他形式的幂律分布,它们数学上是等价的,它们的通式可写成y=c*x^(-r)。
:自然图(natural graph)
对于图来说, 节点的度定义为与该节点相连接的节点的个数
如果每个点都是随机的和其它的点建立连接,那么生成的网络的度分布符合泊松分布这种网络称之为随机网络,度值比平均值高许多或低许多的节点,都十分罕见。因为大家都是随机的,所以某个点突出的可能性很小。
但是随