Multiplex 的社区检测算法比较

摘要

Multiplex 是同一顶点集（即 $\{G(V,E_1),\mathrm{\dots },G(V,E_m)\}$)上的一组图。 它是一个广义图，用于对顶点之间具有平行边的多重关系进行建模。 本文对现有的 Multiplex 社区检测算法进行了文献综述并进行了比较分析。

我简介

复杂性科学研究交互代理系统的集体行为，而图（网络）通常是可视化此类系统的恰当表示。 传统上，代理被表示为顶点，顶点对之间的边意味着它们之间存在交互。

然而，网络科学的现代观点是概括边缘以封装代理之间的多种类型的关系。 例如在社交网络中，人们通过工作、学校、家庭等方式认识。 这是为了保留数据的丰富性并揭示系统更深入的视角。 这称为多路复用。

Multiplex 是图的自然过渡，许多学科独立研究了这种数学模型，用于社区检测等各种应用。 社区是指行为与系统其他部分不同的一组顶点。 这是将复杂的系统模块化为更简单的表示形式，以形成信息流的更大图景。

本文的前半部分是对不同社区检测算法的文献综述以及图切割的一些理论界限。 接下来，我们提出了一套基准多路复用和相似性度量来确定各种社区检测算法的相似性。 最后我们提出本文的实证结果。

II 预赛

Definition II.1.

（多重） 多路复用是 $\mathrm{m}$ 图 $𝒢=\{{\mathrm{G}}^1,\mathrm{\dots },{\mathrm{G}}^{\mathrm{m}}\}$ 的有限集合，其中每个图 ${\mathrm{G}}^{\mathrm{i}}=(\mathrm{V},{\mathrm{E}}_{\mathrm{i}})$ 都有一个不同的边集 ${\mathrm{E}}_{\mathrm{i}}\subseteq \mathrm{V}\times \mathrm{V}$。

Multiplex 有许多同义名称，有时它们同时出现在同一篇论文中。 这是为了帮助读者通过不同的描述来可视化系统。 例如，“多层网络”将多路复用描述为图形层，即层$i$意味着$G^i\in 𝒢$。 以下列表是 Multiplex 的同义名称，本文的其余部分将避免使用： Multigraph Cormode 和 Muthukrishnan (2005)； Gjoka 等人 (2011), 多维网络 Berlingerio 等人 (2011, 2012); Hossmann 等人 (2012); Kazienko 等人 (2011); Lerch 等人 (2006);罗塞蒂等人 (2011);唐 等人 , 多重关系网络 Cai 等人 (2005);戴维斯等人 (2011);罗德里格斯和希纳维尔 (2010)； Szell 等人 (2010); Bry 等人 (2012); Louati等人(2012); Skvoretz 和 Agneessens (2007), 多层网络 Bródka 等人 (2012, 2011, 2013);李等人(2012); Cozzo 等人 (2012); Mucha 等人 (2010)、PolySocial Networks Applin 和 Fischer、多模态网络 Ambrosino 和 Sciomachen (2012) ）；勒布朗 (1988)； Nagurney (2000)、异构网络 Dong 等人 (2012) 和多重网络0> Magnani 和 Rossi (2013) 1>。 但是，我们将使用$i^{th}$ 层、关系或维度来引用图表$G^i\in 𝒢$ 。 这是为了帮助我们更具体地表达某些想法。

例如，当图层彼此堆叠时，将会存在边彼此“重叠”的顶点对（Def. II.2)。 重叠边数的分布是多路复用的一个重要特征，用于对不同的多路复用集成进行分类 Cellai 等人 (2013)；李等人 (2012);陈等人(2012); Ranola 等人 (2010);比安科尼（2013）。

Definition II.2.

（重叠边缘） 令 $𝒢$ 中两个不同图的两条边为 $\mathrm{e}(\mathrm{u},\mathrm{v})\in {\mathrm{E}}_{\mathrm{i}}$ 和 ${\mathrm{e}}^{\prime }({\mathrm{u}}^{\prime },{\mathrm{v}}^{\prime })\in {\mathrm{E}}_{\mathrm{j}}$，其中 $\mathrm{i}\ne \mathrm{j}$。 当且仅当 $\mathrm{e}={\mathrm{e}}^{\prime }$ 时，边 $\mathrm{e}$ 和 ${\mathrm{e}}^{\prime }$ 重叠，即 $\mathrm{u}={\mathrm{u}}^{\prime }$ 和 $\mathrm{v}={\mathrm{v}}^{\prime }$。

如果上下文出现歧义，我们将把 Multiplex 和 Monoplex（Multiplex 中的图形）之间的“社区”区分为 Multiplex-community 和 Monoplex-community分别。 当我们审查不同的 Multiplex 社区检测算法时，这将避免混淆。

许多这样的多路复用算法将多路复用问题划分为单工上的独立社区检测问题。 这些单工的解决方案称为辅助分区，为多路复用算法聚合提供补充信息。 聚合的主要解决方案形成了多路复用分区，它定义了多路复用中的社区。

III 多重社区的定义

社区被模糊地描述为一组交互的代理，它们的共同行为与其相邻代理不同。 然而，没有普遍接受的正式定义，因为社区的构造取决于问题领域。 Fortunato (2010) 按社区的本地定义、全局定义和顶点相似度对这种多样性进行分类。

III.1 本地定义

假设社区与其相邻顶点的交互较弱，社区的评估可以与网络的其余部分隔离。 因此，从社区成员的角度来看，建立一个社区就足够了。

将 Multiplex 中的每个图视为成员之间的独立通信模式，例如电子邮件、电话、邮政等。当其中一种通信方式失败时，高质量社区应在其成员之间恢复高信息流（少一张图）。 因此，Berlingerio 等人提出了社区 Berlingerio 等人 (2011) 的冗余作为衡量多重社区质量的指标。

Definition III.1.

（冗余） 令 $\mathrm{W}\subseteq \mathrm{V}$ 为多路复用社区中的顶点集合，$\mathrm{P}\subseteq \mathrm{W}\times \mathrm{W}$ 为 $\mathrm{W}$ 中与 $\ge 1$ 中相邻的顶点对集合> 关系。 冗余顶点对的集合是${\mathrm{P}}^{\prime }\subseteq \mathrm{P}$，其中$\mathrm{W}$中的顶点对在$\ge 2$关系中相邻。 $\mathrm{W}$的冗余度由下式决定：

