食品安全追溯网络中的社群识别技术

除了关注单个节点特征以外，还应该关注食品供应链网络中是否有些节点关系非常紧密，形成一定的圈子（社群）。这些社群在现实中对应于有经常性业务往来的供应链伙伴。并且，在同一个社群中，成员联系紧密；而不同群体之间，节点联系比较松散。因此，从食品供应链网络中识别出联系密切的社群，对于可追溯食品供应链精细化管理和风险重点监控具有重要意义。

社群是由网络中联系紧密的节点形成的一种子图，在社群外部，节点连接松散［130］。从单个网络节点来看是自发和无序的，但如果从社群行为来看，则可能表现出局部的规则性和全局的有序性［131］。

社群识别是按照节点间的连接关系把节点划分成若干节点组，以发现网络固有的社群结构。目前，社群识别算法研究成果丰富［129］，并在各领域得到了广泛使用［132］。可将社群识别算法大致分为基于相似度的聚类算法［133］、基于模块质量优化的算法［134］、节点分裂的算法［130］及重叠社群发现算法［135，136］。针对社区识别方法，我们一方面使用图数据库Neo4j的传统挖掘算法，另一方面，我们还针对大数据场景设计了一种正则化马尔科夫聚类社群识别算法，并通过数据计算表明了本方法的可行性和优越性。

Neo4j的图挖掘算法包已经实现了两种社群识别算法，即标签传播算法和鲁汶社群识别算法，可以通过直接调用Neo4j算法包的方法来进行社群识别与划分。

（1）标签传播社群识别算法

标签传播算法是一种基于图的半监督学习方法，它先将已知社群的网络节点标示出来，即给该节点打上所属社群的标签，接下来按照一定方法将代表社群号的标签进行传播，最后达到稳定状态的时候，每个节点都有相应的标签，以此来预测未知节点的标签信息，起到社群划分的作用［137-139］。标签传播算法的基本思想是在初始阶段，先给每个节点赋上一个标签（如果是已知标签，则将该标签赋给该节点；如果未知，则设定为一个独立的初始标签），然后，根据节点与相邻节点的相似度，将该节点的标签传给下游节点，每个节点也会接收来自上游不同节点的标签。这时候，每个节点将根据它接收到的标签按对应节点的相似度进行排序，用相似度最大的节点的标签来更新自己的标签。经过反复迭代，标签不断传播，最后相似节点的标签就会趋于相同，每个节点都有了自己的标签，而这个标签就是节点所属的社群号。

Neo4j标签传播社群划分算法调用语句如下图的左侧所示，algo.labelPropagation方法的前两个参数分别是节点和关系的名称，对应的关系图谱如图的右侧所示。计算结果会给每个节点增加一个“community＿id”属性，用于保存每个节点所属的社群。还可以使用下面的Cypher代码来统计前面用标签传播算法划分的社群情况。

图6.11　Neo4j社群识别LPA算法的Cypher代码及结果统计(www.xing528.com)

（2）鲁汶社群识别算法

鲁汶社群识别算法其原理采用的是合并策略，合并标准是模块度增益。即首先将每个节点初始化为不同的社群号，再分别计算将节点加入到邻居社群以后模块度的变化，将当前节点与使模块度增加最大的邻接节点进行合并，将合并后的社群设为当前节点的社群，直到模块度增益不再变化，则停止合并。可以看出，采用不同的社群识别算法，得到的社群结构是不同的。标签传播算法可以指定要最终划分出来的社群数，鲁汶算法最后识别的社群数是未知的。

图6.12　Neo4j社群识别Louvain算法的Cypher代码及结果统计

（3）基于聚类的社群识别算法

在众多的社群识别算法中，MCL（Markov Clustering）算法［140］也称得上经典。MCL算法是将网络之间的交互模拟为在网络中的随机行走过程，假设从某节点出发，进入到一个社群的时候，会尝试遍历其内部的多数节点，然后才走出该社群。该行走过程是由扩展和膨胀两个过程反复迭代来实现的。首先，将网络表示成一个随机马尔科夫矩阵，扩展操作的每一步都选择距离较长的路线行走，而膨胀则通过一定操作，使节点之间的连接密者愈密疏者愈疏，如此反复，直到不再变化或变化小于某个阈值，最后得到不同聚类，完成社群的划分。

马尔科夫聚类算法完全是基于网络结构进行社群划分，原理简单，实现起来也比较容易。然而该算法计算速度比较慢，最后产生的聚类数目也可能会比较多，特别是当网络庞大、结构复杂时，不容易快速得到社群划分结果。为克服上述不足，我们对马尔科夫聚类社群划分算法进行改进，建立了正则化马尔科夫聚类RMCL（Regularized MCL）算法。