李澤荃 楊 曌 劉 嶸 李 靖

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

0 引 言

復(fù)雜網(wǎng)絡(luò)和機(jī)器學(xué)習(xí)分別是統(tǒng)計(jì)物理學(xué)和計(jì)算機(jī)科學(xué)領(lǐng)域內(nèi)重要的研究方向。復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜系統(tǒng)的一種角度和方法，它主要關(guān)注系統(tǒng)中個(gè)體相互作用的拓?fù)浣Y(jié)構(gòu)，以及網(wǎng)絡(luò)上物質(zhì)、能量、信息的動(dòng)力學(xué)傳播過程，是理解復(fù)雜系統(tǒng)性質(zhì)和功能的基礎(chǔ)[1]。機(jī)器學(xué)習(xí)主要指計(jì)算機(jī)利用已有的經(jīng)驗(yàn)來(lái)獲得學(xué)習(xí)能力的一種計(jì)算方法，通過從大量的數(shù)據(jù)特征中獲得數(shù)據(jù)的表示方法，以自動(dòng)的方式模擬人類專家的判斷[2]。

近年來(lái)，將復(fù)雜網(wǎng)絡(luò)和機(jī)器學(xué)習(xí)結(jié)合起來(lái)進(jìn)行研究分析引起了越來(lái)越多學(xué)者的關(guān)注。從本質(zhì)上說，主要包括兩個(gè)方向：一是研究基于復(fù)雜網(wǎng)絡(luò)理論(或圖論)的機(jī)器學(xué)習(xí)技術(shù)；二是利用機(jī)器學(xué)習(xí)算法來(lái)挖掘復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)背后隱藏的信息和知識(shí)。對(duì)于前者，自然界中以網(wǎng)絡(luò)形態(tài)存在的數(shù)據(jù)無(wú)處不在，利用網(wǎng)絡(luò)方式進(jìn)行數(shù)據(jù)表示有其內(nèi)在的優(yōu)點(diǎn)，它能有效地捕獲數(shù)據(jù)的空間、拓?fù)浜凸δ荜P(guān)系，獲得更高的機(jī)器學(xué)習(xí)算法準(zhǔn)確度；而對(duì)于后者，人類社會(huì)的進(jìn)步促使各類系統(tǒng)越來(lái)越復(fù)雜，相對(duì)應(yīng)網(wǎng)絡(luò)的規(guī)模急劇增大，借助智能數(shù)據(jù)分析工具，如各類機(jī)器學(xué)習(xí)算法，有助于解決復(fù)雜網(wǎng)絡(luò)中模型與知識(shí)的有效挖掘問題。

到目前為止，人們根據(jù)所研究的具體問題，提出了多種多樣的基于網(wǎng)絡(luò)的機(jī)器學(xué)習(xí)方法或復(fù)雜網(wǎng)絡(luò)分析工具，并做了一些總結(jié)和探討[3]，但仍不夠全面。關(guān)于復(fù)雜網(wǎng)絡(luò)與機(jī)器學(xué)習(xí)融合的研究圖景，未來(lái)將有更多可能。

1 復(fù)雜網(wǎng)絡(luò)簡(jiǎn)介

在自然界中，從技術(shù)到生物直至社會(huì)各類系統(tǒng)都可以通過復(fù)雜網(wǎng)絡(luò)加以描述，其中節(jié)點(diǎn)表示個(gè)體或組織，邊表示它們之間的關(guān)系[4-7]。對(duì)真實(shí)網(wǎng)絡(luò)進(jìn)行實(shí)證研究不僅有助于認(rèn)識(shí)網(wǎng)絡(luò)行為、改善網(wǎng)絡(luò)性能和有效地管理網(wǎng)絡(luò)，而且能夠先于理論發(fā)現(xiàn)現(xiàn)象，為進(jìn)行理論探索打下基礎(chǔ)，或者作為理論應(yīng)用范圍的重要判據(jù)[7]。為了更好地利用復(fù)雜網(wǎng)絡(luò)，我們對(duì)其數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性和節(jié)點(diǎn)及其相關(guān)連接的多樣性進(jìn)行了統(tǒng)一。

1.1 網(wǎng)絡(luò)演化模型

為了研究真實(shí)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，學(xué)者們提出了許多網(wǎng)絡(luò)模型，其中有一些網(wǎng)絡(luò)模型由于其廣泛的應(yīng)用價(jià)值而得到了重點(diǎn)關(guān)注，例如隨機(jī)網(wǎng)絡(luò)[8]、小世界網(wǎng)絡(luò)[9]、隨機(jī)聚類網(wǎng)絡(luò)[10]、無(wú)標(biāo)度網(wǎng)絡(luò)[11]和核心-邊緣網(wǎng)絡(luò)[12]。

1.1.1 隨機(jī)網(wǎng)絡(luò)

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

(1)

其他更多特性可參考文獻(xiàn)[13-15]。

1.1.2 小世界網(wǎng)絡(luò)

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

圖1 WS小世界重連邊模型

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

1.1.3 無(wú)標(biāo)度網(wǎng)絡(luò)

1998年，Barabási和Albert[11]發(fā)現(xiàn)某些網(wǎng)絡(luò)中的極少數(shù)節(jié)點(diǎn)擁有很高的度值，而大部分節(jié)點(diǎn)只有很小的度值，即極少數(shù)節(jié)點(diǎn)與非常多的節(jié)點(diǎn)連接，而大部分節(jié)點(diǎn)只和很少的節(jié)點(diǎn)連接?；谶@一發(fā)現(xiàn)，1999年他們提出了一種新的網(wǎng)絡(luò)模型，即無(wú)標(biāo)度網(wǎng)絡(luò)，網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布服從冪律分布。無(wú)標(biāo)度網(wǎng)絡(luò)結(jié)構(gòu)中關(guān)鍵節(jié)點(diǎn)或度數(shù)較大的節(jié)點(diǎn)更容易與新節(jié)點(diǎn)相連，從而形成更多的連接，新節(jié)點(diǎn)也有與度值更高節(jié)點(diǎn)相連接的“偏好”。

網(wǎng)絡(luò)的無(wú)標(biāo)度性與網(wǎng)絡(luò)受到攻擊的魯棒性緊密相關(guān)，這種層次結(jié)構(gòu)具有一定的容錯(cuò)能力。關(guān)于無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)隨機(jī)攻擊具有很強(qiáng)的魯棒性而對(duì)蓄意攻擊極為脆弱的特點(diǎn)，Cohen等[17-18]和Callaway等[19]利用滲流理論對(duì)其進(jìn)行了詳細(xì)研究。

1.1.4 隨機(jī)聚類網(wǎng)絡(luò)

一些現(xiàn)實(shí)世界的網(wǎng)絡(luò)如社會(huì)網(wǎng)絡(luò)和生物網(wǎng)絡(luò)呈現(xiàn)出模塊化的結(jié)構(gòu)特性，文獻(xiàn)[10]把它們稱為社團(tuán)，屬于同一個(gè)社團(tuán)的節(jié)點(diǎn)有許多相互連接的邊，而不同的社團(tuán)間的連接相對(duì)較少，這類網(wǎng)絡(luò)被稱為隨機(jī)聚類網(wǎng)絡(luò)。

在隨機(jī)聚類網(wǎng)絡(luò)的形成過程中，兩個(gè)節(jié)點(diǎn)如果屬于同一個(gè)社團(tuán)，它們連接的概率為pin，如果屬于不同的社團(tuán)則連接的概率為pout。典型的隨機(jī)聚類網(wǎng)絡(luò)中，pin值較大，pout值較小，即社團(tuán)之內(nèi)的節(jié)點(diǎn)連接緊密，而社團(tuán)之間的節(jié)點(diǎn)連接稀疏。當(dāng)pin值較小，而pout值較大時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)的聚類效果不顯著?；谝陨蠀?shù)，定義Zin/和Zout/分別為社團(tuán)內(nèi)節(jié)點(diǎn)和社團(tuán)間節(jié)點(diǎn)的連接程度。或許，隨著Zout/值的增大，社團(tuán)間的連接逐漸緊密，社團(tuán)之間的界限也將越來(lái)越模糊。

1.1.5 核心-邊緣網(wǎng)絡(luò)