$$\frac{1}{|𝒢|\times |P|}\sum _{G^i\in 𝒢}\sum _{\{u,v\}\in P^{\prime }}\delta (u,v,E_i),$$ (1)

其中如果 $\{u,v\}\in E_i$，则 $\delta (u,v,E_i)=1$（否则为零）。

等式。 1 计算多路复用社区中相应顶点对在两个或多个图中相邻的边的数量。 该总和通过所有相邻顶点对之间的理论最大边数（即 $(|𝒢|\times |P|)$)进行归一化。 多路复用社区的质量取决于多路复用中各图中子图（由多路复用社区的顶点引起）的相同程度。

因此，冗余并不取决于多路复用社区中的边数，即不是其质量的必要条件。 这可能会导致一个不寻常的想法，即社区的密度可能较低。 例如，重叠边缘的循环形成与重叠边缘的完整集团相同质量的“社区”。

III.2 全局定义

分区的全局度量考虑了社区的质量以及社区之间的交互。 例如，Newman 和 Girvan 的模块化函数衡量单一社区与随机图的差异程度（Def. III.2)纽曼（2006）。

Definition III.2.

（模块化） 令 ${\mathrm{A}}_{\mathrm{i}\mathrm{j}}$ 为具有 $|\mathrm{E}|$ 条边的图的邻接矩阵，${\mathrm{k}}_{\mathrm{i}}$ 为顶点 $\mathrm{i}$ 的度数。如果${\mathrm{v}}_{\mathrm{i}}$和${\mathrm{v}}_{\mathrm{j}}$位于同一社区，则$\mathrm{\delta }({\mathrm{v}}_{\mathrm{i}},{\mathrm{v}}_{\mathrm{j}})=1$，否则$\mathrm{\delta }({\mathrm{v}}_{\mathrm{i}},{\mathrm{v}}_{\mathrm{j}})=0$。 模块化函数衡量社区与随机图的差异程度：

$$Q=\frac{1}{2|E|}\sum _{ij}\left(A_{ij}-\frac{k_i{k}_j}{2|E|}\right)\delta (v_i,v_j).$$ (2)

给定顶点集上的固定分区，多路复用中每个 $m$ 图的模块化都不同。 因此，良好的多重社区表明图中的所有单一社区都具有高模块化性。

为了量化这个概念，Tang 等人。 al 声称，如果多路复用中存在潜在社区，则多路复用中图的子集 ${𝒢}^{\prime }\subset 𝒢$ 有足够的信息来找到这些社区 Tang 等人 。 如果假设成立，那么从 ${𝒢}^{\prime }$ 检测到的社区应该反映多路复用中其余图（即 $𝒢\setminus {𝒢}^{\prime }$)的高度模块化。

在机器学习的语言中，选择一个随机图$G\in 𝒢$作为测试数据，并让${𝒢}^{\prime }=𝒢\setminus G$作为训练数据。 使用测试数据 $G$ 上的模块化函数来评估 ${𝒢}^{\prime }$ 上的社区检测算法生成的多重分区 $P$。如果图 $G$ 上的分区 $P$ 的模块性最大化，则 $P$ 是一个很好的多路复用分区。 这扩展了 Multiplex 的模块化度量。

III.3 顶点相似度

如果两个顶点在某种程度上相似，则它们属于顶点相似度社区。 例如，图中顶点对的边聚类系数 Radicchi 等人 (2004) 衡量它们之间公共邻居的（归一化）数量。 高的边聚类系数意味着顶点对之间有许多共同的邻居，从而表明这两个顶点应该属于同一社区。 在多路复用的扩展中，Brodka 等人。 al 介绍了跨层边缘聚类系数（CLECC）Bródka 等人（2012）。

Definition III.3.

（跨层边缘聚类系数） 给定参数 $\mathrm{\alpha }$，顶点 $\mathrm{v}$、$\mathrm{N}(\mathrm{v},\mathrm{\alpha })$ 的 MIN-Neighbors 是在 at 中与 $\mathrm{v}$ 相邻的顶点集至少 $\mathrm{\alpha }$ 个图表。 两个顶点$\mathrm{u},\mathrm{v}\in \mathrm{V}$的跨层边缘聚类系数衡量它们的公共邻居与所有邻居的比率。

$$CLECC(u,v,\alpha )=\frac{|N(u,\alpha )\cap N(v,\alpha )|}{|N(u,\alpha )\cup N(v,\alpha )\setminus \{u,v\}|}.$$ (3)

具有低 CLECC 的多重社交网络中的一对顶点表明，个体至少不通过 $\alpha$ 个社交网络共享共同的朋友集团。 因此，他们不太可能一起形成一个社区。

III.4紧密联系的社区核心

社区检测是对顶点进行分区的过程，使得每个顶点至少属于一个社区。 然而，在某些情况下，人们只需要多路复用中的某些子结构具有某些属性。 例如，密集连接社区核心是一组顶点，对于所有辅助分区Yin 和 Khaing (2013)，它们位于同一社区中。

IV 理论界限

最大割问题找到图的分区，使得跨簇产生的边数最大化。 因此，补图上的相同划分最大限度地减少了簇之间的边数。 这被称为平衡最小割问题，它与我们的社区检测问题密切相关，其中社区之间产生的边数被最小化。

因此，为了扩展我们对多路复用的理解，我们从最大割问题的已知结果开始。 它使我们能够证明多路复用上平衡最小切割问题的推论。

IV.1 复用上的最大切割问题

Theorem IV.1.

考虑同一顶点集 $V$ 上的图 $G^1,\mathrm{\dots },G^m$。存在 $V$ 到 $k\ge 2$ 社区 $C_1,\mathrm{\dots },C_k$ 的 k 分区，这样对于所有 $i=1,\mathrm{\dots },m$：

