摘要

最近，基于網絡模體（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.