杜翠鳳 陳少權(quán) 蔣仕寶

【摘 要】共同鄰居的數(shù)量、共同鄰居的度數(shù)、節(jié)點(diǎn)之間的路徑長(zhǎng)度等傳統(tǒng)鏈接預(yù)測(cè)忽視鄰居之間的關(guān)系以及節(jié)點(diǎn)本身的拓?fù)浣Y(jié)構(gòu)，導(dǎo)致其無法解決核心節(jié)點(diǎn)與周圍節(jié)點(diǎn)鏈接強(qiáng)度不同的問題。采用鄰域“結(jié)構(gòu)洞”理論，并且結(jié)合節(jié)點(diǎn)本身拓?fù)浣Y(jié)構(gòu)以及共同鄰居的拓?fù)浣Y(jié)構(gòu)的影響來實(shí)現(xiàn)網(wǎng)絡(luò)的鏈接預(yù)測(cè)，提出基于改進(jìn)資源分配的鏈接預(yù)測(cè)算法。實(shí)驗(yàn)證明，該算法不僅更加準(zhǔn)確地反映了動(dòng)態(tài)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，還能更加準(zhǔn)確地預(yù)測(cè)節(jié)點(diǎn)之間是否存在鏈接關(guān)系。

【關(guān)鍵詞】鏈接預(yù)測(cè)；鄰域“結(jié)構(gòu)洞”；資源強(qiáng)度；拓?fù)浣Y(jié)構(gòu)

Link Prediction Algorithm based on Improved Resource Allocation

DU Cuifeng， CHEN Shaoquan， JIANG Shibao

[Abstract] Traditional link prediction， such as the number of common neighbors， the degree of common neighbors and the path length between nodes， ignores the relationship between neighbors and the topological structure of nodes themselves. Thus， the different link intensity between the core node and surrounding nodes can not be solved. Using the theory of "structure hole" of the neighborhood， the link prediction of the network is realized by combining the topological structure of nodes themselves with the topological structure of the common neighbors. A link prediction algorithm based on improved resource allocation was proposed in this paper. Experimental results show that the algorithm not only reflects the topological structure of dynamic network more accurately， but also predicts more accurately whether there is a link between nodes.

[Key words]link prediction； "structure hole" of the neighborhood； resource intensity； topological structure

1 引言