核心-邊緣網(wǎng)絡(luò)結(jié)構(gòu)最早出現(xiàn)在社會(huì)學(xué)[20-21]、國(guó)際關(guān)系學(xué)[22-23]和經(jīng)濟(jì)學(xué)[24]等學(xué)科中。一般認(rèn)為網(wǎng)絡(luò)中的核心節(jié)點(diǎn)是具有很大度數(shù)的節(jié)點(diǎn)，識(shí)別核心-邊緣結(jié)構(gòu)最常用的定量方法是由博爾加蒂和埃弗雷特于1999年提出的[12]，按照該方法，對(duì)某一網(wǎng)絡(luò)進(jìn)行聚類分析時(shí)，對(duì)于其中的關(guān)鍵節(jié)點(diǎn)，采用不同的社團(tuán)檢測(cè)算法可能使它們分配到不同的社團(tuán)[25]。因此，如何判斷它們與不同社團(tuán)之間關(guān)系的強(qiáng)弱至關(guān)重要，可以采用社團(tuán)重疊算法[26]。在這種情況下，一般意義上的社團(tuán)概念可能并不能很好地實(shí)現(xiàn)對(duì)中等尺度網(wǎng)絡(luò)實(shí)際結(jié)構(gòu)的理解，將關(guān)鍵節(jié)點(diǎn)劃分為核心結(jié)構(gòu)來(lái)考慮可能更為合理[27]?？梢詫蝹€(gè)社團(tuán)看作網(wǎng)絡(luò)核心結(jié)構(gòu)的一部分，整個(gè)核心結(jié)構(gòu)由多個(gè)社團(tuán)組成，社團(tuán)之間可以存在重疊[28-29]。

1.2 網(wǎng)絡(luò)度量方法分類

根據(jù)復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性，如度、度的相關(guān)性、距離和路徑、網(wǎng)絡(luò)結(jié)構(gòu)以及網(wǎng)絡(luò)中心性等，眾多學(xué)者已經(jīng)提出了許多網(wǎng)絡(luò)相關(guān)統(tǒng)計(jì)描述計(jì)算方法。按照在計(jì)算中使用信息的類型，可以將其分為三類：

1) 局部算法：僅僅根據(jù)節(jié)點(diǎn)自身的信息來(lái)進(jìn)行計(jì)算。

2) 混合算法：除了根據(jù)節(jié)點(diǎn)信息外，還利用其直接和間接鄰域內(nèi)節(jié)點(diǎn)的拓?fù)湫畔⑦M(jìn)行計(jì)算。這些信息可以是最簡(jiǎn)單的局部拓?fù)?，如鄰域中的三角形?shù)，也可以是網(wǎng)絡(luò)的全局信息，如最遠(yuǎn)兩個(gè)節(jié)點(diǎn)之間的最短路徑等。

3) 全局算法：根據(jù)整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行計(jì)算。

圖2描繪了這三類網(wǎng)絡(luò)統(tǒng)計(jì)度量方法相互關(guān)系的示意圖，表1列出了常用的各類網(wǎng)絡(luò)統(tǒng)計(jì)描述。

圖2 網(wǎng)絡(luò)統(tǒng)計(jì)度量方法分類

表1 復(fù)雜網(wǎng)絡(luò)常用的統(tǒng)計(jì)描述

1.3 復(fù)雜網(wǎng)絡(luò)的動(dòng)力學(xué)過程

1.3.1 隨機(jī)游走

隨機(jī)游走是一系列由連續(xù)隨機(jī)步組成的軌跡的數(shù)學(xué)表示[30]。它常被用來(lái)描述很多自然現(xiàn)象和工程問題，如圖形匹配和模式識(shí)別[31]、圖像分割[32]，神經(jīng)網(wǎng)絡(luò)模型[33-34]、網(wǎng)絡(luò)中心性度量[35]、網(wǎng)絡(luò)劃分[36]、通信網(wǎng)絡(luò)構(gòu)建與分析[37-38]等。

給定一個(gè)網(wǎng)絡(luò)G=和一個(gè)起始節(jié)點(diǎn)v∈V，隨機(jī)選擇一個(gè)鄰居節(jié)點(diǎn)，移動(dòng)到該鄰居；然后，再次隨機(jī)選擇這個(gè)新節(jié)點(diǎn)的鄰居并移動(dòng)，以此類推，以這種方式選擇節(jié)點(diǎn)的隨機(jī)序列就是網(wǎng)絡(luò)上的隨機(jī)游走過程。如果網(wǎng)絡(luò)是加權(quán)網(wǎng)絡(luò)，可以與連邊權(quán)重Avu成正比的概率過渡到鄰居u。

本質(zhì)上，網(wǎng)絡(luò)上的隨機(jī)游走和有限離散馬爾可夫鏈的原理基本是相通的，所以網(wǎng)絡(luò)上的任意一個(gè)離散馬爾可夫鏈都可以被認(rèn)為是一個(gè)隨機(jī)游走過程。眾所周知，離散馬爾可夫鏈?zhǔn)请S機(jī)過程，其未來(lái)狀態(tài)在條件上獨(dú)立于過去的狀態(tài)，因此只要知道當(dāng)前狀態(tài)即可求得未來(lái)狀態(tài)。在圖論中，圖的節(jié)點(diǎn)可以表示狀態(tài)，因此，步行者從節(jié)點(diǎn)v移動(dòng)到其鄰居節(jié)點(diǎn)的概率獨(dú)立于步行者的過去軌跡。

1.3.2 惰性隨機(jī)游走

平穩(wěn)分布只適用于非周期網(wǎng)絡(luò)，如果網(wǎng)絡(luò)具有周期性，就需要引入惰性隨機(jī)游走算法。惰性隨機(jī)游走算法可以被看作是網(wǎng)絡(luò)中經(jīng)典隨機(jī)游走算法的改進(jìn)版，僅將網(wǎng)絡(luò)G中的每個(gè)節(jié)點(diǎn)u添加自身環(huán)即可[39]。

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

(2)

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

(3)

1.3.3 自避行走

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

1.3.4 游客漫步

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

在大多數(shù)與游客漫步相關(guān)的文獻(xiàn)中，游客可以訪問記憶窗口μ以外的其他景點(diǎn)[42-44]。隨著μ值增加，游客有可能在數(shù)據(jù)集上進(jìn)行長(zhǎng)距離跳躍，因?yàn)樵跁r(shí)間范圍內(nèi)鄰居最有可能已經(jīng)被完全訪問。在分類任務(wù)上，可以采用網(wǎng)絡(luò)的方法來(lái)避免該問題，此時(shí)游客僅被允許訪問與其相連的節(jié)點(diǎn)(景點(diǎn))。或許，當(dāng)值很大時(shí)，游客很可能被困在節(jié)點(diǎn)上，而不能進(jìn)一步訪問其他鄰居節(jié)點(diǎn)。

1.3.5 流行病傳播

復(fù)雜網(wǎng)絡(luò)上的流行病傳播已經(jīng)引起了眾多研究者的關(guān)注，大家主要關(guān)心的是網(wǎng)絡(luò)結(jié)構(gòu)如何減弱或放大疾病傳播。由于流行病傳播過程可以看作是信息傳播，因此對(duì)于機(jī)器學(xué)習(xí)來(lái)說非常有用。目前主要有兩種流行病傳播模型，SIR和SIS模型[45-47]。關(guān)于其詳細(xì)綜述，請(qǐng)參閱文獻(xiàn)[48-50]。另外，對(duì)于一些復(fù)雜網(wǎng)絡(luò)上信息傳播的研究進(jìn)展，可參見文獻(xiàn)[51-58]。

2 機(jī)器學(xué)習(xí)簡(jiǎn)介

機(jī)器學(xué)習(xí)的目標(biāo)是讓計(jì)算機(jī)擁有人類的“學(xué)習(xí)”能力[59-64]。傳統(tǒng)的機(jī)器學(xué)習(xí)方法有三種類型：第一種是監(jiān)督學(xué)習(xí)，它主要利用已標(biāo)記的樣本數(shù)據(jù)進(jìn)行訓(xùn)練得到數(shù)學(xué)模型，再利用該模型對(duì)未知數(shù)據(jù)進(jìn)行預(yù)測(cè)[61,65-67]。第二種是無(wú)監(jiān)督學(xué)習(xí)，其主要任務(wù)是利用樣本的相似性或拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)和發(fā)現(xiàn)樣本的內(nèi)在聯(lián)系[63,68-69]。其中，監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)的主要區(qū)別在于監(jiān)督學(xué)習(xí)利用包含外部標(biāo)記信息的數(shù)據(jù)進(jìn)行訓(xùn)練得到函數(shù)，而無(wú)監(jiān)督學(xué)習(xí)沒有任何標(biāo)注數(shù)據(jù)，主要將某種屬性相似的樣本聚集在一起。第三種方法叫半監(jiān)督學(xué)習(xí)，它是監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)相結(jié)合的一種方法[70-72]，半監(jiān)督學(xué)習(xí)中少量的樣本數(shù)據(jù)帶有標(biāo)記，而大多數(shù)樣本數(shù)據(jù)是未標(biāo)記的，學(xué)習(xí)過程就是利用這些少量已標(biāo)記樣本對(duì)其他未標(biāo)記樣本進(jìn)行標(biāo)記和分類。圖3是機(jī)器學(xué)習(xí)的三種范式。

