你在这里

关于图计算和graphx的一些思考

2013 / . 12 / . 25

关于图计算和graphx的一些思考

“全世界的网络连接起来,英特纳雄耐尔就一定要实现。”受益于这个时代,互联网从小众的角落走到了历史的中心舞台。如果无远弗届的互联网将把会整个世界转化成了一个巨型网络,那么就让这一切首先从淘宝开始吧。

最近我们试图将淘宝的交易记录中的物品和人组成一个对分网络(bipartite network)。对于这个网络的,我们有许多有趣的问题:这个网络中节点的度分布会是什么样?在这个网络中,是否也存在“权威节点”?是否也有所谓的“小世界现象”。工欲善其事必先利其器,在回答这个问题前,如何存储这个图(上亿个节点,几十亿条边),如何快速地将图算法应用到这个图上是我们小组在遇到的不可回避的问题。

通过搜索和查新,我们知道基于spark的graphX和spark原生的bagel都提供了对于图操作的API。我们使用pageRank做了两者的性能比较,发现只要图中节点的边数呈现幂律分布,当节点数比较大时(3000W以上),在graphx上的pageRank每次超步(superstep)的时间可以稳定地低于基于spark的原生图算法框架bagel。为了知其所以然,我们花了2天时间,阅读了两篇文章和其他的相关材料,动手写了代码,做了测试,结合网上的查找和自己的思考,对于背后的原因做了一些了解和思考。

  • 幂律分布和自然图(natural graph)

1.1:幂律分布

这段主要来自:http://www.360doc.com/content/10/0124/11/8411_14273195.shtml

现实生活中存在各种不同的现象,可用不同的数学上的分布来描述它。

关于图计算和graphx的一些思考

比如我们以身高为横坐标,以取得此身高的人数为纵坐标,可画出一条钟形分布曲线,这种曲线两边衰减地极快,特别高的人和特别矮的人都是比较少见的;这种分布可以用正态分布或泊松分布来描述它。如左上图的泊松分布

但是有些分布中随机变量对应的值差距悬殊,比如收入为横坐标,以不低于该收入值的个体数或概率为纵坐标,可绘出一条向右偏斜得很厉害的曲线(包括梧苇在内的大多数人都在横轴接近0的地方无语飘过,囧)。这种“长尾”分布表明,绝大多数个体的尺度很小,而只有少数个体的尺 度很大(想想胡润财富榜),而且相当大个体的尺度可以在很宽的范围内变化(比如资产亿元已经可以算是巨富,但是往上,还有资产十亿,百亿,千亿的富豪),这种波动往往可以跨越多个数量级。

上面说的这个现象可以用数学语言描述为:不小于某个特定值x的概率与x的常数次幂亦存在简单的反比关系,它的公式为:P[X≥k]~x^(-k),这就是所谓的Pareto定律。这是一种幂律分布,还有很多其他形式的幂律分布,它们数 学上是等价的,它们的通式可写成y=c*x^(-r)。

1.2:自然图(natural graph)

对于图来说, 节点的度定义为与该节点相连接的节点的个数

如果每个点都是随机的和其它的点建立连接,那么生成的网络的度分布符合泊松分布这种网络称之为随机网络,度值比平均值高许多或 低许多的节点,都十分罕见。因为大家都是随机的,所以某个点突出的可能性很小。

但是随机网络只能说是理论上的网络,实际生活中的网络是出于种种现实的目的建立的。比如微博,姚晨能成为大V,背后有一个分工严谨的团队在进行运作。对于一个现实中的网络而言,当新的节点加入的时候,总是会优先连接那些在网络中最耀眼的节点。比如新用户加入微博,总是先关注那些知名大v。网络中的节点和新节点建立连接的概率与这个节点已有的连接数正相关,网络的度分布则是幂律分布,符合这种特点的网络叫无尺度网络。它的节点度值相差悬殊,往往可以跨越几个数量级,是一种极端“专制”的网络,它有个学名叫无标度网络。它节点的度符合上文提到的公式:y=c*x^(-r),因为这种网络在自然界,显示生活中的存在如此普遍,无标度网络又经常被称为natural graph(自然图)。

 1.3:举个举个例子理解公式

对于上文反复提到的节点的度分布符合幂律分布,节点度分布可表示为y=c*x^(-r),我觉得可以这样理解的:以微博用户的粉丝个数为例,如果粉丝数100个以上的用户有100w,粉丝数200个以上的用户40w,如果微博用户的粉丝数分布符合幂律分布,那么有如下方程组:

100 0000  = c*100^(-r)

40 0000 =  c*200^(-r)

解上述方程组,c=4.4*e8,r=1.32。这个公式在这里的实际应用是:

基于上面的计算,我们可以推算出,粉丝数大于10w的用户数是 c*10 0000^(-r) 大约是108人,粉丝数大于100w的用户数是6人。同时,这个例子也说明了natural graph的自相似性,可以通过部分数据对于整个图的情况进行推测。

像Internet、电子邮件网络、电影演员合作网络、引文关系网络的节点的度都符合幂律分布,数据倾斜是很严重的现象。所以如果要对于现实中存在的”图”进行图计算,需要针对于无标度网络进行一些存储,通信等优化,graphx就对于有这种特点的图进行优化。

1.4:Network science网络科学

上述提到的图在网络科学中被称为网络。阿里有在交易,沟通,认证的过程中沉淀了大量的数据,其中不少都可以以网络的形式表现出来。比如旺旺的好友关系和聊天记录,又比如淘宝中的SNS元素,而淘宝的点击,收藏,购买的流水转变为二分图,更是一个庞大的巨型网络。我们做巨型网络的预研主要是想要从网络科学的角度来对于这些图进行一些分析,希望搞清从购买记录来看用户是否会体现出社区性(community detection),优质商品被用户发觉,接受,传播的过程中是否有“小世界”的现象。

对于一个网络,我们通常有这些维度可以作为调查的入手点:

点的度数(average degree ):对于无向网络而言,就是每个边的平均节点数,有向网络又分为出度和入度。点的度数分布和消息的传播概率P直接决定了一个消息是否可以传遍全网络,还是在传播过程中湮灭了。

平均路径(average path):对于某个点而言,计算它到网络中的所有其他点的最短路径,求和,然后除以网络中点的个数。这个值直接说明了这个点到网络中的其他节点要多少步。而对于网络的所有点的平均路径分布可以判断这个网络是均匀的(各点的平均路径大致相同), 带中心区域的(有的点平均路径大,属于边缘区,反之则为中心区)。

网络半径:所有点的计算到其他点的距离,其中的最大距离就是网络半径。MAX(shortest path)

聚合系数:

对于点i的聚合系数(clustering cofficient)=点i的邻居间的边数/点i的邻居数。这个系数说明了i所在的社群是否是活跃的,有凝聚力的。这个特性在聚划算的效果预估,营销策略策划上有很大的应用前景。

在以上基础上,所谓的小集团(clique)是我们关注的一个重点。所谓的clique在这个是一个完全子图(sub complete graph),在这个子图中,所有点都相互连接,一些在全网络中不能大范围传播的信息会在这个小集团中反复传播,沉淀下来,称为一种类似方言,行话之类的东西。对于淘宝而言,淘宝旅游,淘宝家装就比较容易出现这样的现象,是否是这样,我们要通过对于对应的网络进行计算后进行验证。

转自 http://rdc.taobao.org/?p=1927

 

Copyright © 2014-2015 czbaa.com. 成长吧啊 粤ICP备18096644号-1

手机题库 | RSS | 联系: admin@czbaa.com  网站