异构平台上的社区检测探索

### 异构平台上的社区检测探索 #### 1. 引言 在图论中，社区被定义为一组紧密相连的顶点集合，这些顶点与网络的其他部分连接稀疏。社区检测，即将网络划分为社区的问题，能让我们深入了解复杂网络的结构，在生物学和社会学等不同研究领域有诸多应用。例如，在蛋白质 - 蛋白质相互作用网络中，社区可能对应具有相似功能的蛋白质；在社交网络中，对应有相同兴趣的人；在学术合作网络中，对应研究同一主题的研究人员。 尽管已经有很多研究致力于理解复杂网络的社区结构并设计社区检测算法，但对于如何检测社区尚未达成共识，也没有一种算法被普遍接受。此外，对算法性能的关注较少，当网络规模增大时，这就成了一个问题。使用先进的社区检测算法分析包含数百万甚至数十亿条边的大规模网络可能需要数分钟甚至数小时，因此减少这些算法的处理时间很有必要。 可扩展社区检测（Scalable Community Detection，SCD）是一种现代算法，能产生高质量的结果。SCD 通过贪婪地最大化加权社区聚类（Weighted Community Clustering，WCC）指标，将网络划分为社区。WCC 是一种基于三角形计数的新型社区质量指标。SCD 被设计为高度并行，以便在现代并行平台上高效运行。 本文展示了该算法在大规模并行架构上的潜力，提出了专门为 GPU 设计的 SCD 版本。这个版本将算法中计算量最大的阶段完全放在 GPU 上运行，能带来高性能，但要求整个网络能装入设备内存。为解决这个限制，我们将其扩展为 Het - SCD，这是一个在混合 CPU - GPU 平台上运行的异构版本。Het - SCD 尝试在一个或多个 GPU 上处理尽可能多的顶点，其余顶点在 CPU 上处理，从而有效地结合了 CPU 的大内存容量和 GPU 的强大计算能力。 我们在来自 SNAP 存储库的六个真实数据集上进行了评估，最大的数据集有 18 亿条边。结果表明，仅使用 GPU 时，Het - SCD 相比顺序 CPU 实现能获得数量级的加速。此外，即使网络规模超过 GPU 内存，需要在 CPU 上处理一部分顶点，使用 GPU 对性能仍然有益。 #### 2. 背景 可扩展社区检测（SCD）算法通过最大化加权社区聚类（WCC）指标，将无向无权网络划分为社区。下面简要介绍 WCC 和 SCD。 ##### 2.1 WCC 指标 WCC 是衡量网络划分为社区质量的指标。其基于这样的直觉：顶点与同一社区内的顶点形成的三角形比与社区外顶点形成的三角形更多。 给定一个无向无权图 $G = (V, E)$，顶点 $x \in V$ 和社区 $C \subseteq V$，设 $t(x, C)$ 为顶点 $x$ 与社区 $C$ 内顶点形成的三角形数量，$vt(x, C)$ 为社区 $C$ 中与 $x$ 以及 $C$ 中第三个顶点形成至少一个三角形的顶点数量。顶点 $x$ 与社区 $C$ 的凝聚度定义如下： \[ WCC(x, C) = \begin{cases} \frac{t(x,C)}{t(x,V)} \cdot \frac{vt(x,V)}{|C\{x\}| + vt(x,V) - vt(x,C)} & \text{if } t(x, V) \neq 0 \\ 0 & \text{if } t(x, V) = 0 \end{cases} \] 设 $P = \{C_1, \ldots, C_k\}$ 是 $V$ 的一个划分，即 $C_1 \cup \ldots \cup C_k = V$ 且 $C_i \cap C_j = \varnothing$（$i \neq j$）。定义 $C_x$ 为顶点 $x$ 所属的社区。$P$ 的 WCC 定义为所有顶点 $x$ 的 $WCC(x, C_x)$ 的平均值。 ##### 2.2 可扩展社区检测算法 SCD 算法接受一个图 $G = (V, E)$（其中 $n = |V|$，$m = |E|$），通过贪婪地最大化 WCC 将图划分为社区。该算法有三个步骤：预处理、初始划分和划分细化。 - **预处理**：在此阶段，计算每条边形成的三角形数量，进而计算每个顶点形成的三角形数量。删除不形成任何三角形的边，因为它们不影响 WCC。移除在此步骤后变得孤立的顶点，后续会将它们分配到新的单例社区。假设 $m$ 和 $n$ 之间是准线性关系（即 $O(m) \sim O(n \log n)$），此阶段的时间复杂度为 $O(m \log n)$。 - **初始划分**：使用一种快速启发式方法将顶点分配到初始社区。按照聚类系数（根据预处理数据计算）降序访问顶点，并将它们分配到新创建的社区。此阶段最耗时的操作是对顶点进行排序，需要 $O(n \log n)$ 时间。 - **划分细化**：初始划分作为细化阶段的输入，在此阶段迭代地改进 WCC。每次迭代中，所有顶点执行能使 WCC 增加最大的操作，有三种可能的操作： - **无操作**：顶点留在当前社区。 - **移除**：顶点从当前社区移除，放入新创建的社区。 - **转移**：顶点从当前社区转移到其某个邻居所在的社区。 操作（1）不影响 WCC，操作（2）和（3）会影响 WCC，但精确计算改进量的计算成本很高，