IEEE速递：从“边”到“模体”（motif），高阶社群检测的新视角

摘要

最近，基于网络模体（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

在复杂网络中，社群结构是理解系统拓扑和功能特征的关键。传统社群检测方法多基于节点和边的低阶连接模式，却忽视了真实网络中广泛存在的高阶结构——网络模体 （motif） 。模体是频繁出现的特定子图，如三角形或链式结构，被认为是网络的“功能单元”，例如，能表示基因调控中的信号通路或社交网络中的信息传播模式。然而，基于模体的高阶社群检测面临两大挑战：全局优化能力不足 （易陷入局部最优） 和高低阶结构信息利用不充分 （孤立节点难以处理） 。

针对以上问题，IEEE Transactions on Big Data的一篇研究提出了一种创新方法MOMCD （Motif-based Modularity Community Detection） ，通过结合自然启发算法与结构信息融合策略，显著提升了高阶社群检测的精度和稳定性，为网络科学领域提供了新的工具和洞见。

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

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

模体作为网络的“功能基石”，介于微观节点与介观社群之间。例如，在社交网络中，三角形模体可能代表紧密的三人小组；在神经元网络中，双向边模体可能对应信息反馈回路。MOMCD算法的核心思想是将模体信息转化为加权网络的模块度优化问题： 统计每对节点共同参与的模体实例数量，生成权重矩阵，构建模体邻接矩阵。例如，若节点A和B共同出现在5个三角形模体中，则权重为5。保留原始网络的边结构，并将模体权重叠加到对应节点对上，形成融合高低阶信息的加权网络，这一过程巧妙地将高阶检测问题转化为加权网络的模块度最大化问题。

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

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

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

• 互惠共生：个体不仅向随机个体学习，还引入全局平均向量，平衡探索与开发。例如，算法中每个解 （“生物”） 通过结合随机个体、当前最优解和群体平均方向进行更新。

• 分类共栖：根据适应度将个体分为“强、中、弱”三类，分别采用不同的学习策略。弱个体偏向向最优解靠拢，而强个体则在局部精细搜索。

• 寄生：生成寄生向量干扰当前最优解，避免过早收敛。

实验表明，GSI-SOS在CEC2013基准测试中优于灰狼优化 （GWO） 和鲸鱼算法 （WOA） ，尤其在多峰问题上表现突出。

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

为充分利用网络信息，MOMCD设计了两步优化操作：

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

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

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

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

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

这两步操作使算法在合成网络 （LFR） 上的归一化互信息 （NMI） 相比基线方法提升最高达20%，在真实网络中模块度QW提升8.48%。

图 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。

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

在包含3.7万节点的GitHub协作网络中，MOMCD相比现有方法 （如EdMot、ME+k-means） 展现出显著优势：首先，检测精度提升，在已知真实社群网络中，NMI均领先MOMCD-Simple和MOMCD-EMNCM；其次，该算法鲁棒性较好：当社群结构模糊 （混合参数μ>0.5） 时，MOMCD的NMI仍保持较高水平，在目前的先进算法中保持领先；最后，该算法优化效率较高，虽然模体计数耗时较长，但优化过程在万级节点网络中可在30分钟内完成，适合实际应用。

意义与展望

MOMCD的突破在于首次将模体模块度优化与自然启发算法结合，并通过结构信息融合解决了高低阶特征的协同利用问题。该方法不仅适用于社交网络和生物网络，还可拓展至交通流量分析、脑功能连接组等领域。未来可用于动态模体检测，捕捉随时间演化的社群结构；还可以用于重叠社群识别，即允许节点归属多个功能模块等等。这一研究为高阶网络分析提供了新范式，推动了网络分析从“结构挖掘”到“功能解析”的深化。

彭晨| 编译

复杂网络动力学读书会

集智俱乐部联合合肥工业大学物理系教授李明、同济大学副教授张毅超、北京师范大学特聘副研究员史贵元与在读博士生邱仲普、张章共同发起 。本次读书会将探讨：同步相变的临界性、如何普适地刻画多稳态与临界点、如何识别并预测临界转变、如何通过局部干预来调控系统保持或回到期望稳态、爆炸逾渗临界行为的关键特征、不同类型的级联过程对逾渗相变的影响有何异同、高阶相互作用的影响能否等效为若干简单机制的叠加、如何有效地促进人类个体间的合作等问题。

读书会计划从3月7日开始，每周五晚19:30-21:30进行，持续8-10周。诚挚邀请领域内研究者、寻求跨领域融合的研究者加入，共同探讨。

详情请见：

1.

2.

3.

4.

5.

6.