在現(xiàn)實(shí)中，很多數(shù)據(jù)如移動(dòng)通信網(wǎng)絡(luò)數(shù)據(jù)、社會(huì)關(guān)系數(shù)據(jù)以及生物學(xué)數(shù)據(jù)都能夠通過網(wǎng)絡(luò)進(jìn)行描述。因此，鏈接預(yù)測(cè)有廣泛的應(yīng)用前景[1]：通過分析移動(dòng)用戶的通信社會(huì)網(wǎng)絡(luò)，引入時(shí)間序列算法，實(shí)現(xiàn)用戶鏈接的動(dòng)態(tài)預(yù)測(cè)[2]；基于位置社交網(wǎng)絡(luò)的朋友關(guān)系預(yù)測(cè)研究；結(jié)合網(wǎng)絡(luò)鏈接和內(nèi)容的局部社區(qū)發(fā)現(xiàn)研究；利用鏈路預(yù)測(cè)推斷中國(guó)航空網(wǎng)絡(luò)演化機(jī)制。因此，設(shè)計(jì)具有擴(kuò)展性強(qiáng)的網(wǎng)絡(luò)鏈接預(yù)測(cè)模型，并用于社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)變化預(yù)測(cè)和社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)系預(yù)測(cè)具有重要的意義。關(guān)于鏈接預(yù)測(cè)，以往的大多數(shù)研究主要建立在靜態(tài)社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)基礎(chǔ)上，這種靜態(tài)的研究大多數(shù)利用社會(huì)網(wǎng)絡(luò)鏈接之間的結(jié)構(gòu)信息進(jìn)行用戶關(guān)系以及網(wǎng)絡(luò)結(jié)構(gòu)變化的預(yù)測(cè)。如基于劃分社區(qū)和差分共鄰節(jié)點(diǎn)貢獻(xiàn)的鏈路預(yù)測(cè)算法[3]；基于節(jié)點(diǎn)相似性的手機(jī)通信網(wǎng)絡(luò)鏈路預(yù)測(cè)，采用共同鄰居、通話時(shí)長(zhǎng)和通話時(shí)長(zhǎng)占比作為關(guān)鍵參數(shù)來實(shí)現(xiàn)用戶之間通信的鏈路預(yù)測(cè)[4]；采用共同鄰居的關(guān)系緊密度來進(jìn)行用戶緊密度的鏈接預(yù)測(cè)[5]。隨著研究的深入，考慮到網(wǎng)絡(luò)的動(dòng)態(tài)性，學(xué)者將動(dòng)態(tài)鏈接的問題轉(zhuǎn)化成學(xué)習(xí)問題，引入了半監(jiān)督技術(shù)、集成技術(shù)、機(jī)器學(xué)習(xí)等算法實(shí)現(xiàn)鏈接的動(dòng)態(tài)預(yù)測(cè)。本文在借鑒前人研究的基礎(chǔ)上，為了解決傳統(tǒng)鏈接預(yù)測(cè)忽視共同鄰居之間的關(guān)系、拓?fù)浣Y(jié)構(gòu)以及節(jié)點(diǎn)本身的拓?fù)潢P(guān)系的問題，本文鄰域“結(jié)構(gòu)洞”結(jié)合自身節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)、共同鄰居集合中節(jié)點(diǎn)間拓?fù)潢P(guān)系來描述網(wǎng)絡(luò)鏈接的可能性，提出基于資源分配的鏈接預(yù)測(cè)算法。

2 鏈接預(yù)測(cè)的相關(guān)研究

2.1 鏈接預(yù)測(cè)的定義

鏈接表示網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的相互作用或者相互關(guān)系，鏈接預(yù)測(cè)就是估計(jì)網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間存在相關(guān)作用或者相互關(guān)系的概率大小[5]。從上述的鏈接預(yù)測(cè)定義得知，鏈接預(yù)測(cè)包括2個(gè)方面：

（1）預(yù)測(cè)未知鏈接。由于技術(shù)或者其他因素的限制，網(wǎng)絡(luò)中的某些鏈接并不是都直接可見的，因此需要根據(jù)當(dāng)前的網(wǎng)絡(luò)結(jié)構(gòu)來預(yù)測(cè)鏈接的存在概率，一般把網(wǎng)絡(luò)形式化成網(wǎng)絡(luò)靜態(tài)快照，而不考慮網(wǎng)絡(luò)的發(fā)展變化。

（2）預(yù)測(cè)未來出現(xiàn)的新鏈接。通過t時(shí)刻的鏈接關(guān)系，預(yù)測(cè)t+1時(shí)刻鏈接發(fā)生的可能性，一般把網(wǎng)絡(luò)看成動(dòng)態(tài)變化的。實(shí)際上，鏈接預(yù)測(cè)就是通過節(jié)點(diǎn)之間的相互關(guān)系或者相互作用揭示社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)變化趨勢(shì)。因此，本文研究的鏈接預(yù)測(cè)，是在加權(quán)網(wǎng)絡(luò)中采用邊的結(jié)構(gòu)權(quán)重來衡量節(jié)點(diǎn)之間的相互關(guān)系，并結(jié)合共同鄰居集合中節(jié)點(diǎn)間的關(guān)系緊密程度來描述網(wǎng)絡(luò)的鏈接預(yù)測(cè)。

2.2 鏈接預(yù)測(cè)的算法介紹