$$\text{\# edges cut in}{G}^i\ge \frac{(k-1)|E_i|}{k}-\sqrt{2m|E_i|/k}.$$ (4)

证明。

草图Kühn and Osthus (2007):$k\ge 3$的证明与$k=2$的情况类似，因此我们只证明后者。 WLOG中，$G^1$的顶点集被划分为2个相等的集合，$A$和$B$。 将 $X_i$ 定义为指示函数，其中 $X_i=1$ 如果 $i^{th}$ 边缘从 $A$ 诱导到 $B$,$X_i=0$ 否则。 由于$Pr(X_i)=1/2$并且具有期望的线性，我们得到$𝔼[X_i]=|E_i|/2$和$𝔼[X_i^2]=|E_i||E_i+1|/4$。 现在，我们可以利用切比雪夫不等式求出给定分区在 $G^1$ 时不符合不等式 4 的概率。 由于所有图失败的概率和小于1，因此存在一个划分使得所有图满足不等式4。 ∎

通过施加额外的条件对界限进行了进一步的发展，其中最大度有界 Kühn 和 Osthus (2007) 以及 $k=m=2$ Patel (2008) 的情况。 t2>。 由于图上的最大切割的解决方案是 NP 完全的，因此同时对多路复用中的所有图进行最大切割的扩展自然也是 NP 完全的。 因此，这也意味着平衡最小二分也是 NP 完全的Garey 和 Johnson (1990)。

IV.2 复用上的平衡最小切割问题

Corollary IV.1.

考虑同一顶点集 $V$ 上的图 $G^1,\mathrm{\dots },G^m$。存在将 $V$ 划分为 $k\ge 2$ 个大小相等的社区 $C_1,\mathrm{\dots },C_k$（即 $|C_i|\approx |C_j|$)的 k 分区，这样对于所有 $i=1,\mathrm{\dots },m$：

$$\text{\# edges cut in}{G}^i\le \frac{(k-1)|\overline{E}|}{k}-\sqrt{2m|\overline{E}|/k},$$ (5)

其中$|\overline{E}|=\left(\genfrac{}{}{0pt}{}{n}{2}\right)-|E_i|.$

证明。

设${\overline{G}}^i$为$G^i$的补图，其边集记为${\overline{E}}_i$。 由于图中边的最大数量为 $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$，因此为 $|{\overline{E}}_i|=\left(\genfrac{}{}{0pt}{}{n}{2}\right)-|E_i|$。 将（最大割）定理IV.1应用到补图集${\overline{G}}_i$上，并将${|\overline{E}|}_i$代入结果，推论中的表达式如下。 定理 IV.1 中的证明确保社区大小相等。 ∎

满足等式的分区5 不一定是 III 节中定义的良好社区，反之亦然。 然而，当信息流经网络/多路复用时，分区类之间引起的边缘通常被视为瓶颈。 它们类似于城市和社区之间的桥梁。 因此，社区检测算法倾向于最小化不同社区之间的边数。

V Multiplex 社区检测算法

现有多路复用社区检测算法的一般策略是从多路复用中提取特征并将问题简化为熟悉的表示。 在求解简化表示时，然后从简化问题的辅助解中推导出多重社区。

因此，许多多重算法依赖于现有的单重社区检测算法来获取临时步骤的辅助分区。 算法的选择通常与其对复用的扩展无关，因此理论上可以选择任何社区检测算法来解决中间步骤。 在本文中，我们的实验使用 Louvain 算法来生成辅助分区。

V.1投影

最简单的方法是将多重投影到加权图中。 IE。设$A^i$为$G^i\in 𝒢$的邻接矩阵。 $𝒢$ 的加权投影的邻接矩阵由 $\overline{A}=\frac{1}{m}{\sum }_{i=1}^m{A}^i$ 给出。 我们将其称为多路复用的“投影平均”。

它被独立提议作为更复杂的多路复用算法的基准，因为性能通常“低于标准”Berlingerio 等人 (2011)； Kazienko 等人 (2011);内费多夫（2011）；戴维斯等人 (2011);罗塞蒂等人(2011)。 在我们的实验中，我们将其与未加权的变体进行比较，即多路复用的“投影二进制”，即 $G(V,E_1\cup \mathrm{\dots }\cup E_m)$。

顶点对之间的另一种权重分配是考虑其邻居的连通性，其中共同邻居的高比例意味着更强的联系 Berlingerio 等人 (2011)。 这是基于同一社区的成员倾向于在同一关系子集上进行交互的想法，这是由 Brodka 等人独立提出的。 等人在Def。 III.3 Bródka 等人 (2012)。 这种替代方案将被称为“投影邻居”。

V.2 共识聚类

之前的策略首先聚合图，然后对结果图执行社区检测算法。 这是一个糟糕的策略，因为它忽略了维度 Tang 等人 的丰富信息。 因此，共识聚类策略是首先在图上单独应用社区检测算法作为辅助分区，然后通过以有意义的方式聚合这些辅助分区来导出主聚类（多重社区）。

共识聚类背后的关键概念是测量在辅助分区中的同一社区中找到两个顶点的频率。 经常位于同一单工社区中的顶点更有可能位于同一多路复用社区中。 因此，多路复用上各个图上的社区检测算法决定了多路复用社区的结构属性，而共识聚类则确定了多路复用社区的关系属性。

V.2.1 频繁关闭项集挖掘

数据挖掘是寻找在一系列事务中经常一起出现的一组项目。 例如，根据一系列销售交易，牛奶、谷物和水果等物品经常在超市一起购买。 这些集合称为项集。 柏林杰里奥等。 al 将辅助分区的共识聚类转化为一个数据挖掘问题，以发现多重社区Berlingerio 等人 (2013)。

多路复用中的顶点定义了用于数据挖掘的 $|V|$ 交易，而项是元组 $(c,d)$，其中各顶点属于维度 $d$ 中的单路社区 $c$。例如，假设顶点 $v_i$ 分别属于维度 $d_1,d_2$ 和 $d_3$ 中的单群体 $c_1,c_5$ 和 $c_2$。 $i^{th}$ 事务是项目$\{(c_1,d_1),(c_5,d_2),(c_2,d_3)\}$ 的集合。 因此，当我们使用频繁关闭项集挖掘等数据挖掘方法时，我们能够将频繁（相对于预定义阈值）项集识别为多重社区。

例如，每个顶点是超市中客户的交易，社区是超市想要发现的目标市场。 只有当目标市场足够大时才有意义，因此我们需要定义最小社区规模（例如 10）。 在这种情况下，客户的交易就是他的辅助社区成员资格。 因此，频繁关闭项集挖掘将至少在例如每个客户的交易都是目标市场项目集的子集的 10 个顶点。

V.2.2 基于簇的相似度划分算法

基于簇的相似度划分算法对位于相同辅助社区的实例顶点对的数量进行平均。 例如，在一个 5 维的复数中，如果有 3 个顶点 $v_i$ 和 $v_j$ 在同一个辅助社区中，那么顶点对 $(v_i,v_j)$ 的相似度值就是 $3/5$。

一旦测量了所有顶点对的相似性，就可以通过 k 均值聚类来确定主簇——每次迭代中具有最接近相似性的顶点被分组在一起。 因此，频繁出现在相同辅助社区中的顶点对将具有较高的相似度值，因此更有可能聚集在相同的主要社区中。 Tang 等人将这称为分区集成。 al 唐等人 .

V.2.3 广义典型相关性

每个辅助分区将顶点映射为 $l$ 维（该维独立于复用的维）欧几里得空间中的点。 这些点的定位方式是两个顶点之间的最短路径越短，它们在欧几里得空间中越接近。 其中一种映射可以通过连接邻接矩阵的顶部特征向量来实现。 因此，给定多路复用中的 $d$ 图，存在大小为 $l\times n$ 的 $d$ 结构特征矩阵 $S^i$，其中每个矩阵中的列是$l$ 维欧几里得空间中顶点的位置。

唐等。 al 希望将结构特征矩阵聚合为主结构特征矩阵 $\overline{S}$ ，以便可以根据 $\overline{S}$ Tang 等人 确定主分区。 然而，“平均”$\overline{S}=\frac{1}{d}{\sum }_{i=1}^d{S}^{(i)}$ 不会产生合理的主要结构特征矩阵，因为 $S^{(i)}$ 和 $S^{(j)}$ 之间的矩阵元素是独立的。

解决此问题的一个解决方案是转换 $S^{(i)}$ ，使它们位于同一空间，并且它们的“平均值”是合理的。 即$d$不同欧几里得空间中的同一顶点在欧几里得空间中的同一点上对齐。 具体来说，我们需要一组线性变换$w_i$，以便它们最大化$S^{(i)}$的成对相关性，而广义典型相关分析就是此类标准统计工具之一Kettenring（1971） ）。 这使我们能够以更合理的方式“平均”结构：

$$\overline{S}=\frac{1}{d}\sum _{i=1}^d{S}^{(i)}{w}_i.$$ (6)

最后通过主特征矩阵$\overline{S}$的k均值聚类确定主分区。

V.3桥接检测

图中的桥梁指的是信息流较高的边缘，就像两个城市之间繁忙的道路一样，如果没有这些道路，城市就会被分割成孤立的社区。 实现此目的的一种方法是将多路复用 $𝒢$ 投影到加权网络并根据投影确定桥。 或者，可以通过多路复用桥的定义删除它们以获得所需的分区。

在社交网络中，社区内需要牢固的边缘联系。 因此，为了识别顶点对之间的弱联系，Brodka 等人。 al 提出了 CLECC（方程3)作为一种措施。 在每次迭代中，所有连接的顶点对都会被重新计算，并且具有最低 CLECC 分数的顶点对将在所有图中断开连接。 当贪婪地产生所需数量的社区（组件）时，算法停止Bródka 等人（2012）。 这与 Girvan 和 Newman 提出的策略相同，其中图的桥梁通过其介数中心性得分 Girvan 和 Newman (2002) 来识别。 在实验中，我们将$\alpha =|𝒢|/2$设置为方程式中的CLECC分数。 3。

