基于復雜網絡特征的角色發現算法研究綜述

魏旭光，郝曉倩，畢雪燕

（河北工業大學經濟管理學院，天津 300400）

0 引言

復雜網絡節點數量的激增與其復雜性的逐步升級，使角色發現研究的現實需求逐步增強。角色指具有相同結構特征的節點在網絡中承擔相似職能，角色發現通過量化節點結構，判定節點在網絡中的角色，對分析網絡結構、研究節點間關系具有重要意義。

角色發現最初用于識別個體在社交網絡中承擔的角色及其特征。近年來，角色發現研究逐漸深入到在線社交網絡［1］、通信網絡［2］、合著網絡［3］、生物網絡［4］等諸多領域。研究者針對復雜網絡拓撲結構特征，從網絡整體對網絡中的各類角色進行分析，或識別影響者、意見領袖等重要節點［5］，以便進行網絡管理。

角色發現作為重要的復雜網絡分析工具，通對網絡節點進行識別、分類及深入分析，應用領域不斷拓展。本文在歸納已有角色發現概念和方法基礎上，區分基于圖的角色發現和基于特征的角色發現兩種研究范式，梳理研究邏輯，解析各方法特點和適用條件，繼而對角色發現的動態研究方法進行梳理與說明。研究結果完善了對角色發現已有研究的系統認識，區分了角色發現方法的適用性，有助于拓展角色發現應用領域的新邊界。

1 基于圖的角色發現

基于圖的角色發現是早期角色研究的主要方法，以圖論為基礎，研究者根據結構等價性劃分角色。研究基于自同構等價、正則等價及隨機等價等等價標準及多種相似性度量方法，如結構相似性或社會距離等。基于圖的角色發現衍生出塊模型、概率圖模型及鄰接矩陣相似性3 種主要方法。

（1）塊模型方法。塊模型方法基于隨機等價理論，通過建立交互圖表現網絡角色關系，后續研究者提出了隨機塊模型（SBM）、廣義塊模型及混合隸屬度隨機塊模型（MMSB）等。其中，隨機塊模型得到了廣泛應用與改進；Edoardo 等［6］針對算法只支持單一角色的不足，提出快速嵌套變分推理算法用于多重角色發現；Fu 等［7］基于MMSB考慮節點角色的動態變化，建立動態混合隸屬度隨機塊模型（dMMSB）；徐建民等［8］基于在線社交網絡具體特征對分類混合隸屬度隨機塊模型模型（aMMSB）進行改進，加入節點間單向關系，改進節點隸屬度評價指標。

（2）概率圖模型。概率圖模型以圖為依托表現變量概率的依賴關系，是近年來不確定性推理的研究熱點。基本的概率圖模型分為貝葉斯網絡和馬爾可夫網絡兩大類。早期的角色發現研究基于貝葉斯網絡模擬人類推理過程中因果關系的不確定性，以馬爾可夫鏈蒙特卡洛方法（MCMC）為主要方法進行節點的角色歸類。Aaron 等［9］在此基礎上利用先驗概率加快學習速度，以多智能體（Multi-Agents）強化學習并對MCMC 模型進行改進。此外，也有研究采用DP（Dirichlet Process）［10］確定角色數量并進行參數優化。

（3）鄰接矩陣的行/列相似性。此類方法以節點鄰接矩陣為基礎，以矩陣行/列之間的相似性度量劃分角色。首先，以相似性度量指標（如閔可夫斯基距離、歐氏距離、余弦相似度等）計算鄰接矩陣相似性；然后，對相似度矩陣進行處理，例如采用CONCOR 算法對相似度矩陣進行相似性計算，迭代至形成一個僅包含1 和-1 的系數矩陣即進行二分，通過不斷對子群進行二分實現角色分類［11］。此外，也有其他聚類方法實現類似處理過程，代表性算法有Sim-Rank、RoleSim 等。

綜上，基于圖的角色發現方法以等價概念為理論基礎，結合概率論及矩陣論等，以網絡整體為分析視角對網絡圖進行分割，在網絡整體層面的角色發掘任務中表現較好。但此類方法僅基于節點的結構相似性進行角色發現，計算復雜度較高。因此，基于圖的角色發現方法更適用于復雜度較低、網絡規模較小的研究。現實背景下，企業網絡、在線社交網絡及通信網絡等典型網絡的規模不斷擴大，實時分析需求不斷提升，其計算復雜度方面的劣勢愈發明顯。

2 基于特征的角色發現

基于特征的角色發現算法以復雜網絡理論為基礎［12］，選取具有代表性的度量指標對節點進行描述與分類。根據劃分粒度不同，本文將建立在特征基礎上的角色研究分為基于二維度量的角色發現和基于多維特征的角色發現。

2.1 基于二維度量的角色發現