由于目前大多數(shù)社會(huì)網(wǎng)絡(luò)都具有稀疏性的特點(diǎn)，存在鏈接節(jié)點(diǎn)數(shù)量與不存在鏈接節(jié)點(diǎn)數(shù)量之間的差距很大，如果把鏈接問題稱為分類問題的話，在預(yù)測(cè)的過程中將會(huì)遇到高度不平衡的問題。因此，鏈接預(yù)測(cè)的重點(diǎn)是如何解決鏈接預(yù)測(cè)中不平衡的問題以便提高鏈接的準(zhǔn)確性。

目前鏈接預(yù)測(cè)的主要方法有利用節(jié)點(diǎn)本身屬性、拓?fù)浣Y(jié)構(gòu)以及路徑等進(jìn)行相似性的鏈接預(yù)測(cè)；采用節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性作為屬性集合進(jìn)行監(jiān)督學(xué)習(xí)的鏈接預(yù)測(cè)；利用網(wǎng)絡(luò)深層次結(jié)構(gòu)最大似然估計(jì)的鏈接預(yù)測(cè)；采用參數(shù)調(diào)優(yōu)方式構(gòu)建概率模型的鏈接預(yù)測(cè)。由于篇幅有限，本文重點(diǎn)介紹基于鄰接點(diǎn)相似性和基于路徑相似性的鏈接預(yù)測(cè)方法。

（1）基于鄰接點(diǎn)相似性的鏈接預(yù)測(cè)方法

相似性實(shí)質(zhì)上是衡量網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)的接近程度，相似性鏈接預(yù)測(cè)的基本前提是：兩個(gè)節(jié)點(diǎn)的相似性程度越高，那么兩者產(chǎn)生鏈接的可能性越大?；卩徑狱c(diǎn)的相似性是指通過衡量?jī)蓚€(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)或者鄰居節(jié)點(diǎn)的局部結(jié)構(gòu)密度是否具有一定的關(guān)聯(lián)度，從而預(yù)測(cè)兩個(gè)節(jié)點(diǎn)的鏈接概率大小。

1）共同鄰居法

共同鄰居法是基于兩個(gè)節(jié)點(diǎn)的局部結(jié)構(gòu)的相似性定義方法，該算法的假設(shè)前提是：如果兩個(gè)節(jié)點(diǎn)的公共鄰居越多，那么該兩個(gè)節(jié)點(diǎn)的相似性越高，那么其之間存在的鏈接可能性越高[6]。

score（x， y）=|τ（x）∩τ（y）| （1）

其中，τ（x）和τ（y）分別表示與節(jié)點(diǎn)x和節(jié)點(diǎn)y鏈接的節(jié)點(diǎn)集合元素的個(gè)數(shù)，也就是節(jié)點(diǎn)x和節(jié)點(diǎn)y擁有共同鄰居的數(shù)量。

2）Adamic-Adar法

該算法最先用于計(jì)算兩個(gè)網(wǎng)頁(yè)的相似性，不僅利用兩個(gè)節(jié)點(diǎn)的共同鄰居的數(shù)量，同時(shí)還利用共同鄰居節(jié)點(diǎn)自身的重要性。該重要性是采用共同鄰居節(jié)點(diǎn)度數(shù)的倒數(shù)來衡量。因此，節(jié)點(diǎn)之間的相似性的計(jì)算公式為：

score（x， y）= （2）

τ（z）表示節(jié)點(diǎn)x和節(jié)點(diǎn)y共同鄰居的度數(shù)，通過共同鄰居度數(shù)的倒數(shù)來衡量節(jié)點(diǎn)x與節(jié)點(diǎn)y之間鏈接的可能性。

3）優(yōu)先鏈接法

優(yōu)先鏈接算法的思想是：節(jié)點(diǎn)之間存在鏈接的可能性與自身節(jié)點(diǎn)度數(shù)成正比，如果網(wǎng)絡(luò)中每次引入一個(gè)新的節(jié)點(diǎn)與一條邊，那么網(wǎng)絡(luò)會(huì)按照優(yōu)先的機(jī)制從網(wǎng)絡(luò)中選取度數(shù)較大的節(jié)點(diǎn)實(shí)現(xiàn)節(jié)點(diǎn)之間的鏈接，因此度數(shù)越大的節(jié)點(diǎn)，其被鏈接的可能性越大。其公式為：