圖3 三種類型的機(jī)器學(xué)習(xí)方法

值得一提的是，機(jī)器學(xué)習(xí)領(lǐng)域中的新技術(shù)，即深度學(xué)習(xí)。其主要利用由多個(gè)非線性變換構(gòu)建的高階數(shù)學(xué)模型來(lái)表達(dá)樣本項(xiàng)之間的關(guān)系，通過利用高效的算法進(jìn)行分層特征提取，從面部識(shí)別等實(shí)際應(yīng)用來(lái)看，深度學(xué)習(xí)的一些方法將使機(jī)器學(xué)習(xí)任務(wù)變得更為容易。

2.1 監(jiān)督學(xué)習(xí)

僅利用具有標(biāo)記信息的樣本數(shù)據(jù)進(jìn)行訓(xùn)練和建模的算法稱為監(jiān)督學(xué)習(xí)。通常我們利用監(jiān)督學(xué)習(xí)來(lái)預(yù)測(cè)無(wú)標(biāo)簽樣本的類型標(biāo)簽，其中，對(duì)離散值進(jìn)行預(yù)測(cè)稱為“分類”，而對(duì)連續(xù)值進(jìn)行預(yù)測(cè)稱為“回歸”[59]。

監(jiān)督學(xué)習(xí)主要分為兩個(gè)階段：訓(xùn)練階段和分類階段[59,66-68]。在訓(xùn)練階段，利用帶有標(biāo)簽的樣本集合訓(xùn)練得到分類函數(shù)；在分類階段，利用上一步得到的分類函數(shù)對(duì)未標(biāo)記的測(cè)試集進(jìn)行標(biāo)記分類。關(guān)于監(jiān)督學(xué)習(xí)的詳細(xì)數(shù)學(xué)描述可參見文獻(xiàn)[59,63,68,73]。對(duì)于監(jiān)督學(xué)習(xí)的主要算法，請(qǐng)?jiān)斠娢墨I(xiàn)[74-80]。

2.2 無(wú)監(jiān)督學(xué)習(xí)

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

無(wú)監(jiān)督學(xué)習(xí)最常見的任務(wù)是樣本聚類，這些集簇可以是某種形狀、某種類型的點(diǎn)或?qū)ο蟮萚59,90-93]。隨著數(shù)據(jù)量和數(shù)據(jù)種類的指數(shù)增長(zhǎng)，提高數(shù)據(jù)的自動(dòng)理解和處理能力是重點(diǎn)，例如在數(shù)據(jù)挖掘、文獻(xiàn)檢索、圖像分割、生物分析、模式分類等任務(wù)中，通常我們僅僅掌握很少量的先驗(yàn)信息[91-92,94-96]，因此，其應(yīng)用非常廣泛。

2.3 半監(jiān)督學(xué)習(xí)

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

對(duì)于半監(jiān)督學(xué)習(xí)，數(shù)據(jù)的一致性假設(shè)是前提[99]。通常情況下，半監(jiān)督學(xué)習(xí)中存在一個(gè)或多個(gè)基本假設(shè)，包括聚類假設(shè)、平滑假設(shè)和流形假設(shè)[70]。

一般情況下，可將半監(jiān)督學(xué)習(xí)算法歸納為四類，即生成模型[70,72,89,100-101]、聚類和標(biāo)記模型[102-103]、低密度區(qū)域分離模型[70,72,89,104-105]和基于網(wǎng)絡(luò)(圖)的模型[80,90-92]。

3 基于復(fù)雜網(wǎng)絡(luò)的機(jī)器學(xué)習(xí)方法

在過去的幾年里，基于復(fù)雜網(wǎng)絡(luò)的機(jī)器學(xué)習(xí)方法越來(lái)越受到關(guān)注。該方法有其內(nèi)在的優(yōu)點(diǎn)，即數(shù)據(jù)通過網(wǎng)絡(luò)的形式來(lái)表征能有效捕獲數(shù)據(jù)的空間結(jié)構(gòu)、拓?fù)浣Y(jié)構(gòu)和功能關(guān)系。該類型的數(shù)據(jù)通常以網(wǎng)絡(luò)形式表示，其中一部分節(jié)點(diǎn)被標(biāo)記，另外一些節(jié)點(diǎn)未被標(biāo)記，算法的任務(wù)是預(yù)測(cè)未標(biāo)記節(jié)點(diǎn)的標(biāo)簽。同樣，按照機(jī)器學(xué)習(xí)的分類，下面重點(diǎn)討論基于網(wǎng)絡(luò)的監(jiān)督學(xué)習(xí)、無(wú)監(jiān)督學(xué)習(xí)和半監(jiān)督學(xué)習(xí)技術(shù)。

3.1 網(wǎng)絡(luò)構(gòu)建技術(shù)

在機(jī)器學(xué)習(xí)的很多領(lǐng)域，數(shù)據(jù)樣本點(diǎn)之間的局部關(guān)系以及由局部信息衍生出的全局結(jié)構(gòu)經(jīng)常用網(wǎng)絡(luò)來(lái)表示。在處理機(jī)器學(xué)習(xí)或者數(shù)據(jù)挖掘的問題時(shí)，網(wǎng)絡(luò)構(gòu)建是一個(gè)非常有必要的步驟。當(dāng)應(yīng)用基于網(wǎng)絡(luò)的機(jī)器學(xué)習(xí)方法分析向量表示的數(shù)據(jù)樣本時(shí)，該步驟變得尤為關(guān)鍵，需要采用網(wǎng)絡(luò)構(gòu)建技術(shù)將輸入樣本集形成網(wǎng)絡(luò)。一般來(lái)說，按照網(wǎng)絡(luò)構(gòu)建過程中的信息類型將網(wǎng)絡(luò)構(gòu)建方法分為三類，即局部信息方法、遠(yuǎn)程信息方法和全局信息方法，詳細(xì)情況見表2。

表2 網(wǎng)絡(luò)構(gòu)建技術(shù)分類

3.2 監(jiān)督學(xué)習(xí)方法

對(duì)于網(wǎng)絡(luò)環(huán)境下的監(jiān)督學(xué)習(xí)分類問題，通常利用外部信息(如標(biāo)簽)來(lái)訓(xùn)練模型。與一般的監(jiān)督學(xué)習(xí)類似，學(xué)習(xí)過程通常分為兩個(gè)階段：訓(xùn)練階段和預(yù)測(cè)階段。訓(xùn)練階段，模型根據(jù)帶標(biāo)簽數(shù)據(jù)樣本進(jìn)行學(xué)習(xí)；預(yù)測(cè)階段，利用模型對(duì)未知數(shù)據(jù)樣本進(jìn)行預(yù)測(cè)?；诰W(wǎng)絡(luò)的監(jiān)督學(xué)習(xí)算法仍然研究的不多，主要有關(guān)聯(lián)圖分類算法、關(guān)系分類算法和啟發(fā)式分類算法。

3.2.1 關(guān)聯(lián)圖分類算法

關(guān)聯(lián)圖分類算法中，應(yīng)用最多的是k-關(guān)聯(lián)圖算法[114]。k-關(guān)聯(lián)圖分類算法同樣也是將訓(xùn)練集數(shù)據(jù)構(gòu)建為網(wǎng)絡(luò)，即有向k-關(guān)聯(lián)圖網(wǎng)絡(luò)。該算法是建立在基于向量形式的數(shù)據(jù)集上，主要是將向量數(shù)據(jù)抽象為節(jié)點(diǎn)和連邊。在給定的k值構(gòu)建k-關(guān)聯(lián)圖后，在訓(xùn)練和測(cè)試階段都應(yīng)對(duì)網(wǎng)絡(luò)中的每個(gè)子圖進(jìn)行純度檢驗(yàn)用于確定最佳的網(wǎng)絡(luò)分類。k-關(guān)聯(lián)圖中的連邊根據(jù)修正的k-近鄰算法確定。在這種特殊網(wǎng)絡(luò)形成過程中，只有具有相同標(biāo)簽或類的節(jié)點(diǎn)才允許相連，算法模型根據(jù)這個(gè)簡(jiǎn)單規(guī)則逐步形成整個(gè)網(wǎng)絡(luò)。