該方法選取兩種特征建立坐標系，將所有節點按照兩個指標的表現強弱劃分為4 種或以上的角色類別。一類研究單純基于節點指標進行角色劃分：Burt［13］基于表現突出程度及其與結構等價節點的交互程度，將節點歸類為4個經典角色；李婉鈺［12］根據出拓撲勢值及入拓撲勢值定義4 種經典角色，計算節點與4 種角色向量的歐氏距離以確定節點角色。第二類研究將角色發現與社團發現相結合，基于社團發現結果定義節點角色。Zhu 等［14］在社團劃分基礎上定義inner rank 和outter rank 指標，分別表示節點與社團內節點的連接強度及節點與社團外節點的連接強度，將節點區分為4 類角色。Jerry 等［15］依據模塊度函數Q 測定鏈結構與社團間的關聯程度，根據社團聚類結果與社團間的連接度定性地分配為4種角色。

綜上，基于二維度量的角色發現方法多結合應用場景改進其度量指標及角色劃分原則。該方法適用于較少節點的粗粒度分類，但利用指標數量有限，且角色的表達能力存在局限，對多重特征及其動態變化靈敏度低，不便于對復雜網絡進行動態研究與角色預測。其局限性無法支撐其成為研究的主要發展方向。

2.2 基于多維特征的角色發現

基于多維特征的角色發現方法對大規模復雜網絡研究更加靈活，是角色發現的研究熱點。此類方法考慮角色發現研究需要和無監督學習算法優勢，將聚類算法如Kmeans 聚類、DBSCAN 聚類及降維分析算法如非負矩陣分解（Nonnegative Matrix Factorization，NMF）及Trucker 分解等應用于角色發現，推動了角色發現在各研究領域的發展。本文依據所用算法類別差異，將基于多維特征的角色發現歸納為樸素聚類和矩陣分解兩個主要類別以及張量分解等其他研究方法。

2.2.1 樸素聚類

樸素聚類算法根據聚類原理可分為分塊聚類算法、層次聚類算法、密度聚類算法、網格聚類算法等。研究者使用聚類算法對節點特征進行聚類，將特征相似或特征距離接近的節點歸類為一種角色，已有文獻中的代表性聚類算法有K-means 聚類和DBSCAN 聚類等。

K-means 聚類是一種基于劃分的聚類算法，根據節點特征計算，首先需指定質心初始值，初始劃分后再為每一類重新計算質心，如此迭代，以質心體現某類型節點的平均特性，作為此類節點的角色。Yu 等［16］將K-means 應用于社會網絡角色分析，定義了基本群體描述、社會行為及結構洞等11 項特征并進行角色聚類。針對經典K-means需指定角色數量等不足，部分文獻采用貝葉斯信息準則（BIC）作為最佳聚類數量選擇依據。

DBSCAN 聚類是基于密度的有噪聲應用空間聚類，通過對特征空間密度檢測對節點進行聚類，密度大的區域為節點類內部，密度小的區域為類的界限。Xiao 等［17］借助二維網格空間圖對算法的角色檢測原理進行說明，并首次將算法置于并行分布式計算環境下，進行在線社交網絡的角色分析。

樸素聚類算法相對靈活，但該方法只能將節點劃分至單個角色，難以通過角色的軟分配對節點角色演化趨勢作進一步分析。此外，該方法僅體現節點的最終分類結果，結果準確性受研究者先驗知識影響，這是樸素聚類算法進行角色發現面臨的主要挑戰。

2.2.2 矩陣分解

以矩陣分解進行節點角色發現的步驟包含特征選擇、特征處理及非負矩陣分解，詳細過程如下：

（1）特征選擇。節點基本特征包括局部特征、全局特征、位置特征及隨機游走等。局部特征考慮節點本身及鄰居節點信息，計算復雜度低。全局特征反映節點的全局性結構特征，有助于把握節點的整體性特征，但計算復雜度較高。位置屬性是對節點網絡位置的刻畫，最常用的K-殼分解法可確定節點的網絡位置，該方法對于節點重要性研究具有重要意義。隨機游走特征則指在隨機游走前提下確定節點影響力的方法，例如PageRank、LeaderRank 等。4 種特征可靈活結合，也有部分研究將基于圖的節點分類結果作為特征之一，有助于提升節點特征的全面性，可挖掘出更有意義的潛在角色［18］。

以上文獻均基于低階特征進行角色發現。低階網絡特征指僅表示節點兩兩交互連接的相關屬性，如度、介數等；而網絡中的諸多高階屬性，如模體（motifs）、最大派系、三角形數等，可發掘網絡中更高階的連接關系。Nesreen等［19］首次利用模體（motifs）進行特征提取，通過迭代運算將特征進行深度篩選，使特征矩陣構建更具有深度與代表性。Pei 等［20］使用包含3 節點的模體類作為網絡特征對Zachary 網絡及悲慘世界人物關系網絡進行潛在角色挖掘，與MMSB、MMTM 等已有算法相比，其對角色的定位更加準確高效。

