鏈路預測算法在藥物推薦中的應用研究?

王秋杰 尹心明

（1.廣東工業大學計算機學院 廣州 510006）（2.公安部第三研究所信息安全技術部 上海 201204）

1 引言

社會網絡是一種用于描述現實生活中目標、個體、組織和社區之間模型關系的拓撲結構。我們在不同區域或者不同方式上遇到的許多復雜系統可以通過社會網絡實現可視化［1］。社會網絡是我們了解這些復雜系統的結構、發展和關系的工具。復雜系統的網絡分析能夠幫助提供較多有價值的信息，同時這些信息能為后續更深層的研究提供支撐。

鏈路預測主要用來分析網絡未來演化的狀態，主要借助網絡中節點的特征和已觀察到的連接來預測兩個節點間將來產生連接的概率［2］。其中，社交網絡過去的狀態是分析網絡未來狀態以及確定網絡可能產生哪些新變化的基礎。

在個體之間、社團之間和組織之間的社會關系是會隨著時間的推移發生變化。因此，模擬這些現實世界關系的社交網絡也會隨之發生變化，并且隨著這些關系的變化會產生一定程度的演化。在社會網絡的動態演變中，新的鏈路、節點可以加入到現有的網絡中，同時現有的鏈路、節點也可能從網絡中消失。鏈路預測主要用于確定社交網絡中各目標之間的動態關系。鏈路預測能夠應用在不同的領域［3～6］。例如，在學術研究網絡中，鏈路預測可以幫助找到某項學術研究的共同作者；在網購網絡中，鏈路預測可以幫助客戶推薦產品；在蛋白質作用網絡中，鏈路預測可以幫助預測蛋白質的相互作用；另外，鏈路預測可以幫助預估未來文章的引用，判定人們的活動并加以歸類，以及判定疾病之間的關系。

本文的首要目的是通過現有數據來創建疾病-藥物網絡，這些數據是從www.drugs.com上獲取的，主要是關于哪些藥物可以治愈哪些疾病的數據。建立好這個網絡后，我們可以通過鏈路預測方法確定給定的藥物可用于治愈哪些疾病。本文提出的內部鏈路方法可便于預測疾病-藥物網絡中的鏈路。為了分析提出方法的效果，我們選擇四種基于相似性的鏈路預測算法對該網絡進行預測。同時將內部鏈路方法的結果與四種基于相似性鏈路預測方法的結果進行對比。實驗結果表明提出的方法在精準度、召回率和F-測度準則方面取得更好的結果。

2 鏈路預測問題

社交網絡中的鏈路預測主要用來預測網絡的未來結構，同時該網絡被定義為一張拓撲圖。用節點表示網絡中的數據，用鏈路表示關系。判定未連接鏈路將來的連接狀態是鏈路預測的主要研究內容，并通過鏈路預測算法為每個可能被連接的節點對分配一定的預測分數值。一對節點之間計算出來的預測分數值越高，這對節點未來連接的可能性越大。根據預測分數值的大小排列預測連邊，排在前面的連邊是將來最可能產生連接的鏈路。預測的準確性隨著使用算法的變化而變化。

二分社會網絡是社會網絡的一種特殊形式。在二分社會網絡中，節點位于兩個不同的集群上。預測鏈路僅存在于不同集群的節點之間。同一個集群的節點中沒有鏈路。在實際應用中，很多社會網絡都有二分網絡的結構［7～9］。由于大多數鏈路預測方法都是針對單一模式的網絡結構，傳統的鏈路預測算法很難直接應用到二分網絡中。因此，基于先前的研究，本文首先將二分社會網絡的鏈路預測轉化為單一模式社會網絡的鏈路預測。

在圖1（a）表示的二分圖形中，將僅包含 X節點的單一模式圖表示為X-投影，同時將僅包含Y節點的單一模式圖表示為Y-投影。如果二分圖中的任何兩個X節點與相同的Y節點建立鄰域關系，那么這兩個節點在 X投影中就建立一條鏈路。例如，由于 X1和 X2節點與圖1（a）中的Y1節點連接，因此，X投影中建立了圖1（b）所示的 X1和X2節點之間的鏈路。

