差分化節點特征對復雜網絡鏈接預測的分類性能分析＊

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

（1.廣東工貿職業技術學院計算機工程系，廣東 廣州510510；2.華南理工大學信息科學與技術學院，廣東 廣州510641；3.暨南大學信息科學與技術學院，廣東 廣州510632）

1 引言

復雜網絡分析［1］是數據挖掘和機器學習領域其中一個非常活躍的研究方向，其主要通過學習網絡中實體及其相互之間的活動關系，發掘其中內在的知識。而該類關系和活動可以用網絡或者圖的結構［2］來表示，其中節點（頂點）表示一個實體，鏈接（邊）表示兩個實體之間的關系，利用網絡圖我們可以挖掘其結構特征并找出感興趣的信息，社區發現、信息傳播、節點分類等都是復雜網絡分析研究的方向，本文主要針對鏈接預測這一領域開展研究。

鏈接預測根據網絡的歷史結構信息預測其演化方式及鏈接關系發生的潛在可能，其在眾多領域有著重要的應用價值。例如，通過分析生物信息網絡，預測氨基酸內蛋白質的相互作用；在社交網絡中預測現在尚未成為朋友的未來是否“應該是朋友”［3］；在市場營銷網絡中判斷哪些客戶應該需要去開發等等。

2 相關工作

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

本文研究兩類預測方向結合中所遇到的問題——分類模型所獲取的特征不能完全反映復雜網絡的拓撲屬性。圖1是一個網絡圖模型，黑點代表節點，實線代表鏈接，虛線代表預測鏈接，點線代表共鄰節點之間的鏈接。從圖1可以看到，AB是預測鏈接，C、D、E是三個共鄰節點特征，對于圖1兩子圖中共鄰節點對的聯系，顯然子圖b比子圖a要緊密，所以其共鄰節點的屬性不一樣，那么其對AB預測的影響顯然也不一樣。所以，盡管兩圖共鄰節點數目的特征值均為3，但是由于其共鄰節點屬性不同，那么根據網絡聚集原理，子圖b中AB產生鏈接的可能性更大。因此，如何提取該類特征對分類學習顯示尤其重要。

Figure 1 Network model based on neighbors topology feature圖1 基于節點拓撲特征的網絡模型

本文首先定義復雜網絡的具備不同特征的拓撲結構特征屬性，然后提出賦予具備不同屬性共同鄰接節點的貢獻權重的特征，結合不同分類模型下鏈接預測算法思想，通過對八個真實網絡進行實驗比較其性能，同時分析不同特征對于預測結果的影響。

綜合來說，本文的貢獻主要有以下三點：

（1）引入基于樸素貝葉斯算法LNB（Local Naive Bayesian）［12］共鄰節點的貢獻作為特征并給出基于節點、共鄰節點結構屬性定義。

（2）解釋差異化的網絡拓撲結構特征對分類性能的影響。

（3）分析不同的有監督－分類模型下鏈接預測的性能，給定不同噪音對預測性能的影響。

3 問題定義

3.1 網絡定義

G＝（V，E，R）定義為復雜網絡的無向圖模型，V和E?V×V分別為模型中節點和鏈接的集合，R定義為網絡中的關系，節點u，v∈V形成的鏈接e∈E被認為是R上定義的一個關系，其映射函數為：：V×V×R→E。其中（u，v）為節點對，Γ（u，v）＝Γ（u）∩Γ（v）為節點對的共鄰節點集合。

3.2 問題描述

有監督學習是經典的機器學習思想，它利用一組已知類別的樣本調整分類器的參數，使其達到所要求分類性能的過程。給定一個網絡G，隨機移除20%的邊，剩下的作為訓練集，記為GT，移除的邊作為預測集，記為GP，為了更好地獲取其分類性能，我們分別對GT和GP加上一組不屬于G且隨機生成的噪聲GN。分類模型的目的在于對訓練集GT的學習獲取分類模型，并應用到預測集GP中進行鏈接預測。

3.3 數據集

為了評價算法的有效性，本文采用具備不同拓撲屬性的八個真實網絡進行實驗，該網絡涵蓋了社會、生物、電話、交通等各個領域的數據，其度分布均滿足Babárasi A L［13］提出的無尺度網絡分布—冪律分布，具體如圖2所示，同時各網絡的結構屬性參照表1。

Figure 2 Degree distribution of true networks圖2 真實網絡的度分布

Table 1 Attributes of network structure表1 網絡結構屬性表

表1中｜V｜和｜E｜是網絡的節點和鏈接數目，c＊、d＊和p＊分表代表聚類系數、平均度和平均路徑。

4 特征獲取和分類模型

4.1 基本拓撲結構特征獲取

特征是進行分類學習的必要條件，結合本文定義，給定一個預測節點對，主要通過計算兩節點的屬性及其相似度屬性［4，12］獲取相關特征，該類特征分為節點和共鄰節點特征等幾類。

4.1.1 基于節點屬性的特征

