復雜網絡與機器學習融合的研究進展

李澤荃 楊 曌 劉 嶸 李 靖

1(華北科技學院管理學院 北京 101601) 2(華北科技學院安全工程學院 北京 101601) 3(華北科技學院計算機學院 北京 101601)

0 引 言

復雜網絡和機器學習分別是統計物理學和計算機科學領域內重要的研究方向。復雜網絡是研究復雜系統的一種角度和方法，它主要關注系統中個體相互作用的拓撲結構，以及網絡上物質、能量、信息的動力學傳播過程，是理解復雜系統性質和功能的基礎[1]。機器學習主要指計算機利用已有的經驗來獲得學習能力的一種計算方法，通過從大量的數據特征中獲得數據的表示方法，以自動的方式模擬人類專家的判斷[2]。

近年來，將復雜網絡和機器學習結合起來進行研究分析引起了越來越多學者的關注。從本質上說，主要包括兩個方向：一是研究基于復雜網絡理論(或圖論)的機器學習技術；二是利用機器學習算法來挖掘復雜網絡拓撲結構背后隱藏的信息和知識。對于前者，自然界中以網絡形態存在的數據無處不在，利用網絡方式進行數據表示有其內在的優點，它能有效地捕獲數據的空間、拓撲和功能關系，獲得更高的機器學習算法準確度；而對于后者，人類社會的進步促使各類系統越來越復雜，相對應網絡的規模急劇增大，借助智能數據分析工具，如各類機器學習算法，有助于解決復雜網絡中模型與知識的有效挖掘問題。

到目前為止，人們根據所研究的具體問題，提出了多種多樣的基于網絡的機器學習方法或復雜網絡分析工具，并做了一些總結和探討[3]，但仍不夠全面。關于復雜網絡與機器學習融合的研究圖景，未來將有更多可能。

1 復雜網絡簡介

在自然界中，從技術到生物直至社會各類系統都可以通過復雜網絡加以描述，其中節點表示個體或組織，邊表示它們之間的關系[4-7]。對真實網絡進行實證研究不僅有助于認識網絡行為、改善網絡性能和有效地管理網絡，而且能夠先于理論發現現象，為進行理論探索打下基礎，或者作為理論應用范圍的重要判據[7]。為了更好地利用復雜網絡，我們對其數據結構的復雜性和節點及其相關連接的多樣性進行了統一。

1.1 網絡演化模型

為了研究真實網絡的拓撲結構，學者們提出了許多網絡模型，其中有一些網絡模型由于其廣泛的應用價值而得到了重點關注，例如隨機網絡[8]、小世界網絡[9]、隨機聚類網絡[10]、無標度網絡[11]和核心-邊緣網絡[12]。

1.1.1 隨機網絡

1959年，Erd?s和Réyni[8]首次提出了隨機網絡的概念。隨機網絡模型中任意兩個節點以某一概率相連，不考慮節點之間的空間關系和相似性。即隨機網絡中有V個節點，節點之間的連接概率為p，節點的度分布服從二項分布(V-1,p),表示為：

(1)

其他更多特性可參考文獻[13-15]。

1.1.2 小世界網絡

一些現實世界的網絡表現出很強的小世界性，即節點經過少量的幾步(邊)就可以到達另一個節點，如在社會網絡中，可以經過一個很短的連接與世界上任意一個人產生聯系[9,16]。文獻[9]介紹了小世界網絡的形成方法：在包含V個節點的規則網絡中，每個節點與k個節點相鄰，每條邊以概率p任意隨機連接到另外一個節點。當p=0時，網絡不發生重新連接，仍然保持為規則網絡；當p≠0時，所有的連邊將在概率p下重新連接，隨著p值增加，網絡的小世界屬性越來越顯著；當p=1時，網絡成為隨機網絡，此時網絡中節點度數分布的峰值接近2k[9,16]。圖1為網絡在概率p下重新連接的示意圖。

圖1 WS小世界重連邊模型

網絡的小世界特性最直接的理解是在這種網絡上信息傳播的速度非常迅速。

1.1.3 無標度網絡

1998年，Barabási和Albert[11]發現某些網絡中的極少數節點擁有很高的度值，而大部分節點只有很小的度值，即極少數節點與非常多的節點連接，而大部分節點只和很少的節點連接。基于這一發現，1999年他們提出了一種新的網絡模型，即無標度網絡，網絡中節點的度分布服從冪律分布。無標度網絡結構中關鍵節點或度數較大的節點更容易與新節點相連，從而形成更多的連接，新節點也有與度值更高節點相連接的“偏好”。

網絡的無標度性與網絡受到攻擊的魯棒性緊密相關，這種層次結構具有一定的容錯能力。關于無標度網絡對隨機攻擊具有很強的魯棒性而對蓄意攻擊極為脆弱的特點，Cohen等[17-18]和Callaway等[19]利用滲流理論對其進行了詳細研究。

1.1.4 隨機聚類網絡

一些現實世界的網絡如社會網絡和生物網絡呈現出模塊化的結構特性，文獻[10]把它們稱為社團，屬于同一個社團的節點有許多相互連接的邊，而不同的社團間的連接相對較少，這類網絡被稱為隨機聚類網絡。

在隨機聚類網絡的形成過程中，兩個節點如果屬于同一個社團，它們連接的概率為pin，如果屬于不同的社團則連接的概率為pout。典型的隨機聚類網絡中，pin值較大，pout值較小，即社團之內的節點連接緊密，而社團之間的節點連接稀疏。當pin值較小，而pout值較大時，網絡中節點的聚類效果不顯著。基于以上參數，定義Zin/和Zout/分別為社團內節點和社團間節點的連接程度。或許，隨著Zout/值的增大，社團間的連接逐漸緊密，社團之間的界限也將越來越模糊。

1.1.5 核心-邊緣網絡

