伍杰華，朱岸青，蔡雪蓮，張小蘭

（1.廣東工貿(mào)職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系，廣東 廣州510510；2.華南理工大學(xué)信息科學(xué)與技術(shù)學(xué)院，廣東 廣州510641；3.暨南大學(xué)信息科學(xué)與技術(shù)學(xué)院，廣東 廣州510632）

1 引言

復(fù)雜網(wǎng)絡(luò)分析［1］是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域其中一個(gè)非?；钴S的研究方向，其主要通過(guò)學(xué)習(xí)網(wǎng)絡(luò)中實(shí)體及其相互之間的活動(dòng)關(guān)系，發(fā)掘其中內(nèi)在的知識(shí)。而該類關(guān)系和活動(dòng)可以用網(wǎng)絡(luò)或者圖的結(jié)構(gòu)［2］來(lái)表示，其中節(jié)點(diǎn)（頂點(diǎn)）表示一個(gè)實(shí)體，鏈接（邊）表示兩個(gè)實(shí)體之間的關(guān)系，利用網(wǎng)絡(luò)圖我們可以挖掘其結(jié)構(gòu)特征并找出感興趣的信息，社區(qū)發(fā)現(xiàn)、信息傳播、節(jié)點(diǎn)分類等都是復(fù)雜網(wǎng)絡(luò)分析研究的方向，本文主要針對(duì)鏈接預(yù)測(cè)這一領(lǐng)域開(kāi)展研究。

鏈接預(yù)測(cè)根據(jù)網(wǎng)絡(luò)的歷史結(jié)構(gòu)信息預(yù)測(cè)其演化方式及鏈接關(guān)系發(fā)生的潛在可能，其在眾多領(lǐng)域有著重要的應(yīng)用價(jià)值。例如，通過(guò)分析生物信息網(wǎng)絡(luò)，預(yù)測(cè)氨基酸內(nèi)蛋白質(zhì)的相互作用；在社交網(wǎng)絡(luò)中預(yù)測(cè)現(xiàn)在尚未成為朋友的未來(lái)是否“應(yīng)該是朋友”［3］；在市場(chǎng)營(yíng)銷網(wǎng)絡(luò)中判斷哪些客戶應(yīng)該需要去開(kāi)發(fā)等等。

2 相關(guān)工作

鏈接預(yù)測(cè)作為數(shù)據(jù)挖掘和復(fù)雜網(wǎng)絡(luò)分析的研究方向已經(jīng)有一些工作正在開(kāi)展，主要分為基于網(wǎng)絡(luò)結(jié)構(gòu)信息挖掘的鏈接預(yù)測(cè)［4］和基于機(jī)器學(xué)習(xí)的鏈接預(yù)測(cè)兩類［5］：（1）基于結(jié)構(gòu)信息挖掘預(yù)測(cè)模型。其主要通過(guò)計(jì)算節(jié)點(diǎn)間的相似度獲得，相似度表示兩個(gè)節(jié)點(diǎn)之間（后稱節(jié)點(diǎn)對(duì)）結(jié)構(gòu)屬性的相似性及產(chǎn)生鏈接可能性，假設(shè)相似性越大，它們之間存在鏈接的可能性就越大。Liben－Nowell D 和Kleinberg J［4］總結(jié)了基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的相似性定義方法，將這些指標(biāo)分為基于節(jié)點(diǎn)和基于路徑的兩類，并分析了若干指標(biāo)對(duì)的相互作用，及其對(duì)網(wǎng)絡(luò)鏈接預(yù)測(cè)的效果。后續(xù)的許多工作都是在此基礎(chǔ)上開(kāi)展的［6，7］。（2）基于機(jī)器學(xué)習(xí)理論的鏈接預(yù)測(cè)模型。給定一個(gè)網(wǎng)絡(luò)數(shù)據(jù)集，其訓(xùn)練集的先驗(yàn)類別（存在鏈接或者不存在）易知，所以該類模型的算法基本都是通過(guò)有監(jiān)督學(xué)習(xí)－分類的思想開(kāi)展，其主要分為以下幾類：關(guān)系圖模型［8］主要用可視化的方式（即圖的形式）表示較為抽象的隨機(jī)變量依賴關(guān)系，把鏈接產(chǎn)生可能性定義為概率，并通過(guò)圖的潛在知識(shí)進(jìn)行估計(jì)；基于貝葉斯的鏈接預(yù)測(cè)把產(chǎn)生鏈接的可能看成是給定特征和參數(shù)前提下的條件概率，并把該條件概率轉(zhuǎn)變?yōu)榉菂?shù)化學(xué)習(xí)［9］、最大間隔分類等問(wèn)題［10］和遷移學(xué)習(xí)模型［11］等。