把二分網絡轉變為單一模式的網絡最簡單的方法是不考慮網絡的權重，即不考慮節點間的合作頻率關系，直接建立未加權的網絡。然而，由于單一模式的網絡與二分社會網絡相比包含較少的有用信息，因此圖1展示的二分網絡被轉換成加權的單一模式的網絡。本文根據合作關系的數量來給單一模式的網絡賦予權重。例如在圖1中，X投影上的X1和X2節點之間的權重被設為1。這是因為在二分網絡中這兩個節點之間有一個共同的鄰居節點Y1，即Y1與 X1和 X2在原圖中連接。本文將這種加權方式稱為加權函數［10］，并且表示為

3 相關工作

迄今為止，提出了很多鏈路預測的方法。這些方法大都是基于相似性的鏈路預測方法［11～12］。基于相似性鏈路預測方法的基本理念是x節點和y節點的鄰居節點交集越大，它們將來連接的可能性就越大。本文設定x和y是網絡中的節點，Γ()x和Γ()

y是網絡中x節點和 y節點鄰居節點的集合。四個最常用的基于相似性的鏈路預測方法如下。

1）Common Neighbors（CN）:這種相似性指標的前提假設是兩個節點將來產生連邊的概率正比于這兩個節點的共同鄰居數［13］。由于簡單，因此在鏈路預測問題中是應用最為廣泛的相似性指標之一，其數學公式如下:

2）Jaccard Coefficient（JC）:Jaccard Coefficient是公共近鄰相似性方法的一種標準化形式［14］。它指的是x和 y節點共同鄰居的數量占x和 y節點鄰居數量總和的比例。其中，公共近鄰的數量越大，該相似性方法得到的分值越大。其數學公式如下:

3）Admic/Adar（AA）:這種方法最初是由Adamic和Adar提出的，它的主要目的是為了計算兩個網頁之間的相似性［15］。該方法的基本思想是度小的共同鄰居節點的貢獻大于度大的共同鄰居節點。因此，AA指標根據共同鄰居節點的度為每個節點賦予一個權重值，并且該權重等于該節點的度的對數分支一，即AA指標定義為

4）Preferential Attachment（PA）:這種相似性指標的前提假設是網絡中兩個節點建立新連接的概率與x節點的鄰居數成正比［16］。從另一方面來說，擁有很多近鄰的節點更有可能建立新的連接。紐曼［17］認為在合作網絡中x節點和 y節點合作的可能性與x和y合作者的數量成正比。其數學公式如下:

4 提出的方法

在本次研究中，建立藥物-疾病網絡所需的數據從www.drugs.com中獲得。這個網站包含的信息有針對疾病撰寫的藥物，偏愛這些藥物的用戶百分比、藥物分類、懷孕類別等信息。藥物-疾病網絡上的節點代表了藥物和疾病。在三種最普遍的治病藥物之間建立連接。假設其他藥物使用的百分比較低，并且對應的鏈路不包含在其中。表1展示了從該網站上接收數據的一個特定部分。

根據表1的疾病-藥物關系，我們建立了一個以藥物和疾病為節點集群的二分網絡。圖2是我們選擇疾病和每種疾病使用率最高的前三種藥物之間建立鏈路構造的網絡范例圖。本研究的目的是基于現有的藥物-疾病關系，再通過相關的鏈路預測方法預測哪種藥物可以被寫成與某疾病對應的藥物。

表1 使用數據的一部分

圖2 藥物-疾病網絡范例

與傳統方法不同，研究者們基于二分網絡也提出了許多鏈路預測方法［18～20］。本文為疾病-藥物二分網絡中的鏈路預測提出了內部鏈路方法。在這種方法中，定義了一種稱為內部鏈路的私有鏈路，并根據這些鏈路作出鏈路預測。二分網絡被轉化為一種加權的單模式網絡后，表示原網絡中內部鏈路的連接已被確定。在一個二分網絡中，一個尚不存在連接的節點對被選擇。如果這對節點之間建立的鏈路不造成投影圖拓撲的改變，則被選節點之間的鏈路被稱為內部鏈路。