V.4 张量分解

代数图论是图论的一个分支，其中使用线性代数等代数方法来解决图问题。 因此，多路复用的自然表示是 $3^{rd}$ 阶张量（作为多维数组）而不是矩阵($2^{nd}$ 阶张量）。 Multiplex 中的 $m$ 图集是一组 $m$ $n\times n$ 邻接矩阵，可以表示为 $m\times n\times n$ 多维数组（张量）Rodriguez 和 Shinavier (2010)。 这使我们能够利用可用的张量算术，例如张量分解。

张量分解类似于矩阵中的奇异值分解和“下上”分解，它们将张量表示为更简单的分量。 例如，PARAFAC 张量分解 Harshman (1970) 是张量 $𝒯$ 的 k 级近似，作为一级张量（向量 ${\overline{u}}^{(i)}$ 、${\overline{v}}^{(i)}$ 和 ${\overline{w}}^{(i)}$)，即：

$$𝒯\approx \sum _{i=1}^k{\overline{u}}^{(i)}\circ {\overline{v}}^{(i)}\circ {\overline{w}}^{(i)}.$$ (7)

其中 $\overline{a}\circ \overline{b}$ 表示向量外积。 $i^{th}$ 因素中的组成部分，${\overline{u}}^{(i)}$、${\overline{v}}^{(i)}$ 和 ${\overline{w}}^{(i)}$ 表明存在很强的联系（可能是集群/社区）通过 ${\overline{w}}^{(i)}$ 中顶部组件中的尺寸在 ${\overline{u}}^{(i)}$ 和 ${\overline{v}}^{(i)}$ 中的元素之间。

例如，假设 ${\overline{w}}^{(i)}$ 中的 $j^{th}$ 元素是最大的元素。 这表明在 $i^{th}$ 社区中，${\overline{u}}^{(i)}$ 中的前 10 个（或任何预定义阈值）元素与 ${\overline{v}}^{(i)}$ 中的前 10 个元素位于同一集群中通过$j^{th}$维度/关系Dunlavy等人（2011）； Leginus 等人 (2012);米尔扎尔和古川（2010）； Papalexakis 等人 (2013)。

VI 基准多重

Erdös-Rényi 图 是顶点对以固定概率 Erdös 和 Rényi (1960) 连接的图。 这种结构的随机性通常不具有任何有意义的社区结构。 因此，用作社区检测算法的基准图并不理想。

因此，基准图应该类似于格文和纽曼模型，其中在一组密集子图（作为社区）之间引入一些随机边以形成单个连接的组件/图。 这组密集子图充当社区检测算法要发现的图的“真实”社区，因此成为社区检测算法的基准。 本节的目标是为 Multiplex 设计类似的基准。

