周 婭，楊 邦

(桂林電子科技大學(xué) 計算機(jī)與信息安全學(xué)院，廣西 桂林 541004)

0 引 言

網(wǎng)絡(luò)鏈接預(yù)測主要是研究如何使用已知的網(wǎng)絡(luò)信息對未知和缺失鏈接進(jìn)行預(yù)測[1]。社會網(wǎng)絡(luò)在近些年互聯(lián)網(wǎng)的發(fā)展過程中也得到了巨大的發(fā)展，并已經(jīng)成為各種信息傳播和關(guān)系承載的重要媒介。憑借著這些規(guī)模日趨龐大的社會網(wǎng)絡(luò)，人們構(gòu)建更加廣闊的鏈接關(guān)系成為可能，隨之而來的是社會網(wǎng)絡(luò)的日趨復(fù)雜和龐大。另一方面，當(dāng)我們對復(fù)雜系統(tǒng)中的關(guān)系構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)來近似模擬研究時，數(shù)據(jù)缺失或者鏈接信息不足等問題時有發(fā)生，而且對于關(guān)系網(wǎng)絡(luò)，其中的關(guān)系鏈接往往又是動態(tài)變化的，具體說來就是，網(wǎng)絡(luò)中某些暫時不存在的關(guān)系鏈接可能會出現(xiàn)[2]。因此，從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中預(yù)測和發(fā)掘隱藏的鏈接就顯得很有意義了。鏈接預(yù)測在很多研究和應(yīng)用領(lǐng)域中都有重要應(yīng)用，比如說生物網(wǎng)絡(luò)中的疾病-基因網(wǎng)絡(luò)、蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)[3]，除了生物網(wǎng)絡(luò)領(lǐng)域之外，在學(xué)術(shù)網(wǎng)絡(luò)中用以推斷論文的合作關(guān)系網(wǎng)絡(luò)，在電子商務(wù)中用于對客戶的商品推薦，在移動網(wǎng)絡(luò)中預(yù)測移動網(wǎng)絡(luò)用戶是否有切換運營商的傾向。在犯罪監(jiān)控網(wǎng)絡(luò)中，可以利用鏈接預(yù)測方法來發(fā)現(xiàn)犯罪分子間隱藏的聯(lián)系[4]。

對于網(wǎng)絡(luò)鏈接預(yù)測問題，從使用方法的層面來說，主要有基于相似性計算的方法、基于統(tǒng)計學(xué)似然估計的方法以及基于概率模型的方法等?；诠?jié)點相似性計算的方法是通過對網(wǎng)絡(luò)節(jié)點的某些維度的相似性進(jìn)行計算，如果兩個節(jié)點的相似度計算結(jié)果越大，那么它們之間鏈接存在的概率就越大。基于此種假設(shè)前提，發(fā)展出了不同的相似性計算指標(biāo)。

基于統(tǒng)計學(xué)似然估計的方法一般是將網(wǎng)絡(luò)的結(jié)構(gòu)看作是具有某些層次結(jié)構(gòu)或者是隨機(jī)分塊模型結(jié)構(gòu)。所以此類方法主要分為兩類：基于層次結(jié)構(gòu)模型和基于隨機(jī)分塊模型。分層次模型在呈現(xiàn)層次結(jié)構(gòu)的網(wǎng)絡(luò)中能有較好的效果，但是這類方法每次計算都需要生成若干臨時網(wǎng)絡(luò)樣本，這個過程會使模型復(fù)雜度大大增加，對于大規(guī)模的網(wǎng)絡(luò)，這類方法的綜合性能就不是很好了。而基于隨機(jī)分塊模型的鏈路預(yù)測方法能夠較好的彌補這方面的缺點，其不僅可以預(yù)測缺失的鏈接，而且能夠預(yù)測某些異常鏈接。例如在生物作用網(wǎng)絡(luò)中糾正蛋白質(zhì)相互作用關(guān)系之間的錯誤鏈接[4]。

