Neo4j中的图形算法：标签传播

图算法提供了理解，建模和预测复杂动态的手段，例如资源或信息流，传染或网络故障传播的途径，以及群体的影响和弹性。

本博客系列旨在帮助您更好地利用图形分析和图形算法，以便您可以使用Neo4j等图形数据库更快地有效地创新和开发智能解决方案。

上周我们继续研究社区检测算法，重点关注弱连通分量算法。

本周我们将继续探索社区检测算法，并查看标签传播算法，该算法基于邻域多数传播标签作为推断群集的方法。这种极快的图形分区几乎不需要先验信息，因此被广泛用于大规模网络中进行社区检测。

关于标签传播

标签传播算法（LPA）是一种用于在图中查找社区的快速算法。它仅使用网络结构作为指导来检测这些社区，并且不需要预定义的目标函数或关于社区的先前信息。

LPA的一个有趣特性是您可以选择分配初步标签以缩小生成的解决方案的范围。这意味着您可以将其用作查找社区的半监督方式，您可以在这些社区中挑选一些初始社区。

LPA是一种相对较新的算法，仅由Raghavan等人提出。2007年，在文章“ 近线性时间算法检测大规模网络中的社区结构”中。它的工作原理是在整个网络中传播标签，并根据标签传播过程形成社区。

该算法背后的直觉是，单个标签可以在密集连接的节点组中迅速成为主导，但是它将难以穿过稀疏连接的区域。标签将被捕获在密集连接的节点组内，并且当算法完成时最终具有相同标签的那些节点被视为同一社区的一部分。

注意：算法的工作原理如下：

• • 每个节点都使用唯一标签（标识符）进行初始化。

  • 这些标签通过网络传播。

  • 在每次传播迭代中，每个节点将其标签更新为其邻居的最大数量所属的标签。领带均匀随机地打破。

  • 当每个节点具有其邻居的多数标签时，LPA达到收敛。随着标签的传播，密集连接的节点组很快就在唯一标签上达成共识。在传播结束时，只剩下几个标签 - 大多数都会消失。据说在收敛时具有相同标签的节点属于同一社区。

我应该何时使用标签传播？

• 标签传播已被用于指定推文的极性，作为语义分析的一部分，其使用来自经过训练的分类器的种子标签以结合Twitter跟随者图来检测正面和负面表情符号。有关更多信息，请参阅Twitter极性分类，标签传播通过词汇链接和跟随者图表。“

• 基于化学相似性和副作用特征，标签传播已被用于估计与患者共同开处方的潜在危险药物组合。该研究发现于基于临床副作用的药物 - 药物相互作用的标签传播预测中。“

• 标签传播已被用于在机器学习模型的对话中推断话语的特征，以借助于概念及其关系的维基数据知识图来跟踪用户意图。有关更多信息，请参阅基于维基数据图表上DST标签传播的特征推断。“

提示：与其他算法相比，标签传播在同一图表上多次运行时会产生不同的社区结构。如果一些节点被给予初步标签，则解决方案的范围变窄，而其他节点未标记。未标记的节点更可能采用初步标签。

标签传播示例

让我们看看Label Propagation算法的实际应用。以下Cypher语句创建了一个包含用户和FOLLOWS它们之间关系的Twitter式图表。

MERGE（nAlice：用户{id：“Alice”}）

MERGE（nBridget：User {id：“Bridget”}）

MERGE（nCharles：用户{id：“Charles”}）

MERGE（nDoug：User {id：“Doug”}）

MERGE（nMark：用户{id：“Mark”}）

MERGE（nMichael：用户{id：“Michael”}）

MERGE（nAlice） -  [：FOLLOWS]  - >（nBridget）

MERGE（nAlice） -  [：FOLLOWS]  - >（nCharles）

MERGE（nMark） -  [：FOLLOWS]  - >（nDoug）

MERGE（nBridget） -  [：FOLLOWS]  - >（nMichael）

MERGE（nDoug） -  [：关注]  - >（nMark）

MERGE（nMichael） -  [：FOLLOWS]  - >（nAlice）

MERGE（nAlice） -  [：FOLLOWS]  - >（nMichael）

MERGE（nBridget） -  [：FOLLOWS]  - >（nAlice）

MERGE（nMichael） -  [：FOLLOWS]  - >（nBridget）

MERGE（nCharles） -  [：FOLLOWS]  - >（nDoug）;

现在我们运行LPA来查找用户之间的社区。执行以下查询：

CALL algo.labelPropagation.stream（“User”，“FOLLOWS”，

{direction：“OUTGOING”，迭代次数：10 }）

我们的算法找到两个社区，每个社区有三个成

似乎Michael，Bridget和Alice都在一起，Doug和Mark也是如此。只有查尔斯不会强烈适应任何一方，但结果是道格和马克。

结论

正如我们所见，标签传播算法具有多种应用，从理解社会群体中的共识形成到识别生物化学网络过程（功能模块）中的蛋白质组合。