主要挑战是，对于良好的多元化社区，目前还没有一个普遍接受的定义。 因此，我们没有办法构建一个不支持某些算法的基准。 因此，以下基准图的目的是研究这些多重社区检测算法之间的关系。 这使我们能够使用一组高度不相关的算法来研究多重社区的不同视角。

VI.1 非结构化合成随机多重

随机多路复用的最简单构造是在同一顶点集上生成一组独立图。 然而，许多社区检测算法都是基于对现实世界多路复用的一些观察，并且这些算法不会在这种随机构造上产生有趣的结果。 我们将此类随机多路复用表示为非结构化合成随机多路复用 (USRM)，它们类似于 Erdős-Rényi 图，其中社区检测算法不应在其中找到任何有意义的社区。

为了简化数值实验，多路复用中只有二维，这样我们就可以轻松生成 Erdős-Rényi、Watts Strogatz Watts 和 Strogatz (1998) 和 Barabási-Albert 图 阿尔伯特和巴拉巴西 (2002)。 这种结构的统计特性可以在Loe and Jensen (2013)中找到。

Name	Graph 1	Graph 2
USRM1	Erdős-Rényi	Erdős-Rényi
USRM2	Erdős-Rényi	Watts Strogatz
USRM3	Erdős-Rényi	Barabási-Albert
USRM4	Watts Strogatz	Watts Strogatz
USRM5	Watts Strogatz	Barabási-Albert
USRM6	Barabási-Albert	Barabási-Albert

实验中顶点集的大小为128。 重要的是，两个图中的边数相等，以便两者都不会主导多路复用的交互。 为了确保 Erdős-Rényi 图以高概率连接，顶点对连接的概率必须为 $>\ln |V|/|V|$。 因此，Erdős-Rényi 图（以及多路复用中的其他图）中的边数为 $\left(\genfrac{}{}{0pt}{}{128}{2}\right)2\ln 128/128\approx 616$。

VI.2 结构化合成随机多重

这种结构类似于格文和纽曼模型，其中独立生成的社区以保留“真实”社区的方式连接。 然而，我们在上面看到 Multiplex 社区有不同的观点，我们希望将这些想法封装到 Multiplex 基准中。

结构化合成随机多路复用 (SSRM) 是一种结构，其中不同的多路复用分区提供由不同定义定义的高质量多路复用社区。 然而，与此同时，从多重社区的其他定义的角度来看，分区的质量必须“不太理想”。

我们首先生成多重社区，每个社区对于社区的不同独立定义而言都是高质量的。 接下来，我们修改这些多路复用社区，使其在三个多路复用社区定义之一中保持良好质量，而在其他定义中保持较差质量。 最后一步是将这些 Multiplex 社区合并为一个 Multiplex，作为我们的 SSRM 基准（图 1)。

图 1 将 $\{[c_1,c_2],[c_3,c_4]\}$ 显示为具有 2 个社区的分区，其中集群 1 和 2 形成一个社区，集群 3 和 4 形成第二个社区。 该分区具有高冗余、低模块化和低CLECC复用社区。 还有另一个分区 $\{[c_1,c_3],[c_2,c_4]\}$，其中社区具有较高的模块化程度，但其余指标较低。 最后 $\{[c_2,c_3],[c_1,c_4]\}$ 是社区具有高 CLECC 顶点对的最终分区。 这种综合多重表达了多重社区的多视角性质。

图1： 为了帮助可视化，这个二维 SSRM 中的边缘用实线和虚线绘制。 令簇 $c_1$ 和 $c_3$ 为稠密子图，其中实边多于虚边。 类似地，$c_2$ 和 $c_4$ 是密集子图，其虚线边缘多于实线边缘。 I： $c_1$ 和 $c_4$ 之间的实心边意味着它们之间仅存在实心边。 这同样适用于 $c_2$ 和 $c_3$ 之间的虚线边缘。 II： $c_1$ 和 $c_2$ 之间的所有边都重叠。 III：$c_1$和$c_3$（或$c_2$和$c_4$)之间的边没有重叠。 我们将 $\{[c_1,c_2],[c_3,c_4]\}$ 表示为具有 2 个社区的分区，其中集群 1 和 2 形成一个社区，集群 3 和 4 形成第二个社区。 该分区具有高冗余、低模块化和低CLECC复用社区。

VI.2.1高模块化、低冗余和低 CLECC 复用社区

为了创建一个高度模块化的多重社区，我们从集群 1 和集群 3 开始，在两个维度上都作为一个类似派系的结构。 为了使这些集群的冗余度较低，我们必须删除两个集群中的一些边，以便集群中很少有重叠的边，同时保持高模块化性。 这可以通过使两个簇中的第一维图成为第二维图的补集来完成。

下一步是在簇 1 和簇 3 之间添加边，使生成的簇成为单个连接组件。 我们将 $[c_1,c_3]$ 表示为由集群 1 和集群 3 连接的组件。 为了保持低冗余，新边不能重叠。

最后，我们需要调整簇，使得簇 1 和簇 3 的组合组件中大量顶点对之间的 CLECC 分数较低。 具体来说，我们希望上一步中新边连接的顶点对具有较低的 CLECC 分数。 如果簇 1 在第一维度中具有更多边缘，而簇 3 在第二维度中具有更多边缘，则这是可能的。 这样做时，簇 1 中顶点的邻居将与簇 3 中顶点的邻居显着不同，因此 CLECC 分数较低。

相同的构造适用于集群 2 和集群 4，其中集群 2 与集群 3 相似，集群 4 与集群 1 相似。

VI.2.2 高 CLECC、低模块化和低冗余复用社区

由于所有 4 个簇都不具有重叠边缘，因此多路复用上的任何分区的冗余度仍然较低。 因此，第一步是使聚类 1 和 4 的 CLECC 分数较高，并对聚类 2 和 3 应用相同的构造。

由于簇 1 和 4 类似地基于上一小节的构造，因此每个簇中任何给定顶点的邻居也将相似。 因此，在簇 1 和簇 4 之间添加新边不会影响 CLECC 分数。 然而，这些新边应该仅在第一维中绘制，因为它是$[c_1,c_4]$中的主要维度。 这同时降低了第二维中 $[c_1,c_4]$ 的模块化，因为簇没有连接并且第二维中的图是稀疏的。 这为多元化社区提供了较低的模块化，同时保持了较高的 CLECC 分数。

