基于自動學習機的社會網絡鏈路預測算法

盧 文 趙海興 衛(wèi) 良 李發(fā)旭

1(陜西師范大學計算機科學學院 陜西 西安 710119) 2(青海師范大學計算機學院 陜西 西寧 810008) 3(青海省藏文信息處理與機器翻譯重點實驗室 陜西 西寧 810008) 4(藏文信息處理教育部重點實驗室 陜西 西寧 810008)

0 引 言

社會網絡分析已經成為網絡科學和社會網絡研究者們的重要工作，例如輿情網絡、犯罪網絡、在線社交網絡和科研合作網絡等[1]。研究者們通過對網絡的分析，可以利用人際關系、事物關系、人與事物之間的關系，探索網絡的性質和網絡的演化規(guī)律，提供可靠的決策建議。近年來，在經濟快速發(fā)展和“大數據”時代的社會背景下，社會網絡呈現(xiàn)出了更強的動態(tài)性特征。在這種動態(tài)社會網絡中，一個新關系的出現(xiàn)往往具有重要影響意義，它不僅可以改變網絡的性質還可以影響網絡的演化[2]。例如在謠言傳播網絡中，兩個人從素不相識變成了無話不談的朋友，這代表該網絡中出現(xiàn)了一個新關系，也意味著可能增加了一條謠言傳播路徑，其結果將會擴大謠言的傳播范圍，加快謠言的傳播速度[3]；在犯罪網絡中，兩個罪犯從不認識到認識，這意味著他們以后共同犯罪的可能性會很大[4]；兩位不同研究背景的科研人員共同發(fā)表了一篇論文，這代表著其中一位研究者的研究方向可能發(fā)生了變化[5]。由此不難看出，預測這種新關系的出現(xiàn)是社會網絡分析中一項具有重大意義的工作。為了更好地開展此項研究工作，研究者們將社會網絡抽象為一個復雜網絡，用網絡中的節(jié)點表示人，用邊表示人們之間的關系，將一個新關系的產生建模為鏈路預測[5-6]。

鏈路預測(Link Prediction)作為復雜網絡的研究方向之一，它的主要目的是根據已知網絡特征信息預測出該網絡在未來將要出現(xiàn)的連邊[5]。近年來，鏈路預測根據自身的這一功能優(yōu)勢已成為社會網絡分析中的一個重要工具[4，7]。在電子商務中，鏈路預測可以依據用戶在商務活動中的行為特點為用戶推薦合適的產品[8]，同樣也可以利用它在一個社交網絡中給用戶推薦好友[9]。通過分析疾病-人群、人群-人群之間的特征關系，將傳染病網絡映射為一個二分網絡，鏈路預測可以預測出哪些人被傳染的可能性較高[10]。在消息傳播網絡中，通過對信息傳播機制的分析，預測出了用戶轉發(fā)信息的行為,這對掌握社會輿論形成的規(guī)律具有重要意義[11]。在以上工作中，鏈路預測僅提取了目標網絡在某一時刻的靜態(tài)網絡特征。為進一步提升鏈路預測在動態(tài)網絡中的表現(xiàn)，研究者們將機器學習應用到了鏈路預測中并作出了一些貢獻[12]。Pujari等[13]通過監(jiān)督學習的方式對網絡邊的排序進行動態(tài)聚合，并將此結果作為鏈路預測的依據。Bütün等[14]基于監(jiān)督學習提出了一種通過模式識別進行鏈路預測的方法。陳可佳等[15]將鏈接預測轉化為一個二分類問題，使用半監(jiān)督學習利用網絡中的未標記數據對算法進行訓練。Bliss等[16]利用基于協(xié)方差矩陣的自適應進化策略來預測未來連邊。Shahmohammadi等[17]提出了“協(xié)作路徑”的思想，并在此基礎上改進了四種有向相似性預測算法。Bringmann等[18]提出了一種基于關聯(lián)規(guī)則挖掘和模式頻度檢測技術的鏈路預測算法，該算法在特定社會網絡，如在校園電子郵件網絡中有較好的表現(xiàn)。目前基于機器學習的鏈路預測算法研究存在的主要問題包括：(1)需要掌握的網絡信息過多且通常是全局的，預測結果容易受到網絡結構變化的影響；(2)在提取網絡動態(tài)特征時，忽略了對網絡演化起到關鍵作用的基本結構；(3)沒有根據不同的動態(tài)網絡結構特征選擇一種與之相適應的機器學習方法。本文受目前工作的啟發(fā)，提出一種基于自動學習機的社會網絡鏈路預測算法(LA-SNLP)。