網(wǎng)絡(luò)中子圖純度的定義為：給定參數(shù)k值，利用修正的k-近鄰算法形成網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)最多可以具有2k個(gè)連接。由于網(wǎng)絡(luò)為有向網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)度的取值范圍為[k，2k]。純度測(cè)試確定了每個(gè)節(jié)點(diǎn)的度取值的可行性區(qū)間。本質(zhì)上，它量化了同一類別節(jié)點(diǎn)間有效創(chuàng)建的連邊數(shù)量與每個(gè)節(jié)點(diǎn)可能連接的總連接值2k之間的比值。因此，網(wǎng)絡(luò)中某一組件α的純度φ定義為：

(4)

為了得到最佳k-關(guān)聯(lián)圖，具體步驟是從k的最小取值開始逐一計(jì)算各個(gè)子圖。對(duì)每個(gè)k值和網(wǎng)絡(luò)子圖分別計(jì)算純度值，然后比較由不同k值產(chǎn)生的k-關(guān)聯(lián)圖。獲得最佳k-關(guān)聯(lián)圖之后，學(xué)習(xí)過程進(jìn)入具體的分類階段。在這一階段，文獻(xiàn)[114]采用了貝葉斯分類器進(jìn)行分類。

3.2.2 集合推理算法

集合推理算法處理的數(shù)據(jù)與傳統(tǒng)監(jiān)督學(xué)習(xí)方法處理的數(shù)據(jù)不同，它規(guī)避了數(shù)據(jù)的獨(dú)立性假設(shè)，因?yàn)閿?shù)據(jù)的標(biāo)簽不僅依賴于數(shù)據(jù)本身屬性，同時(shí)也依賴于鄰域數(shù)據(jù)的標(biāo)簽[115]。因此，對(duì)于網(wǎng)絡(luò)數(shù)據(jù)，一個(gè)數(shù)據(jù)項(xiàng)(節(jié)點(diǎn))的標(biāo)簽可能對(duì)與之相關(guān)節(jié)點(diǎn)的標(biāo)簽具有一定的影響。

在網(wǎng)絡(luò)環(huán)境下以相互關(guān)聯(lián)的方式來(lái)推斷相關(guān)節(jié)點(diǎn)標(biāo)簽的算法中較為著名的是集合推理模型[116]。與傳統(tǒng)的分類技術(shù)相比，這種方法可以顯著地減少錯(cuò)誤分類[117]。集合推理模型可以同時(shí)使用數(shù)據(jù)屬性和數(shù)據(jù)關(guān)系特征來(lái)進(jìn)行分類。眾所周知，節(jié)點(diǎn)的標(biāo)簽也可能與網(wǎng)絡(luò)上與之間接相連節(jié)點(diǎn)的標(biāo)簽相關(guān)，同時(shí)對(duì)所有節(jié)點(diǎn)的標(biāo)簽信息進(jìn)行計(jì)算可能更有意義。

另外，在一些學(xué)習(xí)過程中的特定階段也可以采用集合推理算法。例如樸素貝葉斯或關(guān)系概率樹等算法，采用局部分類器預(yù)測(cè)每個(gè)未標(biāo)記節(jié)點(diǎn)的標(biāo)簽，并進(jìn)一步使用如Gibbs抽樣[117]或ICA[118]等集合推理算法重新修改節(jié)點(diǎn)的標(biāo)簽，這類方法為局部方法。另一種方法使用全局算法，主要以優(yōu)化全局目標(biāo)函數(shù)為目標(biāo)進(jìn)行訓(xùn)練，這類算法包括循環(huán)信念傳播和松弛標(biāo)記法等[119]。

關(guān)于集合推理算法，文獻(xiàn)[120]提出了一種基于網(wǎng)絡(luò)的監(jiān)督學(xué)習(xí)模型框架(NetKit)。該框架主要由三部分組成：一是局部分類器，主要利用訓(xùn)練集來(lái)形成概率分布模型；二是關(guān)系分類器，也是估計(jì)樣本的概率分布，但與局部分類器不同的地方是它考慮了網(wǎng)絡(luò)中相鄰節(jié)點(diǎn)關(guān)系的影響；三是集合推理器，利用模型對(duì)樣本類別進(jìn)行預(yù)測(cè)。

此類方法已經(jīng)在各個(gè)領(lǐng)域獲得了廣泛應(yīng)用，如生物學(xué)中分子用途的分析[121]、科研論文鏈接的分類[118]、鏈接預(yù)測(cè)[122]等。再比如在社交網(wǎng)絡(luò)中預(yù)測(cè)當(dāng)前沒有關(guān)聯(lián)的兩個(gè)點(diǎn)在未來(lái)某一時(shí)間連接的可能性[123]，創(chuàng)建一個(gè)小連通子來(lái)中模擬社交網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的關(guān)系[124]。

3.2.3 啟發(fā)式分類算法

文獻(xiàn)[125]首次提出啟發(fā)式分類算法，該算法結(jié)合了“網(wǎng)絡(luò)環(huán)境下的易訪問性”來(lái)執(zhí)行分類任務(wù)。易訪問性的衡量標(biāo)準(zhǔn)是基于馬爾可夫鏈理論中的極限概率而確定的。首先，一組標(biāo)記數(shù)據(jù)被映射為網(wǎng)絡(luò)的節(jié)點(diǎn)。因此，該網(wǎng)絡(luò)可以看成是一個(gè)離散的馬爾可夫鏈，每個(gè)節(jié)點(diǎn)代表馬爾可夫過程中的一個(gè)狀態(tài)。當(dāng)對(duì)未標(biāo)記樣本進(jìn)行分類時(shí)，因?yàn)槲礃?biāo)記樣本的偏差信息應(yīng)被考慮在內(nèi)，包含標(biāo)記樣本的網(wǎng)絡(luò)中連邊的權(quán)值需要重新計(jì)算。在得到修正的極限概率后，未標(biāo)記樣本的類標(biāo)簽由最容易(易訪問)獲得的標(biāo)記樣本表示，最終，這樣的偏差信息將逐步改變網(wǎng)絡(luò)結(jié)構(gòu)。

(5)

3.2.4 集成方法

文獻(xiàn)[126]提出了一種基于低級(jí)分類器和高級(jí)分類器的集成方法。從本質(zhì)上講，低級(jí)分類器是根據(jù)樣本標(biāo)簽和樣本的統(tǒng)計(jì)特性進(jìn)行分類，它可以是任何傳統(tǒng)的分類技術(shù)，如決策樹、支持向量機(jī)、感知機(jī)、貝葉斯學(xué)習(xí)，或k-近鄰等；而高級(jí)分類器除了使用樣本的標(biāo)簽外，還使用樣本的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)或模式信息進(jìn)行分類。集成方法的一個(gè)突出特點(diǎn)是跨網(wǎng)絡(luò)技術(shù)，即它將輸入數(shù)據(jù)看作一個(gè)整體構(gòu)建網(wǎng)絡(luò)，并考慮到網(wǎng)絡(luò)的全局模式。定義集成方法F，它是兩種分類器的凸組合，即：

(6)

關(guān)于集成方法中高級(jí)分類器的構(gòu)建，目前有兩種方法。第一種是平均度、聚類系數(shù)和同配性三種網(wǎng)絡(luò)統(tǒng)計(jì)量的結(jié)合方法[126]，覆蓋了網(wǎng)絡(luò)從局部到全局的所有信息。其中，度可以準(zhǔn)確度量網(wǎng)絡(luò)中節(jié)點(diǎn)的局部信息；聚類系數(shù)通過計(jì)算當(dāng)前節(jié)點(diǎn)及其鄰域內(nèi)的兩個(gè)節(jié)點(diǎn)所形成的三角形數(shù)量度量網(wǎng)絡(luò)的局部結(jié)構(gòu)；同配性不僅考慮當(dāng)前節(jié)點(diǎn)及其鄰域內(nèi)的節(jié)點(diǎn)，而且考慮第二級(jí)鄰域內(nèi)的節(jié)點(diǎn)(鄰域的鄰域)、第三級(jí)鄰域內(nèi)的節(jié)點(diǎn)等。

第二種利用了隨機(jī)游走過程中的動(dòng)力學(xué)特性[127]。與經(jīng)典的網(wǎng)絡(luò)統(tǒng)計(jì)量計(jì)算方法不同，該算法利用網(wǎng)絡(luò)中隨機(jī)游走過程的動(dòng)力學(xué)特性提取網(wǎng)絡(luò)的高級(jí)信息。換句話說，隨機(jī)游走可以理解為在高維數(shù)據(jù)空間中隨機(jī)訪問數(shù)據(jù)節(jié)點(diǎn)的過程，通過不斷調(diào)整隨機(jī)游走過程中記憶窗口的長(zhǎng)度，來(lái)提取從局部到全局的網(wǎng)絡(luò)信息和網(wǎng)絡(luò)特征。當(dāng)隨機(jī)游走的記憶窗口較小時(shí)，提取網(wǎng)絡(luò)的局部結(jié)構(gòu)特征；隨著記憶窗口的逐漸增大，游走過程被迫逐漸遠(yuǎn)離起點(diǎn)，從而學(xué)習(xí)網(wǎng)絡(luò)的全局特性。