簇 2 和簇 3 的构造类似，但只有第二维中的边将两个簇连接在一起。

VI.2.3 高冗余、低模块化和 CLECC 多重社区

鉴于 $[c_1,c_3]$ 的 CLECC 分数较低，因此相同的分数应适用于 $[c_1,c_2]$，因为聚类 2 和聚类 3 相似。 主要目标是连接集群 1 和集群 2，使得 $[c_1,c_2]$ 的冗余度较高。 冗余度由等式测量。 1，计算重叠边的数量。 由于此时的构造没有重叠边，因此增加冗余的最简单方法是在簇之间添加新的重叠边以形成组件 $[c_1,c_2]$ 和 $[c_3,c_4]$。

虽然$[c_1,c_2]$和$[c_3,c_4]$与多路复用中的其他分区相比具有相对较高的冗余，但它仍然比USRM1中的随机社区具有较低的冗余。 为了提高冗余度，有必要添加新的边，使得四个簇中存在重叠。 然而，这可能会增加我们想要避免的 $[c_1,c_2]$ 的模块化。 因此，最后一步必须逐步完成。

VI.2.4 不同地面实况分区的评估

有 3 个不同的“ground-truth”分区 $\{[c_1,c_2],[c_3,c_4]\}$、$\{[c_2,c_3],[c_1,c_4]\}$ 和 $\{[c_1,c_3],[c_2,c_4]\}$，它们各自代表一个不同的“ideal-partition”。 然而，同时从其他指标的角度来看，它们“不太理想”。 尽管其中一些指标总体上是相关的（来自我们的实验），但 SSRM 的这些真实划分表明这些指标都能够捕获社区结构的基本方面。

	Redundancy	*CLECC	**Modularity
$[c_1,c_2]$	0.0492	0.1142	-0.0287
$[c_3,c_4]$	0.0537	0.1087	-0.0332
$[c_2,c_3]$	0	0.1541	0.007
$[c_1,c_4]$	0	0.1642	0.012
$[c_1,c_3]$	0	0.1113	0.0317
$[c_2,c_4]$	0	0.1083	0.0245
Random	0.0217	0.1056	0.0033

表格1： 这些行（最后一行除外）是配对的，这样它们就意味着一个公共分区。 例如，前两行是分区 $\{[c_1,c_2],[c_3,c_4]\}$ 的社区。 群落$[c_1,c_2]$的冗余度和CLECC得分分别为0.0492和0.1142。 *CLECC： CLECC 分数是社区中所有顶点对之间的平均 CLECC 分数。 **模块化： 分区中的两个值指的是 Multiplex 中两个图的模块化。 例如。分区 $\{[c_1,c_2],[c_3,c_4]\}$ 的 SSRM 第一维和第二维的模块化程度分别为 -0.0287 和 -0.0332。 如果一个分区的测量值比最大值（粗体值）更接近随机分区（最后一行），则该分区“不太理想”。

例如表1显示分区$\{[c_1,c_2],[c_3,c_4]\}$具有最大冗余的社区。 然而，它具有多模块化性，并且 CLECC 得分与随机分区相似，这表明它相对于其他指标“不太理想”。

VI.3现实世界多路复用

合成多重的问题在于它不能正确反映现实世界的系统。 顶点之间的关系是人为强加的，以便我们可以区分不同的社区检测算法。 然而，现实世界的社区不会以如此系统的方式运作，即使它们是由不同的动力创建的，也可能会接近类似的结构和关系。 因此，我们将多重社区检测算法与开放数据集中的真实世界多重进行比较。

VI.3.1 Youtube 社交网络

YouTube 是一个视频共享网站，允许视频创作者和观众之间进行互动。 Tang 等人收集了 15,088 个活跃用户，形成一个具有 5 个关系的多路复用，其中两个用户连接，如果 Tang 等人 ：

1. 他们在彼此的联系人列表中；

2. 他们的联系人列表重叠；

3. 他们订阅同一用户的频道；

4. 他们有普通用户的订阅；

5. 他们分享共同喜爱的视频。

VI.3.2交通网络

交通网络中的广义图被称为多式联运网络，其中公交车站、车站和终点站是转乘不同交通工具的不可区分的位置（顶点）。 Cardillo等人根据欧洲航空运输（EAT）网络的数据构建了一个以450个机场为顶点的空中交通复合交通Cardillo等人（2013）。 如果两个顶点之间存在直接飞行，则在两个顶点之间绘制一条边。 EAT 网络中的 37 家不同航空公司中的每家都在机场之间形成了关系。

由于航空公司的基地往往位于老旧的大型机场，因此存在“富者愈富”的现象，新机场往往有直飞主要机场的航班。 因此Cardillo等人通过确保度分布遵循幂律分布来验证这一现象，这意味着无标度系统。

VII 比较分区

归一化互信息 (NMI) Manning 等人 (2008) 是网络分区的一种流行的相似性度量，其中 $[0,1]$ 之间的实值分数与分数 1 表示相同的分区。 然而，我们无法简单地将 NMI 指标应用于所有算法的所有成对比较。

与其他算法不同，频繁闭合项集挖掘和张量分解会产生重叠社区，而 NMI 并非旨在测量重叠社区。 此外，这些算法也不能确保所有顶点都属于至少一个社区，即可能存在没有社区成员资格的“孤立”顶点。 因此，即使是重叠社区的 NMI Lancichinetti 等人 (2009) 的变体也不适用于我们的研究。

调整兰德指数是分类研究中 NMI 的替代指标Hubert 和 Rabie (1985)。 它用于测量重叠社区的扩展被称为 Omega 指数 Collins 和 Dent (1988)，并且能够测量具有孤立顶点的分区。 与 NMI 的重叠变体不同，两个非重叠分区与 Omega 指数的比较可简化为调整兰德指数。

VII.1 归一化互信息

互信息$I(𝒜;ℬ)$在给定$B$中的社区成员资格的情况下测量$A$中所有顶点对的社区成员资格信息，反之亦然。 粗略地说，给定 $ℬ$，我们能在多大程度上猜测 $𝒜$ 中的顶点对位于同一社区中？ 正式定义为 $I(𝒜;ℬ)=H(𝒜)-H(𝒜|ℬ)$，其中 $H(𝒜)$ 是香农熵：

$$H(𝒜)=-\sum _{k}P(a_k)\log P(a_k).$$ (8)

