駱梅柳，裴可鋒

(1.南京航空航天大學(xué)，江蘇 南京 211106；2.江蘇財會職業(yè)學(xué)院 信息系，江蘇 連云港 222061)

0 引 言

時至今日，隨著計算機(jī)技術(shù)和網(wǎng)絡(luò)的高速發(fā)展，大數(shù)據(jù)成為當(dāng)下研究的熱點(diǎn)。大數(shù)據(jù)時代巨大的數(shù)據(jù)量，繁雜的異構(gòu)信息不僅影響著人們的生活，而且對一些研究領(lǐng)域提出了新的挑戰(zhàn)，這其中就包括社交網(wǎng)絡(luò)鏈接預(yù)測研究。

20世紀(jì)90年代以來，社交網(wǎng)絡(luò)不斷地融入人們的生活，web2.0技術(shù)的發(fā)展包括微博、微信、Twitter等社交媒體，更是大大加快了這一進(jìn)程。通過這些社交媒體構(gòu)成的社交網(wǎng)絡(luò)，人們分享自己喜歡的事物，交流想法，結(jié)交朋友。社交網(wǎng)絡(luò)已經(jīng)與人們的生活息息相關(guān)，因此社交網(wǎng)絡(luò)分析儼然已成為當(dāng)前社會科學(xué)以及計算機(jī)學(xué)科研究的熱點(diǎn)話題。

作為復(fù)雜網(wǎng)絡(luò)分析的分支研究任務(wù)，社會網(wǎng)絡(luò)鏈接預(yù)測是根據(jù)已知的社交網(wǎng)絡(luò)中的用戶，社交網(wǎng)絡(luò)結(jié)構(gòu)等信息，預(yù)測尚未“結(jié)交”的用戶建立鏈接成為朋友的可能性[1]。通過計算推薦可以快速查找到社交網(wǎng)絡(luò)中的好友、社區(qū)發(fā)現(xiàn)等，更有利于豐富網(wǎng)絡(luò)演化模型的理論研究。其雖然也是數(shù)據(jù)挖掘中地一個子領(lǐng)域，但是不同于其他挖掘領(lǐng)域關(guān)注于數(shù)據(jù)內(nèi)容信息本身，鏈接預(yù)測一般關(guān)注的是網(wǎng)絡(luò)的結(jié)構(gòu)信息。例如，Common Neighber,Salton,RA等算法都是針對節(jié)點(diǎn)間的關(guān)聯(lián)關(guān)系來進(jìn)行預(yù)測的。但是隨著大數(shù)據(jù)時代的到來，僅僅獲取用戶節(jié)點(diǎn)間的結(jié)構(gòu)信息已不足以進(jìn)行準(zhǔn)確有效的社交網(wǎng)絡(luò)預(yù)測。

盧文羊等人[2]提出基于LDA主題模型的協(xié)作演化鏈接預(yù)測算法，雖然提高了預(yù)測效果，但并沒有很好地結(jié)合結(jié)構(gòu)相似度信息。吳夢蝶等人[3]基于主題模型分析節(jié)點(diǎn)語義信息，綜合節(jié)點(diǎn)屬性特征和網(wǎng)絡(luò)結(jié)構(gòu)特征進(jìn)行鏈接預(yù)測，但是在節(jié)點(diǎn)屬性特征中沒有考慮到命名實體和聯(lián)系特征在用戶區(qū)分中的重要作用。

基于傳統(tǒng)社交網(wǎng)絡(luò)鏈接預(yù)測在大數(shù)據(jù)時代下的不足，文中以微博用戶鏈接預(yù)測為例，提出挖掘社交網(wǎng)絡(luò)中的文本信息與節(jié)點(diǎn)間的結(jié)構(gòu)信息相結(jié)合的方法對社交網(wǎng)絡(luò)鏈接進(jìn)行預(yù)測。

1 主題模型

