关于图计算及graphx的一些思考.docxVIP

  1. 1、本文档共10页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
关于图计算及graphx的一些思考

关于图计算和graphx的一些思考时间2013-12-03 15:51:04 淘宝技术部相似文章 (0)原文? /?p=1927添加到推刊收藏到推刊创建推刊收藏取消已收藏到推刊!请填写推刊名描述不能大于100个字符!权限设置:公开仅自己可见创建取消“全世界的网络连接起来,英特纳雄耐尔就一定要实现。”受益于这个时代,互联网从小众的角落走到了历史的中心舞台。如果无远弗届的互联网将把会整个世界转化成了一个巨型网络,那么就让这一切首先从淘宝开始吧。最近我们试图将淘宝的交易记录中的物品和人组成一个对分网络(bipartite network)。对于这个网络的,我们有许多有趣的问题:这个网络中节点的度分布会是什么样?在这个网络中,是否也存在“权威节点”?是否也有所谓的“小世界现象”。工欲善其事必先利其器,在回答这个问题前,如何存储这个图(上亿个节点,几十亿条边),如何快速地将图算法应用到这个图上是我们小组在遇到的不可回避的问题。通过有哪些信誉好的足球投注网站和查新,我们知道基于spark的graphX和spark原生的bagel都提供了对于图操作的API。我们使用pageRank做了两者的性能比较,发现只要图中节点的边数呈现幂律分布,当节点数比较大时(3000W以上),在graphx上的pageRank每次超步(superstep)的时间可以稳定地低于基于spark的原生图算法框架bagel。为了知其所以然,我们花了2天时间,阅读了两篇文章和其他的相关材料,动手写了代码,做了测试,结合网上的查找和自己的思考,对于背后的原因做了一些了解和思考。幂律分布和自然图(natural graph) 这段主要来自: /content/10/0124/11/8411shtml现实生活中存在各种不同的现象,可用不同的数学上的分布来描述它。比如我们以身高为横坐标,以取得此身高的人数为纵坐标,可画出一条钟形分布曲线,这种曲线两边衰减地极快,特别高的人和特别矮的人都是比较少见的;这种分布可以用正态分布或泊松分布来描述它。如左上图的泊松分布但是有些分布的差距记为悬殊,比如收入为横坐标,以不低于该收入值的个体数或概率为纵坐标,可绘出一条向右偏斜得很厉害的曲线(包括梧苇在内的大多数人都在横轴接近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(自然图)。下面是两种图的直观展示(左图是节点的度符合泊松分布,差别不大。右图是节点的度符合幂律分布,差别悬殊,这种就是natural graph)1.3:举个举个例子理解公式对于上文反复提到的节点的度分布符合幂律分布,节点度分布可表示为y=c*x^(-r),我觉得可以这样理解的:以微博用户的粉丝个数为例,如果粉丝数100个以上的用户有100w,粉丝数200个以上的用户40w,如果微博用户的粉丝数分布符合幂律分布,那么有如下方程组:100 0000 ?= c*100^(-r)解上述方程组,c=4.4*e8,r=1.32。这个公式在这里的实际应用是:基于上面的计算,我们可以推算出,粉丝数大于10w的用户数是 c*10 0000^(-r) 大约是1

文档评论(0)

jdy261842 + 关注
实名认证
文档贡献者

分享好文档!

1亿VIP精品文档

相关文档