摘要

最近，基于网络模体（network motifs）的高阶社群检测受到了越来越多的关注，因为基于模体的社群不仅反映了介观结构（mesoscale structures），还体现了真实网络的功能特征。在这项研究中，我们提出了一种针对基于模体的社群检测的模块度优化方法（Modularity Optimization method for Motif-based Community Detection，MOMCD）。为实现逼近模块优化的全局最优解，我们提出了一种改进的自然启发式元启发式算法（nature-inspired metaheuristic algorithm）作为优化策略。此外，通过综合利用基于模体（高阶）和基于边（低阶）的结构信息，还设计了邻域社群修改算子和局部搜索算子，以提高个体的质量并促进MOMCD的收敛。实验结果表明，MOMCD在从人工合成和真实网络中识别基于模体的社群方面具有良好的前景和竞争力，在质量和准确性上优于现有的先进方法，并加深了我们对网络结构和功能特征的理解。

研究领域：高阶社群检测，网络模体（motif），模块度优化（modularity optimization），自然启发的元启发算法（nature-inspired metaheuristic）

论文题目：Higher-order Community Detection by Motif-based Modularity Optimization

发表时间：2025年2月20日

论文地址：https://ieeexplore.ieee.org/document/10896785

期刊名称：IEEE Transactions on Big Data

网络模体与高阶社群检测：

从“微观”到“介观”的跃迁

图 1. MOMCD 中基于模体的高阶社群检测示例。（a）预先选定的 3 节点三角形模体，（b）网络中所有模体实例，（c）基于模体实例数量和分布构建的模体邻接矩阵，以及（d）通过受自然启发的元启发式模块度优化检测到的具有两个社群（即 C1 和 C2）的高阶划分。

自然启发的优化策略：GSI-SOS算法

传统优化方法（如谱聚类）易受局部最优限制，MOMCD提出改进的自然启发算法GSI-SOS（Generalized Symbiotic Interaction-based Symbiotic Organisms Search），引入了生态系统中生物之间的共生行为：

• 互惠共生：个体不仅向随机个体学习，还引入全局平均向量，平衡探索与开发。例如，算法中每个解（“生物”）通过结合随机个体、当前最优解和群体平均方向进行更新。
• 分类共栖：根据适应度将个体分为“强、中、弱”三类，分别采用不同的学习策略。弱个体偏向向最优解靠拢，而强个体则在局部精细搜索。
• 寄生：生成寄生向量干扰当前最优解，避免过早收敛。

结构信息融合：EM-NCM与ΔQW-NCLS操作

EM-NCM（基于边与模体的邻域社群修正）：

• 结合模体共现次数、节点度相似性，定义综合权重。例如，边连接的节点若度相近则权重更高。

• 计算节点和社群之间的“吸引力”：若某节点的邻居大多属于社群C，则将该节点也调整至C。例如，节点X的模体邻居中70%属于社群C，则X更可能被分配至C。

ΔQW-NCLS（模块度增量驱动的局部搜索）：

• 在高质量解中，逐个节点尝试迁移到相邻社群，分别计算模块度，选择使模块度增益最大的方向。例如，迁移节点Y到社群D可使QW提升0.05，则执行此操作。

图 2. 使用三角形三节点模体在Les Miserables子网络上 MOMCD 通用框架的示例。（a）使用三角形三节点模体 M(3,3) 构建模体邻接矩阵和基于基序的加权网络。（b）通过基于标签的编码方案随机生成 NP 个个体进行初始化，其中每个个体代表涵盖所有节点的一个候选社区划分。（c）在每次迭代中通过三种操作（即 GSI-SOS、EM-NCM 和 ∆QW-NCLS）实现模块度最大化。

图 3. MOMCD 与六种最先进的基于模体的社群检测算法在一组 LFR 网络上获得的平均 NMI，其中 µ 从 0.1 增加到 0.8。

实验结果：从合成网络到万级真实网络

意义与展望

彭晨 | 编译

6. 探索者计划 | 集智俱乐部2025内容团队招募（全职&兼职）