本文研究?jī)深愵A(yù)測(cè)方向結(jié)合中所遇到的問(wèn)題——分類模型所獲取的特征不能完全反映復(fù)雜網(wǎng)絡(luò)的拓?fù)鋵傩浴D1是一個(gè)網(wǎng)絡(luò)圖模型，黑點(diǎn)代表節(jié)點(diǎn)，實(shí)線代表鏈接，虛線代表預(yù)測(cè)鏈接，點(diǎn)線代表共鄰節(jié)點(diǎn)之間的鏈接。從圖1可以看到，AB是預(yù)測(cè)鏈接，C、D、E是三個(gè)共鄰節(jié)點(diǎn)特征，對(duì)于圖1兩子圖中共鄰節(jié)點(diǎn)對(duì)的聯(lián)系，顯然子圖b比子圖a要緊密，所以其共鄰節(jié)點(diǎn)的屬性不一樣，那么其對(duì)AB預(yù)測(cè)的影響顯然也不一樣。所以，盡管兩圖共鄰節(jié)點(diǎn)數(shù)目的特征值均為3，但是由于其共鄰節(jié)點(diǎn)屬性不同，那么根據(jù)網(wǎng)絡(luò)聚集原理，子圖b中AB產(chǎn)生鏈接的可能性更大。因此，如何提取該類特征對(duì)分類學(xué)習(xí)顯示尤其重要。

Figure 1 Network model based on neighbors topology feature圖1 基于節(jié)點(diǎn)拓?fù)涮卣鞯木W(wǎng)絡(luò)模型

本文首先定義復(fù)雜網(wǎng)絡(luò)的具備不同特征的拓?fù)浣Y(jié)構(gòu)特征屬性，然后提出賦予具備不同屬性共同鄰接節(jié)點(diǎn)的貢獻(xiàn)權(quán)重的特征，結(jié)合不同分類模型下鏈接預(yù)測(cè)算法思想，通過(guò)對(duì)八個(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)比較其性能，同時(shí)分析不同特征對(duì)于預(yù)測(cè)結(jié)果的影響。

綜合來(lái)說(shuō)，本文的貢獻(xiàn)主要有以下三點(diǎn)：

（1）引入基于樸素貝葉斯算法LNB（Local Naive Bayesian）［12］共鄰節(jié)點(diǎn)的貢獻(xiàn)作為特征并給出基于節(jié)點(diǎn)、共鄰節(jié)點(diǎn)結(jié)構(gòu)屬性定義。

（2）解釋差異化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征對(duì)分類性能的影響。

（3）分析不同的有監(jiān)督－分類模型下鏈接預(yù)測(cè)的性能，給定不同噪音對(duì)預(yù)測(cè)性能的影響。

3 問(wèn)題定義

3.1 網(wǎng)絡(luò)定義