核心-邊緣網絡結構最早出現在社會學[20-21]、國際關系學[22-23]和經濟學[24]等學科中。一般認為網絡中的核心節點是具有很大度數的節點，識別核心-邊緣結構最常用的定量方法是由博爾加蒂和埃弗雷特于1999年提出的[12]，按照該方法，對某一網絡進行聚類分析時，對于其中的關鍵節點，采用不同的社團檢測算法可能使它們分配到不同的社團[25]。因此，如何判斷它們與不同社團之間關系的強弱至關重要，可以采用社團重疊算法[26]。在這種情況下，一般意義上的社團概念可能并不能很好地實現對中等尺度網絡實際結構的理解，將關鍵節點劃分為核心結構來考慮可能更為合理[27]。可以將單個社團看作網絡核心結構的一部分，整個核心結構由多個社團組成，社團之間可以存在重疊[28-29]。

1.2 網絡度量方法分類

根據復雜網絡的統計特性，如度、度的相關性、距離和路徑、網絡結構以及網絡中心性等，眾多學者已經提出了許多網絡相關統計描述計算方法。按照在計算中使用信息的類型，可以將其分為三類：

1) 局部算法：僅僅根據節點自身的信息來進行計算。

2) 混合算法：除了根據節點信息外，還利用其直接和間接鄰域內節點的拓撲信息進行計算。這些信息可以是最簡單的局部拓撲，如鄰域中的三角形數，也可以是網絡的全局信息，如最遠兩個節點之間的最短路徑等。

3) 全局算法：根據整個網絡拓撲結構進行計算。

圖2描繪了這三類網絡統計度量方法相互關系的示意圖，表1列出了常用的各類網絡統計描述。

圖2 網絡統計度量方法分類

表1 復雜網絡常用的統計描述

1.3 復雜網絡的動力學過程

1.3.1 隨機游走

隨機游走是一系列由連續隨機步組成的軌跡的數學表示[30]。它常被用來描述很多自然現象和工程問題，如圖形匹配和模式識別[31]、圖像分割[32]，神經網絡模型[33-34]、網絡中心性度量[35]、網絡劃分[36]、通信網絡構建與分析[37-38]等。

給定一個網絡G=和一個起始節點v∈V，隨機選擇一個鄰居節點，移動到該鄰居；然后，再次隨機選擇這個新節點的鄰居并移動，以此類推，以這種方式選擇節點的隨機序列就是網絡上的隨機游走過程。如果網絡是加權網絡，可以與連邊權重Avu成正比的概率過渡到鄰居u。

本質上，網絡上的隨機游走和有限離散馬爾可夫鏈的原理基本是相通的，所以網絡上的任意一個離散馬爾可夫鏈都可以被認為是一個隨機游走過程。眾所周知，離散馬爾可夫鏈是隨機過程，其未來狀態在條件上獨立于過去的狀態，因此只要知道當前狀態即可求得未來狀態。在圖論中，圖的節點可以表示狀態，因此，步行者從節點v移動到其鄰居節點的概率獨立于步行者的過去軌跡。

1.3.2 惰性隨機游走

平穩分布只適用于非周期網絡，如果網絡具有周期性，就需要引入惰性隨機游走算法。惰性隨機游走算法可以被看作是網絡中經典隨機游走算法的改進版，僅將網絡G中的每個節點u添加自身環即可[39]。

游走過程中，在時刻t，游走者面臨兩個不同的選擇：它可以根據轉移矩陣以1/2的概率過渡到相鄰節點；或者，以1/2的概率停留在當前節點。因此，從形式上看，惰性隨機游走的概率分布p(t)的演化可以表示為：

(2)

式中：P′(t)為轉移矩陣，有：

(3)

1.3.3 自避行走

網絡自避行走指網絡中所有節點僅被訪問一次所獲得的路徑。自避行走最早在聚合物化學理論中出現[40]，此后其特性也引起了數學家和物理學家的廣泛關注[41]。從廣義的角度看，自避行走通常被考慮為無限格子上的算法，所以每一次移動只允許在離散的方向上進行并且具有一定的步長。可以看出，自避行走不是馬爾可夫過程，因此需要利用過去的軌跡來計算出其可能出現的未來狀態[41]。

1.3.4 游客漫步

游客漫步可以理解為一個游客在P維地圖中游覽景點(數據項)的問題。在每個離散的時間步，游客遵循一個簡單的確定性規則，即游覽最近的景點，且該景點在之前的步沒有被游覽過[42]。游客漫步不同于自避行走，前者是一個確定性過程，而后者是一個隨機過程。游客的行為在很大程度上取決于景點(數據集)的結構和起始景點。在計算方面，游客的行動完全通過鄰域表來實現，其中鄰域表是通過對與特定景點相關的所有數據項進行排序而構建的。一般情況下，每個游覽路徑都可以看成兩個階段：初始瞬態和周期循環(吸引子)。

在大多數與游客漫步相關的文獻中，游客可以訪問記憶窗口μ以外的其他景點[42-44]。隨著μ值增加，游客有可能在數據集上進行長距離跳躍，因為在時間范圍內鄰居最有可能已經被完全訪問。在分類任務上，可以采用網絡的方法來避免該問題，此時游客僅被允許訪問與其相連的節點(景點)。或許，當值很大時，游客很可能被困在節點上，而不能進一步訪問其他鄰居節點。

1.3.5 流行病傳播

復雜網絡上的流行病傳播已經引起了眾多研究者的關注，大家主要關心的是網絡結構如何減弱或放大疾病傳播。由于流行病傳播過程可以看作是信息傳播，因此對于機器學習來說非常有用。目前主要有兩種流行病傳播模型，SIR和SIS模型[45-47]。關于其詳細綜述，請參閱文獻[48-50]。另外，對于一些復雜網絡上信息傳播的研究進展，可參見文獻[51-58]。

2 機器學習簡介

機器學習的目標是讓計算機擁有人類的“學習”能力[59-64]。傳統的機器學習方法有三種類型：第一種是監督學習，它主要利用已標記的樣本數據進行訓練得到數學模型，再利用該模型對未知數據進行預測[61,65-67]。第二種是無監督學習，其主要任務是利用樣本的相似性或拓撲結構學習和發現樣本的內在聯系[63,68-69]。其中，監督學習和無監督學習的主要區別在于監督學習利用包含外部標記信息的數據進行訓練得到函數，而無監督學習沒有任何標注數據，主要將某種屬性相似的樣本聚集在一起。第三種方法叫半監督學習，它是監督學習和無監督學習相結合的一種方法[70-72]，半監督學習中少量的樣本數據帶有標記，而大多數樣本數據是未標記的，學習過程就是利用這些少量已標記樣本對其他未標記樣本進行標記和分類。圖3是機器學習的三種范式。