自動學習機(Learning Automata，LA)是一個自適應決策制定機制，它通過自身與隨機環(huán)境的交互學習調整行為輸出，直到輸出最優(yōu)結果。即在每一個時間步中，學習機會向隨機環(huán)境輸入一個從有限行為集中選擇的行為，隨后隨機環(huán)境產生反饋，根據這個反饋學習機會調整行為集合并再次選擇一個其他行為輸入給隨機環(huán)境，如此反復，直到隨機環(huán)境接收到了一個合適的行為輸入為止[19]。自動學習機具有算法較簡潔、易讀性和擴展性較強的優(yōu)點，目前在不同領域中已有了一些應用[20]。Gheisari等[21]在物聯(lián)網中提出了一種基于數據感知的擁塞控制方法，提高了節(jié)點與邊界路由之間數據傳輸的可靠性。Irandoost等[22]基于自動學習機提出了一種還原分布式計算系統(tǒng)邊緣扭曲數據的方法，提高了全局協(xié)同計算效率。Javadia等[23]利用自動學習機學習無線傳感器網絡的拓撲結構，優(yōu)化了節(jié)點間數據轉發(fā)的路由策略，有效延長了網絡壽命。模體(Motif，mtf )是網絡的子圖，通常由三個或四個節(jié)點組成[24-25]。Juszczyszyn等[26-27]研究表明，掌握了模體的轉化規(guī)律就意味著掌握了網絡的演化規(guī)律，而在眾多的模體類型中，三元組模體(簡記為三元組)是社會網絡中的一個重要基本結構，三元組的轉化在動態(tài)社會網絡的演化中起到了決定性的作用。其中三元閉包是一種更為特殊的三元組，如果一個節(jié)點包含在一個或多個三元閉包中，那么該節(jié)點的聚類系數和重要性就比其他沒有包含在三元閉包中的普通節(jié)點高[28]。

針對動態(tài)社會網絡中的鏈路預測，在本文所提出的LA-SNLP算法中，首次將自動學習機與三元組相結合。以不同類型的三元組轉化作為預測的重要依據，以節(jié)點包含三元閉包的數量為參數提出了六種三元組內節(jié)點相似性指標，利用自動學習機“學習-選擇-反饋”簡潔而又高效的學習機制學習并生成了動態(tài)社會網絡中以三元組為單位的待預測節(jié)點對集合，實現(xiàn)了在動態(tài)社會網絡中的鏈路預測。仿真實驗表明，本文所提出的六種相似性指標的預測準確度和穩(wěn)定性要好于Common Neighbor、Salton、Jaccard、Preferential Attachment、Adamic Adar和Resource Allocation六種常用的預測指標，達到了理想的預測結果。本文算法在社會網絡的分析工作中具有實際應用價值。

1 相關概念與基礎工作

1.1 鏈路預測

定義G(V,E)為一個無向無環(huán)網絡，其中：V為節(jié)點集；E為邊集；U為邊全集，該網絡中共有(N(N-1))/2條邊。鏈路預測的任務是計算出每個沒有連邊節(jié)點對cnp(x,y)∈(U-E)的分值Sxy，并依據此分值預測出網絡在未來將要出現(xiàn)的連邊[4]。一個在時間[t,t′]中的動態(tài)社會網絡，鏈路預測會根據t時刻的網絡特征，預測出該網絡在t′時刻將要出現(xiàn)的連邊[7]。為了訓練和測試一個鏈路預測算法，通常會將網絡的邊集E按比例劃分為訓練集ET和測試集EP(E=ET∪EP且ET∩EP=?)，預測算法僅在測試集中執(zhí)行[4]。

