基于節(jié)點(diǎn)映射與標(biāo)簽數(shù)據(jù)構(gòu)建的鏈接預(yù)測(cè)方法

周 婭，楊 邦

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

0 引 言

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

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

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

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

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

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

1 相關(guān)工作

在基于節(jié)點(diǎn)相似性的方法中，主要有基于局部信息相似性指標(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é)點(diǎn)路徑聯(lián)合指標(biāo)[11]方法(PNC)等。在基于節(jié)點(diǎn)相似性的方法集合中，還有一些使用隨機(jī)游走理論的方法，比如SimRank指標(biāo)，平均通勤時(shí)間(average commute time)指標(biāo)[1]等。

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

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

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

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

2 問(wèn)題與符號(hào)定義

2.1 基礎(chǔ)符號(hào)定義

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

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

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

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

2.3 Windows(N)

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

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

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

2.5 節(jié)點(diǎn)Huffman樹(shù)

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

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

3.1 模型流程概述

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

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

3.2 映射層

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

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

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

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

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

(1)

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

(2)

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

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

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

我們使用VEnv(N)表示葉子節(jié)點(diǎn)N關(guān)于周?chē)h(huán)境節(jié)點(diǎn)的向量表示，式(3)表示在節(jié)點(diǎn)Huffman樹(shù)查找的過(guò)程中，此葉子節(jié)點(diǎn)被按照正常路徑正確分類(lèi)的聯(lián)合概率

(3)

其中

(4)

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

(5)

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

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

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

Va=(a1,a2,…,am)

(12)

Vb=(b1,b2,…,bm)

(13)

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

(14)

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

(15)

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

3.3.2 SVM二分類(lèi)器設(shè)計(jì)

圖4 SVM超平面與決策邊界

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

(16)

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

(17)

(18)

3.4 算法小結(jié)

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

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集介紹

本文實(shí)驗(yàn)使用了4個(gè)公開(kāi)的社會(huì)關(guān)系數(shù)據(jù)集,以下是相關(guān)數(shù)據(jù)集的簡(jiǎn)要介紹。

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

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

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

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

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

4.2 基準(zhǔn)方法

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

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

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

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

(19)

(20)

4.3 評(píng)價(jià)指標(biāo)

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

(21)

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

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

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

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

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

表3 AP結(jié)果記錄

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

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

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

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