基于蟻群算法的骨干網絡發現

呂芳，柏軍，黃俊恒，王佰玲

（1.哈爾濱工業大學（威海）計算機科學與技術學院，山東 威海 264209；2.哈爾濱工業大學（威海）網絡空間安全研究院，山東 威海 264209）

1 引言

信息交互網絡指由實體之間信息的流通構建的有向網絡結構，例如電話網絡、金融網絡、路由網絡、交通網絡等。此類網絡與社交網絡的顯著不同在于，后者中邊的存在表示其連接的實體之間存在相似性關系，而前者中的邊只依賴于實體之間的信息交互需求，不具有傳遞性和相似性。以金融網絡為例，其中龐大、繁雜的交互關系，是真實社會中個人、組織進行有目的的經濟活動的產物。研究交互網絡中實時動態的交互關系，對分析網絡結構背后的組織活動有直接的指導意義，多年來引起了研究者的廣泛關注[1-2]。目前，針對金融網絡中交互路徑的研究可歸為以下3 類：輔助表示節點特征[3-4]、檢測異常交互路徑[5-6]和可疑關系分析與預測[7-8]。上述研究集中于解決動態[3,5]、稀疏[8]的金融網絡中異常節點和異常邊的識別。由于金融網絡數據中的噪聲、冗余信息明顯，上述算法的設計均需要在一定程度上考慮算法的穩健性。如何抽取出能夠反映真實交互關系的核心網絡，為研究人員提供一個相對純凈、可靠的骨干網絡，是本文關注的核心。

為解決上述問題，本文提出模擬信息交互在時空上呈現的交互路徑，即發現核心流通軌跡，以實現骨干網絡的提取。核心流通軌跡發現可抽象為網絡中的最優路徑選擇，屬于組合優化問題。路徑尋優是一類NP-hard 問題，長期以來都是研究者的關注熱點。給定有向圖G=(V,E)，若V中節點的平均出度為d，則G中長度為的路徑總個數約為條，可見路徑條數隨l呈指數增長。當G的規模變大，使用傳統算法解決此類問題的計算成本將無法承受。近年來，眾多研究發現仿生智能算法在解決組合優化問題時體現出了良好的性能，為很多NPC（non-deterministic polynomial complete）問題的求解提供了新的思路和解決方案。其中，蟻群算法（ACA,ant colony algorithm）[9]是一種可用來解決路徑優化問題的概率型智能仿生優化算法。作為一種啟發式全局優化算法，ACA 不依賴于嚴格的數學定義，而是利用信息反饋機制進行啟發式搜索，具有較強的穩健性和并行性[10]，在解決復雜優化問題方面有著很好的性能。ACA 的研究應用從最初的旅行商問題（TSP,traveling salesman problem）[10]逐漸拓展到了路徑規劃、車間作業調度、圖像處理等很多領域。特別地，在圖結構的路徑尋優問題上，搜索螞蟻系統（GBAS,graph-based ant system）[11]最早證明了ACA 在圖結構上進行路徑尋優的合理性。GBAS 將圖上的可行路徑視為優化目標的最優解，實現了蟻群模型向圖結構路徑尋優問題的遷移，此后涌現出一系列針對圖分析領域不同應用的蟻群優化模型[12]。

金融網絡利用實體間的交互關系，由真實的交互信息流數據構建得到，具有復雜網絡特點的圖結構[6]。交互實體可抽象為節點，實體間的有向交互關系抽象為節點間的有向邊，實體間的交互信息量、交互頻次等信息表示有向邊的權重。圖1 為由真實金融流通日志數據構建的局部網絡示意，其中邊的箭頭方向為交互信息的流通方向。

圖1 金融局部網絡示意

真實的信息交互網絡具有如下特點：節點規模龐大，節點之間的路徑不止一條且存在環路，且節點的度分布差異性較大。網絡中存在著少數的活躍節點，其度、交互頻次均顯著高于其他節點。這些活躍節點處于交互網絡中的關鍵位置，對網絡的連通性有著重大的影響。此外，交互網絡的邊會隨著時間的改變而發生變化。本文將其簡化為靜態網絡，將在一定時間周期內存在有序交互活動的連續流通路徑視為有效運行軌跡。核心流通軌跡在時間上具有一定的規律性，且往往流通了網絡中的大部分信息，因此可以反映一定時間內信息的主要活動與分布。以圖1 中的實際金融網絡為例，其核心流通軌跡如圖2 所示?？梢?，金融網絡中有向邊的雙向流通權重不等價；網絡規模較大且稀疏；兩實體間的最優交互路徑不止一條且存在環路。為了實現利用蟻群路徑選擇模擬信息流通，利用蟻群信息素更新標識路徑的重要性，本文提出了一種蟻群模型FNT-Ant，該模型對傳統蟻群模型做了如下改進。