score（x， y）=|τ（x）|×|τ（y）| （3）

4）資源分配法

在社會(huì)網(wǎng)絡(luò)中，節(jié)點(diǎn)的關(guān)系體現(xiàn)的是利益的集中，而資源是指在節(jié)點(diǎn)與節(jié)點(diǎn)之間、社團(tuán)與社團(tuán)之間為了達(dá)到某種目的而傳遞的信息量，或者理解為節(jié)點(diǎn)之間為了維持現(xiàn)有的網(wǎng)絡(luò)結(jié)構(gòu)和拓?fù)潢P(guān)系所投入的精力。

資源強(qiáng)度就是指節(jié)點(diǎn)之間為了維持現(xiàn)有的網(wǎng)絡(luò)結(jié)構(gòu)和拓?fù)潢P(guān)系所投入的精力占比。

資源分配是對(duì)不存在鏈接的兩個(gè)節(jié)點(diǎn)x和y，從節(jié)點(diǎn)x傳到節(jié)點(diǎn)y的資源需要以它們的共同鄰居為介質(zhì)，并且資源傳遞過程中會(huì)產(chǎn)生平均分配或者不平均分配。因此，節(jié)點(diǎn)x和y的相似性可以定義為節(jié)點(diǎn)y從x獲得的資源數(shù)量。資源數(shù)量越多，說明兩節(jié)點(diǎn)的相似性越大[5]。在現(xiàn)實(shí)網(wǎng)絡(luò)中，資源傳遞是不對(duì)稱的，那么從x的角度看y的重要性，也就是y獲得的資源數(shù)的公式為：

score（x， y）= （4）

（2）基于路徑相似性的鏈接預(yù)測(cè)方法

1）最短距離法

該算法的思想是：如果兩個(gè)沒有鏈接節(jié)點(diǎn)之間的距離越近，那么節(jié)點(diǎn)之間存在的鏈接可能性越大[7]。

score（x， y）=length（short（x， y）） （5）

其中，length表示路徑長(zhǎng)度，shorts表示最短路徑。

2）Katz算法

該算法考慮網(wǎng)絡(luò)所有的路徑，通過考慮不同路徑對(duì)節(jié)點(diǎn)相似性的影響程度不同，并使用參數(shù)β來衡量不同長(zhǎng)度的路徑對(duì)鏈接預(yù)測(cè)的影響。

score（x， y）=（βl×|Paths（x， y， l）|） （6）

其中，Paths（x， y， l）表示節(jié)點(diǎn)x和節(jié)點(diǎn)y之間所有長(zhǎng)度為l的路徑集合[5]，β為路徑衰減系數(shù)，表示隨著路徑長(zhǎng)度的增長(zhǎng)，相似性的貢獻(xiàn)就減少。

上面各種算法都是為了解決節(jié)點(diǎn)x和節(jié)點(diǎn)y之間存在隱含鏈接的可能性這個(gè)問題。而這隱含鏈接形成的機(jī)制往往是復(fù)雜的，它需要充分考慮與節(jié)點(diǎn)相連的節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)，還要考慮節(jié)點(diǎn)y之間的共同鄰居數(shù)量。因此，本文提出了一種基于鄰域“結(jié)構(gòu)洞”的網(wǎng)絡(luò)資源分配鏈接預(yù)測(cè)方法，該方法不僅考慮共同鄰居的鏈接關(guān)聯(lián)關(guān)系，還結(jié)合節(jié)點(diǎn)自身拓?fù)浣Y(jié)構(gòu)對(duì)資源傳播的影響程度。

3 基于改進(jìn)資源分配的鏈接預(yù)測(cè)算法

3.1 “結(jié)構(gòu)洞”理論