基于概率模型的方法主要步驟是在特有的網(wǎng)絡(luò)中構(gòu)建一個帶有多個待調(diào)優(yōu)變參的數(shù)學(xué)模型，然后通過對原網(wǎng)絡(luò)上節(jié)點之間的連接關(guān)系以及連接上的權(quán)重關(guān)系的表示方法進(jìn)行轉(zhuǎn)換并作采樣處理，將節(jié)點上的網(wǎng)絡(luò)信息轉(zhuǎn)換成與節(jié)點為中心的特征值表示的形式，最后是不斷迭代進(jìn)行參數(shù)調(diào)整和模型優(yōu)化，最終得到誤差值允許范圍內(nèi)的最優(yōu)參數(shù)解。網(wǎng)絡(luò)中未知鏈接關(guān)系的存在性就可以通過計算節(jié)點對在當(dāng)前最優(yōu)參數(shù)模型中的條件概率[4]得到。

近年來，機(jī)器學(xué)習(xí)與深度學(xué)習(xí)技術(shù)也得到了迅猛的發(fā)展，也得到了廣泛的應(yīng)用，其中深度學(xué)習(xí)已經(jīng)在包括計算機(jī)視覺、自然語言處理等領(lǐng)域取得了較大的成果[5]。在自然語言處理領(lǐng)域，基于神經(jīng)網(wǎng)絡(luò)方法的語義空間模型和文本分布式表達(dá)等模型得到了較為充分的研究。詞語特征的分布式表達(dá)主要思想是將詞語的語法或者語義特征映射到一個固定維度的連續(xù)向量空間，以此解決原有方法中存在的詞語矩陣所包含的稀疏性問題以及計算的維數(shù)災(zāi)難[1]。

本文提出了基于節(jié)點特征構(gòu)建的鏈接分類預(yù)測框架(classification method for link prediction based on node vector building，Net2Vec-CLP)，下文記作Net2Vec-CLP?？蚣芊譃閮蓚€子部分，即Net2Vec部分和CLP部分。在Net2Vec子部分使用node2vec方法獲得網(wǎng)絡(luò)在低維度下關(guān)于節(jié)點的向量表達(dá)，在使用隨機(jī)游走方法獲得節(jié)點周圍環(huán)境節(jié)點序列時，對于普通隨機(jī)游走策略未考慮節(jié)點游走概率的情況，采用改進(jìn)的具有重啟機(jī)制的隨機(jī)游走方式生成節(jié)點環(huán)境向量集合，在對node2vec超參的更新過程中，創(chuàng)新性地使用改進(jìn)的牛頓下降法達(dá)到更快的收斂速度。此過程將輸出節(jié)點向量。對于傳統(tǒng)的直接對節(jié)點向量對計算相似度來評估鏈接存在性的方法做出改變，本文對獲得的節(jié)點向量，根據(jù)原網(wǎng)絡(luò)中存在鏈接邊的節(jié)點對以及無鏈接的節(jié)點對構(gòu)造帶標(biāo)簽的組合向量元數(shù)據(jù)，全部的有鏈接節(jié)點對、無鏈接節(jié)點對構(gòu)成新的帶標(biāo)簽數(shù)據(jù)集，針對此新數(shù)據(jù)集設(shè)計使用采用了Sigmoid核函數(shù)的SVM的分類算法得到針對原網(wǎng)絡(luò)的預(yù)測結(jié)果。

1 相關(guān)工作

在基于節(jié)點相似性的方法中，主要有基于局部信息相似性指標(biāo)的共同鄰居(CN)指標(biāo)，Salton指標(biāo)，Jaccard指標(biāo)[1]，TAES(time-aware actor-level evolution similarity)指標(biāo)[6]，LDAcosin指標(biāo)[7]，TBS(topology-based similarity)指標(biāo)[8]，Scop指標(biāo)[9]，LP-SSN指標(biāo)[10],基于路徑相似性的節(jié)點路徑聯(lián)合指標(biāo)[11]方法(PNC)等。在基于節(jié)點相似性的方法集合中，還有一些使用隨機(jī)游走理論的方法，比如SimRank指標(biāo)，平均通勤時間(average commute time)指標(biāo)[1]等。

在對有節(jié)點內(nèi)容屬性的網(wǎng)絡(luò)鏈接預(yù)測方法中，張昱等[12]提出了一種方法，該方法為網(wǎng)絡(luò)中不同類型的連邊分配邊權(quán)重，最后通過隨機(jī)游走的方法進(jìn)行網(wǎng)絡(luò)鏈接的預(yù)測。