1)根據網絡中心性理論，改進了螞蟻初始位置的選擇策略，以保持節點的重要性與選中概率一致。

2)設計了一種適用于發現核心流通軌跡的蟻群路徑選擇機制，以模擬網絡中的信息流通行為。

3)借鑒GBAS 思想，制定了一種動態自適應的信息素更新策略，以保證模擬過程收斂。

圖2 核心流通軌跡示意

本文提出的FNT-Ant 算法相對傳統蟻群算法收斂速度更快，解的性能更好。在真實數據上的實驗結果表明，FNT-Ant 算法提取的骨干網絡覆蓋了65.57%的網絡關鍵節點。這一結果優于傳統算法，證明了FNT-Ant 算法優化思想的合理性，簡化了后續在信息交互網絡中的異常檢測、可疑路徑分析等任務。

2 相關工作

在金融網絡中，核心流通軌跡發現的研究尚處于初級階段，從網絡理論上來說，其與骨干網絡發現屬于相近的研究范疇。

Chawla 等[13]在對交通網絡進行骨干網絡發現時，采用貪心算法和基于原始對偶的算法，考慮到邊的中介中心性和通勤時間中心性，引入伸縮因子的概念，然后將其定義為加權調和平均數對算法進行優化。文獻[13]的優化目標與本文要解決的問題類似，也是要找出網絡中的主干路徑。但是，文獻[13]中的交通網絡圖數據規模較小且節點的空間分布位置固定，而信息交互網絡的數據集規模龐大，網絡節點相對位置不固定，邊具有方向性，網絡中存在環路且信息流通軌跡不止一條。此外，隨著網絡規模的擴大，網絡結構愈發復雜，軌跡發現的難度也隨之大大增加，這使傳統算法難以求解。Katsikouli 等[14]在研究分布式道路系統時采用了一種隨機抽樣算法進行頻繁的路徑挖掘，其在保證算法準確性的基礎上，大大提高了相對確定性算法的運算效率，證明了隨機算法的高效性和準確性。該問題和本文交互網絡中核心流通軌跡發現問題均為NP-hard 問題，其解決方法為本文提供了思路。

蟻群算法作為隨機算法的一種，綜合了貪心算法和概率的思想，既彌補了貪心算法容易陷入局部最優的不足，又通過概率反映了不同解的最優程度。因此，蟻群算法常被廣泛應用于解決路徑規劃相關的優化問題，如車輛路徑規劃[15]、數據挖掘[16]、網絡路由[17]、圖像處理[18]、機器人路徑規劃[19]等。蟻群算法是一種通過模擬自然界真實螞蟻的群體行為來尋求問題最優解的仿生優化算法。它的基本模型最早是在1991 年由Colorni 等[20]提出，此后結合實際應用問題的優化方案層出不窮[9]，如Gambaedella 等[21]提出的Ant-Q System 和Gutjahr[11]提出的基于圖的蟻群系統（GBAS,graph-based ant system）。Gutjahr[11]首次對蟻群算法的收斂性進行了證明，隨后將其應用于圖結構中的路徑尋優。他將圖中的可行路徑視為蟻群系統在圖結構中路徑優化問題的可行解。Gutjahr[11]還提出了圖中邊、全局路徑上信息素的累積和揮發策略，之后又相繼提出了GBAS/tdev 和GBAS/tdlb 算法[12]。他的研究證明了通過改變信息素的揮發因子或給信息素設置下界可加快算法收斂到最優解的速度。為了避免尋優過程的過早停滯，Stuetzle 等[22]改進了信息素更新策略，提出了最大?最小螞蟻系統（MMAS,max-min ant system）。MMAS 只更新本次迭代最優路徑上的信息素，并通過設置邊上信息素濃度的上下限來避免尋優過程過早停滯。近年來，我國學者對蟻群算法也做了大量的研究[23-25]。在理論方面，段海濱等[23]利用Markov 鏈和離散熵對信息素軌跡向量的收斂性進行了理論證明，給出了基本蟻群算法首達時間的定義及其理論分析；楊佳等[24]提出了一種新的量子蟻群優化算法，結合量子計算理論、進化計算理論和蟻群算法解決連續空間的優化問題。在算法優化方面，朱慶保等[25]提出了一種基于變異策略，采用最近鄰居節點選擇原則并對信息素進行動態更新的蟻群優化算法，大大提高了蟻群算法的收斂速度，該算法可用于解決大規模優化問題等。蟻群模型在圖結構上路徑尋優的研究，為本文利用基本蟻群模型解決流通路徑尋優問題提供了理論依據和實驗指導。