“結(jié)構(gòu)洞”的思想是：由于節(jié)點(diǎn)之間沒有鏈接關(guān)系，因此需要一個(gè)中間節(jié)點(diǎn)“Ego”充當(dāng)中間人的角色，以便信息能夠在節(jié)點(diǎn)之間進(jìn)行傳播。Burt首先提出網(wǎng)絡(luò)約束系數(shù)來衡量網(wǎng)絡(luò)節(jié)點(diǎn)形成結(jié)構(gòu)洞所受到的約束[9]。一旦結(jié)構(gòu)洞存在，那么結(jié)構(gòu)洞兩邊的“中間人”可以帶來累加而非疊加的網(wǎng)絡(luò)收益。如圖1可知，A和B存在結(jié)構(gòu)洞，中間人E充當(dāng)A和B之間的信息傳播的角色，所以節(jié)點(diǎn)A和節(jié)點(diǎn)B為了維持目前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，所投入精力的比例會(huì)比其他鄰居節(jié)點(diǎn)大。

3.2 基于“結(jié)構(gòu)洞”的資源分配算法

“結(jié)構(gòu)洞”認(rèn)為，節(jié)點(diǎn)的關(guān)系可視為節(jié)點(diǎn)為了維持鄰居關(guān)系或者網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的關(guān)系所投入精力的占比。從圖2可知，i作為社會(huì)網(wǎng)絡(luò)中鏈接數(shù)量最多的節(jié)點(diǎn)，根據(jù)約束系數(shù)理論，Ci表示節(jié)點(diǎn)i對(duì)鄰居節(jié)點(diǎn)所投入的精力占比的總和，而CiA表示節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)A所投入的精力占比。i的鄰居節(jié)點(diǎn)為Г（i）={A， B， C， D， E， F， L， M}，pij表示節(jié)點(diǎn)i為維持節(jié)點(diǎn)j的鄰居關(guān)系所投入的精力占總精力的占比，piq和pqj分別是指節(jié)點(diǎn)i和節(jié)點(diǎn)j與共同鄰居q維持關(guān)系投入的精力占總精力的占比。同理：

Ci=CiA+CiB+CiC+CiD+CiE+CiF+CiL+CiM （7）

（8）

（9）

那么，CiA=（1/8+1/8×1/3+1/8×1/4+1/8×1/4）2，同理可求得CiB、CiC、…?？梢奀ij越大，i對(duì)節(jié)點(diǎn)j投入的精力占比越大。

但是，基于“結(jié)構(gòu)洞”約束系數(shù)的方法僅僅考慮鄰居節(jié)點(diǎn)對(duì)信息傳播的影響，并沒有考慮到鄰居節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)會(huì)影響核心節(jié)點(diǎn)對(duì)鄰居節(jié)點(diǎn)信息傳播的強(qiáng)度。根據(jù)上面的約束系數(shù)的計(jì)算方式，CiE=CiF=（1/8+1/8×

1/3+1/8×1/4）2，而CFG=CEK=（1/4+1/4×1/3）2，那么CiG=CiF×CFG=CiK=CiE×CEK。顯然，由于與G的鄰居以及鄰居的拓?fù)浣Y(jié)構(gòu)更加復(fù)雜，因此，核心節(jié)點(diǎn)i為了維持當(dāng)前網(wǎng)絡(luò)的結(jié)構(gòu)必將會(huì)對(duì)G付出更多的“精力”，也就是分配更多的資源給G。

同理，本文采用傳統(tǒng)的方法，如傳統(tǒng)的資源分配、共同鄰居、Adamic-Adar法、最短距離方式、Katz算法衡量節(jié)點(diǎn)之間的鏈接預(yù)測(cè)來說明問題。

資源分配法score（i， G）=score（i， K）=1/8×（1/4+

1/3）=7/96；

共同鄰居法score（i， G）=score（i， K）=2；