3.3 無(wú)監(jiān)督學(xué)習(xí)方法

眾所周知，無(wú)監(jiān)督學(xué)習(xí)任務(wù)中樣本數(shù)據(jù)沒有類別屬性的先驗(yàn)知識(shí)。基于網(wǎng)絡(luò)的無(wú)監(jiān)督學(xué)習(xí)方法類似，學(xué)習(xí)過程首先根據(jù)相似度標(biāo)準(zhǔn)從輸入數(shù)據(jù)構(gòu)建網(wǎng)絡(luò)，再通過網(wǎng)絡(luò)結(jié)構(gòu)完成知識(shí)的學(xué)習(xí)。無(wú)監(jiān)督學(xué)習(xí)的一個(gè)主要任務(wù)是數(shù)據(jù)聚類問題，實(shí)際上，一旦原始數(shù)據(jù)集轉(zhuǎn)化為網(wǎng)絡(luò)，數(shù)據(jù)聚類可以被認(rèn)為是社團(tuán)檢測(cè)問題。眾多學(xué)者業(yè)對(duì)于此問題提出了近似的、有效的解決方法，其中包括譜方法[128]，基于介數(shù)的算法[129]，模塊化貪心優(yōu)化算法[130]，基于Potts模型的社團(tuán)檢測(cè)算法[131]，同步方法[132]，信息論方法[133]和隨機(jī)游走[134]。

3.3.1 基于介數(shù)的算法

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

3.3.2 模塊度最大化算法

模塊度是用來(lái)衡量網(wǎng)絡(luò)中一個(gè)特定區(qū)塊劃分質(zhì)量的方法[137-138]，或者用于衡量網(wǎng)絡(luò)區(qū)塊劃分為模塊(也稱為組、聚類或社團(tuán))的能力。一般來(lái)說，其范圍為0到1之間的數(shù)值。當(dāng)模塊度接近0時(shí)，表明網(wǎng)絡(luò)沒有劃分出社團(tuán)結(jié)構(gòu)，認(rèn)為網(wǎng)絡(luò)中的邊是隨機(jī)連接的。隨著模塊度增加，社團(tuán)結(jié)構(gòu)越來(lái)越顯現(xiàn)，社團(tuán)內(nèi)的連邊比例逐漸大于社團(tuán)間。模塊度定義為：

(7)

式中：E表示網(wǎng)絡(luò)中邊的總數(shù)目；Aij表示節(jié)點(diǎn)i與j之間的連邊權(quán)重；ki、kj分別表示節(jié)點(diǎn)i和j的度；ci表示節(jié)點(diǎn)i的社團(tuán)；1[ci=cj]為指示函數(shù)，當(dāng)ci=cj，為1；否則，為0。

第一個(gè)提出模塊度優(yōu)化方法的是Clauset等[137]，隨后又有其他學(xué)者陸續(xù)提出一些改進(jìn)方法[139-143]。Clauset算法的主要思路是在網(wǎng)絡(luò)社團(tuán)劃分過程中加入了貪婪算法，即在模塊度最大化的每個(gè)時(shí)間步，選擇合并兩個(gè)能使模塊度增幅最大的社團(tuán)，即找到最大的模塊度增量。但該算法有一個(gè)缺點(diǎn)，即社團(tuán)的不平衡問題，計(jì)算過程中會(huì)產(chǎn)生包含大部分節(jié)點(diǎn)的超社團(tuán)。為解決社團(tuán)劃分的不平衡問題，加速社團(tuán)合并過程運(yùn)行時(shí)間，出現(xiàn)了Louvain方法[139]，它能夠處理百萬(wàn)節(jié)點(diǎn)的網(wǎng)絡(luò)，是迄今為止最快的模塊度優(yōu)化算法。

3.3.3 譜分析方法

圖譜分析關(guān)注的是圖的屬性，如其特征多項(xiàng)式、特征值和與鄰接矩陣或拉普拉斯矩陣相關(guān)的特征向量。首先考慮采用譜分析方法來(lái)計(jì)算圖切割的是Donath和Hoffman[144]，也是他們首先采用圖的鄰接矩陣特征向量來(lái)發(fā)現(xiàn)社團(tuán)的。此后，用于計(jì)算和分割圖的譜分析方法越來(lái)越受到關(guān)注[145-147]。例如Zhou等[146]計(jì)算了含有任意度和社團(tuán)結(jié)構(gòu)的隨機(jī)網(wǎng)絡(luò)的譜特征。桂春等[148]在Ahn方法[149]的基礎(chǔ)上提出了邊圖譜分析算法，并應(yīng)用到邊社團(tuán)發(fā)現(xiàn)上，進(jìn)行了兼顧層次性和重疊性的社團(tuán)檢測(cè)研究，實(shí)驗(yàn)結(jié)果表明該算法實(shí)現(xiàn)了網(wǎng)絡(luò)的重疊社團(tuán)檢測(cè)并且社團(tuán)劃分結(jié)果比較滿意。

3.3.4 基于粒子競(jìng)爭(zhēng)機(jī)制的算法

粒子競(jìng)爭(zhēng)模型的演化與眾多自然和社會(huì)現(xiàn)象進(jìn)化過程非常類似，例如資源競(jìng)爭(zhēng)、動(dòng)物領(lǐng)地爭(zhēng)奪、競(jìng)選活動(dòng)等。Quiles等[150]將此演化過程引入到社團(tuán)檢測(cè)問題中，通過研究網(wǎng)絡(luò)環(huán)境下多個(gè)粒子的競(jìng)爭(zhēng)機(jī)制來(lái)識(shí)別社團(tuán)。由于競(jìng)爭(zhēng)效應(yīng)，粒子要么處于活躍狀態(tài)，要么處于沉寂狀態(tài)。每當(dāng)粒子處于活躍狀態(tài)時(shí)，它會(huì)同時(shí)受到兩種相互正交的游走規(guī)則的引導(dǎo)，這兩種規(guī)則分別為隨機(jī)游走和優(yōu)先游走。隨機(jī)游走是一種無(wú)條件規(guī)則，它只依賴于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，控制粒子在網(wǎng)絡(luò)中的探索行為；相反，優(yōu)先游走是粒子通過強(qiáng)化它們已經(jīng)占領(lǐng)的節(jié)點(diǎn)來(lái)完成粒子的防御行為。這些粒子以占領(lǐng)新節(jié)點(diǎn)為目標(biāo)在網(wǎng)絡(luò)中自主運(yùn)動(dòng)(隨機(jī)的或確定的方式)，同時(shí)也試圖守衛(wèi)它們已占領(lǐng)的領(lǐng)地。至此，定義一個(gè)轉(zhuǎn)移矩陣用來(lái)控制粒子游走到下一個(gè)狀態(tài)的概率分布：

(8)

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

表3 多種算法的數(shù)據(jù)聚類結(jié)果比較

3.3.5 變色龍算法

變色龍算法常用于數(shù)據(jù)聚類問題[159]。它是一種層次聚類算法，其在識(shí)別相似社團(tuán)時(shí)采用了互連性和近似性特征。網(wǎng)絡(luò)完成構(gòu)建之后，變色龍方法通過最小化邊割將網(wǎng)絡(luò)劃分為多個(gè)社團(tuán)來(lái)發(fā)現(xiàn)網(wǎng)絡(luò)的初始分區(qū)。在找到子群之后，該算法通過使用社團(tuán)相似性度量準(zhǔn)則(社團(tuán)間的相對(duì)互連度(RI)和相對(duì)近似度(RC))來(lái)重復(fù)組合這些子群。這兩個(gè)指數(shù)定義如下：

相對(duì)互聯(lián)度:

(9)

相對(duì)近似度：

(10)

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

3.3.6 基于群體動(dòng)力學(xué)的算法