機(jī)器學(xué)習(xí)與深度學(xué)習(xí)思想的方法在網(wǎng)絡(luò)鏈接預(yù)測問題中的應(yīng)用，最早是Grover A等[13]提出Node2Vec算法，首先將所有節(jié)點初始化成指定特征數(shù)的向量化表示，通過對網(wǎng)絡(luò)節(jié)點進(jìn)行基于邊連通的游走，生成節(jié)點環(huán)境節(jié)點集合，通過BP神經(jīng)網(wǎng)絡(luò)參數(shù)回退更新策略，通過參數(shù)學(xué)習(xí)和更新過程，同步完成節(jié)點向量表示的更新，直到游走序列結(jié)束和參數(shù)收斂，得到保留了網(wǎng)絡(luò)性質(zhì)的節(jié)點向量化表示。然后節(jié)點之間連邊存在的概率值可以通過兩節(jié)點之間的相似度來評估。

同時，基于網(wǎng)絡(luò)表示學(xué)習(xí)的方法也被一些研究者運用到了鏈接預(yù)測工作中來，網(wǎng)絡(luò)表示學(xué)習(xí)方法將原網(wǎng)絡(luò)中的信息轉(zhuǎn)換成以節(jié)點實體為中心的低維向量表示，以這種方式盡可能完整保留原網(wǎng)絡(luò)的拓?fù)湫畔⒑蛯傩孕畔?。在獲得網(wǎng)絡(luò)的低維向量表示之后，使用機(jī)器學(xué)習(xí)以及統(tǒng)計分析的方法對向量數(shù)據(jù)集進(jìn)行分析和預(yù)測[14,15]。

在數(shù)據(jù)分類方法的研究領(lǐng)域，SVM模型有了很多的應(yīng)用，也達(dá)到了較好的效果。汪生等[16]提出了基于模糊SVM模型的入侵檢測分類方法，能夠較好地適用于入侵檢測問題中的訓(xùn)練樣本少的問題，提高了分類準(zhǔn)確率。曲蘊慧等[17]提出了將SVM模型運用于工業(yè)中紙病檢測分類的方法，有效解決了以前的方法中存在的實時性差、難以適應(yīng)生產(chǎn)線在線檢測要求等問題。SVM模型方法在數(shù)據(jù)分類，特別是二分類數(shù)據(jù)集上，有著運用范圍廣，準(zhǔn)確率較高，可擴(kuò)展性強(qiáng)，適用領(lǐng)域廣泛等優(yōu)勢。

2 問題與符號定義

2.1 基礎(chǔ)符號定義

本節(jié)會給出所涉及到的基本問題的定義(見表1)，主要是模型涉及到的一些概念以及對應(yīng)的簡稱表示。

表1 基礎(chǔ)符號定義

2.2 節(jié)點N的周邊環(huán)境節(jié)點Env(N)

與鄰居節(jié)點不同的是，Env(N)不僅僅包含N的鄰居節(jié)點，還有可能包含非直接相連的節(jié)點。另外，周邊環(huán)境節(jié)點是通過隨機(jī)游走產(chǎn)生的，所以在每一次的運算過程中，甚至是同一次運算的不同游走序列中，其結(jié)果都是動態(tài)變化的。

2.3 Windows(N)

環(huán)境窗口Windows(N)用于表示每一個待預(yù)測的節(jié)點的周邊節(jié)點的個數(shù)。對于當(dāng)前節(jié)點N，其Windows(N)數(shù)值大小就是Env(N)中節(jié)點數(shù)目。

2.4 節(jié)點結(jié)構(gòu)特征表達(dá)嵌入矩陣M

節(jié)點結(jié)構(gòu)特征表達(dá)嵌入矩陣M是由節(jié)點特征向量構(gòu)成的矩陣，在Node2Vec框架體系中[14]，一個重要概念就是節(jié)點結(jié)構(gòu)特征向量，即網(wǎng)絡(luò)的向量化，對于原網(wǎng)絡(luò)，Node2Vec過程之后，轉(zhuǎn)變成 |V|×m型矩陣數(shù)據(jù)，即我們此節(jié)所表述的M，而M中的行數(shù)據(jù)即為每個節(jié)點的特征向量表示。對于矩陣M的更新，會在算法開始之前的初始階段進(jìn)行隨機(jī)初始化賦值，在映射層階段對節(jié)點特征向量進(jìn)行迭代更新，當(dāng)訓(xùn)練數(shù)據(jù)運算完畢時，M矩陣中所有節(jié)點向量更新完畢。