為了說明蟻群算法對路徑尋優的原理，本節對其原理進行簡要介紹。蟻群算法最早成功應用于TSP[10]問題中。下面，以TSP 為例，對傳統蟻群算法的數學模型進行描述。設TSP 問題中的城市規模為n，螞蟻的總數目為m，任意t時刻城市i中螞蟻的數目為bi(t)，則

在初始時刻，將各路徑上信息素濃度設為定值tij(0)，其中，tij(t)為t時刻路徑(i,j)上的信息素濃度。在螞蟻行走過程中，使用禁忌表tabu 依次記錄螞蟻k(k=1,2,…,m)走過的城市，并隨螞蟻的迭代過程對tabu 進行動態更新?，F有針對蟻群算法的研究核心為路徑選擇機制和信息素調節機制，對其介紹如下。

1)路徑選擇機制

路徑選擇機制是螞蟻在轉移過程中根據當前路徑上信息素的濃度來決定下一步要到達的城市。螞蟻k的路徑選擇可使用狀態轉移概率獲得，則在t時刻螞蟻k由節點i轉移到節點j的狀態轉移概率為

其中，allowedk={C?tabuk}為k下一步允許選擇的城市集合；α為信息素啟發因子，用來表示信息素積累項的重要度；ηik(t)為t時刻路徑(i,k)的期望啟發函數，反映了螞蟻從城市i到k的期望程度，為城市(i,k)間的距離；β為期望啟發因子，表示信息素能見度項的重要度，β取值越大，螞蟻的路徑選擇策略越接近于貪心。

2) 信息素調節機制

為了避免因為路徑上的信息素過多而削弱啟發信息的作用，蟻群算法需要對路徑上的信息素進行更新，更新方法主要有2 種：一種是局部更新，即螞蟻每走完一步就利用局部信息對路徑上的信息素進行更新；另一種是全局更新，即螞蟻在完成一個循環后利用整體信息對所有路徑上的信息素進行更新。根據信息素積累和揮發規則，調節路徑上的信息素濃度。用表示本次循環結束時第k只螞蟻在路徑(i,j)上信息素的增量，τij(t+1)表示t+1 時刻路徑(i,j)上的信息素總量，兩者分別按照式(3)和式(4)進行更新。

其中，ρ為信息素揮發因子，1?ρ為信息素殘留系數。根據信息素的更新策略不同，Colorni 等[20]提出了 3 種不同的基本蟻群算法模型，分別為Ant-Quantity 模型、Ant-Density 模型和Ant-Cycle模型，這3 種模型的差別在于的計算方法。Ant-Quantity 模型和Ant-Density 模型采用的是信息素局部更新，而Ant-Cycle 模型采用的是信息素全局更新，具體計算式為

其中，Q和Lk分別表示信息素強度和第k只螞蟻在本次循環過程中所走路徑的總長度。相較另外2 種模型，Ant-Cycle 模型在求解TSP 問題時性能更好，因此該模型被視為蟻群算法的基本模型。

3 FNT-Ant 算法

在傳統蟻群算法的理論基礎上，本文根據信息交互關系的特點，設計了一種適用于發現交互網絡中核心流通軌跡的FNT-Ant 算法。FNT-Ant 算法引入網絡中心性設置螞蟻初始點，設計了符合信息流通特點的路徑選擇機制，制定了自適應的信息素動態更新策略，有效地將傳統蟻群算法遷移到了交互網絡路徑尋優問題中。下面，將首先給出問題定義，然后詳細介紹FNT-Ant 算法的具體構建方法。

3.1 問題定義

實體之間的動態流通數據體現了復雜的信息交互關系，可構建成有向加權時序交互網絡。交互實體抽象為網絡節點，實體之間的交互關系抽象為網絡中的有向邊，實體之間的交互信息量、頻次特征作為有向邊的權重。有向加權時序交互網絡的定義如下。

定義1信息交互網絡。一個信息交互網絡可表示為G=（V,E,W），其中，V={v1,v2,…,vn}為節點集合；E={eij=＜vi,vj＞|vi,vj∈V,vi對vj至少有一次交互}?V×V為邊集合。W={wij|eij∈E,1 ≤i,j≤n},，wij={(t(1)ij,r(1)ij),(t(2)ij,r(2)ij),…,(t(Nij)ij,r(Nij)ij)}，其中，t(k)ij、r(k)ij分別表示節點vi向vj的第k次交互時間、信息量，Nij表示vi向vj的總交互次數。

G中邊的權重反映了節點的關系強度，eij流通的信息量越大，交互越頻繁，說明vi對vj的聯系越緊密，影響作用越強。因此，利用交互信息量和頻次這2 個因子度量邊eij的權重，如式(6)所示。