主題模型[4]是一種能夠?qū)Υ笠?guī)模文檔集中的文字所隱含的主題進(jìn)行有效分析并進(jìn)行數(shù)學(xué)建模的方法，將每一篇文檔看作一個關(guān)于主題的概率分布，而每一個主題又看作是一個關(guān)于單詞的概率分布。現(xiàn)有存在的主題模型有很多種，包括PLSA、LDA等。由于LDA模型采用無監(jiān)督的方法，適用于大規(guī)模文本語料，計算高效，因此文中采用LDA模型對文本進(jìn)行主題建模。

LDA模型是一種基于分層的貝葉斯模型[5]，由Blei等人在2003年提出，LDA的分層主要是分為文檔、主題及詞三個層次。LDA模型地核心思想是應(yīng)用詞袋模型的方法，將語料庫的每一個文檔都視為若干潛在主題的混合分布，每個主題的確定由詞匯庫中所有單詞的概率分布決定[6]。通過將庫的文檔看作是一個詞頻向量，可將文本有用信息構(gòu)建成易于建模的數(shù)字信息[7]。LDA模型的文本生成過程如圖1所示。

圖1 隱Dirichlet分配主題模型

(1)根據(jù)Poission分布，抽取文本長度，N～Poission(φ)；

(2)根據(jù)狄里克雷分布系數(shù)α，得到該文檔主題概率分布，θ～Dir(α)；

(3)根據(jù)狄里克雷分布系數(shù)β，生成k個主題的主題-詞的概率分布φ，φ～Dir(β)；

(4)對長度為N的文檔中的每一字Wn：

·從已知的主題分布θ中通過多項式分布得到這個字的主題Zn，Zn～Multinomial(θ)。

·根據(jù)Zn，選擇該主題對應(yīng)的詞概率分布φzn，通過多項式分布選擇出該字Wn～Multinomial(φzn)。

其中θ和φ是兩個需要估計的參數(shù)。由于難以直接求出這兩個參數(shù)，因此可以采用Gibbs抽樣迭代法進(jìn)行求解。

2 社交網(wǎng)絡(luò)鏈接預(yù)測模型

2.1 總體框架

文中對社交網(wǎng)絡(luò)鏈接進(jìn)行預(yù)測是通過判斷節(jié)點(diǎn)的相似度來預(yù)測兩個節(jié)點(diǎn)間是否會鏈接。對節(jié)點(diǎn)相似度的判斷主要針對如下幾個方面：

(1)基于節(jié)點(diǎn)屬性的用戶興趣特征；(2)基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的特征。

其中，基于節(jié)點(diǎn)屬性的用戶興趣特征相似度度量主要包含三個部分：首先，利用LDA模型對用戶發(fā)表的微博信息進(jìn)行主題建模得到該用戶的主題信息，并利用KL距離進(jìn)行相似度度量；其次，對用戶微博信息中的命名實體進(jìn)行識別，根據(jù)不同用戶相同命名實體數(shù)量計算用戶間的相似度；最后根據(jù)用戶微博特征如轉(zhuǎn)發(fā)或者@，找出用戶共同轉(zhuǎn)發(fā)的微博數(shù)或者@同一個人次數(shù)，從而進(jìn)行用戶相似度的度量。而基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的相似性分析則可以通過目前預(yù)測效果比較好的RA指數(shù)進(jìn)行度量。

最后，綜合上述的各個部分可以得出每個節(jié)點(diǎn)代表的用戶相似性，從而進(jìn)行預(yù)測。預(yù)測結(jié)果可以通過鏈接預(yù)測的常用評價指標(biāo)AUC進(jìn)行計算?？傮w框架如圖2所示。

圖2 社交網(wǎng)絡(luò)鏈接預(yù)測模型總體框架

2.2 用戶興趣特征相似度度量

文中將用戶興趣相似度分為三個方面：文本主題特征度量、文本命名實體度量、文本聯(lián)系特征度量。

2.2.1 文本主題特征度量

