整套大数据学习资料(视频+笔记)百度网盘无门槛下载:http://www.edu360.cn/news/content?id=3377

16.7.4社区提取

hadoop 花牛 10℃ 0评论

到目前为止,我们已经提供了节点度量(入度)@度量的方法(对称链接判 定)。让我们进一步看看如何度量邻居关系:一个I旨定用户的朋友中有多少 人彼此之间是朋友?同时,我们将产生一个边集来实现前一个例子那样的 可视化展示。

1.获取邻居

选择一个种子节点(这里是@hadoop)。首先“收集”种子节点的邻居节点:

a_replies_b = LOAD 1a_replies_b.tsv' AS (src:chararray, dest:chararray); 
--Extract edges that originate or terminate on the seed 
n0_edges = FILTER a_replies_b BY (src == 'hadoop') OR (dest == 'hadoop');
--Choose the node in each pair that *isn't* our seed:
n1_nodes_all = FOREACH n0_edges GENERATE
((src == 'hadoop') ? dest : src) AS screen_name; 
nl_nodes = DISTINCT nl_nodes_all;
DUMP nl_nodes

现在我们把这个邻居集和开始节点集进行交集处理,从而找出所有始于 n1_nodes集合的边:

n1_edges_out_j = DOIN a_replies_b BY src,
n1_nodes BY screen_name USING 'replicated'; 
n1_edges._out = FOREACH nl_edges_out_j GENERATE src, dest;

我们得到的图的副本数据(超过io亿条边)仍然太大而不能搬入内存。另一 方面,一个单独用户的邻居人数很少会超过百万,所以它可以轻松地读入 内存。在JOIN操作里包含USING 'replicated'会让Pig做一个map端的连 接操作(也称作fragment replicate join,片断复制连接)Pignl_nodes关系数据读入内存当作一个査找表,然后把整个边集的数据连续地载入内存。 只要连接条件满足(srcnl_nodes查询表中),就产生输出。没有reduce步骤意味着速度得以显著提升。

为了只留下源和目标节点都是种子节点的邻居的边,重复执行如下连接操作:

n1_edges_j = 30IN n1_edges_out BY dest,
n1_nodes BY screen_name USING 'replicated'; 
n1_edges = FOREACH n1_edges_j GENERATE src, dest;
DUMP n1_edges
(mrflip,tom_e_white)
(mrflip,mza)
(wattsteve,josephkelly)
(nealrichter,tlipcon)
(bradfordcross,lusciouspear)
(mrflipj jeromatron)
(mndoci,mrflip)
(nealrichter, datajunkie)

2.社区度量标准和1百万百万数量级的问题

把@hadoop、@cloudera@infochimps作为种子节点,我把类似的脚本应用到20亿条消息集中来创建图16-24,本书网站(http:hadoopbook.cow)上 也有。

 image.png

图16-24. Twitter上的大数据社区

可以看出,这种大数据社区的关联度是很髙的。相对来说,名人(如 @THE_REAL_SHAQ)的邻居非常稀疏。我们可以用“集聚系数”(clustering coefficient)来表示这样的关系,定义为:实际的nl_edges和可能的 nl_edges的集合数据量的比值。值的范围是从0(邻居节点互不关联)到 1(邻居节点两两互相关联)。集聚系数值髙,表明它是一个凝聚性高的社 区。集聚系数值较低表明社区节点的兴趣很分散(@THE_REAL_SHAQ节点 的情况),或表明这是一个非有机组织社区,可能存在垃圾账户。

3.在全局数据上的局部特性

我们已经算出了对一个节点、一条边以及一个邻居的社区度量标准。那么 面对整个网络该怎么做?这里没有足够的篇幅来4井述这个问题,但是通过 在图上产生节点的“三角关系”,你能同时测量每个节点的集聚系数值。 对每个用户,比较他们所属的三角关系的个数及其链接度,就可以得到集聚 系数值。

请注意,还记得我们前面对节点度巨大差异性的讨论吗?不假思索地扩展前面的方法会导致数据的激增流行音乐明星@britneyspears(在2010年7月有520万粉丝,42万关注)@WholeFoods(170万粉丝,60万关 注),每个人都会产生上万亿的数据记录。更糟糕的是,因为大社区具有稀 疏的集聚系数,所以几乎所有这些数据都会被丢弃掉!我们有更巧妙的方法 在整个图上做数据处理。但一定要牢记现实世界是如何描述这个问题的。如果你断言@britneyspears和这42万人不是朋友,你可以只保留强链 接。给每条边赋权重(考虑关注数、是否是对称链接等因素)并且给来自某个节点.的链接数设置上限。这将大幅缩减中间数据的规模,但仍然可以合理 地估计社区的凝聚性。

转载请注明:全栈大数据 » 16.7.4社区提取

喜欢 (0)or分享 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址