G＝（V，E，R）定義為復(fù)雜網(wǎng)絡(luò)的無(wú)向圖模型，V和E?V×V分別為模型中節(jié)點(diǎn)和鏈接的集合，R定義為網(wǎng)絡(luò)中的關(guān)系，節(jié)點(diǎn)u，v∈V形成的鏈接e∈E被認(rèn)為是R上定義的一個(gè)關(guān)系，其映射函數(shù)為：：V×V×R→E。其中（u，v）為節(jié)點(diǎn)對(duì)，Γ（u，v）＝Γ（u）∩Γ（v）為節(jié)點(diǎn)對(duì)的共鄰節(jié)點(diǎn)集合。

3.2 問(wèn)題描述

有監(jiān)督學(xué)習(xí)是經(jīng)典的機(jī)器學(xué)習(xí)思想，它利用一組已知類別的樣本調(diào)整分類器的參數(shù)，使其達(dá)到所要求分類性能的過(guò)程。給定一個(gè)網(wǎng)絡(luò)G，隨機(jī)移除20%的邊，剩下的作為訓(xùn)練集，記為GT，移除的邊作為預(yù)測(cè)集，記為GP，為了更好地獲取其分類性能，我們分別對(duì)GT和GP加上一組不屬于G且隨機(jī)生成的噪聲GN。分類模型的目的在于對(duì)訓(xùn)練集GT的學(xué)習(xí)獲取分類模型，并應(yīng)用到預(yù)測(cè)集GP中進(jìn)行鏈接預(yù)測(cè)。

3.3 數(shù)據(jù)集

為了評(píng)價(jià)算法的有效性，本文采用具備不同拓?fù)鋵傩缘陌藗€(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，該網(wǎng)絡(luò)涵蓋了社會(huì)、生物、電話、交通等各個(gè)領(lǐng)域的數(shù)據(jù)，其度分布均滿足Babárasi A L［13］提出的無(wú)尺度網(wǎng)絡(luò)分布—冪律分布，具體如圖2所示，同時(shí)各網(wǎng)絡(luò)的結(jié)構(gòu)屬性參照表1。

Figure 2 Degree distribution of true networks圖2 真實(shí)網(wǎng)絡(luò)的度分布

Table 1 Attributes of network structure表1 網(wǎng)絡(luò)結(jié)構(gòu)屬性表

表1中｜V｜和｜E｜是網(wǎng)絡(luò)的節(jié)點(diǎn)和鏈接數(shù)目，c＊、d＊和p＊分表代表聚類系數(shù)、平均度和平均路徑。

4 特征獲取和分類模型

4.1 基本拓?fù)浣Y(jié)構(gòu)特征獲取

特征是進(jìn)行分類學(xué)習(xí)的必要條件，結(jié)合本文定義，給定一個(gè)預(yù)測(cè)節(jié)點(diǎn)對(duì)，主要通過(guò)計(jì)算兩節(jié)點(diǎn)的屬性及其相似度屬性［4，12］獲取相關(guān)特征，該類特征分為節(jié)點(diǎn)和共鄰節(jié)點(diǎn)特征等幾類。

4.1.1 基于節(jié)點(diǎn)屬性的特征

（1）PA（Preferential Attachment）：PA 是 鏈接，趨向于出現(xiàn)在度比較高的節(jié)點(diǎn)對(duì)之間，其定義：

（2）CC（Clustering Coefficient）：CC是表示一個(gè)圖形中節(jié)點(diǎn)聚集程度的系數(shù)，由于相對(duì)高密度連接點(diǎn)的關(guān)系，鏈接總是趨向于出現(xiàn)在以下這樣一組嚴(yán)密的組織關(guān)系中［14］，定義為：

（3）PR（Page Rank）：PR 是Google用于標(biāo)識(shí)網(wǎng)頁(yè)的等級(jí)/重要性的一種方法，也適用于對(duì)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行排序，鏈接也是傾向于出現(xiàn)在排序較高的節(jié)點(diǎn)對(duì)之間，其公式和算法相對(duì)復(fù)雜，具體可參考［4］。