Adamic-Adar法score（i， G）=score（i， K）=1/lg4+1/lg3；

最短距離法score（i， G）=score（i， K）=2；

Katz算法score（i， G）=score（i， K）=4×β2+9×β3+16×β4。

很明顯，由于G具有更好“關(guān)系”，因此，i在資源分配的過程中，肯定會(huì)分配更多的資源給G，以期與G產(chǎn)生鏈接關(guān)系。那么，i在資源傳遞過程中，傳遞給F的資源肯定比E的資源多，所以根據(jù)傳統(tǒng)的相似性鏈接算法（共同鄰居的數(shù)量、共同鄰居的度數(shù)、節(jié)點(diǎn)之間的路徑長(zhǎng)度）很難區(qū)分圖2鏈接預(yù)測(cè)的區(qū)別。如果以傳統(tǒng)方法進(jìn)行鏈接預(yù)測(cè)，則無法識(shí)別復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的鏈接關(guān)系的差異。本文參考文獻(xiàn)[8]的改進(jìn)約束系數(shù)衡量核心節(jié)點(diǎn)把資源傳遞到不同節(jié)點(diǎn)的強(qiáng)度。通過“鄰域”結(jié)構(gòu)洞約束系數(shù)來體現(xiàn)資源分配不均衡的問題。

3.3 基于改進(jìn)資源分配的鏈接預(yù)測(cè)算法

傳統(tǒng)的約束系數(shù)僅考慮了自身與最近鄰節(jié)點(diǎn)之間的關(guān)系，沒有充分考慮鄰居節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)，也就是第二近鄰、第三近鄰等節(jié)點(diǎn)的關(guān)系。如果不考慮拓?fù)浣Y(jié)構(gòu)，那么就會(huì)面臨上面提到的問題，無法真實(shí)反映資源分配不均衡的問題，也就無法反映節(jié)點(diǎn)之間資源傳遞的關(guān)系。因此，需要改進(jìn)結(jié)構(gòu)洞的約束系數(shù)，以便更精確衡量節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中的地位。

設(shè)無向網(wǎng)絡(luò)G=（V， E），其中V={v1， v2， …， vn}是網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，節(jié)點(diǎn)i的度可以表示為：

（10）

其中，αij=

那么，節(jié)點(diǎn)i的鄰接度被定義為：

（11）

那么節(jié)點(diǎn)i維持與節(jié)點(diǎn)j鄰居關(guān)系所投入的精力占比為：

（12）

其中，Q（j）是節(jié)點(diǎn)j的鄰接度，Q（q）是節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)的鄰接度。

節(jié)點(diǎn)i與鄰居節(jié)點(diǎn)之間的關(guān)系仍用公式表示，那么，根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)，τ（i）為i的鄰居集合在新的約束系數(shù)定義下，i向E傳遞的資源強(qiáng)度為：

CiE=（piE+piA×pAE+piM×pME）2

=

=0.0447。

i向L傳遞的資源強(qiáng)度為：

CiL=（piL+piF+pFL）2=

=0.0335。

i向F傳遞的資源強(qiáng)度為：

CiF=（piF+piA×pAF+piL×pLF）2

=

=0.0645。

i向M傳遞的資源強(qiáng)度為：

CiM=（piM+piE×pEM）2=

=0.0196。

同理，F(xiàn)向G傳遞的資源強(qiáng)度為：

CFG=（pFG+pFL+pLG）2=

=0.0356。

L向G傳遞的資源強(qiáng)度為：

CLG=（pLG+pLF+pFG）2=

=0.0575。

E向K傳遞的資源強(qiáng)度為：

CEK=（pEK+pEM+pMK）2=

=0.0199。

M向K傳遞的資源強(qiáng)度為：

CMK=（pMK+pME+pEK）2=

=0.0343。

那么，根據(jù)資源分配的鏈接預(yù)測(cè)算法為，信息源節(jié)點(diǎn)i通過共同鄰居節(jié)點(diǎn)傳遞資源，再通過鄰居節(jié)點(diǎn)傳播到節(jié)點(diǎn)G。