（2）特征處理。特征處理對模型準確度具有重要作用。配合后續矩陣分解實施要求，對單一特征值作歸一化、標準化等預處理，可使數據實現無量綱化或縮小數據波動范圍。對多維特征進行降維，通過Filter、Wrapper 或Embedded 方法進行特征篩選，可使特征表征能力得到提升。已有研究大多延續ReFex 算法［21］的特征處理方法：通過遞歸法對特征進行交互，并通過垂直對數分箱法及特征關聯圖對遞歸特征進行篩選（如算法1 所示）。角色發現算法構建具有靈活性，研究者可使用其他特征處理方式進行特征矩陣構建［2］。

算法1Refex 特征遞歸

（3）非負矩陣分解。給定非負矩陣Gn×m，將該矩陣分解為兩個非負矩陣Wn×r及Hr×m，使Gn×m≈Wn×rHr×m；其中，Gn×m為節點—特征矩陣，n 為節點數量，m 為特征數量；Wn×r與Hr×m分別為節點—角色矩陣與角色—特征矩陣，r為角色數量。

研究者就角色數量選擇、分解約束條件等不斷作出改進，并就分解結果的解釋與評價提出了諸多經典模型。利用矩陣分解算法進行角色發現的研究多基于RolX 算法［2］，該算法以F 范數最小化為目標函數對特征矩陣進行非負矩陣分解，通過最小描述長度方法（MDL）進行角色數量選擇，實現基于特征的自動角色識別。將角色發現應用于圖的去匿名化、遷移學習及相似度評估等多個數據挖掘任務中，拓展了角色發現與其他領域的關聯研究。

Gilpin 等［22］針對算法的無監督性提出基于約束引導的角色發現算法GLRD，將分解過程視為每行每列對應處理的子問題，使矩陣分解轉化為凸優化問題，且分別將稀疏性約束、多樣性約束與可選擇性約束加入矩陣分解過程，用于發現更具有可解釋性、創新性的潛在角色集合。

RIDεRs 算法［23］是εER 準則下基于圖與基于特征的角色發現算法的結合，εER 準則是一個基于圖的等價概念。設置ε 為節點間的平均度松弛值進行節點的塊劃分，將劃分結果作為節點特征之一，并提出基于零模型的角色評價方法。

2.2.3 張量分解

張量指代三階及以上的高階張量，張量可以包含更廣維度的節點特征，包括時間維度、網絡層級關系等，研究者可基于核心張量開展角色演化分析。

于興隆［24］結合節點角色的現實意義選擇平行因子分解，以誤差平方和及核一致性診斷確定角色數量，將三維特征矩陣分解為角色—時間映射關系及節點—角色映射關系，實現了時間維度下角色的演化研究。段松青等［25］類似地采用CP 分解將節點映射為權威性角色及樞紐性角色。Gilpin 等［26］基于多重關系圖指出已有研究僅對節點關系進行單一層次劃分的不足，建立節點、特征及關系層面的三維張量模型，采用Trucker 分解獲得核張量，發掘節點在不同關系層面下的角色。

綜上，張量模型相較矩陣具有更高的特征容納及分析能力，在動態數據分析、復雜關系分析等任務中也較矩陣分析更高效，在節點特征復雜度或數據分析實時性要求較高的網絡角色分析中優勢更顯著，但模型構建復雜度較高。

相較于樸素聚類算法，矩陣分解方法及張量分解方法通過隸屬度評分為節點分配不同角色，對角色分配更加靈活。研究者將矩陣分解方法所得的角色—特征矩陣可直觀展示各角色特征及角色間的相似度，也可通過意義構建對角色的現實意義進行解析，提升角色發現在各研究領域的可解釋性與適用性。

3 基于特征的角色發現動態研究

動態角色分析通過對網絡中節點角色隨時間變化的演變規律挖掘演化過程中網絡的結構性及功能性變化。動態網絡的時序演化過程增加了其量化表示與研究的難度，動態網絡的角色發現研究仍處于起步階段。

動態網絡的角色發現包括歷史快照及張量模型兩種方法。快照研究將動態網絡分割為快照子圖，分別在各快照中進行角色識別，最終對各節點的角色演化過程進行分析。Rossi 等［27］利用歷史快照方法進行網絡角色的一系列研究：首先基于網絡動力學提出混合隸屬度動態模型DBMM，并將核函數模式與時間權重衰減法結合進行角色預測。此外，李川等［28］針對TM 模型中矩陣轉移方法只考慮前一時刻角色的不足，構建二階訓練模型MTR-RP 進行角色的動態研究及預測。馮冰清等［29］基于向量自回歸（VAR）方法進行角色的動態分析與預測。