（4）Katz（Path Count）：計(jì)算兩個(gè)節(jié)點(diǎn)之間存在的路徑數(shù)目，定義為：

（5）APD（Average Path Distance）：計(jì)算兩個(gè)節(jié)點(diǎn)之間的平均路徑長(zhǎng)度：

4.1.2 基于共鄰節(jié)點(diǎn)的特征

該經(jīng)典特征通過(guò)計(jì)算兩節(jié)點(diǎn)共同鄰居ω的屬性獲得，本文主要通過(guò)其拓?fù)浣Y(jié)構(gòu)信息獲取相關(guān)特征：

（1）CN（Common Neighbors）：共鄰節(jié)點(diǎn)的數(shù)目：

（2）AA（Adamic－Adar）：共鄰節(jié)點(diǎn)度的對(duì)數(shù)分子和：

（3）RA （Resource Allocation）：共鄰節(jié)點(diǎn)度的分子和：

4.2 基于差分化節(jié)點(diǎn)貢獻(xiàn)的特征獲取

基于共鄰節(jié)點(diǎn)的相似度算法假設(shè)所有節(jié)點(diǎn)對(duì)預(yù)測(cè)節(jié)點(diǎn)對(duì)的貢獻(xiàn)權(quán)重視為一致，不利于區(qū)分具備不同屬性共鄰節(jié)點(diǎn)的角色及其貢獻(xiàn)。Liu Z 等人［12］提出可以把預(yù)測(cè)鏈接看成兩類分類模型，e和分別視為鏈接存在和不存在，并把其存在的概率定義為給定一組共鄰節(jié)點(diǎn)的條件概率P（e｜Γ（u，v））：

由于Γ（u，v）是共鄰節(jié)點(diǎn)的集合，直接計(jì)算較為困難，所以在此假設(shè)各個(gè)共鄰節(jié)點(diǎn)對(duì)預(yù)測(cè)鏈接的影響是獨(dú)立的，那么基于樸素貝葉斯的獨(dú)立性理論，式（1）可以轉(zhuǎn)變?yōu)橐韵聝蓚€(gè)公式：

在式（2）中，每一個(gè)共鄰節(jié)點(diǎn)對(duì)鏈接產(chǎn)生的影響由P（ωi｜e）或者給出，為了簡(jiǎn)化運(yùn)算，我們定義式（2）和式（3）的比率為共鄰節(jié)點(diǎn)的關(guān)系：

式（4）的左部分是網(wǎng)絡(luò)中鏈接的比率，右部分則為節(jié)點(diǎn)的貢獻(xiàn)：

Rω定義為節(jié)點(diǎn)的貢獻(xiàn)權(quán)重，其中e是（x，y）存在鏈接，為該節(jié)點(diǎn)的聚類系數(shù)，從而經(jīng)典的CN 算 法 改 進(jìn) 后 定 義 為L(zhǎng)NB－CN（Local Naive Bayesian Common Neighbors）：

同理，AA 和RA 形式的LNB特征如下所示：

LNB－AA（Local Naive Bayesian Common Adamic－Adar）：

LNB－RA（Local Naive Bayesian Resource Allocation）：

4.3 分類模型

有監(jiān)督學(xué)習(xí)是分類機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域最基本的模型，下面是本文使用的部分經(jīng)典算法模型：（1）線性判別分析LDA （Linear Discriminate Analysis）；（2）二次判別分析QDA（Quadratic Discriminate Analysis）；（3）樸素貝葉斯NB（Na?ve Bayesian）；（4）分類樹(shù)CT（Classification Tree）；（5）退化樹(shù)RT（Regression Tree）；（6）K 近鄰分類KNN（K－Nearest Neighbor）；（7）支持向量機(jī)SVM（Support Vector Machine）。

5 實(shí)驗(yàn)評(píng)價(jià)

5.1 實(shí)驗(yàn)評(píng)價(jià)模型