其中，a、b=1?a分別表示信息量、頻次所占的權重，h1、h2分別表示對應系數。wij采用模糊集合論中隸屬度的思想，對兩因子進行規范化，即利用tanh 函數構造隸屬度函數，以縮小權值之間的差異。本文交互網絡中的骨干網絡定義如下。

定義2骨干網絡。給定G=（V,E,W），若存在子網絡H=(V′,E′,W′)，滿足

則稱子網絡H為G的骨干網絡，其中，分別為集合W和W′中元素的個數，M和K為閾值。

核心流通軌跡可反映出交互網絡中信息的主要流向，表現在全局交互網絡中即為網絡的主干路徑。核心流通軌跡發現問題可抽象為從交互網絡G中抽取出主干路徑構成骨干網絡H。

3.2 FNT-Ant 蟻群模型

在蟻群算法中，螞蟻初始位置的選擇和信息素的更新策略對算法的收斂速度和解的質量有很大影響，而螞蟻的路徑選擇機制則需要依據具體的問題進行設置。下面，針對FNT-Ant 蟻群模型中螞蟻初始位置的選擇、路徑選擇機制的設置和自適應的信息素動態更新策略進行詳細闡述。

3.2.1 螞蟻初始位置的選擇

傳統蟻群算法在解決TSP 問題時，螞蟻的初始位置是隨機放置的，這在處理TSP 問題時是可行的，原因在于：1) 在求解TSP 問題時，要求每只螞蟻遍歷所有節點，該過程構造出來的所有路徑均為問題的可行解；2)算法優化目標為找到一個最優解。然而上述思路難以直接遷移到文本問題中，因為：1)交互網絡規模龐大節點眾多，遍歷網絡中的所有節點難以實現；2) 優化目標為最優信息流通路徑集合，即每只螞蟻所找到的路徑可能只是最優解的一部分。在蟻群算法中，初始位置的選擇對算法執行的效率和求解的性能均有著很大的影響。4.3 節將蟻群初始位置隨機設置和本文對初始位置的改進進行了對比實驗，對比分析發現，隨機放置螞蟻時得到的解的性能較差，算法容易出現早熟停滯現象。由此可見，隨機放置螞蟻在本文問題中顯然是不可行的。因此，本文基于交互網絡的特點以及復雜網絡中的節點中心性理論[26]，改進了初始位置選擇策略，其中對網絡中處于關鍵位置的節點給予了更多的關注。

網絡中節點的重要程度可以通過節點的中心性來進行評價[27]，包括節點的度中心性、介數中心性等。節點的度中心性[28]是節點中心性最直接的度量指標。節點i的度中心性DCi為

其中，ki為節點i在網絡中的連邊數，n為網絡中的節點數目，n?1為節點可能的最大度值。DCi通過節點鄰居數量多少來反映節點的影響力大小，也就是說節點的度越大，它的重要性也就越大?？梢?，節點的度中心性是網絡局部特性的重要評價指標。

節點的介數中心性[29]指圖中經過該節點的所有最短路徑的比重。節點i的度中心性BCi為

其中，α(s,t)表示節點s到節點t的最短路徑數目，α(s,t|i)表示節點s到節點t的最短路徑中經過節點i的數目?？梢?，BCi反映了網絡的全局特性。

對于節點i來說，DCi和BCi這2 個指標評價依據不同且各有側重，為了避免單一指標評價過于片面，本文綜合兩者對節點i的重要性進行度量，具體計算式為

其中，k1和k2為比例系數，且k1+k2=1。G中V的節點重要性總和為SP，本文使用輪盤賭方式為螞蟻選擇起始位置，節點i的選擇概率為

本文中螞蟻初始位置的選擇對網絡中的重要節點給予了更多關注，增大了網絡中重要節點作為螞蟻起始節點的概率，提高了算法的收斂速度和求解質量。

3.2.2 路徑選擇機制的設置

以金融網絡為例，交互日志數據中包含的信息有原賬號、對手賬號、金額、頻次等，部分數據如表1 所示，其中權值項由式(6)得到。

表1 金融網絡日志記錄數據示例

蟻群算法的優化目標與實際應用問題直接相關，在解決不同的問題時需要構建不同的目標函數。例如，TSP 問題的目標函數是路徑長度和最小[30]；車輛路徑規劃問題的目標函數是汽車總的行駛路程最短和車輛數目最少[31]；圖像處理的目標函數是螞蟻與聚類中心的相似度最大[32]。本文問題與其他同類問題對比如表2 所示，可見研究問題都屬于組合優化問題中的路徑優化問題，但是數據類型以及規模不同，優化目標不同。