本文提出的內部鏈路主要是指那些在二分網絡中尚不存在連接的鏈路，并且滿足當它們之間添加連接后，該二分網絡的投影圖不會發生變化。在我們的研究中，所有已知的鏈路都不能被稱為內部鏈路。同時，為了確保重要的鏈路不被丟失且不必要的鏈路不被考慮，本文設定了一個閾值。其中，將那些權重值大于設定閥值的鏈路認定為內部鏈路。

5 實驗結果

本文主要在藥物-疾病網絡中對提到的算法進行性能分析。另外，這類網絡數據能夠從www.drugs.com官網上獲取。本文所選取的網絡總共包含500條邊。為了測試相關算法的預測準確性，本文隨機選取其中100條邊作為測試集，另外400條鏈路作為訓練集。緊接著基于該疾病-藥物網絡，本文采用提到的算法進行鏈路預測。另外在尚未建立連邊的節點間查找內部鏈路，同時將那些權重值高于預設閾值的鏈路定義為內部鏈路。緊接著，將已發現的內部鏈路按照權重值的大小進行排序，并選擇權重排在前100的鏈路。本文為了對提到方法的預測效果進行對比分析，我們選擇先前提到的四個基于相似性的方法進行疾病-藥物二分網絡的鏈路預測。計算出每個在訓練集中不相連節點對的分數值。與先前研究類似，這個分數值代表的是節點x和y之間的相似性。預測分數值越高意味著當前缺失的鏈路在將來出現的可能性就越大。另外，為了進行預測效果的對比，本文將公共鄰近（CN）、杰卡德系數（JC）、優先連接（PA）和Adamic/Adar（AA）等方法作為分數值的計算函數。將所有的預測鏈路按照預測分數值的大小進行降序排列，并且篩選出分數值較高的前100個鏈路作為預測結果。最后我們將本文提到的內部鏈路算法（IL）、共同鄰居算法（CN）、杰卡德系數算法（JC）、優先連接算法（PA）和Adamic/Adar算法（AA）的預測鏈路與先前提取的測試集數據進行對比分析。同時，本文選擇預測準確度、召回率和F-測度這三項指標作為性能評估準則。圖3顯示了五種不同方法在預測準確度、召回率和F-測度這三方面的性能比較結果。由圖3可得，所提出的方法在三項指標中均體現出最高的預測效果。與其他四個基于相似性的鏈路預測算法相比，本文提出的算法具有更高的刪除鏈路恢復效果。綜上所述，根據所獲得的預測結果，本文提出的算法具有較高的預測成功率，能夠更方便地預測哪種藥物可以用于治愈某種疾病。

6 結語

迄今為止，二分網絡中的鏈路預測已經成為很多學術領域的研究焦點。不同領域的研究者加大了對這個課題的研究。近些年關于二分網絡的鏈路預測大多集中在疾病-藥物網絡中。通常可以從網站（www.drugs.com）上獲取藥物推薦關系的網絡數據集，該網絡數據集是一個二分網絡。與單一模式網絡中的鏈路預測相比，二分網絡中的預測鏈路是一個更難更復雜的任務。另外，基于單一模式網絡的鏈路預測算法不能直接用于預測二分網絡。因此，為了能夠更好地實現二分網絡的鏈路預測，首先需要將現有的二分網絡轉化為單一模式的網絡。與其他經典算法相比，獲得較高預測準確性的的內部鏈路方法能夠較好地應用于疾病-藥物網絡中。同樣，公共鄰居、杰卡德系數（JC）、優先連接（PA）和Adamic/Adar（AA）等基于相似性的鏈路預測方法也已經被應用于二分網絡中。當考慮到五種不同方法的預測效果，哪種藥物可用來治療哪種疾病已經取得了一定的突破。

圖3 五種不同方法的效果對比