圖3 三種類型的機器學習方法

值得一提的是，機器學習領域中的新技術，即深度學習。其主要利用由多個非線性變換構建的高階數學模型來表達樣本項之間的關系，通過利用高效的算法進行分層特征提取，從面部識別等實際應用來看，深度學習的一些方法將使機器學習任務變得更為容易。

2.1 監督學習

僅利用具有標記信息的樣本數據進行訓練和建模的算法稱為監督學習。通常我們利用監督學習來預測無標簽樣本的類型標簽，其中，對離散值進行預測稱為“分類”，而對連續值進行預測稱為“回歸”[59]。

監督學習主要分為兩個階段：訓練階段和分類階段[59,66-68]。在訓練階段，利用帶有標簽的樣本集合訓練得到分類函數；在分類階段，利用上一步得到的分類函數對未標記的測試集進行標記分類。關于監督學習的詳細數學描述可參見文獻[59,63,68,73]。對于監督學習的主要算法，請詳見文獻[74-80]。

2.2 無監督學習

從本質上來看，無監督學習是分析樣本分布的概率密度函數[70]。無監督學習算法可以歸納為四類：聚類[10,81-84]、異常檢測[85-86]、降維[87]和關聯分析[88]等。聚類是根據樣本特征進行分類，通常假設一個相似函數來判斷樣本之間的同質性或異質性，分類后同一類別應具有盡可能高的同質性，而類別之間則具有盡可能高的異質性[63]。異常檢測的目標是找出原始樣本中與其他樣本屬于不同類別的樣本項[85]。降維是指采用某種映射方法，將原本屬于高維空間中的樣本點映射到低維空間中，從而簡化樣本之間的關系[87]。關聯分析簡單地說是尋找樣本數據間的隱含關系[87]。關于無監督學習的詳細數學描述可參見文獻[59,63-64,89-91]。

無監督學習最常見的任務是樣本聚類，這些集簇可以是某種形狀、某種類型的點或對象等[59,90-93]。隨著數據量和數據種類的指數增長，提高數據的自動理解和處理能力是重點，例如在數據挖掘、文獻檢索、圖像分割、生物分析、模式分類等任務中，通常我們僅僅掌握很少量的先驗信息[91-92,94-96]，因此，其應用非常廣泛。

2.3 半監督學習

自然界中存在許多半監督學習的實例。如嬰兒通過聽到聲音到學會說話的過程，期初，嬰兒并不了解聽到的聲音，嬰兒的反應僅是記住這些聲音，這便是標記的數據，通過不斷地刺激和學習，嬰兒最終實現了從聽到說的能力[97-98]。半監督學習可以有效減少標記樣本的工作量，特別是當數據標記成本高昂且耗費時間。關于半監督學習的詳細數學描述可參見文獻[70-72]。半監督學習應用的領域包括視頻索引、音頻信號分類、自然語言處理、醫學診斷、基因數據處理等[70,72]。

對于半監督學習，數據的一致性假設是前提[99]。通常情況下，半監督學習中存在一個或多個基本假設，包括聚類假設、平滑假設和流形假設[70]。

一般情況下，可將半監督學習算法歸納為四類，即生成模型[70,72,89,100-101]、聚類和標記模型[102-103]、低密度區域分離模型[70,72,89,104-105]和基于網絡(圖)的模型[80,90-92]。

3 基于復雜網絡的機器學習方法

在過去的幾年里，基于復雜網絡的機器學習方法越來越受到關注。該方法有其內在的優點，即數據通過網絡的形式來表征能有效捕獲數據的空間結構、拓撲結構和功能關系。該類型的數據通常以網絡形式表示，其中一部分節點被標記，另外一些節點未被標記，算法的任務是預測未標記節點的標簽。同樣，按照機器學習的分類，下面重點討論基于網絡的監督學習、無監督學習和半監督學習技術。

3.1 網絡構建技術

在機器學習的很多領域，數據樣本點之間的局部關系以及由局部信息衍生出的全局結構經常用網絡來表示。在處理機器學習或者數據挖掘的問題時，網絡構建是一個非常有必要的步驟。當應用基于網絡的機器學習方法分析向量表示的數據樣本時，該步驟變得尤為關鍵，需要采用網絡構建技術將輸入樣本集形成網絡。一般來說，按照網絡構建過程中的信息類型將網絡構建方法分為三類，即局部信息方法、遠程信息方法和全局信息方法，詳細情況見表2。

表2 網絡構建技術分類

3.2 監督學習方法

對于網絡環境下的監督學習分類問題，通常利用外部信息(如標簽)來訓練模型。與一般的監督學習類似，學習過程通常分為兩個階段：訓練階段和預測階段。訓練階段，模型根據帶標簽數據樣本進行學習；預測階段，利用模型對未知數據樣本進行預測。基于網絡的監督學習算法仍然研究的不多，主要有關聯圖分類算法、關系分類算法和啟發式分類算法。

3.2.1 關聯圖分類算法

關聯圖分類算法中，應用最多的是k-關聯圖算法[114]。k-關聯圖分類算法同樣也是將訓練集數據構建為網絡，即有向k-關聯圖網絡。該算法是建立在基于向量形式的數據集上，主要是將向量數據抽象為節點和連邊。在給定的k值構建k-關聯圖后，在訓練和測試階段都應對網絡中的每個子圖進行純度檢驗用于確定最佳的網絡分類。k-關聯圖中的連邊根據修正的k-近鄰算法確定。在這種特殊網絡形成過程中，只有具有相同標簽或類的節點才允許相連，算法模型根據這個簡單規則逐步形成整個網絡。