目前，在多種不同的鏈路預測算法中，基于局部相似性算法具有在僅掌握少量局部信息的基礎上就能獲得較好預測效果的優(yōu)勢，因此LA-SNLP算法采用這種算法作為主要參考依據。以下是六種常用的基于局部相似性的鏈路預測指標[29-31]。

(1)共同鄰居(Common Neighbor,CN)指標：如果兩個節(jié)點x和y擁有更多的共同鄰居節(jié)點，則代表它們之間出現(xiàn)連邊的可能性更高。

Sxy=|Γ(x)∩Γ(y)|

(1)

式中：Γ(x)為節(jié)點x的共同鄰居節(jié)點。

(2)Salton指標，又稱為余弦相似性指標。

(2)

式中：kx為節(jié)點x的度。

(3)Jaccard指標，該指標在比較有限樣本集之間的相似性和差異性上有著較為突出的表現(xiàn)。

(3)

(4)Preferential Attachment(PA)指標：在一個無標度網絡中，節(jié)點對之間出現(xiàn)新邊的概率與它們自身的度成正比。

Sxy=kxky

(4)

(5)Adamic Adar(AA)指標：度小的共同鄰居節(jié)點的貢獻大于度大的共同鄰居節(jié)點。也就是說在一個社會網絡中，不同的兩個人在眾多關注點中同時都關注了一個不太流行的小眾關注點，則說明這兩人有著更加相似的共同興趣，今后他們之間出現(xiàn)聯(lián)系的可能性會很大。

(5)

(6)Resource Allocation(RA)指標：假設每個源節(jié)點都有一定數量的資源并將此資源通過媒介進行傳輸，哪個目標節(jié)點得到的資源數越多，就代表這個目標節(jié)點和源節(jié)點的相似性越高，它們之間出現(xiàn)連邊的可能性也就越高。

(6)

預測算法采用鄰接矩陣和相似度矩陣存儲網絡結構和節(jié)點間的相似性分值。以下為這兩個矩陣的定義：

定義1鄰接矩陣A∈Rn×n，其中n為網絡節(jié)點數。A(x,y)=1表示節(jié)點x與節(jié)點y之間存在連邊；A(x,y)=0則表示它們之間不存在連邊。

定義2相似度矩陣S∈Rn×n，其中n為網絡節(jié)點數。矩陣元素表示兩個節(jié)點的相似性分值。

1.2 三元組模體

模體是網絡的子圖，也是網絡中經常出現(xiàn)且相互作用的基本結構。三元組是一種較為常見且能夠影響社會網絡演化的重要結構[26-27]。本文所提出的LA-SNLP算法是基于無向社會網絡的，所以僅對無向三元組進行說明。在一個無向網絡中，由三個節(jié)點組成的三元組共有兩種類型[32]，如圖1(a)和圖1(b)所示。圖1(b)是一種特殊的三元結構，稱作三元閉包(Tri-closure)。

圖1 無向網絡中的三元組

從圖1中不難看出，一個三元組由(a)轉化到(b)時，會產生一條新邊。LA-SNLP算法的預測依據正是利用了這種轉化。

1.3 自動學習機

自動學習機(LA)是一個由學習機和隨機環(huán)境組成的自適應決策制定機制。通過學習機與隨機環(huán)境反復交互學習不斷更新自身的行為輸出，最終得到一個適合于隨機環(huán)境的最好行為[17-18]。在LA的運行過程中，學習機會根據一個選擇標準從一個有限的行為集中選擇一個行為，并把它輸入給與之相對應的隨機環(huán)境，之后，隨機環(huán)境評估該輸入是否合適并給學習機反饋一個信號(Reinforcement signal)，學習機學習反饋信號后更新選擇標準并再次選擇一個其他行為作為隨機環(huán)境的輸入，如此反復，直到學習機選擇到了一個能適合隨機環(huán)境的最好行為停止。LA的組成與工作流程分別如圖2和圖3所示。