本實(shí)驗(yàn)基于Complex Networks Package for MatLab［15］平 臺(tái) 和Matlab 自 帶 的Machine learning包。預(yù)測(cè)精確度采用10－folder交叉驗(yàn)證方法進(jìn)行，交叉重復(fù)驗(yàn)證10次，每次隨機(jī)產(chǎn)生一個(gè)訓(xùn)練集GT和一個(gè)預(yù)測(cè)集GP作為測(cè)試集，并將10次的平均交叉驗(yàn)證precision作為評(píng)價(jià)指標(biāo)。precision指的是訓(xùn)練集中分類正確的數(shù)目和目標(biāo)集應(yīng)分類數(shù)目的比率。

實(shí)驗(yàn)首先比較各種特征的分類精確度，然后整合三類特征，比較各類有監(jiān)督分類模型的性能。

5.2 實(shí)驗(yàn)結(jié)果與分析

5.2.1 分類準(zhǔn)確度

從表2和圖3中的實(shí)驗(yàn)結(jié)果可以看出，判別分析（LDA，QDA）和KNN 的結(jié)果相對(duì)其他模型要好，其中LDA 為最優(yōu)分類器，其平均預(yù)測(cè)精確度達(dá)到0.819 6（見(jiàn)圖3a），同時(shí)，從圖3b 看出，Jazz數(shù)據(jù)集的分類準(zhǔn)確度是最高的，達(dá)到0.899 8，這是由于該網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征密度較高，其聚類系數(shù)和平均度分別達(dá)到0.64 和27.69，造成特征差異化明顯，從而提高了分類精確度；同時(shí)，該特性也使Facebook數(shù)據(jù)集的分類效果最差。

此外，我們?cè)陬A(yù)測(cè)集GP加上一組不屬于G且與其集合長(zhǎng)度有關(guān)并隨機(jī)生成的噪聲GN，實(shí)驗(yàn)中分別取GP概率0.1～0.9的九組噪聲進(jìn)行預(yù)測(cè)，實(shí)驗(yàn)結(jié)果參考圖3c。從圖3曲線的方向我們可以看出，分類精確度隨著噪聲數(shù)據(jù)集比率的增多而遞增，這是由于噪聲數(shù)據(jù)是隨機(jī)生成的一組不存在的鏈接集合，這些不存在（類別的0）的鏈接具備差異化較為明顯的特征，有助于分類模型更好地學(xué)習(xí)和劃分。

5.2.2 特征集選擇

復(fù)雜網(wǎng)絡(luò)的特征是分類的基礎(chǔ)，特征選擇的好壞對(duì)于分類的精度會(huì)產(chǎn)生重要的影響，本文分別針對(duì)基于節(jié)點(diǎn)信息、共鄰節(jié)點(diǎn)信息和鏈接路徑信息三類特征給出實(shí)驗(yàn)結(jié)果。從圖4a～圖4c可以看出，基于共鄰節(jié)點(diǎn)的特征分類精度最佳，達(dá)到0.76，其他兩類特征的精度則在0.7左右，這一結(jié)果也符合目前鏈接預(yù)測(cè)的研究方向，因?yàn)榛诠侧徆?jié)點(diǎn)相似度的方法一直都是既簡(jiǎn)單又有效的預(yù)測(cè)算法；同時(shí)也表明，本文引入的共鄰節(jié)點(diǎn)的角色及其貢獻(xiàn)作為特征的有效性。

Table 2 Comparison of link prediction precision of different classifiers表2 不同分類模型對(duì)鏈接預(yù)測(cè)精確度

Figure 3 Different feature prediction precision and relation functions圖3 特征預(yù)測(cè)精度及關(guān)系函數(shù)

Figure 4 Comparison of prediction precision of different classifiers圖4 不同分類器的分類精度比較

5.2.3 案例簡(jiǎn)介