2.5 節(jié)點Huffman樹

在Net2Vec-CLP算法中，節(jié)點Huffman樹是為了提升節(jié)點查找效率，降低算法的復(fù)雜度而做出的一個設(shè)計，其是按照節(jié)點度的大小為關(guān)鍵信息指標(biāo)，構(gòu)建Huffman樹。此樹基于這樣一種假設(shè)：度較大的節(jié)點在游走數(shù)據(jù)集中更大概率出現(xiàn)，所以會涉及到更多次數(shù)的節(jié)點信息訪問，正好可以結(jié)合Huffman樹的特點進(jìn)行網(wǎng)絡(luò)節(jié)點重構(gòu)存儲。且此Huffman樹的分支可以看作一個個分類器。原網(wǎng)絡(luò)結(jié)構(gòu)中的所有節(jié)點保存在Huffman樹的葉子節(jié)點，所以此Huffman樹存在 |V| 個葉子結(jié)點。在每次對網(wǎng)絡(luò)節(jié)點的查找過程中，會經(jīng)過若干個非葉子節(jié)點，每一個非葉節(jié)點都存在待學(xué)習(xí)更新的m維參數(shù)向量。

3 基于節(jié)點特征構(gòu)建的鏈接分類預(yù)測模型(Net2Vec-CLP)

3.1 模型流程概述

如圖1所示，Net2Vec-CLP框架主要分為映射層和學(xué)習(xí)層。本章后續(xù)內(nèi)容會對整個流程作更詳細(xì)的介紹。

圖1 Net2Vec-CLP架構(gòu)流程

3.2 映射層

3.2.1 映射層模型構(gòu)造

此階段主要是對網(wǎng)絡(luò)進(jìn)行節(jié)點向量化轉(zhuǎn)換。首先是使用隨機(jī)游走的方式對網(wǎng)絡(luò)進(jìn)行多輪采樣，多輪隨機(jī)采樣之后獲得網(wǎng)絡(luò)關(guān)于節(jié)點集的序列化表示。此過程中需要仔細(xì)考慮的是對節(jié)點游走的策略合理性，較好的游走策略會對原網(wǎng)絡(luò)信息有較好的覆蓋性，能夠較充分表達(dá)原網(wǎng)絡(luò)的拓?fù)湫畔⒑蛯傩孕畔ⅰ１疚氖褂脦е貑C(jī)制的隨機(jī)游走方法來實現(xiàn)序列化過程。重啟機(jī)制應(yīng)用于度為1的網(wǎng)絡(luò)節(jié)點，在這種情況下，當(dāng)前節(jié)點游走完畢后下一游走起始節(jié)點是從已有的序列中隨機(jī)選擇一個節(jié)點(非當(dāng)前節(jié)點)作為重啟后的新的游走起始節(jié)點，如圖2所示。

圖2 網(wǎng)絡(luò)游走序列化示例

圖2中MAX_LENGTH表示每個游走序列的最大長度，WALK_TIMES表示整個游走過程所需要的游走總次數(shù)。Windows(N) 根據(jù)經(jīng)驗值取為8，得到節(jié)點的Env(N)。則整個網(wǎng)絡(luò)的游走過程的輸出訓(xùn)練集為式(1)

Training set={(N,Env(N))},N∈V

(1)

然后，在游走產(chǎn)生節(jié)點N的周邊環(huán)境節(jié)點之后，參數(shù)優(yōu)化的最終目標(biāo)函數(shù)為式(2)

(2)

式(2)表示模型的最終目標(biāo)是通過對游走得到的Env訓(xùn)練集進(jìn)行參數(shù)更新迭代運算，使得模型在某套參數(shù)解的條件下出現(xiàn)當(dāng)前訓(xùn)練集的概率p取到最大。

圖3表示了對節(jié)點的周邊環(huán)境節(jié)點取樣策略的示例。我們以節(jié)點A為例，示例中節(jié)點A的向量序列表示由 {H,D,B,H,G} 5個節(jié)點聚合運算結(jié)果來表示，本文采用線性求和聚合策略，此聚合操作輸出Env(VA)。在對每個節(jié)點向量的處理過程中，借助構(gòu)造的節(jié)點Huffman樹進(jìn)行快速查詢。從根節(jié)點到每一個葉子節(jié)點會經(jīng)歷若干個分類節(jié)點。每一個分類節(jié)點相當(dāng)于一個二分類器角色。分類節(jié)點上的決策激活函數(shù)采用Sigmoid函數(shù)。