群體行為是由大量簡(jiǎn)單的個(gè)體通過互相作用呈現(xiàn)出宏觀復(fù)雜的組織系統(tǒng)[161-162]。目前，群體行為技術(shù)已經(jīng)被成功用于解決各種優(yōu)化問題[163]，如De Oliveira等[164-165]將群體動(dòng)力學(xué)模型引入到網(wǎng)絡(luò)中的社團(tuán)檢測(cè)研究。社團(tuán)檢測(cè)算法的思路分為兩個(gè)步驟：1) 將數(shù)據(jù)樣本轉(zhuǎn)為化網(wǎng)絡(luò)形式;2) 在構(gòu)建的網(wǎng)絡(luò)上檢測(cè)集群或社團(tuán)。計(jì)算時(shí)，最初將整個(gè)網(wǎng)絡(luò)視為一個(gè)大社團(tuán)，然后逐步分解為小社團(tuán)，直到每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)社團(tuán)。迭代過程中，關(guān)鍵的因素是更新規(guī)則，在該算法中節(jié)點(diǎn)按照?qǐng)A形組織，給定初始隨機(jī)角度θi(t=0)，節(jié)點(diǎn)角度的更新規(guī)則按以下公式來(lái)定義：

(11)

式中：N(vi)為節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集，ηi(t)為vi在時(shí)間步t的移動(dòng)速率，Aij為鄰居vj對(duì)鄰居vi的影響權(quán)重。

由于該算法具有層次性結(jié)構(gòu)，因此可以使用樹狀圖來(lái)描述計(jì)算結(jié)果。例如，Oliveira[166]利用此算法在海豚社會(huì)網(wǎng)絡(luò)上進(jìn)行了仿真計(jì)算，所得結(jié)果如圖4所示，圖中節(jié)點(diǎn)的虛實(shí)表示它原有所屬社團(tuán)。

圖4 文獻(xiàn)[59]中的海豚社會(huì)網(wǎng)絡(luò)社團(tuán)檢測(cè)結(jié)果

3.3.7 同步方法

近年來(lái)，物理學(xué)家越來(lái)越關(guān)注復(fù)雜系統(tǒng)多樣性的動(dòng)力學(xué)特性，一些學(xué)者也進(jìn)行了大量的耦合振蕩器的實(shí)證分析[166-167]。實(shí)際上，這些系統(tǒng)內(nèi)單元同步的涌現(xiàn)與單元之間交互的拓?fù)浣Y(jié)構(gòu)密切相關(guān)，隨著時(shí)間的演化，這些動(dòng)力學(xué)模型呈現(xiàn)出不同的模式，而這些模式與復(fù)雜網(wǎng)絡(luò)中社團(tuán)的層級(jí)組織有著內(nèi)在的聯(lián)系。理解同步現(xiàn)象最成功的嘗試之一來(lái)自Kuramoto[168]，他提出的相位振蕩器耦合模型非常適合用來(lái)仿真各類同步模式。

網(wǎng)絡(luò)環(huán)境下，每個(gè)節(jié)點(diǎn)都可以看作是一個(gè)振蕩器，連邊權(quán)重則表示不同振蕩器之間的耦合強(qiáng)度。有些文獻(xiàn)已經(jīng)發(fā)現(xiàn)高度相互關(guān)聯(lián)的振蕩器集合更容易與那些稀疏連接的振蕩器同步[168-171]。因此，對(duì)于具有重要連接模式的復(fù)雜網(wǎng)絡(luò)，從隨機(jī)初始條件開始，那些形成局部社團(tuán)的高度互連的單元將首先同步。隨后，越來(lái)越大的網(wǎng)絡(luò)結(jié)構(gòu)采用同樣的形式繼續(xù)演化，直至達(dá)到最終狀態(tài)。此狀態(tài)下，所有的節(jié)點(diǎn)都具有相同的相變過程，只要有明確的社團(tuán)結(jié)構(gòu)存在，該過程會(huì)在某個(gè)時(shí)間尺度上產(chǎn)生。因此，擁有全局吸引子的動(dòng)力學(xué)過程揭示了不同的拓?fù)浣Y(jié)構(gòu)，而且這些拓?fù)浣Y(jié)構(gòu)可能表示的就是網(wǎng)絡(luò)社團(tuán)。在Kuramoto模型的基礎(chǔ)上，Wu等[171]將一種無(wú)連邊節(jié)點(diǎn)的負(fù)耦合作用考慮在內(nèi)，建立了同步過程的動(dòng)力學(xué)演化模型，即：

Aij)sin(θj-θi)

(12)

式中：V表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目；ωi表示第i個(gè)節(jié)點(diǎn)的固有頻率；Aij表示節(jié)點(diǎn)之間的耦合關(guān)系；θi和θj分別表示節(jié)點(diǎn)i和j的相位；Kp和Kn分別表示正負(fù)耦合強(qiáng)度。

3.4 半監(jiān)督學(xué)習(xí)方法

在諸如視頻識(shí)別、聲音信號(hào)分類、文本分類、醫(yī)療診斷以及其他應(yīng)用領(lǐng)域中，很容易找到海量的無(wú)類標(biāo)簽的樣例，但需要使用特殊設(shè)備或經(jīng)過昂貴且用時(shí)非常長(zhǎng)的實(shí)驗(yàn)過程進(jìn)行人工標(biāo)記才能得到有類標(biāo)簽的樣本，由此產(chǎn)生了極少量的有類標(biāo)簽的樣本和過剩的無(wú)類標(biāo)簽的樣例，也就產(chǎn)生了半監(jiān)督學(xué)習(xí)[172]。而在基于網(wǎng)絡(luò)的方法中，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是將標(biāo)簽從已標(biāo)簽節(jié)點(diǎn)向未標(biāo)簽節(jié)點(diǎn)傳播的主要引擎。近年來(lái)，關(guān)于用復(fù)雜網(wǎng)絡(luò)理論來(lái)研究半監(jiān)督學(xué)習(xí)取得了重要進(jìn)展，將這些方法進(jìn)行分類，主要包括最小割算法[173]、局部和全局一致性算法[174]、局部和全局正則化[175]、半監(jiān)督模塊化[176]、判別式游走[177]、隨機(jī)游走[178-179]和標(biāo)簽傳播技術(shù)[180-181]等。

3.4.1 最大流與最小割算法

最大流和最小割算法最初用在二分類問題中[182]。半監(jiān)督學(xué)習(xí)的分類方法可以看作是一個(gè)圖分割問題。在二分類問題中，正標(biāo)簽被看作是源點(diǎn)，負(fù)標(biāo)簽被看作是匯點(diǎn)。算法的目標(biāo)是找到一個(gè)最小邊的集合來(lái)阻斷從源點(diǎn)到匯點(diǎn)的流量。被分割后的圖中，連接源樣本點(diǎn)的將會(huì)被分類為正樣本，而連接匯點(diǎn)的樣本將會(huì)被分類為負(fù)樣本。因此，損失函數(shù)可以寫為：

(13)

最大流與最小割算法有很多有趣的特性[183]，可以采用網(wǎng)絡(luò)流工具進(jìn)行多項(xiàng)式的時(shí)間計(jì)算，學(xué)習(xí)過程也可以被視為馬爾可夫隨機(jī)場(chǎng)過程?；蛟S，該算法也存在一些缺陷，如它是不存在置信區(qū)間的硬分類問題。為解決此問題，文獻(xiàn)[184]引入了基于譜劃分的方法，可以在圖中產(chǎn)生近似的最小割比率。

3.4.2 高斯隨機(jī)場(chǎng)與調(diào)和函數(shù)

為解決最小割算法的硬分類問題，有學(xué)者提出了高斯隨機(jī)場(chǎng)與調(diào)和函數(shù)方法[173,181]。該方法被視作是最近鄰方法的一種變種形式，其中最近鄰的標(biāo)注樣本在圖上用隨機(jī)行走的方式計(jì)算。另外，調(diào)和函數(shù)根據(jù)鄰近節(jié)點(diǎn)標(biāo)簽的加權(quán)平均數(shù)來(lái)估計(jì)未標(biāo)注節(jié)點(diǎn)的標(biāo)簽。同樣，它可以看作是一個(gè)平方損失函數(shù)，已標(biāo)記的數(shù)據(jù)樣本標(biāo)簽是固定的，然后加上一個(gè)拉普拉斯正則項(xiàng)。因此，損失函數(shù)可表示為：

(14)

3.4.3 局部全局一致性學(xué)習(xí)

局部全局一致性學(xué)習(xí)算法是基于網(wǎng)絡(luò)的半監(jiān)督學(xué)習(xí)技術(shù)中最早的方法之一[174]。該算法通過構(gòu)造標(biāo)記樣本與未標(biāo)記樣本結(jié)構(gòu)的足夠平滑的分類函數(shù)來(lái)進(jìn)行學(xué)習(xí)。損失函數(shù)定義如下：

(15)

