星火graphFrames -标签传播与强连接组件

Question

在https://docs.databricks.com/spark/latest/graph-analysis/graphframes/user-guide-scala.html标准示例中：

• 强连接的组件在计算上似乎是合理的，同时在绘图时也会目视它们。

​

​

• 因此，我对检测“社区”的标签传播感到惊讶。

​

​

我遗漏了什么？从数据来看，A，D，E可能也是一个社区，结果也是相似的。我尝试了更多的周期。标签传播似乎是“集群”的可怜表亲。

Answer 1

您在这里发现的是一种已知的现象，称为标签振荡，当标签被同步更新时，(子)图具有二部结构(或星图)。这两个社区将无休止地交换他们的标签，而LPA永远不会自行终止。

标签t:

​

标签在t+1:

​

标签在t+2:

​

..。诸若此类。

正如您已经提到的，这并不是我们所期望的社区检测算法，因为在社区中没有边缘。但这仍然是一种快速算法，对非二部结构有很好的效果。拉加文提出了一种使用异步更新的快速替代方案。但这还没有在Graphframes中实现。Graphframes调用LPA的graphX实现(查看代码代码)，它使用Pregel (查看代码代码)，这是同步的。

除了二分结构的LPA问题外，SCC和LPA之间也有一个普遍的区别。

• SCC社区:社区的每个节点都知道(有一个边缘)社区中的所有其他节点。
• LPA社区:对于一个社区的每个节点，在社区内有一个路径(边缘序列)到一个社区中的所有其他节点。