圖3 節(jié)點向量映射

我們使用VEnv(N)表示葉子節(jié)點N關(guān)于周圍環(huán)境節(jié)點的向量表示，式(3)表示在節(jié)點Huffman樹查找的過程中，此葉子節(jié)點被按照正常路徑正確分類的聯(lián)合概率

(3)

其中

(4)

所以需要優(yōu)化的最終目標(biāo)函數(shù)式(2)即為

(5)

3.2.2 模型參數(shù)更新過程

(6)

為了方便閱讀，記Φ(N,i) 為式(7)

(7)

(8)

(9)

(10)

(11)

3.3 學(xué)習(xí)層

3.3.1 標(biāo)簽化數(shù)據(jù)集構(gòu)建

映射層進(jìn)行迭代更新，最終輸出網(wǎng)絡(luò)節(jié)點構(gòu)特征矩陣M，已有的方案是直接對此節(jié)點向量矩陣進(jìn)行相似度計算，并根據(jù)相似度值高低給出鏈接存在性預(yù)測結(jié)果。但是由于很多網(wǎng)絡(luò)中節(jié)點相關(guān)信息比較少，可能簡單到只有稀疏的度信息，簡單進(jìn)行相似度計算的方式難免會存在數(shù)據(jù)稀疏，數(shù)據(jù)分布不均，算法穩(wěn)定性較差的問題。文獻(xiàn)[1]采用余弦相似性指標(biāo)計算節(jié)點間的相似程度。從原網(wǎng)絡(luò)中的邊集中選擇部分邊集，對每一條邊的兩個端點計算相似度，并與網(wǎng)絡(luò)中隨機(jī)的兩沒有鏈接關(guān)系的節(jié)點對之間的相似度進(jìn)行比較，如果鏈接預(yù)測準(zhǔn)確，則前者值大于后者。文獻(xiàn)[16]是根據(jù)DeepWalk算法得到向量矩陣Φ，然后根據(jù)節(jié)點之間的轉(zhuǎn)移概率矩陣計算得到節(jié)點的相似度矩陣。

本文對節(jié)點特征向量進(jìn)一步進(jìn)行處理，通過對節(jié)點特征向量進(jìn)行標(biāo)簽化訓(xùn)練數(shù)據(jù)集構(gòu)建，將兩個節(jié)點向量對構(gòu)成的新向量分為兩個明確類別：鏈接存在和鏈接不存在。并在此基礎(chǔ)上訓(xùn)練二分類模型，從而在劃分的測試集上對鏈接存在與否進(jìn)行計算驗證。具體的構(gòu)建策略如下：其中式(12),式(13)分別為節(jié)點a,b的特征向量。Eab表示a,b構(gòu)成的邊。

Va=(a1,a2,…,am)

(12)

Vb=(b1,b2,…,bm)

(13)

通過向量聚合方式，a,b構(gòu)成的邊向量表示為式(14)

(14)

其中，邊向量的標(biāo)簽劃分參考式(15)

(15)

選擇數(shù)量為0.3*|E| 的無鏈接節(jié)點對作為分類標(biāo)簽為-1的數(shù)據(jù)。加上鏈接存在的數(shù)據(jù)，數(shù)據(jù)集總共有 (1+0.3)|E|條。

3.3.2 SVM二分類器設(shè)計

圖4 SVM超平面與決策邊界

除此之外，對于線性不可分的數(shù)據(jù)集，SVM方法引入核函數(shù)的概念，其具體操作是將原數(shù)據(jù)映射到更高維度以使得轉(zhuǎn)換后的數(shù)據(jù)在新的維度能夠線性可分。這個過程中的數(shù)據(jù)映射方法即前文提到的核函數(shù)概念，基于此，svm二分類優(yōu)化問題可以表示為式(16)

(16)

式(16)所對應(yīng)的拉格朗日對偶問題可表示為式(17)

(17)

(18)

3.4 算法小結(jié)