這部分是用戶興趣特征度量的重點(diǎn)。主題模型出現(xiàn)之前，一般采用用戶詞匯矩陣來對不同的用戶進(jìn)行標(biāo)注，即通過統(tǒng)計用戶使用詞匯概率的不同來進(jìn)行用戶識別，但是由于詞匯的數(shù)量很多，而且不同單詞之間出現(xiàn)頻率相差很大，造成稀疏性和度量的不準(zhǔn)確性。而采用LDA主題模型將用戶與詞匯間的維度轉(zhuǎn)化為兩個維度，一是用戶與主題，二是主題與詞匯，這樣可以解決稀疏性和度量的不準(zhǔn)確性的問題，如圖3所示。

圖3 文本主題特征度量

通過LDA過程可以得到兩個矩陣：用戶主題矩陣、主題單詞矩陣。應(yīng)用用戶主題矩陣得到各個用戶的主題向量表示θi={pi1,pi2,…,pik}，i表示第i個用戶，Pij表示第i個用戶在第j個主題下的概率。不同的用戶概率主題向量必然不同?？梢酝ㄟ^度量用戶概率主題向量的相似度來度量用戶興趣的相似度?？梢岳肒L散度(相對熵)來計算兩個概率分布的相關(guān)度[8]:

(1)

其中，pi和pj分別表示第i個用戶和第j個用戶的主題向量，KL散度越大表示兩個用戶之間的相關(guān)度越大。

2.2.2 文本命名實體度量

命名實體是以名稱為標(biāo)識的實體，比如人名、機(jī)構(gòu)名等，還包括數(shù)字、日期等[5]。在用戶微博文本表示中，命名實體如人名、地名等在用戶所要表達(dá)的思想中具有重要的意義，通過這些命名實體可以看出用戶關(guān)注的人或地點(diǎn)等甚至可以標(biāo)注出用戶在現(xiàn)實中所處的環(huán)境。但是對用戶具有標(biāo)識作用的人名和地名在表達(dá)中并不是經(jīng)常出現(xiàn)的，因此常常被歸類到低頻詞中。通過LDA將用戶映射到主題空間的過程中，命名實體這類特殊低頻詞往往會被忽略掉，從而不能發(fā)揮任何作用。所以利用LDA模型將用戶文本主題化之后，進(jìn)行文本命名實體分析是有意義的。

命名實體識別目前是一個比較熱的研究領(lǐng)域，已有工具可以較準(zhǔn)確地識別出文本中的命名實體[9]。通過判斷不同用戶微博中出現(xiàn)的命名實體相同數(shù)量可以反映用戶之間的相似性。令Nx為用戶x的命名實體集，Ny是用戶y的命名實體集。不同于主題向量的比較，用戶之間基于命名實體的相似性還與共同命名實體占各自總命名實體比例有關(guān)系。如果用戶x與用戶y的共同命名實體數(shù)量占其自身很小的比率，用戶的相似性就應(yīng)該較小，反之比率越大則相似性越大。另一方面，可能共同部分占x總比重相對較小，占y總比重相對較大，則x接受y產(chǎn)生鏈接概率就小，y的概率就相對較大。因此是不對稱的。用戶x鏈接到用戶y的概率可以表示為：

(2)

數(shù)值越大，表示用戶x會鏈接到用戶y的可能性越大。

2.2.3 文本聯(lián)系特征度量

微博是目前主流的網(wǎng)絡(luò)社交媒體，其具有實時性強(qiáng)、短小精煉等特征。微博的一大特點(diǎn)是可以轉(zhuǎn)發(fā)別人的微博以及可以@某人與其進(jìn)行互動。顯然，用戶的轉(zhuǎn)發(fā)和@構(gòu)成了用戶的重要標(biāo)識特征。與上一小節(jié)類似，進(jìn)行語義分析主題建模并不能充分有效地把這部分重要的信息利用起來，所以在進(jìn)行用戶興趣相似度度量時可以把這部分內(nèi)容加進(jìn)去。