網絡中子圖純度的定義為：給定參數k值，利用修正的k-近鄰算法形成網絡，每個節點最多可以具有2k個連接。由于網絡為有向網絡，每個節點度的取值范圍為[k，2k]。純度測試確定了每個節點的度取值的可行性區間。本質上，它量化了同一類別節點間有效創建的連邊數量與每個節點可能連接的總連接值2k之間的比值。因此，網絡中某一組件α的純度φ定義為：

(4)

為了得到最佳k-關聯圖，具體步驟是從k的最小取值開始逐一計算各個子圖。對每個k值和網絡子圖分別計算純度值，然后比較由不同k值產生的k-關聯圖。獲得最佳k-關聯圖之后，學習過程進入具體的分類階段。在這一階段，文獻[114]采用了貝葉斯分類器進行分類。

3.2.2 集合推理算法

集合推理算法處理的數據與傳統監督學習方法處理的數據不同，它規避了數據的獨立性假設，因為數據的標簽不僅依賴于數據本身屬性，同時也依賴于鄰域數據的標簽[115]。因此，對于網絡數據，一個數據項(節點)的標簽可能對與之相關節點的標簽具有一定的影響。

在網絡環境下以相互關聯的方式來推斷相關節點標簽的算法中較為著名的是集合推理模型[116]。與傳統的分類技術相比，這種方法可以顯著地減少錯誤分類[117]。集合推理模型可以同時使用數據屬性和數據關系特征來進行分類。眾所周知，節點的標簽也可能與網絡上與之間接相連節點的標簽相關，同時對所有節點的標簽信息進行計算可能更有意義。

另外，在一些學習過程中的特定階段也可以采用集合推理算法。例如樸素貝葉斯或關系概率樹等算法，采用局部分類器預測每個未標記節點的標簽，并進一步使用如Gibbs抽樣[117]或ICA[118]等集合推理算法重新修改節點的標簽，這類方法為局部方法。另一種方法使用全局算法，主要以優化全局目標函數為目標進行訓練，這類算法包括循環信念傳播和松弛標記法等[119]。

關于集合推理算法，文獻[120]提出了一種基于網絡的監督學習模型框架(NetKit)。該框架主要由三部分組成：一是局部分類器，主要利用訓練集來形成概率分布模型；二是關系分類器，也是估計樣本的概率分布，但與局部分類器不同的地方是它考慮了網絡中相鄰節點關系的影響；三是集合推理器，利用模型對樣本類別進行預測。

此類方法已經在各個領域獲得了廣泛應用，如生物學中分子用途的分析[121]、科研論文鏈接的分類[118]、鏈接預測[122]等。再比如在社交網絡中預測當前沒有關聯的兩個點在未來某一時間連接的可能性[123]，創建一個小連通子來中模擬社交網絡中兩個節點之間的關系[124]。

3.2.3 啟發式分類算法

文獻[125]首次提出啟發式分類算法，該算法結合了“網絡環境下的易訪問性”來執行分類任務。易訪問性的衡量標準是基于馬爾可夫鏈理論中的極限概率而確定的。首先，一組標記數據被映射為網絡的節點。因此，該網絡可以看成是一個離散的馬爾可夫鏈，每個節點代表馬爾可夫過程中的一個狀態。當對未標記樣本進行分類時，因為未標記樣本的偏差信息應被考慮在內，包含標記樣本的網絡中連邊的權值需要重新計算。在得到修正的極限概率后，未標記樣本的類標簽由最容易(易訪問)獲得的標記樣本表示，最終，這樣的偏差信息將逐步改變網絡結構。

(5)

3.2.4 集成方法

文獻[126]提出了一種基于低級分類器和高級分類器的集成方法。從本質上講，低級分類器是根據樣本標簽和樣本的統計特性進行分類，它可以是任何傳統的分類技術，如決策樹、支持向量機、感知機、貝葉斯學習，或k-近鄰等；而高級分類器除了使用樣本的標簽外，還使用樣本的網絡拓撲結構或模式信息進行分類。集成方法的一個突出特點是跨網絡技術，即它將輸入數據看作一個整體構建網絡，并考慮到網絡的全局模式。定義集成方法F，它是兩種分類器的凸組合，即：

(6)

關于集成方法中高級分類器的構建，目前有兩種方法。第一種是平均度、聚類系數和同配性三種網絡統計量的結合方法[126]，覆蓋了網絡從局部到全局的所有信息。其中，度可以準確度量網絡中節點的局部信息；聚類系數通過計算當前節點及其鄰域內的兩個節點所形成的三角形數量度量網絡的局部結構；同配性不僅考慮當前節點及其鄰域內的節點，而且考慮第二級鄰域內的節點(鄰域的鄰域)、第三級鄰域內的節點等。

第二種利用了隨機游走過程中的動力學特性[127]。與經典的網絡統計量計算方法不同，該算法利用網絡中隨機游走過程的動力學特性提取網絡的高級信息。換句話說，隨機游走可以理解為在高維數據空間中隨機訪問數據節點的過程，通過不斷調整隨機游走過程中記憶窗口的長度，來提取從局部到全局的網絡信息和網絡特征。當隨機游走的記憶窗口較小時，提取網絡的局部結構特征；隨著記憶窗口的逐漸增大，游走過程被迫逐漸遠離起點，從而學習網絡的全局特性。

3.3 無監督學習方法

眾所周知，無監督學習任務中樣本數據沒有類別屬性的先驗知識。基于網絡的無監督學習方法類似，學習過程首先根據相似度標準從輸入數據構建網絡，再通過網絡結構完成知識的學習。無監督學習的一個主要任務是數據聚類問題，實際上，一旦原始數據集轉化為網絡，數據聚類可以被認為是社團檢測問題。眾多學者業對于此問題提出了近似的、有效的解決方法，其中包括譜方法[128]，基于介數的算法[129]，模塊化貪心優化算法[130]，基于Potts模型的社團檢測算法[131]，同步方法[132]，信息論方法[133]和隨機游走[134]。

3.3.1 基于介數的算法