Net2Vec-CLP框架主要流程主要分為3個子部分：第一部分是Net2Vec子過程，完成網(wǎng)絡(luò)節(jié)點的向量化過程，輸出網(wǎng)絡(luò)節(jié)點特征向量表示矩陣；第二部分是標(biāo)簽化數(shù)據(jù)集構(gòu)建；第三部分是對第二部分輸出的標(biāo)簽化數(shù)據(jù)集，采用Sigmoid核作為映射函數(shù)的SVM模型訓(xùn)練過程。

4 實驗與結(jié)果分析

4.1 實驗數(shù)據(jù)集介紹

本文實驗使用了4個公開的社會關(guān)系數(shù)據(jù)集,以下是相關(guān)數(shù)據(jù)集的簡要介紹。

(1)Facebook社交網(wǎng)絡(luò)，其中包含4039個節(jié)點和 88 234 條邊。

(2)Email-Enron 電子郵件通信網(wǎng)絡(luò)，其中包含36 692個節(jié)點和183 831條邊。

(3)CA-HepTh科學(xué)家合作網(wǎng)絡(luò)，其中包含9877個節(jié)點和51 971條邊。

(4)Epinions 用戶信任關(guān)系數(shù)據(jù)網(wǎng)絡(luò)，其中包括 49 290 個頂點和487 182條邊。這4個數(shù)據(jù)集的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如表2所示。其中N表示節(jié)點數(shù)，E表示邊數(shù)，表示平均度，表示平均聚集系數(shù)。

表2 各數(shù)據(jù)集拓?fù)浣Y(jié)構(gòu)特征

4.2 基準(zhǔn)方法

(1)CN指標(biāo)：如果NBx與NBy分別表示節(jié)點x與y的鄰居節(jié)點，則基于CN指標(biāo)的相似性可表示為Sx,y=|NBx∩NBy|。

(2)Node2Vec：主要還是網(wǎng)絡(luò)結(jié)構(gòu)向量化映射的思想，不過在隨機(jī)游走序列生成過程時增加p，q兩個超參來平衡隨機(jī)游走的深度和廣度。此方法在獲得網(wǎng)絡(luò)節(jié)點的向量化表示之后，借助余弦相似度指標(biāo)來衡量節(jié)點之間相似度，并以此為判斷鏈接存在性的根據(jù)。

(3)ACT指標(biāo)：平均通勤時間相似度指標(biāo)(average commute time，ACT)是基于這樣一個理論假設(shè)：假設(shè)有一個隨機(jī)粒子從節(jié)點x到達(dá)節(jié)點y平均要走的步數(shù)為m(x,y)， 在此基礎(chǔ)上，節(jié)點x與節(jié)點y的平均通勤時間定義為式(19)

n(x,y)=m(x,y)+m(y,x)

(19)

(20)

4.3 評價指標(biāo)

算法的結(jié)果評估采用AUC(area under curve)和平均準(zhǔn)確率(average precision，AP)兩個常用指標(biāo)。AP指標(biāo)能夠很好展現(xiàn)Precision-Recall曲線下面積，能較好反映算法整體性能。AUC方法能較好評估方法的準(zhǔn)確程度，鏈接預(yù)測問題中的準(zhǔn)確率定義為在網(wǎng)絡(luò)中存在鏈接的節(jié)點對鏈接存在可能性高于不存在鏈接節(jié)點對的概率。假設(shè)進(jìn)行了n次評估實驗，其中有n′次結(jié)果存在鏈接節(jié)點對得分較高，其中n″次的結(jié)果中兩類節(jié)點對得分相同。則AUC結(jié)果的計算公式如式(21)

(21)

4.4 實驗結(jié)果