張量分解方法憑借其高維特征優勢，將時間序列作為張量模型的時間維度，通過張量分解過程直接獲得時間—角色序列，對節點角色演化規律進行剖析。于興隆［24］、段松青等［25］均將時間維度建立在張量模型中進行角色動態分析。

快照分析建模簡單且計算復雜度低，適用于數據的時間跨度較小或數據變化較慢的研究領域；張量模型分析建模復雜度較高，但在角色的演化分析任務中更加高效。在動態分析基礎上，對節點角色的預測研究也成為近年來的研究重點。目前，對節點角色的預測工作還限于線性模型和向量回歸方法。然而，角色發現預測屬于時間序列預測問題，諸多時間序列預測方法均可運用于角色發現任務中。

4 研究展望

本文簡要歸納了基于圖的角色發現研究原理及主要方法，并分靜態與動態對基于特征的角色發現研究進行梳理。基于圖的角色發現為早期研究的主要方法，但計算復雜度高、靈活性差，在大規模復雜網絡中難以擴展。基于二維度量的角色發現方法以便捷性和與社團發現等方法的易結合性在基于特征的角色發現研究初期起到了重要作用。以樸素聚類、矩陣分解等為代表的機器學習方法則使基于特征的角色發現算法以細粒度深入探討復雜特征，為更多復雜網絡研究提供了新視角和有力工具。基于角色發現的理論必要性與需求現實性，以及對角色發現已有文獻的梳理與分析，本文從理論與實踐角度對未來研究方向進行展望。

4.1 理論延伸方向

4.1.1 基于圖與特征混合方法的角色發現

基于圖與基于特征的角色發現算法各具優勢，研究者通常從中擇其一。事實上，兩種方法的結合可使研究兼顧網絡全局與局部信息，使角色更貼合實際。RIDεRs 算法是對兩種方法結合的初次嘗試，但該方法僅將基于圖的特征利用特征矩陣的方式進行構造，未考慮局部特征，故兩種方法的結合仍是后續研究的方向之一。

4.1.2 邊角色發現

網絡的復雜性不僅源于節點變化，更源于節點間連接關系的變化，如企業規模、中心性及度等特征在較短周期內變動較小。但企業間的合作關系變動速度相對較快，對合作關系的分析更能體現企業在網絡中承擔的角色等。因此，網絡中邊角色的分析極其重要。已有文獻多以節點為中心展開研究，對網絡中邊角色的挖掘工作較少，Nesreen 等［19］已在其部分研究中開始了對邊角色發現的探索，邊角色發現方法在經濟、交通及社交網絡等領域有很大研究空間。

4.1.3 時序網絡

時序網絡是復雜網絡的擴展，可在網絡中記錄節點在歷史時刻的交互信息和交互次序。傳統網絡研究基于系統動力學將時間維度編碼于動態系統，而時序網絡將時間維度提升至網絡本身的數學性表征，對節點交互和網絡拓撲結構的異構性研究以及大規模動態現象的解釋和預測具有重要意義。時序網絡與角色發現在大規模網絡、動態網絡及角色預測方面的理論和實際需求日益突出的現狀十分契合，借助時序網絡的一般方法可對潛在角色進行更深層次的挖掘與分析。

4.2 實踐應用空間

目前，角色發現方法主要應用于社會網絡、生物網絡及通信網絡等。隨著角色發現靜態方法的不斷完善，動態研究依托的理論基礎不斷豐富，角色發現研究可擴展到更多實踐領域。供應鏈網絡是典型的復雜網絡之一，網絡中的企業具有很強的實體意義，企業角色對于供應鏈網絡的節點研究、演化研究具有重要意義。

企業的角色不僅取決于企業規模，也與交易額、專利數目等各方面特征密切相關，供應鏈網絡顯著的層級性也通過影響企業在網絡中的位置使企業承擔角色各異。在創新網絡中進行角色發現研究，能夠對創新網絡和專利網絡中節點角色的識別與演化產生更加清晰的認知與理解，以角色為依托的演化研究也可借助創新主體的合作行為促使網絡的良好發展。此外，在典型的病毒網絡研究中，由于同構節點傳播效果相似，節點的角色識別可用于同構節點的識別與病毒網絡的演化研究，拓展病毒網絡研究方法與研究視角。

除上述詳細說明的3 個理論延伸方向與3 個實踐應用延伸外，角色發現還可借助分布式平臺、并行式平臺實現海量數據處理，借助遷移學習實現跨領域知識的學習與應用，借助分層網絡對多種交通方式進行綜合研究等。綜上所述，角色發現方法的基礎研究已經逐漸完善，隨著橫向研究領域與縱向研究深度的不斷發展，角色發現研究依然面臨諸多現實問題，因此具有廣闊的發展空間。