識別網絡中社團的自然策略是檢測并刪除連接不同社團節點的連邊，以便社團最終彼此斷開。在這種情況下，網絡單元的數量代表了社團的數量。這是分裂算法的思想，其關鍵就是尋找社團之間連邊的專有特征，從而進行識別。目前最為流行的是基于介數中心性的算法，首先由Girvan和Newman[10,129]提出，在選擇要刪除的連邊過程中，算法根據邊介數中心性來確定。在計算時，他們考慮了測地線、隨機游走和流三種邊介數。如果網絡中存在層次結構，原始的Girvan-Newman算法準確度將下降，為此，有學者把模塊度最大化算法加入了網絡分區的最優劃分過程中[129]。Chen和Yuan[136]認為在邊介數的評估中考慮所有可能的最短路徑可能會導致分區不平衡，即社團大小完全不一致。為了克服這個問題，他們建議只計算非冗余路徑，即那些端點互不相同的路徑。

3.3.2 模塊度最大化算法

模塊度是用來衡量網絡中一個特定區塊劃分質量的方法[137-138]，或者用于衡量網絡區塊劃分為模塊(也稱為組、聚類或社團)的能力。一般來說，其范圍為0到1之間的數值。當模塊度接近0時，表明網絡沒有劃分出社團結構，認為網絡中的邊是隨機連接的。隨著模塊度增加，社團結構越來越顯現，社團內的連邊比例逐漸大于社團間。模塊度定義為：

(7)

式中：E表示網絡中邊的總數目；Aij表示節點i與j之間的連邊權重；ki、kj分別表示節點i和j的度；ci表示節點i的社團；1[ci=cj]為指示函數，當ci=cj，為1；否則，為0。

第一個提出模塊度優化方法的是Clauset等[137]，隨后又有其他學者陸續提出一些改進方法[139-143]。Clauset算法的主要思路是在網絡社團劃分過程中加入了貪婪算法，即在模塊度最大化的每個時間步，選擇合并兩個能使模塊度增幅最大的社團，即找到最大的模塊度增量。但該算法有一個缺點，即社團的不平衡問題，計算過程中會產生包含大部分節點的超社團。為解決社團劃分的不平衡問題，加速社團合并過程運行時間，出現了Louvain方法[139]，它能夠處理百萬節點的網絡，是迄今為止最快的模塊度優化算法。

3.3.3 譜分析方法

圖譜分析關注的是圖的屬性，如其特征多項式、特征值和與鄰接矩陣或拉普拉斯矩陣相關的特征向量。首先考慮采用譜分析方法來計算圖切割的是Donath和Hoffman[144]，也是他們首先采用圖的鄰接矩陣特征向量來發現社團的。此后，用于計算和分割圖的譜分析方法越來越受到關注[145-147]。例如Zhou等[146]計算了含有任意度和社團結構的隨機網絡的譜特征。桂春等[148]在Ahn方法[149]的基礎上提出了邊圖譜分析算法，并應用到邊社團發現上，進行了兼顧層次性和重疊性的社團檢測研究，實驗結果表明該算法實現了網絡的重疊社團檢測并且社團劃分結果比較滿意。

3.3.4 基于粒子競爭機制的算法

粒子競爭模型的演化與眾多自然和社會現象進化過程非常類似，例如資源競爭、動物領地爭奪、競選活動等。Quiles等[150]將此演化過程引入到社團檢測問題中，通過研究網絡環境下多個粒子的競爭機制來識別社團。由于競爭效應，粒子要么處于活躍狀態，要么處于沉寂狀態。每當粒子處于活躍狀態時，它會同時受到兩種相互正交的游走規則的引導，這兩種規則分別為隨機游走和優先游走。隨機游走是一種無條件規則，它只依賴于網絡拓撲結構，控制粒子在網絡中的探索行為；相反，優先游走是粒子通過強化它們已經占領的節點來完成粒子的防御行為。這些粒子以占領新節點為目標在網絡中自主運動(隨機的或確定的方式)，同時也試圖守衛它們已占領的領地。至此，定義一個轉移矩陣用來控制粒子游走到下一個狀態的概率分布：

(8)

隨后，Silva等[151-152]在粒子競爭過程中考慮了隨機非線性動力學機制，提出了形式化的數學表達式，并在手寫數字和字母聚類數據集(USPS、MNIST、LR)上進行了測試，達到了非常好的效果，具體見表3，平均排名第一。關于網絡中重疊節點或結構的檢測，文獻[153]利用重疊度進行了分析，他們通過粒子競爭過程中產生的控制水平矩陣對重疊度進行了重新定義，并在扎卡里空手道俱樂部網絡、海豚社交網絡和《悲慘世界》的人物關系網絡進行了計算，所得結果比傳統方法更準確。

表3 多種算法的數據聚類結果比較

3.3.5 變色龍算法

變色龍算法常用于數據聚類問題[159]。它是一種層次聚類算法，其在識別相似社團時采用了互連性和近似性特征。網絡完成構建之后，變色龍方法通過最小化邊割將網絡劃分為多個社團來發現網絡的初始分區。在找到子群之后，該算法通過使用社團相似性度量準則(社團間的相對互連度(RI)和相對近似度(RC))來重復組合這些子群。這兩個指數定義如下：

相對互聯度:

(9)

相對近似度：

(10)

最終，變色龍算法將高RI和RC值的社團對進行合并。也就是說，它選擇連接性強的而且緊密結合的社團。該算法非常適合用于大數據樣本的計算，但在高維數據上，表現不盡人意[160]。

3.3.6 基于群體動力學的算法

群體行為是由大量簡單的個體通過互相作用呈現出宏觀復雜的組織系統[161-162]。目前，群體行為技術已經被成功用于解決各種優化問題[163]，如De Oliveira等[164-165]將群體動力學模型引入到網絡中的社團檢測研究。社團檢測算法的思路分為兩個步驟：1) 將數據樣本轉為化網絡形式;2) 在構建的網絡上檢測集群或社團。計算時，最初將整個網絡視為一個大社團，然后逐步分解為小社團，直到每個節點對應一個社團。迭代過程中，關鍵的因素是更新規則，在該算法中節點按照圓形組織，給定初始隨機角度θi(t=0)，節點角度的更新規則按以下公式來定義：