螞蟻在選擇路徑的過程中，目標函數會通過一系列約束條件來不斷調整螞蟻的前進方向，將優化方向向著最優方向引導。本文所解決的問題相對較復雜，作為優化目標的核心流通軌跡要能體現出在整個網絡中信息的主要流動方向，這就需要通過對具體的實驗數據進行分析來構造出合適的目標函數?；诙x1，本文的優化目標為網絡中的核心流通軌跡整體權重之和占據網絡總權重的比重盡量大，且軌跡中每條邊的權重盡量大，能夠表現出信息的主要流動方向。據此，本文設計的目標函數如下。

表2 本文問題與其他同類問題對比

設路徑為Γ=v1,v2,…,vl?1,vl,vl+1，路徑上的邊權重為wij,1≤i＜j≤l+1，設計的目標函數為

其中，fk(t)為第t代第k只螞蟻走過路徑的目標函數，lk(t)為此螞蟻走過的路徑長度，ωij為螞蟻走過邊的權值。螞蟻從節點的鄰居集合中選擇一個節點u，計算此時的fl+u，若fl+u＞fl，則選中該有向邊為轉移路徑，反之則排除該節點，重新進行路徑選擇，直到無邊可選。當一只螞蟻停止，即可得到一條局部最優路徑；一代螞蟻走完之后，得到本代的最優路徑集合及其目標函數值之和。表1 中日志數據交互關系如圖3 所示。具體地，圖3 中最優路徑集合的目標函數之和計算過程如下。

圖3 表1 中數據的交互關系

假設螞蟻當前已經走過的路徑為a→b→c，則fac為

若選擇邊(c,d)，則fad為

由于fad＜fac，則放棄邊(c,d)，嘗試走(c,e)，則fae為

此時，fae＞fac，則沿邊(c,e)轉移，并將當前走過的路徑更新為a→b→c→e，直到達到算法結束條件時螞蟻停止行走。

該目標函數也可以作為螞蟻行走軌跡質量評優標準，并權衡了路徑邊權值和和邊平均權值兩者之間的關系，利用α和β來調節兩者的比重，并采用乘積的形式來放大結果之間的差異。目標函數取值越大，表示路徑上邊的信息流通權重越大，則該軌跡越有可能組成骨干網絡。

3.2.3 自適應的信息素動態更新策略

在傳統蟻群算法中，路徑上的信息素用于引導蟻群找到到達食物源的最短路徑。在蟻群每次迭代完成之后，都需要對信息素進行更新，更新具體包括信息素積累和揮發2 個方面。本文算法借鑒GBAS 算法[11-12]中的信息素更新方式，即采用信息素濃度反饋填補機制，在每次迭代結束后，將圖中所有路徑上揮發的信息素作為螞蟻走過的路徑上的積累信息素的總量，這種回填機制保證了整個網絡中信息素濃度總量的恒定，即為初始時刻圖中每條路徑上的信息素濃度總和。

在信息素濃度迭代更新的過程中，往往存在某些路徑上的信息素持續積累或揮發，進而導致路徑之間濃度差異逐漸增大的現象。一些路徑上的信息素一直揮發，使這條路徑被選中的概率也越來越低；進而，頻繁被選中的路徑會積累更多的信息素。這一循環加劇了路徑上信息素的差異，破壞了路徑選擇的隨機性，使算法過早收斂。因此為了保證螞蟻始終有著足夠大的解空間，算法不會過早停滯，本文借鑒了MMAS 算法[22]的思想，為路徑信息素濃度設置一個濃度變化區間，以保證路徑上的信息素不會無限制的增加或減少。此外，利用回填機制為路徑分配信息素積累量時，按照本代螞蟻走過路徑的目標函數值Fij(t)占路徑集合目標函數之和SF(t)的比例進行計算，即。

然后根據蟻周模型將增加的信息素平鋪在路徑包含的所有的有向邊上。值得注意的是，網絡總體信息素量為定值，則每次揮發出的信息素總量也是定值，回填機制保證了網絡信息素總量恒定。關于信息素濃度的具體計算式為

其中，ρ為信息素揮發系數，τij(t+1)為更新后邊上的信息素濃度，τij(t)為第t代圖中＜vi,vj＞邊上的信息素濃度，(1?ρ(t))τij(t)為每條邊上的信息素揮發后的殘余量，Q為揮發的信息素總量。