近年來(lái)，國(guó)內(nèi)的研究人員也對(duì)局部全局一致性學(xué)習(xí)算法進(jìn)行了研究。針對(duì)文獻(xiàn)[174]提出的算法分類精度在很大程度上取決于控制參數(shù)的合理設(shè)置問題，王雪松等[185]提出了一種少參數(shù)的簡(jiǎn)潔算法；另外，在標(biāo)簽傳遞過程中，他們僅將未標(biāo)記樣本的標(biāo)簽根據(jù)相似度傳遞給近鄰，而將已標(biāo)記樣本的標(biāo)簽強(qiáng)制回填，確保了標(biāo)簽傳遞源頭的準(zhǔn)確性。為降低計(jì)算復(fù)雜度，白本督等[186]提出一種K-均值構(gòu)圖法，主要將稀疏表示理論應(yīng)用到基于圖的半監(jiān)督學(xué)習(xí)過程中，通過稀疏分解稀疏矩陣來(lái)得到圖中鄰接矩陣和邊權(quán)重。

3.4.4 附著法

(16)

3.4.5 相互作用力算法

受自然界中物體之間存在吸引力的啟發(fā)，Cupertino等[189]提出相互作用力算法來(lái)進(jìn)行網(wǎng)絡(luò)的半監(jiān)督學(xué)習(xí)。它將數(shù)據(jù)樣本模型化為一個(gè)P維空間上的節(jié)點(diǎn)，并根據(jù)施加在它之上的合力執(zhí)行相應(yīng)的運(yùn)動(dòng)。已標(biāo)注數(shù)據(jù)樣本充當(dāng)吸引點(diǎn)，而未標(biāo)注樣本獲得吸力并朝這些吸引點(diǎn)移動(dòng)。一旦一個(gè)未標(biāo)注樣本足夠接近已標(biāo)注樣本，比如說半徑，那么吸引點(diǎn)的標(biāo)簽就傳播到位于其周圍的未標(biāo)注樣本上。同時(shí)，未標(biāo)注樣本從標(biāo)注節(jié)點(diǎn)接收標(biāo)簽，然后成為新的吸引點(diǎn)。通過反復(fù)迭代，所有的數(shù)據(jù)樣本都會(huì)收斂到某個(gè)吸引點(diǎn)，完成標(biāo)簽的傳播過程。

3.4.6 判別式游走算法

判別式游走(D-Walks)算法在文獻(xiàn)[177]中有詳細(xì)介紹。從本質(zhì)上看，D-Walks算法依賴于網(wǎng)絡(luò)上的隨機(jī)游走過程，該過程可以被看作是馬爾可夫鏈，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于馬爾可夫鏈的一個(gè)狀態(tài)。另外，D-Walks算法需要計(jì)算節(jié)點(diǎn)介數(shù)，未標(biāo)注節(jié)點(diǎn)被分配到介數(shù)最高的類別。介數(shù)的大小可以按下式計(jì)算得到：

(17)

3.4.7 隨機(jī)競(jìng)爭(zhēng)-合作學(xué)習(xí)

(18)

式中：i和j表示網(wǎng)絡(luò)中的節(jié)點(diǎn)，vk表示粒子k的父節(jié)點(diǎn)。

隨后，Wu等[192]又將該算法應(yīng)用于錯(cuò)誤標(biāo)簽傳播的預(yù)防上。眾所周知，真實(shí)世界中，由于儀器誤差或人為標(biāo)注的失誤，錯(cuò)誤標(biāo)注樣本在數(shù)據(jù)集中常見。如果這些錯(cuò)誤標(biāo)簽被用來(lái)進(jìn)一步分類新數(shù)據(jù)(有監(jiān)督學(xué)習(xí))或傳播到未標(biāo)記樣本(半監(jiān)督學(xué)習(xí))，可能會(huì)產(chǎn)生嚴(yán)重后果。通過模擬計(jì)算，該算法在真實(shí)數(shù)據(jù)集上的表現(xiàn)優(yōu)于線性傳播算法(LP)[193]和線性鄰域傳播算法(LNP)[194]。

4 基于機(jī)器學(xué)習(xí)的復(fù)雜網(wǎng)絡(luò)信息挖掘

如前所述，對(duì)于復(fù)雜網(wǎng)絡(luò)，我們主要關(guān)注的是其統(tǒng)計(jì)特征、拓?fù)浣Y(jié)構(gòu)及關(guān)鍵節(jié)點(diǎn)和連邊。隨著數(shù)據(jù)量的急速增加，網(wǎng)絡(luò)變得越來(lái)越大，單純地網(wǎng)絡(luò)分析方法已經(jīng)難以滿足網(wǎng)絡(luò)信息快速挖掘的需要。這促使部分學(xué)者開始從事計(jì)算機(jī)技術(shù)用于分析復(fù)雜網(wǎng)絡(luò)的研究，特別是近年來(lái)人工智能技術(shù)的快速進(jìn)步，給機(jī)器學(xué)習(xí)和復(fù)雜網(wǎng)絡(luò)的交叉應(yīng)用提供了思路。如在社會(huì)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等領(lǐng)域，已有研究人員利用機(jī)器學(xué)習(xí)算法進(jìn)行了網(wǎng)絡(luò)信息挖掘的嘗試。

4.1 網(wǎng)絡(luò)統(tǒng)計(jì)特征提取

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

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

4.2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分類

自閉癥癥狀的早期篩查有助于及時(shí)發(fā)現(xiàn)患者，通常的做法是進(jìn)行正常人和疑似病例的大腦功能性連接模式對(duì)比。文獻(xiàn)[199]基于Granger因果關(guān)系的腦連通性數(shù)據(jù)，運(yùn)用支持向量機(jī)和Fisher準(zhǔn)則進(jìn)行了連接模式的分類，并對(duì)由鄰接矩陣構(gòu)成的各類特征進(jìn)行排序，進(jìn)而確定使網(wǎng)絡(luò)分割函數(shù)達(dá)到最大值時(shí)的最佳子集，計(jì)算結(jié)果表明，基于鄰接矩陣和圖論方法的組合分類模型可以達(dá)到87.5%的準(zhǔn)確度。Matthew D S等[200]在進(jìn)行抑郁患者與正常人的分類模型構(gòu)建時(shí)，采用了一種新的特征評(píng)估方法，即運(yùn)用迭代分類器的分類性能來(lái)評(píng)估所選特征的魯棒性。另外，文獻(xiàn)[198]進(jìn)行分類模型構(gòu)建時(shí)采用的是多核SVM算法，認(rèn)為網(wǎng)絡(luò)拓?fù)涮卣鞯奶崛『瓦B邊權(quán)重閾值的選擇可以同時(shí)進(jìn)行。

4.3 網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)和關(guān)鍵邊識(shí)別

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

在社會(huì)網(wǎng)絡(luò)分析領(lǐng)域，節(jié)點(diǎn)排序是一個(gè)核心任務(wù)。根據(jù)復(fù)雜程度的不同，節(jié)點(diǎn)重要程度度量分為局部度量和全局度量。Jeh等[204]提出了一種估計(jì)兩個(gè)節(jié)點(diǎn)相似度的度量標(biāo)準(zhǔn)，主要通過隨機(jī)游走計(jì)算這兩個(gè)節(jié)點(diǎn)到它們所連接的相似節(jié)點(diǎn)的度數(shù)。除了靜態(tài)圖上的節(jié)點(diǎn)排序，一些學(xué)者[205]還研究了動(dòng)態(tài)圖上的節(jié)點(diǎn)排序，考慮了利用諸如電子郵件等事件的時(shí)間信息來(lái)追蹤節(jié)點(diǎn)隨新事件發(fā)生的排序變化情況。

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

4.4 網(wǎng)絡(luò)節(jié)點(diǎn)分類

在具有連邊的節(jié)點(diǎn)分類問題中，連邊的屬性與結(jié)構(gòu)有助于節(jié)點(diǎn)分類任務(wù)。Lu等[208]對(duì)每個(gè)數(shù)據(jù)樣本增加新的屬性，使其能夠處理基于鏈接的節(jié)點(diǎn)分類問題，擴(kuò)展了機(jī)器學(xué)習(xí)分類器的應(yīng)用范圍。Bhagat等[209]基于局部和全局的鏈接結(jié)構(gòu)相似性算法對(duì)博客進(jìn)行標(biāo)注，完成分類任務(wù)。Sen等[210]研究了網(wǎng)絡(luò)數(shù)據(jù)樣本的集體分類方法，比較了四種常用的推理算法在模擬數(shù)據(jù)和現(xiàn)實(shí)數(shù)據(jù)上的分類性能。Backstrom等[211]通過分析社團(tuán)進(jìn)化過程來(lái)刻畫網(wǎng)絡(luò)中個(gè)體位置的結(jié)構(gòu)特征，并成功用于節(jié)點(diǎn)的分類中。