(11)

式中：N(vi)為節點vi的鄰居節點集，ηi(t)為vi在時間步t的移動速率，Aij為鄰居vj對鄰居vi的影響權重。

由于該算法具有層次性結構，因此可以使用樹狀圖來描述計算結果。例如，Oliveira[166]利用此算法在海豚社會網絡上進行了仿真計算，所得結果如圖4所示，圖中節點的虛實表示它原有所屬社團。

圖4 文獻[59]中的海豚社會網絡社團檢測結果

3.3.7 同步方法

近年來，物理學家越來越關注復雜系統多樣性的動力學特性，一些學者也進行了大量的耦合振蕩器的實證分析[166-167]。實際上，這些系統內單元同步的涌現與單元之間交互的拓撲結構密切相關，隨著時間的演化，這些動力學模型呈現出不同的模式，而這些模式與復雜網絡中社團的層級組織有著內在的聯系。理解同步現象最成功的嘗試之一來自Kuramoto[168]，他提出的相位振蕩器耦合模型非常適合用來仿真各類同步模式。

網絡環境下，每個節點都可以看作是一個振蕩器，連邊權重則表示不同振蕩器之間的耦合強度。有些文獻已經發現高度相互關聯的振蕩器集合更容易與那些稀疏連接的振蕩器同步[168-171]。因此，對于具有重要連接模式的復雜網絡，從隨機初始條件開始，那些形成局部社團的高度互連的單元將首先同步。隨后，越來越大的網絡結構采用同樣的形式繼續演化，直至達到最終狀態。此狀態下，所有的節點都具有相同的相變過程，只要有明確的社團結構存在，該過程會在某個時間尺度上產生。因此，擁有全局吸引子的動力學過程揭示了不同的拓撲結構，而且這些拓撲結構可能表示的就是網絡社團。在Kuramoto模型的基礎上，Wu等[171]將一種無連邊節點的負耦合作用考慮在內，建立了同步過程的動力學演化模型，即：

Aij)sin(θj-θi)

(12)

式中：V表示網絡的節點數目；ωi表示第i個節點的固有頻率；Aij表示節點之間的耦合關系；θi和θj分別表示節點i和j的相位；Kp和Kn分別表示正負耦合強度。

3.4 半監督學習方法

在諸如視頻識別、聲音信號分類、文本分類、醫療診斷以及其他應用領域中，很容易找到海量的無類標簽的樣例，但需要使用特殊設備或經過昂貴且用時非常長的實驗過程進行人工標記才能得到有類標簽的樣本，由此產生了極少量的有類標簽的樣本和過剩的無類標簽的樣例，也就產生了半監督學習[172]。而在基于網絡的方法中，網絡的拓撲結構是將標簽從已標簽節點向未標簽節點傳播的主要引擎。近年來，關于用復雜網絡理論來研究半監督學習取得了重要進展，將這些方法進行分類，主要包括最小割算法[173]、局部和全局一致性算法[174]、局部和全局正則化[175]、半監督模塊化[176]、判別式游走[177]、隨機游走[178-179]和標簽傳播技術[180-181]等。

3.4.1 最大流與最小割算法

最大流和最小割算法最初用在二分類問題中[182]。半監督學習的分類方法可以看作是一個圖分割問題。在二分類問題中，正標簽被看作是源點，負標簽被看作是匯點。算法的目標是找到一個最小邊的集合來阻斷從源點到匯點的流量。被分割后的圖中，連接源樣本點的將會被分類為正樣本，而連接匯點的樣本將會被分類為負樣本。因此，損失函數可以寫為：

(13)

最大流與最小割算法有很多有趣的特性[183]，可以采用網絡流工具進行多項式的時間計算，學習過程也可以被視為馬爾可夫隨機場過程。或許，該算法也存在一些缺陷，如它是不存在置信區間的硬分類問題。為解決此問題，文獻[184]引入了基于譜劃分的方法，可以在圖中產生近似的最小割比率。

3.4.2 高斯隨機場與調和函數

為解決最小割算法的硬分類問題，有學者提出了高斯隨機場與調和函數方法[173,181]。該方法被視作是最近鄰方法的一種變種形式，其中最近鄰的標注樣本在圖上用隨機行走的方式計算。另外，調和函數根據鄰近節點標簽的加權平均數來估計未標注節點的標簽。同樣，它可以看作是一個平方損失函數，已標記的數據樣本標簽是固定的，然后加上一個拉普拉斯正則項。因此，損失函數可表示為：

(14)

3.4.3 局部全局一致性學習

局部全局一致性學習算法是基于網絡的半監督學習技術中最早的方法之一[174]。該算法通過構造標記樣本與未標記樣本結構的足夠平滑的分類函數來進行學習。損失函數定義如下：

(15)

近年來，國內的研究人員也對局部全局一致性學習算法進行了研究。針對文獻[174]提出的算法分類精度在很大程度上取決于控制參數的合理設置問題，王雪松等[185]提出了一種少參數的簡潔算法；另外，在標簽傳遞過程中，他們僅將未標記樣本的標簽根據相似度傳遞給近鄰，而將已標記樣本的標簽強制回填，確保了標簽傳遞源頭的準確性。為降低計算復雜度，白本督等[186]提出一種K-均值構圖法，主要將稀疏表示理論應用到基于圖的半監督學習過程中，通過稀疏分解稀疏矩陣來得到圖中鄰接矩陣和邊權重。

3.4.4 附著法

(16)

3.4.5 相互作用力算法

受自然界中物體之間存在吸引力的啟發，Cupertino等[189]提出相互作用力算法來進行網絡的半監督學習。它將數據樣本模型化為一個P維空間上的節點，并根據施加在它之上的合力執行相應的運動。已標注數據樣本充當吸引點，而未標注樣本獲得吸力并朝這些吸引點移動。一旦一個未標注樣本足夠接近已標注樣本，比如說半徑，那么吸引點的標簽就傳播到位于其周圍的未標注樣本上。同時，未標注樣本從標注節點接收標簽，然后成為新的吸引點。通過反復迭代，所有的數據樣本都會收斂到某個吸引點，完成標簽的傳播過程。