在信息素的更新機制中，揮發因子的大小直接影響到蟻群算法的全局搜索能力和收斂速度，在處理大規模問題時，它的影響更突出。因此，本文在調節揮發因子的過程中引入動態自適應調節策略，即將揮發因子定義為一個和目標函數相關的值，根據每次迭代目標函數取值與歷史取值的差異進行動態調整。具體地，當本次迭代的目標函數取值相比之前有所增大時，增大揮發因子，以增加螞蟻走過路徑的信息素積累量，從而加快算法的收斂速度；反之，則減小揮發因子，進而擴大蟻群的搜索空間。同時，為避免揮發因子過小，影響算法的收斂速度，對其設置一個閾值下界。動態改變的揮發因子ρ的計算式為

其中，q∈[t?T,t)，T為考察代數。對于時刻t，若t＞T，則考察[t?T,t)代的max{SF(i)}和min{SF(i)}，利用計算出每次迭代得到的目標函數值在歷史迭代中的相對大小。

在迭代結束后，利用式(13)和式(14)計算出ρ(t)的值，再通過式(11)和式(12)對信息素τ進行更新。

在本問題中，每只螞蟻所構造的解可能只是問題解的一部分，即每只螞蟻的最優路徑是骨干網絡H的路徑分支。定義2 中M和K的取值由實驗確定。

本文采用的自適應動態調節機制利用信息素回填機制保證了蟻群有足夠大搜索空間，利用揮發因子根據目標函數的變化進行動態調整，保證了算法可以得到一個滿意解。

3.3 FNT-Ant 蟻群算法描述

輸入信息交互網絡G=（V,E,W）；參數α、β、ρ、m；揮發因子閾值X；迭代計數器NC；最大迭代次數NC_MAX

輸出骨干網絡H=(V′,E′,W′)

步驟1初始化α、β、ρ、m、NC_max ；根據式(6)初始化G，NC=0。

步驟2根據式(9)按照輪盤賭算法選擇m個網絡節點作為螞蟻的初始位置。

步驟3針對任意螞蟻k，若allowedk≠?，則k根據式(1)選擇下一節點，更新tabuk、allowedk，根據式(10)計算當前fl+1；若為空，則算法終止。

步驟4如果fl+1＞fl，則繼續步驟5，否則回到步驟3 重新進行選擇。

步驟5將所有螞蟻走過路徑的目標函數進行加和，按照式(13)和式(14)更新ρ值，進而按照式(11)和式(12)更新全局信息素。

步驟6NC+1，若NC＞NC_max，則轉步驟7，否則轉步驟2。

步驟7輸出H={ρab|τ(ρab)＞X}。

4 實驗與分析

根據前面的算法介紹，本文分別設計并實現了FNT-Ant 算法、貪心算法，然后對FNT-Ant 算法改進前后進行了對比實驗，下面對實驗結果進行比較分析。

4.1 實驗設置

本文的實驗環境為Windows 10，MATLAB R2017b。

4.2 實驗數據

本文使用真實的金融日志，每條日志信息包含賬號、對手賬號、時間、方式、金額等屬性信息。首先根據已獲涉及金字塔影響的可疑名單調集其日志記錄，隨后又根據其對手進行兩輪調集，形成包含35 842 個實體自其開卡之日起的所有日志組成的數據集，時間跨度為2014 年1 月到2018 年4月。本實驗將數據集以年為單位進行劃分并選取了2015 年的數據進行實驗，利用該數據構建的交互網絡中共包含35 842 個節點、101 699 條邊?？梢姳疚牡慕换ゾW絡存在骨干網絡，即可疑涉及金字塔營銷人員的交互關系網絡。由于金字塔式經營模式中成員繳納會費和收益的關系呈現金字塔型，因此擔任不同角色的實體具有不同的信息流通特點。例如申購實體具有入對手多、出對手少且信息流通總量、頻率皆較高的特點；Boss 實體具有出入對手數量少、流通頻次低但流通量大的特點?？梢?，上述金融交互網絡中不同角色的實體呈現不同交互特點（細節請參考文獻[33]）。因此，在缺乏特定組織運作背景知識的前提下，難以量化實體的交互差異。但是，網絡中信息的流向與分布，反映了核心骨干的收益情況。對該包含金字塔式經營的交互網絡中骨干網絡，可通過本文提出的FNT-Ant 算法進行提取。

4.3 對比實驗結果分析

為了驗證本文提出的FNT-Ant 算法的有效性和可行性，將FNT-Ant 算法和改進前的蟻群算法在目標函數值和收斂速度上進行比較，并將FNT-Ant 算法和貪心算法在骨干網絡中的重點（可疑）節點覆蓋率、準確率和節點角色分布進行了對比分析。具體介紹如下。

4.3.1 對比實驗

