基于復雜網(wǎng)絡特征的角色發(fā)現(xiàn)算法研究綜述

魏旭光，郝曉倩，畢雪燕

（河北工業(yè)大學經(jīng)濟管理學院，天津 300400）

0 引言

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

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

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

1 基于圖的角色發(fā)現(xiàn)

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

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

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

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

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

2 基于特征的角色發(fā)現(xiàn)

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

2.1 基于二維度量的角色發(fā)現(xiàn)

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

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

2.2 基于多維特征的角色發(fā)現(xiàn)

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

2.2.1 樸素聚類

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

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

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

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

2.2.2 矩陣分解

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

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

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

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

算法1Refex 特征遞歸

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

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

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

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

2.2.3 張量分解

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

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

綜上，張量模型相較矩陣具有更高的特征容納及分析能力，在動態(tài)數(shù)據(jù)分析、復雜關系分析等任務中也較矩陣分析更高效，在節(jié)點特征復雜度或數(shù)據(jù)分析實時性要求較高的網(wǎng)絡角色分析中優(yōu)勢更顯著，但模型構建復雜度較高。

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

3 基于特征的角色發(fā)現(xiàn)動態(tài)研究

動態(tài)角色分析通過對網(wǎng)絡中節(jié)點角色隨時間變化的演變規(guī)律挖掘演化過程中網(wǎng)絡的結構性及功能性變化。動態(tài)網(wǎng)絡的時序演化過程增加了其量化表示與研究的難度，動態(tài)網(wǎng)絡的角色發(fā)現(xiàn)研究仍處于起步階段。

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

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

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

4 研究展望

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

4.1 理論延伸方向

4.1.1 基于圖與特征混合方法的角色發(fā)現(xiàn)

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

4.1.2 邊角色發(fā)現(xiàn)

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

4.1.3 時序網(wǎng)絡

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

4.2 實踐應用空間

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

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

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