其中$P(a_k)$是随机顶点位于分区$𝒜$的$k^{th}$社区中的概率，即$k^{th}$的大小的比率> 社区的顶点总数。 类似地，$P(b_k)$ 表示分区$ℬ$ 的情况。 互信息也可以表示为：

$$I(𝒜;ℬ)=\sum _j\sum _{k}P(a_k\cap b_j)\log \frac{P(a_k\cap b_j)}{P(a_k)P(b_j)},$$ (9)

其中 $P(a_k\cap b_j)$ 是随机顶点同时位于 $k^{th}$ 和 $j^{th}$ 社区中的概率。 基本上，$𝒜$和$ℬ$的$k^{th}$和$j^{th}$社区的交集越大，互信息就越高。 最后标准化互信息分数：

$$\text{NMI}(𝒜,ℬ)=\frac{I(𝒜;ℬ)}{[H(𝒜)+H(ℬ)]/2.}$$ (10)

VII.2 欧米茄指数

未经调整的 Omega 指数对相同数量社区中的顶点对数量进行平均。 已知此类顶点对一致。 考虑有两个分区$𝒜$和$ℬ$的情况，其中社区的数量分别为$|𝒜|$和$|ℬ|$。 函数$t_j(𝒜)$返回恰好出现在$𝒜$中的$j\ge 0$重叠社区中的顶点对集合。 因此，未经调整的欧米茄指数：

$${\omega }_u(𝒜;ℬ)=\frac{1}{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}\sum _{j=0}^{max(|𝒜|,|ℬ|)}|t_j(𝒜)\cap t_j(ℬ)|.$$ (11)

为了考虑偶然分配到相同社区的顶点对，我们必须从空模型的预期 omega 索引中减去它：

$${\omega }_e(𝒜;ℬ)=\frac{1}{{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}^2}\sum _{j=0}^{max(|𝒜|,|ℬ|)}|t_j(𝒜)|\cdot |t_j(ℬ)|.$$ (12)

最后，欧米茄指数由下式给出：

$$\omega (𝒜;ℬ)=\frac{{\omega }_u(𝒜;ℬ)-{\omega }_e(𝒜;ℬ)}{1-{\omega }_e(𝒜;ℬ)}.$$ (13)

欧米茄指数有可能为负值，其一致性低于纯粹随机巧合的预期。 它被认为是无趣的，因为它除了表明分区不相似这一事实之外没有任何暗示。 相同分区的 Omega 指数为 1。

VII.3 经验结果的符号

为了简化展示实验结果的图，我们将使用一些简写来表示算法和分区。 对于社区检测算法，我们使用$𝒜$和$𝒫$分别表示“算法”和“SSRM分区”（表2)。

Notation	Description
${𝒜}_1$	Projection-Binary
${𝒜}_2$	Projection-Average
${𝒜}_3$	Projection-Neighbors
${𝒜}_4$	Cluster-based Similarity Partition Algorithm
${𝒜}_5$	Generalized Canonical Correlations
${𝒜}_6$	CLECC Bridge Detection
${𝒜}_7$	Frequent Closed Itemsets Mining
${𝒜}_8$	PARAFAC, Tensor Decomposition
${𝒫}_1$	$\{[c_1,c_2],[c_3,c_4]\}$ of SSRM
${𝒫}_2$	$\{[c_2,c_3],[c_1,c_4]\}$ of SSRM
${𝒫}_3$	$\{[c_1,c_3],[c_2,c_4]\}$ of SSRM

表2： 不同算法和“真实情况”社区的简写。

VIII多重社区检测算法的实证比较

VIII.1 非结构化合成随机多重

图2显示了USRM基准的所有成对多重社区检测算法的Omega指数。 右侧最后 13 个箱线图是与重叠社区算法的成对比较，即 ${𝒜}_7$ 和 ${𝒜}_8$。

第一个观察结果是 ${𝒜}_8$ (PARAFAC) 与任何算法都不相似。 原因之一是很难为 PARAFAC 选择正确的参数，即方程 (1) 的 $k$ 近似值。 7 以及一阶张量的前几个元素的预定义阈值。 对于给定的图，除了手动实验外，没有系统的方法 Dunlavy 等人 (2011)； Leginus 等人 (2012);米尔扎尔和古川（2010）； Papalexakis 等人 (2013)。

然而，重叠社区算法${𝒜}_7$（频繁关闭项集挖掘）类似于一类非重叠算法，即${𝒜}_1$到${𝒜}_4$。 具体来说，频繁闭项集挖掘类似于投影算法${𝒜}_1$到${𝒜}_3$类。 事实上，算法系列 $ℱ=\{{𝒜}_1,{𝒜}_2,{𝒜}_3,{𝒜}_4,{𝒜}_7\}$ 的所有成对比较的 Omega 指数通常大于其他算法对。 图 3 中的 NMI 分数支持了这一点。

然而，算法系列 $ℱ$ 对于 USRM 1、3 和 6 的成对 Omega 指数和 NMI 分数较低。 没有根本原因说明为什么投影算法类(${𝒜}_1$ 到 ${𝒜}_3$)应该产生非相似社区，因此我们可以推断 USRM 1、3 和 6 不是好的多路复用为基准。

原因是USRM1是两个Erdős-Rényi图的组合，因此不存在社区结构。 而 USRM 3 和 6 分别是 Barabási-Albert 图与 Erdős-Rényi 和 Barabási-Albert 的组合。 尽管 Barabási-Albert 具有结构特性，但它具有较低的聚类系数（类似于 Erdős-Rényi），该系数衡量顶点聚类在一起的趋势。 因此，USRM 3 和 6 中的顶点不形成社区。

为了增加多路复用的聚类系数，我们可以在系统中引入 Watts Strogatz 图。 我们可以近似这种多重投影的聚类系数Loe and Jensen (2013)并推断社区存在的趋势。 这使我们能够从 USRM 2、4 和 5 等基准多路复用中观察算法之间有趣的关系。

例如图3中的USRM 5表明$ℱ$与${𝒜}_6$（CLECC桥检测）的相似性范围很宽。 当我们研究它们与 SSRM 基准的关系时，这一点更加明显。

