apache-spark - Spark 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 处的标签:


... 等等。

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

除了二分结构的 LPA 问题，还有一个 SCC 和 LPA 的一般区别 :

SCC 社区:社区的每个节点都知道(具有边缘)社区内的所有其他节点。

LPA 社区:对于社区的每个节点都有一条路径
(边缘序列)到社区内的所有其他节点
一个社区。