圖5a 和圖5b 給出了各分類器對(duì)Metabolic——生物網(wǎng)絡(luò)的分類效果的ROC 曲線，圖5c則展示了最優(yōu)分類器LDA 對(duì)最有效的LNB－AA、LNB－RA 屬性分類器的效果。

Figure 5 Comparison of different classifiers Metabolic networks圖5 各分類器對(duì)Metabolic網(wǎng)絡(luò)的預(yù)測(cè)分類

6 結(jié)束語(yǔ)

本文研究了基于復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征的有監(jiān)督學(xué)習(xí)－分類模型的問(wèn)題。主要引入了樸素貝葉斯模型定義的共鄰節(jié)點(diǎn)貢獻(xiàn)作為網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征進(jìn)行學(xué)習(xí)和分類，同時(shí)探討了有監(jiān)督學(xué)習(xí)模型對(duì)鏈接預(yù)測(cè)性能的影響。八個(gè)真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)表明，提出的LNB特征有較優(yōu)的分類預(yù)測(cè)性能，同時(shí)發(fā)現(xiàn)差異化的特征選擇在不同的分類模型下預(yù)測(cè)效果存在一定的規(guī)律。但是，本文的實(shí)驗(yàn)數(shù)據(jù)網(wǎng)絡(luò)都是同構(gòu)的，分析分類模型對(duì)異構(gòu)和多維網(wǎng)絡(luò)的預(yù)測(cè)性能是下一步需要開(kāi)展的工作。

［1］ Samuel L.Social networks：A developing paradigm［M］.New York：Academic Press，1977.

［2］ Wasserman S，F(xiàn)aust K.Social network analysis：Methods and applications［M］.Cambridge：Cambridge University Press，1994.

［3］ Leskovec J，Huttenlocher D，Kleinberg J.Predicting positive and negative links in online social networks［C］∥Proc of the 19th International Conference on World Wide Web，2010：641－650.

［4］ Liben－Nowell D，Kleinberg J.The link prediction problem for social networks［J］.Journal of the American Society for Information Science and Technology，2007，58（7）：1019－1031.

［5］ Al Hasan M，Chaoji V，Salem S，et al.Link prediction using supervised learning［C］∥Proc of Workshop on Link Analysis，Counterterrorism and Security，2006：1.

［6］ Donghyuk S，Si Si，Dhillon I S.Multi－scale link prediction［EB/OL］.［2012－04－08］.http：arxiv.org/abs/1206.1891.

［7］ Valverde－Rebaza J C，de Andrade Lopes A.Link prediction in complex networks－based on cluster information［C］∥Proc of SBIA’12，2012：92－101.

［8］ Popescul A，Ungar L H.Statistical relational learning for link prediction［C］∥Proc of IJCAI Workshop on Learning Statistical Models from Relational Data，2003：1.

［9］ Miller K，Griffiths T，Jordan M.Nonparametric latent feature models for link prediction［C］∥Proc of Advances in Neural Information Processing Systems，2009：1276－1284.

［10］ Zhu J.Max－margin nonparametric latent feature models for link prediction［EB/OL］.［2012－12－10］.http：arxiv.rog/abs/1206.4659.

［11］ Cao B，Liu N N，Yang Q.Transfer learning for collective link prediction in multiple heterogenous domains［C］∥Proc of the 27th International Conference on Machine Learning，2010：159－166.

［12］ Liu Z，Zhang Q M，LüL，et al.Link prediction in complex networks：A local na?ve Bayes model［J］.EPL（Europhysics Letters），2011，96（4）：48007.

［13］ Barabási A L，Réka A.Emergence of scaling in random networks［J］.Science，1999，286：509－512.

［14］ Feng X，Zhao J C，Xu K.Link prediction in complex networks：A clustering perspective［J］.The European Physical Journal B，2012，85（1）：1－9.

［15］ http：//www.levmuchnik.