為對比不同揮發因子和信息素更新策略和對算法結果的影響，設計了 FNT-Ant(S)算法、FNT-Ant(SP)算法和FNT-Ant 算法進行比較。其中FNT-Ant 算法的揮發因子根據目標函數動態調整，而FNT-Ant(S)算法和FNT-Ant(SP)算法均采用固定值；FNT-Ant 算法和FNT-Ant(SP)算法的信息素更新采用回填機制，而FNT-Ant(S)算法采用非回填機制。為了比較起點隨機選擇和起點結合網絡中心性進行概率選擇對算法結果的影響，對比分析了FNT-Ant(R)算法和FNT-Ant 算法。此外，本文還設計了貪心算法和FNT-Ant 算法進行對比，其區別在于貪心算法在進行路徑選擇時完全依據貪心策略，而FNT-Ant 算法則采用輪盤賭算法進行概率選擇。具體的對比實驗設置如表3 所示。

4.3.2 評價標準

本文將算法的收斂速度和最終得到的目標函數值作為評價算法性能優劣的標準，利用數據中已標記的重點節點及其角色信息，將軌跡中重點節點的覆蓋率和準確率以及找到的節點角色分布作為算法有效性的判斷標準。

表3 對比實驗設置

4.3.3 參數分析

本文構建的金融網絡原始節點中心性分布數據如表4 所示。

表4 原始節點中心性分布數據

由于網絡中節點的介數中心性數值過低，為使介數中心性重要度得以體現，需對其值進行放大處理，并利用tanh 函數進行規范化處理，如式(15)所示，即=tanh(k3BCi)，其中k3為介數中心性放大系數，其對金融網絡中Level1 級別的節點（金字塔頂層節點，為Boss 角色）作為螞蟻初始節點的概率變化曲線如圖4 所示。

圖4 Level1 級別的節點作為初始點的概率與k3 的關系

圖4 中，橫坐標為介數中心性的放大系數，縱坐標為Level1 級別的節點作為初始節點的概率，曲線上的圓圈表示最優值。由圖4 可知，概率曲線隨著介數中心性的增大，先迅速升高后開始趨于平穩并緩慢下降，當k3=62 時，Level1 級別的節點作為螞蟻初始節點的概率最高。

當k3=62 時，k1和k2的取值對Level1 節點作為起始節點概率和所有異常節點（涉及金字塔經營的所有賬戶，記為全Level 節點）作為起始點概率的影響如圖5 所示。

圖5 Level1 和全Level 節點作為初始點的概率與k1 的關系

圖5 中，橫坐標為節點的度中心性系數k1，介數中心性系數k2=1?k1，縱坐標為網絡中節點作為初始節點的概率，其中k1=0.4、k2=0.6為Level1節點作為起始點概率和全Level 節點作為起始點概率隨k1變化曲線的拐點。此參數取值使起始概率在介數中心性作用下，重點異常節點作為起始點概率較大；在度中心性作用下，起始點有著足夠大的擴展范圍，蟻群可以進行大范圍搜索。

實驗的具體參數設置如下。信息素啟發因子α=1，期望啟發因子β=1，式(6)中的信息量、頻次所占的權重分別為所占的權重a=0.5、b=0.5，對應系數分別為h1=1 ×10?5、h2=1 ×10?1。度中心性、介數中心性、介數中心性放大系數分別為k1=0.4、k2=0.6、k3=62?？疾齑鷶礣=30，式(14)中的揮發因子更新系數k=0.05，揮發因子最小值d=0.005。

4.3.4 算法性能測試

算法的目標函數值代表了蟻群在骨干網絡上積累的信息素總量。通過比較目標函數值的大小及算法的收斂速度對不同算法的性能進行分析。本節分別分析FNT-Ant 算法采用不同信息素更新策略和初始位置選擇機制對算法性能的影響。信息素更新策略改進前后目標函數值的變化對比如圖6 所示。

圖6 算法目標函數值變化對比

圖6 中橫坐標為算法迭代次數，縱坐標為每代對應的目標函數值。從圖6 中可以看到，FNT-Ant算法的收斂速度位于 FNT-Ant(S)算法和 FNTAnt(SP)算法之間，且在曲線走勢趨于平緩時，FNT-Ant 算法得到的目標函數值高于其他2 種算法，這說明信息素的動態更新策略在一定程度上加快了算法的收斂速度，避免了算法早熟、停滯，且提高了解的性能，使最終得到的目標函數值更大。

當螞蟻初始點設置采用不同策略時，算法目標函數值變化情況對比如圖7 所示。

圖7 算法目標函數值變化情況對比

圖7 中橫坐標為算法迭代次數，縱坐標為每代對應的目標函數值。從圖7 中可以看到，采用起點結合網絡中心性進行選擇的FNT-Ant 算法的收斂速度及目標函數值均高于采用起點隨機策略的FNT-Ant(R)算法?？梢?，起點選擇策略改進后的FNT-Ant 算法具有更快的收斂速度，并且所得解的性能更優，避免了蟻群算法在未找到較好解時便早熟停滯。