第一部分實驗是AUC指標(biāo)下的結(jié)果評估，此過程中還考察了數(shù)據(jù)集分類比例對算法以及基準(zhǔn)方法的結(jié)果的影響，實驗數(shù)據(jù)集總共進(jìn)行了4種不同比例測試數(shù)據(jù)集的劃分方案，分為10%，20%，30%，40%，每種方案運行50次，最終取值取多次結(jié)果的平均值。如圖5的幾組柱狀圖中可以觀察到：本文提出的方法在測試集的比例為20%和30%時表現(xiàn)較優(yōu)異，其中最突出的是在Facebook數(shù)據(jù)集和Email-Enron數(shù)據(jù)集上。在Epinions數(shù)據(jù)集上受測試數(shù)據(jù)集劃分比例影響最小，只在測試數(shù)據(jù)為20%和30%比例的情況下與排名其后的Node2Vec方法有微小優(yōu)勢。同時還能夠發(fā)現(xiàn)，當(dāng)測試數(shù)據(jù)比例選取到40%時， Net2Vec-CLP方法甚至?xí)陀谄渌鶞?zhǔn)方法。所以，Net2Vec-CLP方法的優(yōu)勢還應(yīng)該受測試數(shù)據(jù)集劃分比例這一參數(shù)的影響，當(dāng)測試數(shù)據(jù)集劃分比例為一個比較合理的數(shù)值時，能體現(xiàn)出結(jié)果優(yōu)勢。

圖5 不同數(shù)據(jù)集上AUC結(jié)果數(shù)據(jù)比較

同時，在分類方法角度考慮本文提出的Net2Vec-CLP方法，二分類的方法能夠雙向又全面的對能對數(shù)據(jù)集中有鏈接節(jié)點對、無鏈接節(jié)點對進(jìn)行分類預(yù)測，相對于相似度計算的方式，其能從反向?qū)o鏈接節(jié)點對與任選存在的鏈接進(jìn)行比較計算，因為按照網(wǎng)絡(luò)模型規(guī)律，所有存在鏈接節(jié)點之間的相似度都要盡量大于無鏈接節(jié)點對之間相似度，模型才會比較準(zhǔn)確。

第二大部分實驗是基于AP指標(biāo)的結(jié)果評估，這個階段我們的測試數(shù)據(jù)集選取為30%。具體結(jié)果見表3。

表3 AP結(jié)果記錄

Net2Vec-CLP在所有測試數(shù)據(jù)集上都有較好表現(xiàn)，其中表現(xiàn)最明顯的是在Facebook數(shù)據(jù)集上，測試結(jié)果高出了Node2Vec方法3.35個百分點。但是在Epinions數(shù)據(jù)集上的結(jié)果低于Node2Vec方法。這種情況可能是因為Epinions數(shù)據(jù)集的節(jié)點的網(wǎng)絡(luò)聚集程度較低，從而在隨機(jī)序列生成過程中要依賴更多的重啟機(jī)制獲取新的游走起點，最終向量構(gòu)造的過程中體現(xiàn)出的便是這些隨機(jī)重啟的信息，而并非原網(wǎng)絡(luò)的網(wǎng)絡(luò)信息，從而在分類訓(xùn)練階段中的超參會出現(xiàn)過擬合的問題。對于這類問題，可以在進(jìn)一步的后續(xù)研究中做專門的改進(jìn)和研究。

5 結(jié)束語

本文在網(wǎng)絡(luò)節(jié)點序列化表示思想的基礎(chǔ)之上，提出Net2Vec-CLP方法，在向量化過程中采用增強(qiáng)的牛頓下降法更新參數(shù)，提升了參數(shù)的收斂速度，同時通過輔助函數(shù)f1(X)=ep(X-Xn)f(X) 解決在更新過程中梯度為0的問題。映射過程將輸出網(wǎng)絡(luò)節(jié)點的向量表示，然后將網(wǎng)絡(luò)鏈接構(gòu)造成標(biāo)簽化的分類訓(xùn)練數(shù)據(jù)集，運用以Sigmoid為核的SVM算法對標(biāo)簽數(shù)據(jù)集進(jìn)行分類。在幾個數(shù)據(jù)集上運行測試的結(jié)果表明，框架在幾個數(shù)據(jù)集上，AUC指標(biāo)和AP指標(biāo)都能達(dá)到很好的效果。較以前對節(jié)點計算相似度的方法，此框架能夠?qū)υW(wǎng)絡(luò)中無鏈接節(jié)點對有均衡，準(zhǔn)確的度量。

下一步工作將會在本文工作的基礎(chǔ)上擴(kuò)展對有向社會網(wǎng)絡(luò)數(shù)據(jù)預(yù)測問題的支持，針對有向網(wǎng)絡(luò)中鏈接的有方向性特點，從節(jié)點游走策略，標(biāo)簽化數(shù)據(jù)集構(gòu)建規(guī)則等方面為出發(fā)點來開展下一步研究工作。