score（i，G）=CiF×CFG+CiL×CLG=0.0643×0.0356+

0.0335×0.0575=0.00421。

信息源節(jié)點(diǎn)i通過共同鄰居節(jié)點(diǎn)傳遞資源，再通過鄰居節(jié)點(diǎn)傳播到節(jié)點(diǎn)K。

score（i，K）=CiE×CEK+CiM×CMK=0.0447×0.0199+

0.0196×0.0343=0.0016。

可見，雖然i與G的共同鄰居數(shù)量、路徑長(zhǎng)度以及共同鄰居度數(shù)和i與K相同，但是i傳遞的資源數(shù)量卻有很大的區(qū)別。改進(jìn)后的資源分配算法更能體現(xiàn)節(jié)點(diǎn)在傳播資源的過程中會(huì)受到節(jié)點(diǎn)本身拓?fù)浣Y(jié)構(gòu)以及共同鄰居的拓?fù)浣Y(jié)構(gòu)的影響。上述公式的共同鄰居只有一個(gè)，如果節(jié)點(diǎn)之間有多個(gè)共同鄰居，可采取累加的方式評(píng)價(jià)節(jié)點(diǎn)鏈接的可能性。

4 基于改進(jìn)資源分配的鏈接預(yù)測(cè)的應(yīng)用

4.1 數(shù)據(jù)獲取

移動(dòng)用戶在發(fā)生移動(dòng)業(yè)務(wù)的過程中，運(yùn)營(yíng)商會(huì)記錄用戶的各種業(yè)務(wù)信息，包括發(fā)生業(yè)務(wù)的用戶ID、開始時(shí)間、結(jié)束時(shí)間、業(yè)務(wù)類型、接收ID等。

本文提取某運(yùn)營(yíng)商5萬(wàn)用戶3個(gè)月的業(yè)務(wù)量數(shù)據(jù)，并按照一定的規(guī)則進(jìn)行預(yù)處理，形成滿足本文數(shù)據(jù)分析的表格，如表1所示：

4.2 結(jié)合用戶間每月發(fā)生業(yè)務(wù)頻次剔除無效數(shù)據(jù)

本文結(jié)合用戶間每月發(fā)生業(yè)務(wù)的頻次剔除無效數(shù)據(jù)，考慮到本文的重點(diǎn)是識(shí)別用戶之間的鏈接關(guān)系?；诂F(xiàn)實(shí)數(shù)據(jù)分析的結(jié)果，本文設(shè)置用戶間每個(gè)月的用戶發(fā)生業(yè)務(wù)的頻次為20，然后把聯(lián)系大于20次的用戶關(guān)系看成有效鏈接。

4.3 基于改進(jìn)資源分配的鏈接預(yù)測(cè)模型的建立

通過剔除無效數(shù)據(jù)后按照日期分為兩部分，前45天作為訓(xùn)練集，后45天作為測(cè)試集。參考實(shí)驗(yàn)結(jié)果，設(shè)置改進(jìn)前的資源分配的鏈接預(yù)測(cè)score的閾值為0.055；設(shè)置改進(jìn)后的資源分配的鏈接預(yù)測(cè)score的閾值為0.000 63。然后根據(jù)用戶的改進(jìn)資源分配鏈接模型對(duì)訓(xùn)練集進(jìn)行打分，得到一系列用戶間的鏈接預(yù)測(cè)值，選擇鏈接預(yù)測(cè)值大于閾值作為鏈接的候選集合。然后采用改進(jìn)前的資源分配的鏈接預(yù)測(cè)模型和改進(jìn)后的資源分配的鏈接預(yù)測(cè)模型進(jìn)行對(duì)比。最后把候選集合與測(cè)試集合的結(jié)果進(jìn)行對(duì)比，得到的正確率如圖3所示。

4.4 實(shí)驗(yàn)結(jié)果及分析

