在https://docs.databricks.com/spark/latest/graph-analysis/graphframes/user-guide-scala.html 标准示例：
在图形上直观地观察强连接的组件时，它们在计算上似乎是合理的。
因此，我对检测“社区”的标签传播感到惊讶。
我错过了什么[a、 d，e]从数据来看，我也会认为这是一个社区，结果也会相似。我尝试了更多的周期。标签传播似乎是“集群”的近亲。
在https://docs.databricks.com/spark/latest/graph-analysis/graphframes/user-guide-scala.html 标准示例：
在图形上直观地观察强连接的组件时，它们在计算上似乎是合理的。
因此，我对检测“社区”的标签传播感到惊讶。
我错过了什么[a、 d，e]从数据来看，我也会认为这是一个社区，结果也会相似。我尝试了更多的周期。标签传播似乎是“集群”的近亲。
1条答案
按热度按时间x8goxv8g1#
您在这里发现的是一种已知的现象，称为标签振荡，它发生在标签同步更新并且（子）图具有二部结构（或星形图）时。两个社区将无休止地交换他们的标签，lpa将永远不会自行终止。
t处的标签：
t+1处的标签：
t+2处的标签：
... 等等。
正如您已经提到的，这并不是我们期望的社区检测算法，因为社区中没有边缘。但这仍然是一个快速的算法，对于非二部结构可以得到很好的结果。raghavan提出了一种使用异步更新的快速替代方案。但这还没有在graphframes中实现。graphframes调用lpa（查看代码）的graphx实现，lpa使用pregel（查看代码），pregel是同步的。
除了二部结构的lpa问题外，scc和lpa之间还有一个普遍的区别：
scc社区：社区中的每个节点都知道（有一个边缘）社区中的所有其他节点。
lpa社区：对于社区中的每个节点，社区中有一条路径（边序列）通向社区中的所有其他节点。