圖2 自動學習機的組成

圖3 自動學習機的工作原理

一個學習機可以用三元組L≡<α,β,C>來進行描述，其中：α={α1,α2,…,αr}表示包含r個有限行為的行為集;β={β1,β2,…,βm}表示學習機接收到的來自于隨機環(huán)境的反饋信號；C={c1,c2,…,cr}表示懲罰系數。C與α關聯(lián)，當C的取值變?yōu)榱艘粋€常量則代表著當前的行為α就是適合隨機環(huán)境的最好行為。由圖2可知，隨機環(huán)境的輸入X即為學習機的輸出α，即X→α；它的輸出Y即為學習機的輸入β，即Y→β。根據β的取值不同可以將自動學習機的隨機環(huán)境分為P-型、Q-型和S-型。在P-型中，β取值為0或1，在Q-型中，β在[0,1]區(qū)間中連續(xù)取值，在S-型中，β則在自定義區(qū)間[a,b]中連續(xù)取值。在LA-SNLP算法中，隨機環(huán)境即為三元組，所以采用P-型反饋。

針對動態(tài)社會網絡，本文改寫了傳統(tǒng)學習機三元組，使其變?yōu)長D≡<α,β,T>，其中：α和β的含義不變，T為動態(tài)學習函數，其功能為學習三元組內動態(tài)結構信息，根據反饋信號生成最佳行為集合α。定義T函數為：

(7)

式中：α(t)為t時刻的行為輸出;α(t′)為t′時刻的待選行為;β(t)為t時刻隨機環(huán)境的反饋信號；r為有限行為集合的個數。當β(t)=0時，學習算法懲罰α(t)行為，獎勵除α(t)以外的行為；當β(t)=1時，學習算法獎勵α(t)行為，認為它是一個最佳行為；當α(t′)=0時，表示該學習機已無待選行為并停止再次輸出。

2 算法描述

2.1 算法設計

在LA-SNLP算法中，不同三元組的轉化是指模體內節(jié)點對從尚未連邊到出現(xiàn)連邊的過程。因此，預測出模體內哪個節(jié)點對在未來將要出現(xiàn)連邊也就預測出了這個模體的轉化，確定這些節(jié)點對就成為了鏈路預測的首要工作。

在LA-SNLP算法中，每個三元組會分配到一個LA并將隨機環(huán)境設置成為這個模體，LA根據學習函數生成最優(yōu)行為集，這個行為集是當前模體在預測開始時刻的尚未連邊的節(jié)點對；之后，每個LA的最優(yōu)行為集會被匯總成最終待預測節(jié)點對(CNPs)集合；最后計算每個CNP的相似性分值，并根據這個分值大小完成鏈路預測。

如上所述，共同鄰居指標只考慮了兩個節(jié)點之間的一階鄰居節(jié)點，并以此鄰居節(jié)點個數作為兩個節(jié)點的相似性依據。而在一個社會網絡中，除了鄰居節(jié)點的個數外更重要的是要考慮這個鄰居節(jié)點在網絡中的重要性。三元閉包作為社會網絡中的一個特殊結構，它代表著三個節(jié)點之間存在著更加穩(wěn)定更加平衡的關系。如果一個節(jié)點包含在一個或多個三元閉包中，那么這個節(jié)點在網絡中的聚集系數和重要性就高于其他的普通節(jié)點[28]。如圖4所示，節(jié)點vi和vj之間的共同鄰居節(jié)點包含在三元閉包中，則它們之間的相似性要高于共同鄰居節(jié)點為普通節(jié)點的兩個節(jié)點之間的相似性，圖中虛線部分表示“多個”。本文受此啟發(fā)，考慮到三元閉包在社會網絡中起到的重要作用，提出三元組內節(jié)點相似性指標(STMSI)。該指標的核心思想是：如果兩個節(jié)點的共同鄰居節(jié)點包含在越多的三元閉包中，則這兩個節(jié)點之間就有著更高的相似性，在未來出現(xiàn)連邊的可能性很大，并在式(1)-式(7)的基礎上提出了6種新的節(jié)點相似性指標。