图2： 不同基准 USRM 的所有成对多重社区检测算法的 Omega 指数。 x轴上的元组$(i,j)$指的是${𝒜}_i$和${𝒜}_j$的成对比较。 元组的排列使得与重叠社区算法（13 个元组）的比较位于右侧。

图3： USRM 基准的所有成对非重叠多重社区检测算法的 NMI 分数。 元组的排列方式使得 $\{{𝒜}_1,{𝒜}_2,{𝒜}_3,{𝒜}_4\}$ 的成对比较分组到箱线图的左侧。 “有趣”的数字 USRM 2、4 和 5 放在右侧进行比较。

VIII.2 结构化合成随机多重

在上一节中，USRM 基准表明 $\{{𝒜}_1,{𝒜}_2,{𝒜}_3,{𝒜}_4\}$ 会产生类似的社区。 然而，图 4 显示，${𝒜}_4$（基于聚类的相似性划分算法）中的 SSRM 社区与投影算法类(${𝒜}_1$ 到 ${𝒜}_3$)。 因此我们可以得出结论，基于簇的相似度划分算法为多重社区提供了另一种视角，并且它不能简化为投影算法类。

回想一下上一节中的最后观察，${𝒜}_6$（CLECC 桥检测）与投影算法的相似性范围很广。 图4显示，存在它们非常不同的情况（接近NMI=0），并且存在NMI$>0.8$的情况。 通过这种方式，我们的实验凸显了 CLECC 桥检测算法的弱点。

CLECC 有时会过早地产生单独的组件，其中一个组件是一小群顶点，甚至是作为一个社区的单个顶点。 因此，CLECC 似乎产生了显着不同的社区，因为其余算法倾向于产生平衡大小的社区。 因此，如果我们排除 CLECC 的此类情况，${𝒜}_6$ 与 SSRM 的投影算法类似。

最后，我们将算法与“ground-truth”分区 ${𝒫}_1$、${𝒫}_2$ 和 ${𝒫}_3$ 进行比较。 表3显示，没有一种算法能够捕获${𝒫}_1$，即具有高冗余的分区。 ${𝒜}_3$（Projection-Neighbors）被提出来提取高冗余社区Berlingerio等人（2011）。

相反，${𝒜}_6$（CLECC 桥检测）能够找到高 CLECC 分区${𝒫}_2$。 然而，与任何投影算法(${𝒜}_1$ 到 ${𝒜}_3$)相比，它没有任何优势。 这进一步支持 ${𝒜}_6$ 与投影算法类相似。

Tang 等人的结果。 al 表明，${𝒜}_5$（广义规范相关性）往往比 ${𝒜}_4$（基于聚类的相似性划分算法）更好地捕获像 ${𝒫}_3$ 这样的高模块化社区唐等人 . 本实验中也观察到了这一点。

图4： SSRM 基准的所有成对非重叠多重社区检测算法的 NMI 分数。 元组的排列方式与图3相同。

	${𝒫}_1$	${𝒫}_2$	${𝒫}_3$
${𝒜}_1$	0	0.983	0
${𝒜}_2$	0.002	0.94	0.017
${𝒜}_3$	0	0.978	0
${𝒜}_4$	0.019	0.14	0.083
${𝒜}_5$	0.004	0.002	0.158
${𝒜}_6$	0.006	0.964	0.006

表3： 算法和不同真实分区之间的 NMI 分数。 粗体条目表示“接近”真实分区的算法。

VIII.3现实世界多路复用

欧洲航空运输网络的结果与 Youtube 社交网络类似，因此图 5 足以进行此讨论。 总体观察类似于图 2 中的 USRM 2、4 和 5，其中算法集 $\{{𝒜}_1,{𝒜}_2,{𝒜}_3,{𝒜}_4,{𝒜}_7\}$ 与成对 NMI 得分 $\approx 0.55$ 相对相似>。

此外，图5强调重叠社区检测算法${𝒜}_8$（PARAFAC）与${𝒜}_5$（广义规范相关性）相对更相似。非重叠社区检测算法。 这种观察结果在图 2 中不太明显。

不幸的是，尽管参数选择不同，${𝒜}_6$（CLECC 桥检测）往往会过早停止。 因此，我们在此实验中未能获得有关 CLECC 桥检测的任何见解。

图5： 欧洲航空运输网络所有成对算法的 Omega 指数热图。 这个结果与Youtube社交网络类似。

VIII.4总结

算法${𝒜}_6$、${𝒜}_7$和${𝒜}_8$中的参数需要手动微调才能产生有意义的社区进行比较。 因此，详尽地测试这些算法的所有配置是不切实际的。 然而，当选择不同的参数时，分析结果不会发生任何本质的变化。

从 USRM 基准和现实世界的多路复用来看，$\{{𝒜}_1,{𝒜}_2,{𝒜}_3,{𝒜}_4,{𝒜}_7\}$ 组中的算法往往会生成相对相似的分区。 然而，SSRM 基准测试表明 ${𝒜}_4$ 能够捕获高冗余社区，并且执行方式与投影算法类别不同。

我们对 USRM 和 SSRM 基准进行的实验表明，当算法不将小顶点簇推断为社区时，${𝒜}_6$（CLECC 桥检测）与投影算法类 $\{{𝒜}_1,{𝒜}_2,{𝒜}_3\}$ 类似。 因此，如果不仔细分析，CLECC 桥接检测不是很稳定。

最后我们必须强调，对于大多数成对比较来说，绝对 Omega 指数和 NMI 指数通常较低 ()。 这意味着算法在技术上以不同的方式感知不太理想的多重社区。 然而，我们的结果表明，社区内的一些顶点簇比其他算法更有可能被某些算法捕获。

九讨论与结论

文献综述和 SSRM 基准强调了定义多重社区的额外复杂性。 它是社区的结构拓扑及其关系之间的平衡。 SSRM 是一个有用的基准，可以揭示这些算法之间的根本差异。 因此，需要进行进一步的研究来改进 SSRM，以使社区的不同定义更加明显。

本文的主要贡献是巩固和比较所有现有的多重社区检测算法。 多路复用的一长串同义名称导致许多研究人员不知道多路复用的相关工作，因此倾向于使这项研究变得分散和分散Mikko Kivela (2013)。 因此，我们希望本文能让人们认识到多重社区检测算法的进一步发展，以便研究人员能够在现有想法的基础上继续发展。