3.4.6 判別式游走算法

判別式游走(D-Walks)算法在文獻[177]中有詳細介紹。從本質上看，D-Walks算法依賴于網絡上的隨機游走過程，該過程可以被看作是馬爾可夫鏈，網絡中的每個節點對應于馬爾可夫鏈的一個狀態。另外，D-Walks算法需要計算節點介數，未標注節點被分配到介數最高的類別。介數的大小可以按下式計算得到：

(17)

3.4.7 隨機競爭-合作學習

(18)

式中：i和j表示網絡中的節點，vk表示粒子k的父節點。

隨后，Wu等[192]又將該算法應用于錯誤標簽傳播的預防上。眾所周知，真實世界中，由于儀器誤差或人為標注的失誤，錯誤標注樣本在數據集中常見。如果這些錯誤標簽被用來進一步分類新數據(有監督學習)或傳播到未標記樣本(半監督學習)，可能會產生嚴重后果。通過模擬計算，該算法在真實數據集上的表現優于線性傳播算法(LP)[193]和線性鄰域傳播算法(LNP)[194]。

4 基于機器學習的復雜網絡信息挖掘

如前所述，對于復雜網絡，我們主要關注的是其統計特征、拓撲結構及關鍵節點和連邊。隨著數據量的急速增加，網絡變得越來越大，單純地網絡分析方法已經難以滿足網絡信息快速挖掘的需要。這促使部分學者開始從事計算機技術用于分析復雜網絡的研究，特別是近年來人工智能技術的快速進步，給機器學習和復雜網絡的交叉應用提供了思路。如在社會網絡、生物網絡等領域，已有研究人員利用機器學習算法進行了網絡信息挖掘的嘗試。

4.1 網絡統計特征提取

在神經科學領域，大腦網絡中神經元(可看作為網絡節點)之間是否存在同步特征通常由腦電圖(EGG)和腦磁圖(MEG)記錄的時間序列來評估。為區分正常人與阿爾茨海默癥患者，Roberto H等[32]建立了機器學習分類模型，并且考慮了五種特征選擇方法，即近似熵、樣本熵、多尺度熵、自動互信息和Lempel-Ziv復雜度，通過在EGG和MEG數據上進行測試，前兩種方法獲得了非常好的分類結果，特別是樣本熵方法能有效地減少對信號長度的依賴。另外，大腦網絡中不同區域的功能連通性也是研究熱點，傳統的網絡同步度量方法仍存在檢驗盲點[195]。Zhang等[196]基于靜態的和視頻刺激下動態的fMRI(功能性磁共振成像)數據得到的大規模功能性連接模式進行了分類試驗，并且在連通性測量時考慮了Pearson相關系數、偏相關系數、互信息和小波變換相干性四種指標，結果表明小波變換相干性度量標準在分類任務中性能最優。

在對網絡進行二值化時，一般根據連邊權重的相關規則來修剪圖，如刪除權重低于給定閾值的連邊，這類閾值的確定相當困難，或許，機器學習的方法可以優化此過程。Massimiliano Z等[197]提出了利用機器學習分類模型來選擇閾值的方法，并將獲得的分類結果作為二值化網絡的閾值，或許，該方法只能解決單閾值問題。而對于多閾值問題，Jie等[198]提出了一個基于功能性連接網絡的分類框架，主要應用多個閾值來對不同級別的區域進行編碼，隨后利用基于圖核的遞歸特征消除方法選擇最相關特征，以及利用支持向量機算法建立分類模型，在識別正常人與阿爾茨海默癥患者時分類準確率可達91.9%。

4.2 網絡拓撲結構分類

自閉癥癥狀的早期篩查有助于及時發現患者，通常的做法是進行正常人和疑似病例的大腦功能性連接模式對比。文獻[199]基于Granger因果關系的腦連通性數據，運用支持向量機和Fisher準則進行了連接模式的分類，并對由鄰接矩陣構成的各類特征進行排序，進而確定使網絡分割函數達到最大值時的最佳子集，計算結果表明，基于鄰接矩陣和圖論方法的組合分類模型可以達到87.5%的準確度。Matthew D S等[200]在進行抑郁患者與正常人的分類模型構建時，采用了一種新的特征評估方法，即運用迭代分類器的分類性能來評估所選特征的魯棒性。另外，文獻[198]進行分類模型構建時采用的是多核SVM算法，認為網絡拓撲特征的提取和連邊權重閾值的選擇可以同時進行。

4.3 網絡關鍵節點和關鍵邊識別

在分析大腦網絡映射功能時，通常采用模式識別方法檢測多體素模式，為解決維數多的問題，Federico D M等[201]采用基于多特征選擇的機器學習算法(遞歸特征消除算法RFE)進行功能性成像數據分類任務，即通過支持向量機算法遞歸地消除不相關的體素來識別關鍵節點。Rodolphe J等[202]提出使用正則化樹來進行fMRI數據節點選擇的方法，該方法基于先前選擇的樹節點中的變量構造的函數來懲罰當前的節點，這使得整個預測結果變得更加魯棒和精確。在生物信息學領域，一個核心任務是根據基因表示譜推斷出基因調控網絡，一般來說，該方法面臨的主要問題是樣本少而維數大。為解決此問題，通常利用訓練數據之外的先驗知識(網絡拓撲結構)來獲得統計規律，Fabricio M L等[203]將基因調控網絡的無標度特性加入到一個經典的特征選擇方法中，稱為序列浮動前向選擇算法(SFFS)，它從完整的網絡開始，并根據目標函數(自頂向下方法)消除最少相關的節點，重復這個過程直到滿足停止條件為止。

在社會網絡分析領域，節點排序是一個核心任務。根據復雜程度的不同，節點重要程度度量分為局部度量和全局度量。Jeh等[204]提出了一種估計兩個節點相似度的度量標準，主要通過隨機游走計算這兩個節點到它們所連接的相似節點的度數。除了靜態圖上的節點排序，一些學者[205]還研究了動態圖上的節點排序，考慮了利用諸如電子郵件等事件的時間信息來追蹤節點隨新事件發生的排序變化情況。

