分享

Spark 高级分析:第七章第12,13节 小世界网络

本帖最后由 feilong 于 2018-8-31 14:13 编辑
问题导读

1.什么是小世界网路?其数学模型有何特性?
2.如何判定图示完全的?
3.感知图的局部密度可以使用什么度量?有何公式?GraphX中如何计算?



关注最新经典文章,欢迎关注公众号



上一篇:第七章第10,11节 处理边三元组,分析过滤后的图
http://www.aboutyun.com/forum.php?mod=viewthread&tid=25124

图的连通性和度分布可给出其总体结构的基本概念,而GraphX使得计算和分析这些性质变得容易。在本节中,我们将深入探讨GraphX APIs,并展示如何使用它们计算GraphX中没有内置的图的一些更高级的属性。

随着像万维网这样的计算机网络和像Facebook和Twitter这样的社交网络的兴起,数据科学家们现在拥有丰富的数据集来描述现实世界的网络结构和形成,与之相对是数学家和图论家传统上拥有的理想化网络。1998年,Duncan Watts和Steven Strogatz发表了第一篇描述这些现实世界网络的特性以及它们与理想化模型的区别的论文,题为“小世界网络的集体动力学”。这是一篇开创性的论文,概述了如何生成具有我们在现实世界图中看到的小世界特性的图的第一个数学模型:

1.网络中的大多数节点度较小,属于相对密集的其它节点簇,也就是说,节点的大部分邻居也是相互连接的。
2.尽管图中大多数节点都具有小的度和密集的聚类,但是通过遍历少量的边,可以相对快速地从任何其他网络到达网络中的任何节点。

对于这些属性中的每一个,Watts和Strogatz定义了一个度量,这个度量可以用来根据图表表达这些属性的强度对图表进行排序。在本节中,我们将使用GraphX来计算概念网络的这些度量,并将得到的值与理想化随机图的值进行比较,以测试概念网络是否显示小世界特性。

如果每个顶点通过边连接到每个顶点,则图是完整的。在一个给定的图中,可能有许多完整的顶点子集,我们称这些完整的子图组。图中许多大团块的存在表明该图具有我们在真实小世界网络中看到的那种局部致密结构。

不幸的是,在给定的图表中发现小团体是很难做到的。检测给定图是否具有给定大小的团的问题是NP完全的,这意味着在小的图中找到小团体在计算上可能非常密集。

计算机科学家已经发展出许多简单的度量,这些度量使我们能够很好地感知图的局部密度,而不需要计算代价来找到所有给定大小的小集团。这些度量之一是顶点的三角形计数。三角形是在三个顶点上的一个完全图,在顶点V处的三角形计数仅仅是包含V的三角形的数目。Watts和Strogatz定义了一个新的度量,称为局部聚类系数,它是一个顶点的实际三角形计数与该顶点的可能三角形数量的比率,基于它有多少个邻居。对于一个无向图,具有k近邻和t三角形的顶点的局部聚类系数c是:
图片1.png

让我们使用GraphX来计算过滤后的概念网络中每个节点的局部聚类系数。GraphX有一个名为triangleCount 的内置方法,该方法返回一个Graph,该图的VertexRDD 包含每个顶点处的三角形数:
[mw_shl_code=scala,true]val triCountGraph = graph.triangleCount()
triCountGraph.vertices.map(x => x._2).stats()
...
(count: 13034, mean: 163.05,
stdev: 616.56, max: 38602.0, min: 0.0)[/mw_shl_code]
为了计算局部聚类系数,我们需要通过每个顶点处可能的三角形的总数来标准化这些三角形计数,我们可以根据度RDD来计算这些三角形计数:
[mw_shl_code=scala,true]val maxTrisGraph = graph.degrees.mapValues(d => d * (d - 1) / 2.0)[/mw_shl_code]
现在我们关联三角形计数的VrordRDD从三分图到正规化项的VordeRDD,我并计算两者的比率,对于只有一个边的任意顶点,要小心避免除以零:
[mw_shl_code=scala,true]val clusterCoefGraph = triCountGraph.vertices.
innerJoin(maxTrisGraph) { (vertexId, triCount, maxTris) => {
if (maxTris == 0) 0 else triCount / maxTris
}
}[/mw_shl_code]
计算图中所有顶点的局部聚类系数的平均值给出网络平均聚类系数:
[mw_shl_code=scala,true]clusterCoefGraph.map(_._2).sum() / graph.vertices.count()
...
0.2784084744308219[/mw_shl_code]

已有(1)人评论

跳转到指定楼层
jiangzi 发表于 2018-9-3 19:48:34
小世界网络~~
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

推荐上一条 /2 下一条