統(tǒng)計用戶轉(zhuǎn)發(fā)的微博及@的用戶名，比較兩個用戶在這方面的相似性能在一定程度上反映用戶之間的相似性。類似命名實體的度量，根據(jù)兩個用戶共同部分的數(shù)量比各自的總數(shù)量來衡量用戶鏈接到另一用戶的可能性大小。數(shù)值越大，可能性越大。用戶x鏈接到用戶y的概率計算公式[10]如下：

(3)

其中，Ax表示用戶x轉(zhuǎn)發(fā)微博數(shù)量地集合，Bx表示用戶x@用戶名的集合，Ax∩y表示用戶x與用戶y共同轉(zhuǎn)發(fā)的微博數(shù)量，Bx∩y同理。

將上述文本主題特征、命名實體、聯(lián)系特征三個方面得到的用戶間相似度度量進(jìn)行整合，可以得到用戶節(jié)點(diǎn)的興趣相似度量。因為三個方面都是與用戶興趣相似度正相關(guān)，所以可以通過這幾個指標(biāo)的簡單累加得出用戶興趣相似度量的值。計算公式如下：

g(x,y)=KL(px||py)+p1(x,y)+p2(x,y)

(4)

2.3 網(wǎng)絡(luò)結(jié)構(gòu)相似度度量

社交網(wǎng)絡(luò)結(jié)構(gòu)是存在網(wǎng)絡(luò)結(jié)構(gòu)中各個用戶節(jié)點(diǎn)之間鏈接狀態(tài)，在網(wǎng)絡(luò)中有效提高鏈接預(yù)測的準(zhǔn)確度，需要準(zhǔn)確掌握社交網(wǎng)絡(luò)各個節(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)[11]。目前在基于節(jié)點(diǎn)相似度的鏈接預(yù)測中應(yīng)用較多的預(yù)測方法有CN(common neighbor)、RA(recourses allocation)、AA(Adamic-Adar)等，其中應(yīng)用較多、預(yù)測效果較好的方法是RA[12]。

RA是指網(wǎng)絡(luò)中兩個節(jié)點(diǎn)之間不存在直接相連，但它們之間傳遞資源是通過兩個節(jié)點(diǎn)之間的鄰居來完成。公式定義為：

(5)

2.4 節(jié)點(diǎn)相似度計算

將網(wǎng)絡(luò)結(jié)構(gòu)相似度和用戶興趣相似度進(jìn)行結(jié)合，計算出所要求的節(jié)點(diǎn)相似度，計算公式如下：

Sxy=g(x,y)+u*RAxy

(6)

其中，u用于調(diào)節(jié)兩類特征值在節(jié)點(diǎn)相似度計算中的權(quán)重，可以通過實驗進(jìn)行確定。

3 實 驗

3.1 實驗數(shù)據(jù)集

以微博社交網(wǎng)絡(luò)為數(shù)據(jù)源，使用了微博堂中分享的63 641個微博用戶的新浪微博數(shù)據(jù)集，其中包括用戶uid、用戶昵稱、用戶姓名、用戶所在地、微博數(shù)等用戶信息以及84 168條在2018-05-03至2018-05-11采集的關(guān)于12個主題的微博信息，1 391 718條用戶好友關(guān)系，27 759條微博轉(zhuǎn)發(fā)關(guān)系，以滿足實驗需要。分析微博用戶之間的用戶關(guān)系，利用好友關(guān)系構(gòu)建社交網(wǎng)絡(luò),網(wǎng)絡(luò)中的每一個節(jié)點(diǎn)代表用戶發(fā)送的微博信息和用戶信息。對節(jié)點(diǎn)進(jìn)行預(yù)處理，去除發(fā)送微博數(shù)小于5以及為孤立點(diǎn)的微博節(jié)點(diǎn)，從而得到實驗分析所應(yīng)用的社交網(wǎng)絡(luò)，隨機(jī)抽取實驗網(wǎng)絡(luò)的20%的節(jié)點(diǎn)作為測試集，剩余作為訓(xùn)練集。

3.2 實驗方法