一旦網絡形成，就可能面臨選擇代表網絡結構的連邊子圖問題，因此，通過過濾無關的連邊來選擇關鍵信息的方法對于獲得簡單的相關子圖是必要的。從數據挖掘的角度來看，目前主要采用的方法為互信息。代表性的方法是由Adam A[206]提出的ARACNE算法，主要用于檢測和刪除網絡中的非直接連邊，算法核心是在給定互信息閾值的情況下，通過分析網絡中每組三節點連邊，迭代刪除低于閾值的連邊。另外一種方法是利用玻爾茲曼熵最大化原理，由Lezon T R等[207]提出，其主要思想是以最小程度依賴于缺失信息的形式來完成統計學習。

4.4 網絡節點分類

在具有連邊的節點分類問題中，連邊的屬性與結構有助于節點分類任務。Lu等[208]對每個數據樣本增加新的屬性，使其能夠處理基于鏈接的節點分類問題，擴展了機器學習分類器的應用范圍。Bhagat等[209]基于局部和全局的鏈接結構相似性算法對博客進行標注，完成分類任務。Sen等[210]研究了網絡數據樣本的集體分類方法，比較了四種常用的推理算法在模擬數據和現實數據上的分類性能。Backstrom等[211]通過分析社團進化過程來刻畫網絡中個體位置的結構特征，并成功用于節點的分類中。

5 重點關注的兩類問題

綜上所述，復雜網絡與機器學習有相似的目標，給定一些數據，通常表示一個復雜系統，目的是從其挖掘一些信息，并創建一個新的知識表征(拓撲結構或者機器學習模型)。目前，復雜網絡與機器學習交叉應用的可能方向主要體現在社團檢測與聚類、鏈路預測和語義表征等。

5.1 聚類與社團檢測

機器學習中的聚類與復雜網絡分析中的社團檢測是兩個具有較多相似性特征的問題。大多數聚類算法僅利用樣本間相似性(距離)的局部信息，而復雜網絡方法允許網絡的全局拓撲結構包含在算法當中，因此計算結果更加準確。如圖5所示，左側的聚類任務中，雖然節點A與節點B更相似，同屬于一個類別，卻劃分到其他類別中；而對于右側的社團檢測任務，雖然節點A更接近三角形社團，但因其與節點B有連邊存在，所以社團劃分合理。

圖5 聚類與社團檢測問題的對比[212]

可以看出，在聚類任務中引入復雜網絡理論能有效地提高計算準確度。目前來看，該方法在不同研究領域都有所應用。在網絡音樂領域，Joan S等[213]采用社團檢測算法檢測同一首歌曲的覆蓋類別和范圍，其結果由于傳統聚類算法。經濟物理學中，在金融市場交易的投資者集群被確定為統計校準網絡中的社團[214]。或許，某些情況下聚類算法也可以用于進行復雜網絡中的社團檢測，例如復雜網絡中重疊社團結構識別的模糊c-均值聚類算法[215]、社團檢測的自適應聚類算法[216]、重疊和非重疊社團結構識別的模糊聚類算法[217]。

5.2 鏈路預測

鏈路預測已經成為復雜網絡中一個重要的研究方向，特別是在生物網絡和社會網絡。同樣在數據挖掘領域，推薦系統與之對應，也是計算機技術中的主要研究方向之一，研究思路和方法基于馬爾可夫鏈和機器學習。盡管它們在實質上是等價的，但仍舊是在不同的研究路徑上前行，僅有個別的研究人員在聯合方向上進行了嘗試。

6 結 語

眾所周知，現實世界中，幾乎所有的系統都可以采用網絡的方式來描述，復雜網絡就是以網絡的視角去分析這些數據，找出可被解釋的結果或者現象，相當于挖掘隱藏在數據背后的規則；對于機器學習，我們主要研究如何使計算機從給定的數據中學習規律或模型，并利用學到的模型進行預測。從本質上來說，復雜網絡和機器學習的目標是一致的，都是為了挖掘數據內在的規律，兩者的融合將有更多突破。

可以看出，融合復雜網絡理論和機器學習技術已經是眾多學者開始著手研究的領域。隨著諸如大數據、人工智能等技術的出現，要想讓它們發揮更大的作用，需要在理論層次和技術層次上更進一步創新。我們總結了在該交叉領域未來可能成為研究熱點的幾大問題，希望在不久的將來，這些問題能夠得到完美解決。

首先，從有益于促進復雜網絡研究效率的角度看：

(1) 優化復雜網絡統計度量指標。隨著大數據時代的到來，數據集越來越大，如大型在線社交網絡，對網絡的度量變得越來越復雜，尤其是從計算成本的角度來看，耗時耗力。如果按照這種趨勢發展，復雜網絡的各類度量指標將不得不依靠機器學習技術進行重新優化設計，在具體設計時應特別關注其計算成本，以確保其可擴展到數億的節點。

(2) 開發用于復雜網絡分析的軟件平臺。數據的規模性和復雜性將迫使研究人員需要設計開發新的軟件工具和機器學習模型來管理和分析這些數據集。雖然在這個方向上已經采取了一些措施，例如創建圖形數據庫等，但是大多數解決方案僅限于可視化的思路，忽略了真實世界網絡的復雜性。

另外，從有益于強化機器學習理論背景的角度看：

(1) 提升機器學習算法準確度。如實際應用中，通常樣本特征的提取過于簡單、解釋性差，使用復雜網絡理論去挖掘潛在的可被解釋的規律，再融合群體智慧知識，然后構建相關數據特征，按照這樣的思路去解決機器學習任務視為最優路徑。

(2) 擴展機器學習模型數學理論。由于大量缺乏標注樣本，或者人工標注成本過高，我們越來越依賴半監督學習技術，但是半監督技術理論的不完善限制了其廣泛應用。或許，從復雜網絡領域可以尋找可能，如利用復雜網絡上的流行病擴散動力學過程來完成半監督學習中數據標簽的傳播。