由圖3可知，不考慮鄰域“結(jié)構(gòu)洞”的方法在實(shí)現(xiàn)節(jié)點(diǎn)之間的鏈接預(yù)測(cè)的準(zhǔn)確率比考慮鄰域“結(jié)構(gòu)洞”的方法低，因此，結(jié)合鄰域“結(jié)構(gòu)洞”的鏈接預(yù)測(cè)能夠在一定程度上提升網(wǎng)絡(luò)鏈接預(yù)測(cè)的準(zhǔn)確度。

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

本文基于真實(shí)的移動(dòng)用戶社交網(wǎng)絡(luò)提出了節(jié)點(diǎn)的鏈接預(yù)測(cè)模型。首先基于用戶聯(lián)系的頻次剔除無效數(shù)據(jù)，構(gòu)建移動(dòng)用戶社交網(wǎng)絡(luò)；然后再結(jié)合鄰域“結(jié)構(gòu)洞”理論在描述兩個(gè)節(jié)點(diǎn)具有相同共同鄰居數(shù)量、相同共同鄰居度數(shù)、相同的路徑長(zhǎng)度在鏈接預(yù)測(cè)上的區(qū)別。該方法能夠從本質(zhì)上描述社交網(wǎng)絡(luò)中節(jié)點(diǎn)在傳播資源的過程中會(huì)受到節(jié)點(diǎn)本身度數(shù)、拓?fù)浣Y(jié)構(gòu)以及共同鄰居的拓?fù)浣Y(jié)構(gòu)、共同鄰居之間的關(guān)系的影響，從而能夠較好地實(shí)現(xiàn)節(jié)點(diǎn)之間的鏈接預(yù)測(cè)。實(shí)驗(yàn)證明，考慮節(jié)點(diǎn)本身拓?fù)浣Y(jié)構(gòu)以及共同鄰居的拓?fù)浣Y(jié)構(gòu)的影響與傳統(tǒng)的算法相比具有較高的準(zhǔn)確率。

參考文獻(xiàn)：

[1] D Liben-Nowell， J K leinberg. The Link Prediction Problem for Social Networks[J]. Science Technology， 2007，58（7）： 1019-1031.

[2] 郭景峰，代軍麗，馬鑫，等. 針對(duì)通信社會(huì)網(wǎng)絡(luò)的時(shí)間序列鏈接預(yù)測(cè)算法[J]. 計(jì)算機(jī)科學(xué)與探索， 2010，4（6）： 552-559.

[3] 伍杰華. 基于劃分社區(qū)和差分共鄰節(jié)點(diǎn)貢獻(xiàn)的鏈路預(yù)測(cè)[J]. 計(jì)算機(jī)應(yīng)用研究， 2013，30（10）： 2954-2957.

[4] 張秋明. 基于節(jié)點(diǎn)相似性的手機(jī)通信網(wǎng)絡(luò)鏈路預(yù)測(cè)[J]. 計(jì)算機(jī)工程， 2015，41（7）： 149-152.

[5] 李淑玲. 基于相似性的鏈接預(yù)測(cè)方法研究[D]. 哈爾濱： 哈爾濱工程大學(xué)， 2012.

[6] Newman M E J. The structure and function of complex networks[J]. SIAM REVIEW， 2003，45（2）： 167-256.

[7] M Fredman， R Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms[J]. Journal of the ACM， 1987，34（12）： 596-615.

[8] 沈文明，杜翠鳳. 基于“鄰域”結(jié)構(gòu)洞的社團(tuán)發(fā)現(xiàn)算法[J]. 移動(dòng)通信， 2017，41（14）： 36-40.

[9] 蘇曉萍，宋玉蓉. 利用鄰域“結(jié)構(gòu)洞”尋找社會(huì)網(wǎng)絡(luò)中最具影響力節(jié)點(diǎn)[J]. 物理學(xué)報(bào)， 2015，64（2）： 1-11.