（1）PA（Preferential Attachment）：PA 是 鏈接，趨向于出現在度比較高的節點對之間，其定義：

（2）CC（Clustering Coefficient）：CC是表示一個圖形中節點聚集程度的系數，由于相對高密度連接點的關系，鏈接總是趨向于出現在以下這樣一組嚴密的組織關系中［14］，定義為：

（3）PR（Page Rank）：PR 是Google用于標識網頁的等級/重要性的一種方法，也適用于對復雜網絡節點進行排序，鏈接也是傾向于出現在排序較高的節點對之間，其公式和算法相對復雜，具體可參考［4］。

（4）Katz（Path Count）：計算兩個節點之間存在的路徑數目，定義為：

（5）APD（Average Path Distance）：計算兩個節點之間的平均路徑長度：

4.1.2 基于共鄰節點的特征

該經典特征通過計算兩節點共同鄰居ω的屬性獲得，本文主要通過其拓撲結構信息獲取相關特征：

（1）CN（Common Neighbors）：共鄰節點的數目：

（2）AA（Adamic－Adar）：共鄰節點度的對數分子和：

（3）RA （Resource Allocation）：共鄰節點度的分子和：

4.2 基于差分化節點貢獻的特征獲取

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

由于Γ（u，v）是共鄰節點的集合，直接計算較為困難，所以在此假設各個共鄰節點對預測鏈接的影響是獨立的，那么基于樸素貝葉斯的獨立性理論，式（1）可以轉變為以下兩個公式：

在式（2）中，每一個共鄰節點對鏈接產生的影響由P（ωi｜e）或者給出，為了簡化運算，我們定義式（2）和式（3）的比率為共鄰節點的關系：

式（4）的左部分是網絡中鏈接的比率，右部分則為節點的貢獻：

Rω定義為節點的貢獻權重，其中e是（x，y）存在鏈接，為該節點的聚類系數，從而經典的CN 算 法 改 進 后 定 義 為LNB－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 分類模型

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

5 實驗評價

5.1 實驗評價模型

本實驗基于Complex Networks Package for MatLab［15］平 臺 和Matlab 自 帶 的Machine learning包。預測精確度采用10－folder交叉驗證方法進行，交叉重復驗證10次，每次隨機產生一個訓練集GT和一個預測集GP作為測試集，并將10次的平均交叉驗證precision作為評價指標。precision指的是訓練集中分類正確的數目和目標集應分類數目的比率。

實驗首先比較各種特征的分類精確度，然后整合三類特征，比較各類有監督分類模型的性能。

5.2 實驗結果與分析

5.2.1 分類準確度

從表2和圖3中的實驗結果可以看出，判別分析（LDA，QDA）和KNN 的結果相對其他模型要好，其中LDA 為最優分類器，其平均預測精確度達到0.819 6（見圖3a），同時，從圖3b 看出，Jazz數據集的分類準確度是最高的，達到0.899 8，這是由于該網絡的拓撲結構特征密度較高，其聚類系數和平均度分別達到0.64 和27.69，造成特征差異化明顯，從而提高了分類精確度；同時，該特性也使Facebook數據集的分類效果最差。

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

5.2.2 特征集選擇

復雜網絡的特征是分類的基礎，特征選擇的好壞對于分類的精度會產生重要的影響，本文分別針對基于節點信息、共鄰節點信息和鏈接路徑信息三類特征給出實驗結果。從圖4a～圖4c可以看出，基于共鄰節點的特征分類精度最佳，達到0.76，其他兩類特征的精度則在0.7左右，這一結果也符合目前鏈接預測的研究方向，因為基于共鄰節點相似度的方法一直都是既簡單又有效的預測算法；同時也表明，本文引入的共鄰節點的角色及其貢獻作為特征的有效性。

Table 2 Comparison of link prediction precision of different classifiers表2 不同分類模型對鏈接預測精確度

Figure 3 Different feature prediction precision and relation functions圖3 特征預測精度及關系函數

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

5.2.3 案例簡介

圖5a 和圖5b 給出了各分類器對Metabolic——生物網絡的分類效果的ROC 曲線，圖5c則展示了最優分類器LDA 對最有效的LNB－AA、LNB－RA 屬性分類器的效果。

Figure 5 Comparison of different classifiers Metabolic networks圖5 各分類器對Metabolic網絡的預測分類

6 結束語

本文研究了基于復雜網絡拓撲結構特征的有監督學習－分類模型的問題。主要引入了樸素貝葉斯模型定義的共鄰節點貢獻作為網絡的拓撲結構特征進行學習和分類，同時探討了有監督學習模型對鏈接預測性能的影響。八個真實網絡的實驗表明，提出的LNB特征有較優的分類預測性能，同時發現差異化的特征選擇在不同的分類模型下預測效果存在一定的規律。但是，本文的實驗數據網絡都是同構的，分析分類模型對異構和多維網絡的預測性能是下一步需要開展的工作。

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

［2］ Wasserman S，Faust 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.