在訓(xùn)練集上采用文中提出的方法進(jìn)行鏈接預(yù)測。首先采用RA指數(shù)計算網(wǎng)絡(luò)中各個節(jié)點(diǎn)的結(jié)構(gòu)相似性，以此作為拓?fù)浣Y(jié)構(gòu)相似性度量。然后是主題模型的求取。由于微博文本短小的特點(diǎn)，合并同一個用戶所有的微博內(nèi)容，利用LDA模型對其進(jìn)行分析處理。根據(jù)數(shù)據(jù)集，網(wǎng)絡(luò)主題數(shù)設(shè)置為12，得到各個用戶對12個主題的概率分布，并利用KL距離得到用戶間主題相似度，利用各個節(jié)點(diǎn)得到的命名實體集和轉(zhuǎn)發(fā)關(guān)系，@特征集從而得到上一小節(jié)的命名實體相似度和特征實體相似度，得到用戶間興趣相似度并利用最后的合成公式得到最終的節(jié)點(diǎn)相似度對微博網(wǎng)絡(luò)鏈接進(jìn)行預(yù)測，其中取參數(shù)u為0.8。作為對比，采用僅考慮節(jié)點(diǎn)屬性的方法以及僅計算RA指數(shù)的方法對測試集進(jìn)行鏈接預(yù)測。

3.3 實驗結(jié)果評價指標(biāo)

文中應(yīng)用鏈接預(yù)測最常用的評價體系A(chǔ)UC來評價鏈接預(yù)測方法的效果。AUC[13]通常是指從整體上評價鏈接預(yù)測方法的精確度。AUC的具體作法是分別從測試集和不存在的邊中隨機(jī)抽取n次，對兩者的分?jǐn)?shù)進(jìn)行比較，邊的分?jǐn)?shù)即是鏈接存在的可能性。文中用兩個頂點(diǎn)的相似度表示，AUC用公式表示為：

(7)

其中，n'表示測試集中邊的分?jǐn)?shù)大于不存在的邊的次數(shù)，n''表示兩者相等的次數(shù)。若所有的評分值都來自于獨(dú)立同分布的情況，則AUC的值在0.5到1之間，AUC的值大0.5的程度越大、越靠近1，表示該算法的執(zhí)行效果比隨機(jī)的執(zhí)行效果越好，鏈接預(yù)測準(zhǔn)確度越高[14]。

3.4 實驗結(jié)果

使用AUC方法分別對三種方法的預(yù)測結(jié)果進(jìn)行評價，隨機(jī)從測試集和不存在的邊中抽取n次進(jìn)行比較，n分別取500，1 000和3 000三種情況，結(jié)果見表1。

表1 鏈接預(yù)測AUC

其中節(jié)點(diǎn)屬性一列表示單考慮用戶興趣相似度得到的AUC值，RA表示采用僅考慮網(wǎng)絡(luò)結(jié)構(gòu)相似度得到的AUC值，最后一列表示采用文中方法得到的AUC值。明顯可以看出，文中方法的預(yù)測精度更高。

4 結(jié)束語

面對大數(shù)據(jù)時代帶來的挑戰(zhàn)，提出了一種基于主題模型的社會網(wǎng)絡(luò)鏈接預(yù)測算法。在傳統(tǒng)的基于網(wǎng)絡(luò)結(jié)構(gòu)相似性計算節(jié)點(diǎn)相似性的基礎(chǔ)上，利用LDA為代表的主題模型挖掘用戶的興趣相似度，同時結(jié)合用戶的命名實體集和聯(lián)系特征集對用戶興趣相似度的計算進(jìn)行補(bǔ)充完善，最后得出用戶節(jié)點(diǎn)相似度從而進(jìn)行社交網(wǎng)絡(luò)進(jìn)行預(yù)測。在微博的數(shù)據(jù)集上，將文中方法與使用節(jié)點(diǎn)屬性、RA指數(shù)的方法進(jìn)行比較，結(jié)果表明該方法預(yù)測效果更優(yōu)。