4.3.5 算法有效性測試

本節通過對比不同算法對重點異常節點的覆蓋率和準確率及角色分布來對算法的有效性進行說明。由于本文數據來源為涉及金字塔式經營實體的金融日志數據，因此該金融網絡中隱藏著大量設計金字塔式經營的流通軌跡。為解決這一實際問題，FNT-Ant 算法的優化目標為盡可能讓螞蟻模擬有向流通路徑，當算法收斂時，骨干網絡中可疑節點的覆蓋率和準確率越高，算法的性能也就越好。因此本文將標注數據中確定的重點異常參與者及其角色信息作為算法評價依據，對比分析了FNT-Ant 算法和貪心算法得到的骨干網絡的覆蓋率和準確率，實驗結果如圖8 所示。

圖8 骨干網絡可疑節點覆蓋

圖8 中橫坐標為骨干網絡包含的節點數量，縱坐標為異常節點的覆蓋率和準確率，覆蓋率即骨干網絡中包含的異常節點占網絡中所有異常節點的比重，準確率即骨干網絡中包含的異常節點占其覆蓋的所有節點的比重。這2 條曲線分別為FNT-Ant算法和貪心算法隨著骨干網絡的規模擴大，軌跡覆蓋的異常節點個數的變化情況。

從圖8 中可以看出，前期在相同軌跡節點數目情況下，貪心算法比FNT-Ant 算法找到的異常節點數目增速快，但當貪心算法找到的異常節點數目達到389 個時出現了轉折，增速急劇放緩，很快覆蓋率低于FNT-Ant 算法，并且之后一直低于?？梢?，貪心算法雖然在前期因優先選擇權值大的路徑所以快速找到了大量可疑節點，但由于其策略固定，沒有發散能力，故在找到一部分權值大的路徑后陷入局部最優，增速急劇放緩；而FNT-Ant 算法則能保持其增速直到找到所有可疑節點，FNT-Ant 算法在收斂速度、覆蓋率和準確率這3 個方面均高于貪心算法。FNT-Ant 算法在最高準確率為28.52%時可疑節點的覆蓋率達到了65.57%，而貪心算法在覆蓋率同樣為65.57%時，準確率為22.14%，由此可見，在找到同等數量可疑節點的情況下，FNT-Ant 算法比貪心算法的準確率更高，說明了FNT-Ant 算法在解決實際應用問題時的有效性。

金字塔式經營模式的成員角色關系架構也呈金字塔型，其組織發展模式具有固定性和裂變復制性。不同節點的信息流通量、交互頻率等對組織的重要性不同，因此在組織中具有不同的角色。根據節點在組織中的重要性，將其按照重要程度遞減的順序依次劃分為Level1、Level2 和Level3 共3 種角色。本文針對FNT-Ant 算法和貪心算法找到的可疑節點進行了進一步的角色分析，具體結果如圖9 所示。

圖9 可疑節點角色分布

圖9 中橫坐標為節點數量，縱坐標為角色層次。從圖9 中可以看出，FNT-Ant 算法找到的所有層次中的角色數目均高于貪心算法，其中FNT-Ant 算法覆蓋率最高的為位于Level1 層次的角色，其覆蓋率達到了87%，而貪心算法的覆蓋率為70%。由此可見，相比于傳統的貪心算法，FNT-Ant 算法對具有重要角色的可疑節點覆蓋率更高，這也說明了FNT-Ant 算法在骨干網絡的發現上具有一定的應用價值。

5 結束語

本文將交互網絡中的核心信息流通軌跡發現問題轉化為網絡上的路徑尋優問題，提出了一種基于組合優化思想發現骨干網絡的FNT-Ant 算法。FNT-Ant 算法以傳統蟻群模型為依據，結合復雜網絡中的節點中心性理論改進了交互網絡中螞蟻初始位置的選擇策略，依據信息流通特點提出了一種交互網絡中的路徑轉移機制，此外，為保證模型的收斂性能和尋優性能，提出了一種動態改變信息素揮發因子的自適應信息素更新機制。實驗結果表明，FNT-Ant 算法在骨干網絡發現問題上具有較好的求解性能和較快的收斂速度，并在金融網絡的約減和異常分析上具有相當的應用價值。

本文的研究為蟻群算法在交互網絡上應用的初探，算法為解決組合優化問題、資金追蹤問題、主干路徑發現問題提供了新思路?，F階段，算法對蟻群初始位置選擇參考因素較少，在參數優化、算法的時間空間復雜度等方面還有進一步的研究空間。