圖4 vi和vj之間的共同鄰居節(jié)點包含在三元閉包中

在LA-SNLP算法中，三元閉包的判定函數為：

(8)

式中：I(x,y,z)∈mtf為節(jié)點(x,y,z)的笛卡爾積，表示模體mtf內節(jié)點的連邊情況。如果Fi=1，表示節(jié)點之間均存在連邊，此模體是一個三元閉包。六種新的相似性指標表達式定義如下：

(9)

STMSI-Saltoncnp(i,j)=

(10)

STMSI-Jaccardcnp(i,j)=

(11)

(12)

(13)

(14)

式中：|{(x,y,z)∈mtfC}|表示包含共同鄰節(jié)點z的三元閉包數量。

LA-SNLP算法的流程框架如圖5所示。

圖5 LA-SNLP算法框架

2.2 算法舉例

設網絡G(V,E)為一個無向社會網絡，其中：V={v1,v2,v3,v4,v5}為節(jié)點集，表示人；E為邊集，表示人之間的關系。網絡拓撲結構如圖6所示。

圖6 一個無向社會網絡G(V,E)

為LA-SNLP算法的主要步驟如下：

步驟1輸入無向網絡G(V,E)；

步驟2統(tǒng)計六個節(jié)點包含的三元組和三元閉包的數量，結果如表1和表2所示。

表1 六個節(jié)點包含的三元組

表2 六個節(jié)點包含的三元閉包數量和LA生成的最佳行為集

步驟3給每個三元組分配一個LA，各LA生成最佳行為集α，如表2所示。

步驟4將各LA的α匯總成待預測節(jié)點對集合ω，ω為 {cnp{v1,v2}，cnp{v1,v4}，cnp{v1,v6}，cnp{v2,v4}，cnp{v2,v6}，cnp{v3,v5}}，并計算STMSI分值。在本例中，為更好體現(xiàn)共同鄰居節(jié)點和三元閉包發(fā)揮的作用，選擇STMSI-RA指標進行計算。

計算ω中每個節(jié)點對的STMSI指標分值。

STMSIcnp(v1,v2)=0.25;STMSIcnp(v1,v4)=0.25;

STMSIcnp(v1,v6)=0.25;STMSIcnp(v2,v4)=0.25;

STMSIcnp(v2,v6)=0.25;STMSIcnp(v3,v5)=1.33。

步驟5根據分值大小排序，并生成新的待輸出節(jié)點對集合ωout，ωout為{cnp{v3,v5}，cnp{v1,v2}，cnp{v1,v4}，cnp{v1,v6}，cnp{v2,v4}，cnp{v2,v6}}。

步驟6LA-SNLP算法選擇分數較大的節(jié)點對cnp{v3,v5}作為預測結果輸出，完成鏈路預測。

3 仿真實驗與結果分析

3.1 數據集與實驗環(huán)境

為驗證LA-SNLP算法在社會網絡中的預測表現(xiàn)，實驗共采用了四個社會網絡數據集。這四個數據集分別是Facebook[33]、安然公司郵件網絡(Enron)[34]、量子學科研合作網(GRQCCN)[35]和加拿大大眾點評網(Epinions)[36]。在Epinions數據集中，節(jié)點表示用戶，邊表示用戶間的信任關系，即“用戶—信任—用戶”。四個數據集的網絡特征信息如表3所示。實驗硬件平臺為：CPU為i5-7200,內存為16 GB，虛擬內存為50 GB；軟件平臺為：操作系統(tǒng)為Windows server 2008r2,仿真軟件為Python 2.7 64 bit,Origin pro 2018C 64 bit。

