Spark 高级分析:第七章第6,7节 连通分支

问题导读

1.什么是连通图？如何判断？
2.Graphx中内置的计算连通分支的方法是什么？如何使用？
3.判断图是否是连通图对数据分析有何意义？





上一篇：Spark 高级分析:第七章第5节 用GraphX构造共现网络
http://www.aboutyun.com/forum.php?mod=viewthread&tid=24987


当我们探索一个表的内容时，有一些关于我们想要立即计算的列的汇总统计数据，这样我们就可以感觉到数据结构并探索任何问题领域。当我们正在调查一个新的图表时，同样的原理适用，尽管我们感兴趣的汇总统计数据略有不同。图类提供了用于计算这些统计数的内置方法，并且与常规Spark RDD API相结合，使得我们能够快速地获得对图的结构的感觉，以便指导我们的探索。

我们想知道关于图形的最基本的事情之一是它是否连通。在一个连通图中，任何顶点都可以通过跟踪一个路径到达任何其他顶点，这只是从一个顶点到另一个顶点的一个边缘序列。如果图不连通，那么它可以被划分成更小的一组连通子图，我们可以单独研究。

连通性是一个基本的图形属性，因此，GraphX在图形中包含一个用于标识连通分支的内置方法并不奇怪。会注意到，一旦调用图形上的连接组件方法，就会启动大量的Spark作业，然后将最终看到计算结果：
[mw_shl_code=scala,true]val connectedComponentGraph: Graph[VertexId, Int] =
topicGraph.connectedComponents()[/mw_shl_code]
查看方法connectedComponents返回的对象的类型：它是图形类的另一个实例，但是顶点属性的类型是一个被用作每个顶点所属的组件的唯一标识符的VertexId。为了得到连接组件的数量和它们的大小，我们可以使用可信的countByValue方法来给VeltRDD中每个VertexId赋值。我们将编写一个函数来查找所有的连通组件的列表，并根据它们的大小排序。[mw_shl_code=scala,true]def sortedConnectedComponents(
connectedComponents: Graph[VertexId, _])
: Seq[(VertexId, Long)] = {
val componentCounts = connectedComponents.vertices.map(_._2).
countByValue
componentCounts.toSeq.sortBy(_._2).reverse
}[/mw_shl_code]
让我们看看有多少连通组件，先取10个。
[mw_shl_code=scala,true]val componentCounts = sortedConnectedComponents(
connectedComponentGraph)
componentCounts.size
...
1039
componentCounts.take(10)foreach(println)
...
(-9222594773437155629,11915)
(-6468702387578666337,4)
(-7038642868304457401,3)
(-7926343550108072887,3)
(-5914927920861094734,3)
(-4899133687675445365,3)
(-9022462685920786023,3)
(-7462290111155674971,3)
(-5504525564549659185,3)
(-7557628715678213859,3)[/mw_shl_code]
最大的分支包括超过90%的顶点，而第二大的包含4个--这是图的一个非常小的部分。看看这些小分支的一些主题是值得的，只要了解它们为什么没有连接到最大的分支。为了查看与这些较小的分支相关联的主题的名称，我们需要加入与原始概念图中的顶点连通图VertexRDD。VertexRDD提供了一个内部连接转换，可以利用GraphX设置数据的方式比Spark正则join转换具有更好的性能。在innerJoin方法中，我们需要在VertexID和包含在两个VertexRDDs中的每一个内部的数据上提供一个函数，该函数返回一个值，该值将用作生成的VertexRDD的新数据类型。在这种情况下，我们希望了解每个连接分支的概念名称，因此我们将返回包含两个值的元组。
[mw_shl_code=scala,true]val nameCID = topicGraph.vertices.
innerJoin(connectedComponentGraph.vertices) {
(topicId, name, componentId) => (name, componentId)
}[/mw_shl_code]
让我们来看一下最大连通分支的主题名称，它不是巨型分支的一部分：
[mw_shl_code=scala,true]val c1 = nameCID.filter(x => x._2._2 == topComponentCounts(1)._2)
c1.collect().foreach(x => println(x._2._1))
...
Reverse Transcriptase Inhibitors
Zidovudine
Anti-HIV Agents
Nevirapine[/mw_shl_code]
如果我们在谷歌中查到[齐多夫定]和[奈韦拉平]，我们发现奈韦拉平的维基百科条目，这表明这两种药物联合用于治疗HIV-11，最严重的HIV形式。
令人惊讶的是，这个子图在整个子图中没有连接到任何关于HIV或AIDS的话题。如果我们看一看在整个数据中提到HIV的主题的分布，我们会看到：
[mw_shl_code=scala,true]val hiv = topics.filter(_.contains("HIV")).countByValue()
hiv.foreach(println)
...
(HIV Seronegativity,10)
(HIV Long Terminal Repeat,2)
(HIV Long-Term Survivors,1)
(HIV Integrase Inhibitors,1)
(HIV Infections,104)
(HIV-2,2)
(HIV Seroprevalence,6)
(Anti-HIV Agents,1)
(HIV-1,72)
(HIV,16)
(HIV Seropositivity,41)[/mw_shl_code]
感觉图中的这个不同的子成分是数据的一个伪像，它可能是对索引中单独引用的主要主题的吝啬标记，排除了其他主要主题，如HIV-1，这将把本文并入图的巨大分支中。这里的教训是，话题共现网络趋向于完全连接，因为随着时间的推移，我们添加更多的引用，并且似乎没有结构性原因，我们期望它会断开成不同的子图。
在后台，connectedComponents方法在我们的图上执行一系列迭代计算，利用顶点是每个顶点唯一的数字标识符的事实，以识别每个顶点所属的分支。在计算的每个阶段中，每个顶点广播它所看到的每个邻居的最小顶点值。在第一次迭代中，这将仅仅是顶点自身的ID，但这通常在后续迭代中被更新。每个顶点保持跟踪它所看到的最小顶点，并且当这些最小ID在迭代中都没有变化时，连通分支的计算就完成了，每个顶点被分配给由顶点的最小顶点表示的分支，这是一个部分的顶点。图上的这些迭代计算是常见的，并且在本章后面，我们将看到如何使用这种迭代模式来计算阐述图的结构的其他图形矩阵。