motif标签传播算法MWLP：利用高阶结构进行社区发现

导语

网络社团检测（或图聚类）对于揭示复杂网络的结构性质至关重要。标签传播算法作为一种重要的网络社团检测方法，可以在线性时间复杂度内找到网络中的社团结构，不过标签传播算法存在一些问题，比如可能忽略对于社团检测至为关键的网络高阶结构。本文提出使用网络的高阶信息 motif，捕捉网络结构特征，提升标签传播算法的性能。基于多个现实世界数据库的实验结果表明该方法的优越性。

研究领域：社团结构，高阶网络

无知影 | 作者

知乎 | 来源

原文链接：

https://zhuanlan.zhihu.com/p/349410718

标签传播算法 (LPA) 因其能在线性复杂度内找到网络中的社区结构而著称，但多次运行LPA大概率会得到不同的社区结构，稳定性令人堪忧。本文使用网络的高阶信息motif不仅提升了LPA的稳定性，也增强了算法的性能：

论文题目：

Community Detection by Motif-Aware Label Propagation

论文地址：

https://dl.acm.org/doi/pdf/10.1145/3378537

论文贡献

使用代表性模体（motif of interest）刻画网络的高阶特征。
整合高阶与低阶结构信息并据此设计了一个新的带权网络。
提出了一个新的投票策略NaS用于降低标签传播过程中的随机性以获得更稳定的社区结构。

标签传播算法（LPA）

LPA算法的思路非常简单：更新网络中每个节点的标签，使得节点标签更新为多数邻居节点的标签，如果最多的邻居标签不止一个，那么就随机选一个作为自己的标签，直到网络中的社区结构不再变化为止。

正如下图所示：网络中每个节点初始化为不同标签，随着标签传播过程的进行，结构上紧密相连的节点群会在某个特定标签上达成共识。

标签传播过程示意图（图中数字表示节点社区标签）

LPA算法在更新过程中”如果最多的邻居标签不止一个，那么就随机选一个作为自己的标签”，是造成算法不稳定的根源所在，正如下图所示的标签震荡现象：

LPA算法的不稳定性-标签震荡现象

利用高阶结构进行社区发现：MWLP算法

为了解决上面的问题，本文提出的MWLP算法可以分为以下几步：

1. 找到输入网络的代表性motif

2. 利用代表性motif重构网络权重

3. 使用新的标签更新策略NaS降低LPA算法的不稳定性

基于模体的带权标签传播算法（MWLP）示意图

找到输入网络的代表性motif

代表性motif指的是网络中重复出现的，具有显著意义的连接模式（其实就是图中反复出现的小型子图，类似DNA的某些基因片段），比如这样的：

代表性motif检测算法有很多种，例如Mfinder、MAvisto、FANMOD和Kavosh等，本文采用的是FANMOD算法（有兴趣的朋友们可以找找相关资料）。

利用代表性motif重构网络权重

我们首先需要构建一个motif权重网络，邻接矩阵元素表示为节点i和j共同作为motif端点的次数，即，其中表示的是同时包含节点i和节点j的模体实例个数。

接下来我们需要将motif权重网络和原始的邻接矩阵叠加，得到新的加权邻接矩阵 W：W=A+W_M，其中W(i, j)可以看做是节点i与节点j之间的连接亲密度，据此可以区分不同强度的连接。

标签更新策略Nas

投票策略NaS用于标签更新，该策略将节点间连接的数量和强度同时考虑在内。具体来说，在更新当前节点ν的标签时，我们为其所有邻居都分配一个投票分数。

记 Γ(ν) 为节点ν的邻居（同时考虑高阶和低阶连接）集合，对于其中任意一个邻居，其投票分数的计算如下：

Ci是邻居i所携带的标签
表示节点ν的邻居中携带标签Ci的数目
W(ν, i)衡量的是节点ν和其邻居i基于motif的亲密程度
λ∈[0, 1]是一个平衡参数用于调节邻居数量和连接质量的影响，λ可根据不同网络结构进行调节

通过NaS标签更新策略，节点ν的标签将更新为其邻居中投票分数最高者所携带的标签。若投票分数最高的邻居不止一个，则从中随机选择一个，但实际上这种随机选择的情况鲜有发生，因为投票分数取决于 , W(ν, i)以及平衡参数λ，相比于传统标签传播的更新策略，NaS策略中投票分数的可变空间更大，这意味着两个及以上节点具有同样投票分数的可能性大大降低。因此，标签传播的随机性便被削弱，这在很大程度上提升了方法的稳定性。

实验

作者首先设计了一个人工网络，其中每个节点在初始状态携带各不相同的社区标签。在同样的网络设置下，分别运行原始的LPA算法和MWLP算法多次，结果如下面两个图所示。从图中不难看出，原始的LPA算法在多次运行之后产生的社区结构各不相同，而MWLP得到的结果却较为稳定且社区结构也让人颇为满意。（本文实验所使用的motif都是无向的motif，个人感觉使用有向的motif效果会更明显）

原始的LPA算法运行结果

MWLP算法运行结果

作者将MWLP应用于7个真实数据集，并同多个社区发现算法进行对比，实验结果也显示了MWLP的优越性（尽管MWLP未能在全部数据集上均取得最高评估分数，但其平均排名在两个评估指标上均位列前三，且相比于其他算法MWLP的复杂度很低，只有O(m^1.5) ，其中m是边的数量）

NMI指标对比

purity指标对比

各数据集的平均排名对比

作者还讨论了参数λ的不同取值对MWLP算法的影响（个人感觉其实没啥影响，按照二八原则取0.2或者0.8就可以了）

以上就是本文的所有内容啦~

高阶网络读书会启动

随着对现实世界探索的不断深入，人们发现在许多真实的复杂系统中，组成系统的个体之间不仅存在二元交互关系，也广泛存在多个体同时（或以特定顺序）进行交互，即高阶交互现象。为此，研究人员分别发展出了基于超图、单纯复形、依赖关系等的网络高阶表示模型，为复杂网络分析和研究提供了新的思路。为了促进此领域的交流与合作，我们发起了【高阶网络读书会】。

集智俱乐部读书会是面向广大科研工作者的系列论文研读活动，其目的是共同深入学习探讨某个科学议题，激发科研灵感，促进科研合作。【高阶网络读书会】由电子科技大学吕琳媛老师、任晓龙老师及中国地质大学（北京）管青老师联合发起，每周分享时间为每周四 19:30-21:30 进行，预计持续 10-12 周。这其间，我们将围绕高阶交互网络的基本概念、模型、方法与应用等研究进行研讨，本次读书会分享会按照「基础理论」+「深入理论」+「案例研讨」的模式展开。