Enhancing Discrete Particle Swarm Optimization for Hypergraph-Modeled Influence Maximization
最新研究提出 HDPSO 演算法，透過超圖建模精準捕捉高階群體互動，在 144 項影響力最大化測試中成功壓制傳統基準方法。
- 採用兩層局部影響力近似機制取代蒙地卡羅模擬，大幅降低超圖結構中的擴散運算開銷。
- 結合離散速度更新規則與 10% 局部搜尋機率，有效引導粒子跳脫局部最佳解的陷阱。
- 在真實世界超圖資料集驗證中，HDPSO 僅需極少數種子節點即可達成幾近全域觸發的傳播效果。
影響力最大化（Influence Maximization, IM）是複雜網路分析的核心難題，但在真實世界的群體互動中，傳統圖形模型往往無法精確捕捉多人同時參與的高階關聯。為了突破這個盲區，最新研究提出基於超圖（Hypergraph）的離散粒子群最佳化演算法 HDPSO，透過兩層局部影響力近似與獨特的離散更新機制，在 144 項效能對比測試中，成功有 140 項測試擊敗或打平 7 種傳統基準演算法。
傳統圖形模型的侷限與超圖結構的維度挑戰
企業行銷或資訊傳播經常面臨預算限制，必須在龐大的使用者中挑選少數「種子節點」，以期觸發最大規模的連鎖反應。過去多數影響力最大化研究仰賴傳統圖形模型，將節點間的關係簡化為一對一的二元連結。然而現實生活中的社群互動通常具有群體導向特徵，例如多名使用者共同參與一個線上社團或討論串。
這種超越成對關係的結構，需要引入超圖技術來進行更精準的建模。超圖允許單一超邊（Hyperedge）同時連接任意數量的節點，完美契合真實系統中複雜的群體相依性。
引入超邊雖然提升了模型的表達能力，卻也帶來兩大根本性挑戰。首先是搜尋空間的爆炸性成長，因為同時連接多個節點的超邊會讓關係組合呈指數級攀升。其次是動態傳播過程的建模變得異常複雜，使得傳統尋找關鍵影響力節點的演算法難以負荷龐大的運算開銷。
HDPSO 演算法導入兩層局部影響力近似
為解決超圖模型帶來的龐大運算負擔，研究團隊選用粒子群最佳化（Particle Swarm Optimization, PSO）演算法作為基礎框架。PSO 是一種啟發自鳥群覓食行為的演化計算技術，相比依賴交配與突變的基因演算法，它具備參數更少、收斂更快的優勢。
在 HDPSO 方法中，每個「粒子」代表一組種子節點的候選名單，其位置與速度向量皆被重新定義為適應超圖結構的離散形式。為了提升初始解的品質，該研究設計了基於節點分支度（Degree）的初始化策略。系統會根據節點連接的超邊數量給予基礎評分，同時加入介於 0.5 到 1.0 之間的均勻分布亂數作為擾動因子，避免所有粒子從相似位置出發而導致早熟收斂。
評估種子節點的影響力通常需要執行耗時的蒙地卡羅模擬，但在 HDPSO 中，團隊導入了兩層局部影響力近似（Two-layer local influence approximation）機制。演算法僅依賴兩跳（Two-hop）範圍內的網路結構資訊，透過閾值模型快速推算種子節點引發的擴散範圍。這種替代方案不僅大幅降低了反覆運算的龐大開銷，還能在演化過程中維持高度的評估準確性。
離散速度更新與 10% 局部搜尋機率的尋優策略
粒子群在多維空間中的移動方向，取決於速度向量的更新規則。傳統 PSO 的連續數值更新無法直接應用於節點組合的離散選擇，因此 HDPSO 引入了基於相似度的交集運算。
當粒子更新速度時，會比對目前位置與「個體最佳解」及「全域最佳解」之間的共通元素。若節點存在於最佳解中，速度向量對應位置會設為 0 以保留該節點；否則設為 1，並在後續的位置更新中替換成網路中的隨機新節點。這種機制允許粒子有效繼承歷史最佳經驗，精準引導搜尋方向。
為了避免粒子群陷入局部最佳解，研究團隊進一步整合了超圖結構專屬的局部搜尋策略。在每個演化世代中，系統會對 10% 的粒子執行貪婪式的鄰居探索。若用相鄰節點替換現有種子能帶來更高的適應度得分，就會立刻進行替換，藉由在具潛力的區域內進行微調，進一步強化整體的收斂速度與解的品質。
在 4 大真實世界超圖中擊敗 7 種基準演算法
為了驗證 HDPSO 的實際效能，實驗涵蓋了合成超圖以及四大真實世界超圖資料集。這些真實場景包含線上問答社群的 Algebra 與 Geometry 互動數據、電商平台的 Music-Blue 評論網路，以及代表生物代謝反應的 IJO1366 資料庫。
對比方法包含了基因演算法（GA）、隨機挑選（Random）、PageRank 以及多種基於中心性的啟發式指標（如 HHD、NP、HCI1 等 7 種演算法）。實驗結果顯示，隨著種子節點數量增加與最佳化空間變得複雜，HDPSO 展現出極具統治力的全域探索優勢。
在連結密度極高的 Geometry 資料集測試中，HDPSO 展現了驚人的傳播效率，僅需選取 10 個種子節點，就幾乎觸發了整個超圖網路的全域啟動。在整體統計顯著性檢定中，HDPSO 徹底超越傳統的基準方法，不僅在整體平均排名中穩居首位，更在絕大多數測試項目中拉開顯著的效能差距。
消融實驗確立慣性權重 0.7 的最佳參數配置
釐清不同模組對整體效能的貢獻是評估演算法的關鍵，研究團隊為此進行了詳盡的消融實驗。數據表明，僅加入初始化策略的 PSO-init 版本在早期迭代階段確實能獲得較高的傳播值，但到了第 50 代左右，擁有局部搜尋機制的完整 HDPSO 展現出更強大的後期突破能力。這證實了初始化負責前期加速，而局部搜尋負責後期精煉的雙重奏效應。
參數敏感度分析進一步揭示了控制粒子運動軌跡的細節。慣性權重決定了粒子保留前次速度的比例，過高會導致過度探索，過低則容易停滯。實驗反覆測試後發現，將慣性權重設定在 0.7 時，能取得探索與利用的最佳平衡。
負責引導粒子向個體經驗與群體領袖靠攏的學習因子，則在雙雙設定為 1.2 的配置下表現最為穩定。這組黃金參數組合確保了 HDPSO 在面對不同拓樸結構的超圖時，皆能維持強悍的尋優能力。
透過將高階節點關聯與離散粒子群最佳化結合，HDPSO 證明了超圖結構在解決大規模網路傳播難題時的無可取代性。