表3 四個數據集的網絡特征信息

3.2 評估指標

AUC指標和Precision指標是目前較為常用的檢驗鏈路預測算法準確度的評估指標[4-5]。AUC可以理解為測試集中存在邊的節(jié)點對相似值和不存在邊的節(jié)點對相似值之間的比較，如果測試集中的邊的分數值大于不存在邊的分數值，加1分；如果兩個分數值相等，加0.5分。獨立地比較n次，如果有n′次測試集中的邊的分數值大于不存在邊的分數，有n″次兩邊分數值相等，其中n′和n″均表示小于等于n的數。根據以上方法，AUC定義為：

Precision定義為在前L個預測結果中被預測正確的比例。Precision表達式定義為：

式中：L為預測結果的個數；m為在L預測結果中預測正確的邊的條數。Precision值越大代表預測越準確。若兩個預測算法的AUC值相同，但前者Precision大于后者，說明前者算法更好。

3.3 不同大小訓練集的測試效果

在本實驗中，為分析不同大小的訓練集對LA-SNLP算法的六個預測指標準確度的影響，按0.75和0.5兩個不同比例分別劃分了四個數據集的訓練集。為增強實驗結果的可讀性和可對比性，按照f(x)=1/(1+lgx)將結果映射到區(qū)間[0,1]中。實驗結果如表4和表5所示，表中S為STMSI的簡寫。

表4 訓練集大小為0.75的AUC結果

表5 訓練集大小為0.5的AUC結果

從表4和表5中不難得出，LA-SNLP算法中的六個預測指標的預測準確度受訓練集大小變化的影響較小，這恰恰證明了LA-SNLP算法抓取的僅是以三元組為單位的網絡局部特征。同時也可以發(fā)現(xiàn)，LA-SNLP算法在平均聚集系數較大的網絡中表現(xiàn)更好。

3.4 與六種預測算法的比較

為評估和比較LA-SNLP算法的預測準確度，本實驗將較為常用的六種相似性指標：CN指標、Salton指標、Jaccard指標、PA指標、AA指標和RA指標通過AUC和Precision在四個數據集中進行了驗證，并與LA-SNLP算法的六個預測指標進行對比。四個數據集的訓練集比例均為0.75。實驗結果如表6和表7所示。

表6 AUC結果對比

表7 Precision結果對比

從表6和表7中不難看出，LA-SNLP算法的六種相似性指標的預測準確度要好于其他指標，該算法可以在較短時間內達到最佳預測效果并保持平穩(wěn)。值得注意的是，S-PA指標在Epinions數據集中的表現(xiàn)要明顯好于其他指標，這是因為通過LA產生的待預測節(jié)點對可以保證它們之間至少存在一個共同鄰居節(jié)點。

4 結 語

本文提出一種針對社會網絡的鏈路預測算法(LA-SNLP)。該算法首次將自動學習機與三元組相結合，以不同類型三元組的轉化作為預測的重要依據，以節(jié)點包含三元閉包的數量為參數提出6種三元組內節(jié)點相似性指標，利用自動學習機“學習-選擇-反饋”簡潔而又高效的學習機制學習并生成了動態(tài)社會網絡中以三元組為單位的待預測節(jié)點對集合，實現(xiàn)了在動態(tài)社會網絡中的鏈路預測。仿真實驗表明，LA-SNLP算法提出的六種相似性指標的預測準確度和穩(wěn)定性要好于常用的Common Neighbor、Salton、Jaccard、Preferential Attachment、Adamic Adar和Resource Allocation六種相似性指標，達到了一個理想的預測結果。本文算法在動態(tài)社會網絡的分析工作中具有實際應用價值。同時，我們在實驗過程中也發(fā)現(xiàn)該算法在網絡鄰接矩陣和相似度矩陣的存儲上還需改進。

在下一步工作中，除改進本文算法不足，我們還將進一步調整優(yōu)化自動學習機和學習函數，爭取能在有向加權社會網絡和超網絡的預測工作中有新的突破。