5 重點(diǎn)關(guān)注的兩類問題

綜上所述，復(fù)雜網(wǎng)絡(luò)與機(jī)器學(xué)習(xí)有相似的目標(biāo)，給定一些數(shù)據(jù)，通常表示一個(gè)復(fù)雜系統(tǒng)，目的是從其挖掘一些信息，并創(chuàng)建一個(gè)新的知識(shí)表征(拓?fù)浣Y(jié)構(gòu)或者機(jī)器學(xué)習(xí)模型)。目前，復(fù)雜網(wǎng)絡(luò)與機(jī)器學(xué)習(xí)交叉應(yīng)用的可能方向主要體現(xiàn)在社團(tuán)檢測(cè)與聚類、鏈路預(yù)測(cè)和語(yǔ)義表征等。

5.1 聚類與社團(tuán)檢測(cè)

機(jī)器學(xué)習(xí)中的聚類與復(fù)雜網(wǎng)絡(luò)分析中的社團(tuán)檢測(cè)是兩個(gè)具有較多相似性特征的問題。大多數(shù)聚類算法僅利用樣本間相似性(距離)的局部信息，而復(fù)雜網(wǎng)絡(luò)方法允許網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu)包含在算法當(dāng)中，因此計(jì)算結(jié)果更加準(zhǔn)確。如圖5所示，左側(cè)的聚類任務(wù)中，雖然節(jié)點(diǎn)A與節(jié)點(diǎn)B更相似，同屬于一個(gè)類別，卻劃分到其他類別中；而對(duì)于右側(cè)的社團(tuán)檢測(cè)任務(wù)，雖然節(jié)點(diǎn)A更接近三角形社團(tuán)，但因其與節(jié)點(diǎn)B有連邊存在，所以社團(tuán)劃分合理。

圖5 聚類與社團(tuán)檢測(cè)問題的對(duì)比[212]

可以看出，在聚類任務(wù)中引入復(fù)雜網(wǎng)絡(luò)理論能有效地提高計(jì)算準(zhǔn)確度。目前來(lái)看，該方法在不同研究領(lǐng)域都有所應(yīng)用。在網(wǎng)絡(luò)音樂領(lǐng)域，Joan S等[213]采用社團(tuán)檢測(cè)算法檢測(cè)同一首歌曲的覆蓋類別和范圍，其結(jié)果由于傳統(tǒng)聚類算法。經(jīng)濟(jì)物理學(xué)中，在金融市場(chǎng)交易的投資者集群被確定為統(tǒng)計(jì)校準(zhǔn)網(wǎng)絡(luò)中的社團(tuán)[214]?；蛟S，某些情況下聚類算法也可以用于進(jìn)行復(fù)雜網(wǎng)絡(luò)中的社團(tuán)檢測(cè)，例如復(fù)雜網(wǎng)絡(luò)中重疊社團(tuán)結(jié)構(gòu)識(shí)別的模糊c-均值聚類算法[215]、社團(tuán)檢測(cè)的自適應(yīng)聚類算法[216]、重疊和非重疊社團(tuán)結(jié)構(gòu)識(shí)別的模糊聚類算法[217]。

5.2 鏈路預(yù)測(cè)

鏈路預(yù)測(cè)已經(jīng)成為復(fù)雜網(wǎng)絡(luò)中一個(gè)重要的研究方向，特別是在生物網(wǎng)絡(luò)和社會(huì)網(wǎng)絡(luò)。同樣在數(shù)據(jù)挖掘領(lǐng)域，推薦系統(tǒng)與之對(duì)應(yīng)，也是計(jì)算機(jī)技術(shù)中的主要研究方向之一，研究思路和方法基于馬爾可夫鏈和機(jī)器學(xué)習(xí)。盡管它們?cè)趯?shí)質(zhì)上是等價(jià)的，但仍舊是在不同的研究路徑上前行，僅有個(gè)別的研究人員在聯(lián)合方向上進(jìn)行了嘗試。

6 結(jié) 語(yǔ)

眾所周知，現(xiàn)實(shí)世界中，幾乎所有的系統(tǒng)都可以采用網(wǎng)絡(luò)的方式來(lái)描述，復(fù)雜網(wǎng)絡(luò)就是以網(wǎng)絡(luò)的視角去分析這些數(shù)據(jù)，找出可被解釋的結(jié)果或者現(xiàn)象，相當(dāng)于挖掘隱藏在數(shù)據(jù)背后的規(guī)則；對(duì)于機(jī)器學(xué)習(xí)，我們主要研究如何使計(jì)算機(jī)從給定的數(shù)據(jù)中學(xué)習(xí)規(guī)律或模型，并利用學(xué)到的模型進(jìn)行預(yù)測(cè)。從本質(zhì)上來(lái)說，復(fù)雜網(wǎng)絡(luò)和機(jī)器學(xué)習(xí)的目標(biāo)是一致的，都是為了挖掘數(shù)據(jù)內(nèi)在的規(guī)律，兩者的融合將有更多突破。

可以看出，融合復(fù)雜網(wǎng)絡(luò)理論和機(jī)器學(xué)習(xí)技術(shù)已經(jīng)是眾多學(xué)者開始著手研究的領(lǐng)域。隨著諸如大數(shù)據(jù)、人工智能等技術(shù)的出現(xiàn)，要想讓它們發(fā)揮更大的作用，需要在理論層次和技術(shù)層次上更進(jìn)一步創(chuàng)新。我們總結(jié)了在該交叉領(lǐng)域未來(lái)可能成為研究熱點(diǎn)的幾大問題，希望在不久的將來(lái)，這些問題能夠得到完美解決。

首先，從有益于促進(jìn)復(fù)雜網(wǎng)絡(luò)研究效率的角度看：

(1) 優(yōu)化復(fù)雜網(wǎng)絡(luò)統(tǒng)計(jì)度量指標(biāo)。隨著大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)集越來(lái)越大，如大型在線社交網(wǎng)絡(luò)，對(duì)網(wǎng)絡(luò)的度量變得越來(lái)越復(fù)雜，尤其是從計(jì)算成本的角度來(lái)看，耗時(shí)耗力。如果按照這種趨勢(shì)發(fā)展，復(fù)雜網(wǎng)絡(luò)的各類度量指標(biāo)將不得不依靠機(jī)器學(xué)習(xí)技術(shù)進(jìn)行重新優(yōu)化設(shè)計(jì)，在具體設(shè)計(jì)時(shí)應(yīng)特別關(guān)注其計(jì)算成本，以確保其可擴(kuò)展到數(shù)億的節(jié)點(diǎn)。

(2) 開發(fā)用于復(fù)雜網(wǎng)絡(luò)分析的軟件平臺(tái)。數(shù)據(jù)的規(guī)模性和復(fù)雜性將迫使研究人員需要設(shè)計(jì)開發(fā)新的軟件工具和機(jī)器學(xué)習(xí)模型來(lái)管理和分析這些數(shù)據(jù)集。雖然在這個(gè)方向上已經(jīng)采取了一些措施，例如創(chuàng)建圖形數(shù)據(jù)庫(kù)等，但是大多數(shù)解決方案僅限于可視化的思路，忽略了真實(shí)世界網(wǎng)絡(luò)的復(fù)雜性。

另外，從有益于強(qiáng)化機(jī)器學(xué)習(xí)理論背景的角度看：

(1) 提升機(jī)器學(xué)習(xí)算法準(zhǔn)確度。如實(shí)際應(yīng)用中，通常樣本特征的提取過于簡(jiǎn)單、解釋性差，使用復(fù)雜網(wǎng)絡(luò)理論去挖掘潛在的可被解釋的規(guī)律，再融合群體智慧知識(shí)，然后構(gòu)建相關(guān)數(shù)據(jù)特征，按照這樣的思路去解決機(jī)器學(xué)習(xí)任務(wù)視為最優(yōu)路徑。

(2) 擴(kuò)展機(jī)器學(xué)習(xí)模型數(shù)學(xué)理論。由于大量缺乏標(biāo)注樣本，或者人工標(biāo)注成本過高，我們?cè)絹?lái)越依賴半監(jiān)督學(xué)習(xí)技術(shù)，但是半監(jiān)督技術(shù)理論的不完善限制了其廣泛應(yīng)用?；蛟S，從復(fù)雜網(wǎng)絡(luò)領(lǐng)域可以尋找可能，如利用復(fù)雜網(wǎng)絡(luò)上的流行病擴(kuò)散動(dòng)力學(xué)過程來(lái)完成半監(jiān)督學(xué)習(xí)中數(shù)據(jù)標(biāo)簽的傳播。