秦 強 生佳根 嚴長春

（江蘇科技大學(xué)計算機學(xué)院 鎮(zhèn)江 212000）

1 引言

隨著微博等社交網(wǎng)站［1］的規(guī)模不斷變大，單個的用戶希望能夠快速準確高效地找到與自身體興趣相關(guān)一致的共同的愛好的用戶、群體，這樣用戶之間可以交流，從而生出更多的啟迪和共鳴。然而面對海量的信息，僅僅通過搜索是無法精確及時地發(fā)現(xiàn)志同道合的朋友，因此需要通過挖掘微博網(wǎng)絡(luò)中用戶信息，找出興趣相投的用戶社區(qū)。因此對于社交網(wǎng)絡(luò)而言，通過社區(qū)發(fā)現(xiàn)技術(shù)可以挖掘用戶潛在的興趣社區(qū)，研究用戶社區(qū)的關(guān)系結(jié)構(gòu)，對興趣推薦［2］，廣告準確投放［3］等方面有重要意義。常用的社區(qū)發(fā)現(xiàn)算法，例如CPM［4］算法時間復(fù)雜度高，計算復(fù)雜的，不適用于社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)；又如基于層次聚類［5～6］的算法需要事先確定社區(qū)的個數(shù)，也不適用于社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。標(biāo)簽傳播算法［7］（LPA）算法時間復(fù)雜度低、不需要預(yù)先設(shè)置社區(qū)個數(shù)、計算過程簡單，在處理大型復(fù)雜網(wǎng)絡(luò)時，具有較高的效率的特點，所以被廣泛的運用到社區(qū)發(fā)現(xiàn)的分析研究中。但該算法存在些不穩(wěn)定性和隨機性，主要表現(xiàn)在節(jié)點標(biāo)簽更新的順序，以及標(biāo)簽傳播過程中存在較大的隨機性，通過一些改進，就可以避免原始算法這些缺點，例如：未考慮到相鄰節(jié)點在網(wǎng)絡(luò)結(jié)構(gòu)中的相似性，以及節(jié)點與節(jié)點之間的內(nèi)容相似性。SimRank［8］算法為度量節(jié)點在網(wǎng)絡(luò)結(jié)構(gòu)中的相似度，主題模型［9］可以度量節(jié)點內(nèi)容上的主題分布。受此啟發(fā)，本章從節(jié)點相似度角度出發(fā)，在標(biāo)簽傳播算法基礎(chǔ)上，運用SimRank算法度量網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點間相似度，同時結(jié)合節(jié)點內(nèi)容的主題分布的相似性改進傳播策略，來降低實驗結(jié)果的隨機性。

2 背景知識介紹

2.1 LDA主題模型

主題模型是當(dāng)今在文本處理領(lǐng)域比較經(jīng)典一種生成式概率模型。該模型主要思想是：一篇文檔可由若干個主題以某種概率分布形式表示，而每一個主題則可由若干個詞以某種概率分布形式表示，文檔和詞之間通過主題相互關(guān)聯(lián)。LDA生成過程如圖1所示。

圖1 LDA概率圖模型

圖1中雙圓圈部分表示可觀察變量，單圓圈部分表示不可觀察變量，箭頭表示兩個變量之間存在條件概率依賴，方框表示重復(fù)采樣，方框當(dāng)中的大寫字母表示采樣次數(shù)。M表示文檔的數(shù)目，同時也表示反復(fù)采樣M次，來生成M篇文檔；Nm表示第m文檔中詞的數(shù)目，同時也表示反復(fù)采樣Nm次，來生成第m篇文檔中的Nm個詞；K表示主題的數(shù)目；wm，n表示第m文檔中的第n詞；zm，n表示詞 wm，n所屬的主題表示為文檔主題分布θ的共軛先驗分布；表示主題詞分布，β表示為主題詞分布?的共軛先驗分布。

以第m篇文檔為例，LDA的生成過程如下：

1）首先根據(jù)泊松分布來生成文檔中的Nm個詞；

4）對文檔下的每個單詞 wm，n，n=1，2，…，Nm：

（1）從第m篇文檔的文檔主題多項式概率分布中采樣，生成一個主題2，…，K}；

（2）從主題為zm，n的主題單詞多項式概率分布中采樣，生成一個詞{w1，w2，…，wv}。

5）上述操作就是主題模型的生成過程。

LDA模型求解就是對LDA的參數(shù)進行推理的過程，常用Gibbs采樣［10］求解，該方法根據(jù)給定的最優(yōu)化目標(biāo)函數(shù)，最終得到對目標(biāo)參數(shù)的估計值。

2.2 SimRank算法

2002年Jeh G等對PageRank算法加以擴展，提出了SimRank算法，算法通過分析網(wǎng)絡(luò)中網(wǎng)絡(luò)的全局性特征，來計算節(jié)點相似性。2010年Lizorkin D等［11］對SimRank計算過程提出了改進，使得計算時間大大縮短。2014年尹坤［12］等運用SimRank計算百度百科詞條與詞條之間的語義相似度。2015年王春磊［13］等提出一種可異步執(zhí)行的大規(guī)模Sim?Rank算法。如今SimRank已被應(yīng)用于生物科學(xué)、社會網(wǎng)絡(luò)［14］等眾多領(lǐng)域。

定義有向圖G=（V，E），其中V為圖中的節(jié)點集合，E為圖中邊的集合，邊代表兩個節(jié)點之間的關(guān)系，對于圖中的任意一個節(jié)點a，用I（a）表示指向它的邊所對應(yīng)的頂點集合，|I（a）|表示頂點集合所包含頂點的個數(shù)。該算法主要思想是，網(wǎng)絡(luò)中兩個節(jié)點的相似度，依賴于網(wǎng)絡(luò)中其兩個鄰接節(jié)點集合相似度。對于圖中任意兩個頂點a和頂點b，s(a，b)表示頂點a與頂點b的相似度，則SimRank計算兩頂點間相似度 s(a，b)的式（1）如下，其中 C∈(0，1)為衰減因子，通常為一個常數(shù)。

SimRank算法通常采用迭代計算的方式來計算相似度，第k次迭代后頂點a和頂點b的相似度用sk(a，b)表示，同時k+1次頂點相似度值可通過k次頂點相似度值計算得到，式（2）如下：

其中迭代初始狀態(tài)如式（3）：

當(dāng)k趨近于無窮大時，就得到頂點間的相似度limk→αsk(a，b)=s(a，b)。通常需要設(shè)置一個閾值ε，用來表示精確度，當(dāng)算法迭代后達到精確度就停止迭代。第k次迭代后，生產(chǎn)的相似度矩陣為Sk，最終算法停止迭代的條件為‖Sk+1-Sk‖≤ε。文獻［11］中分析了迭代次數(shù)與精度值的關(guān)系，并給出了相關(guān)式（4），即第k次迭代后的相似度sk(a，b)與實際相似度s(a，b)的關(guān)系，這樣就可以依據(jù)精度值 ε，預(yù)先計算出需要迭代的次數(shù)k=[lg ε/lg C-1]。

2.3 標(biāo)簽傳播算法

標(biāo)簽傳播核心思想是：首先給網(wǎng)絡(luò)中每個的節(jié)點分配一個唯一的標(biāo)簽，代表著當(dāng)前節(jié)點所屬社區(qū)的標(biāo)簽，然后統(tǒng)計與當(dāng)前節(jié)點相連節(jié)點的標(biāo)簽分別出現(xiàn)的個數(shù)，將標(biāo)簽個數(shù)最大的標(biāo)簽賦予給當(dāng)前節(jié)點，多次迭代之后，網(wǎng)絡(luò)中每個節(jié)點的標(biāo)簽達到穩(wěn)定，此時擁有相同標(biāo)簽的節(jié)點就組成為一個社區(qū)。更新操作的規(guī)則如式（5）：

其中l(wèi)i為等待更新目標(biāo)節(jié)點i的標(biāo)簽；N(vi)為節(jié)點vi的鄰接節(jié)點的集合；k為鄰接節(jié)點中一個節(jié)點；lk為節(jié)點k的標(biāo)簽；δ(lk，l)表示克羅內(nèi)克函數(shù)，其輸入變量為兩個整數(shù)，當(dāng)兩個整數(shù)相等時，函數(shù)輸出值為1，否則輸出值為0。該公式的最優(yōu)解為節(jié)點v鄰接節(jié)點中標(biāo)簽數(shù)量最多的標(biāo)簽。

具體的算法步驟如下：

1）初始化：將網(wǎng)絡(luò)中的所有節(jié)點都分配一個標(biāo)簽，在具體算法中一般把節(jié)點的ID作為標(biāo)簽分配給這個節(jié)點，代表了該節(jié)點所屬的社區(qū)的編號；

2）更新標(biāo)簽：對網(wǎng)絡(luò)中所有的節(jié)點進行標(biāo)簽的更新。標(biāo)簽更新規(guī)則為，統(tǒng)計標(biāo)簽在鄰接節(jié)點中出現(xiàn)的頻率，并將當(dāng)前節(jié)點的標(biāo)簽更新為頻率數(shù)最大的標(biāo)簽。如果出現(xiàn)頻率數(shù)最大的標(biāo)簽有好多個，則隨機從出現(xiàn)頻率數(shù)最大的標(biāo)簽中選擇一個標(biāo)簽更新為該節(jié)點的標(biāo)簽；

3）重復(fù)執(zhí)行上述操作，直到達到算法停止條件；

4）社區(qū)劃分：統(tǒng)計各個節(jié)點的標(biāo)簽，具有相同的標(biāo)簽的節(jié)點就處于同一個社區(qū)。

該算法在對每個節(jié)點分配標(biāo)簽時間復(fù)雜度為O(n)，每次迭代傳播耗時O(m)，所以總的時間復(fù)雜度為O(m+n)。但是一般情況下，該算法需要迭代多次才能使節(jié)點的標(biāo)簽趨于穩(wěn)定，但是即使多次迭代，時間復(fù)雜度仍然是線性的。該算法時間復(fù)雜度非常小，適用于大型網(wǎng)絡(luò)。

3 本文算法

若以G（V，E）表示社區(qū)網(wǎng)絡(luò)，其中，V表示社區(qū)節(jié)點組成的集合，E代表節(jié)點之間的各種關(guān)聯(lián)。對于任意的社區(qū)節(jié)點vi∈V，li表示其標(biāo)簽，θi表示社區(qū)節(jié)點vi內(nèi)容上的主題分布，n代表網(wǎng)絡(luò)節(jié)點數(shù)，m代表網(wǎng)絡(luò)邊數(shù)。

在傳統(tǒng)標(biāo)簽傳播算法中，節(jié)點在更新其標(biāo)簽時，該節(jié)點的每個鄰居的重要性同等重要，由此導(dǎo)致節(jié)點在更新其標(biāo)簽時，同類型標(biāo)簽的數(shù)量成為唯一的衡量標(biāo)準。受此啟發(fā)，本文在預(yù)測節(jié)點標(biāo)簽時，既考慮節(jié)點間在網(wǎng)絡(luò)拓撲圖中的相似性，也考慮節(jié)點內(nèi)容的相似性，相似度越高，其影響力越強，權(quán)重也越大；在標(biāo)簽更新過程中，節(jié)點的標(biāo)簽不再是由鄰接節(jié)點中標(biāo)簽的數(shù)量唯一確定，而是由鄰接節(jié)點的標(biāo)簽的加權(quán)和來決定。

首先考慮鄰接節(jié)點與當(dāng)前節(jié)點在網(wǎng)絡(luò)拓撲圖中的相似性。運用SimRank算法，可以得出在網(wǎng)絡(luò)結(jié)構(gòu)圖G中節(jié)點結(jié)構(gòu)相似度公式ssim(vi，vj)，通過計算求得任意網(wǎng)絡(luò)結(jié)構(gòu)中兩個節(jié)點結(jié)構(gòu)相似度，從而得到相似度矩陣SSIMn*n。

同時傳統(tǒng)標(biāo)簽傳播算法，往往忽略了網(wǎng)絡(luò)中節(jié)點內(nèi)容的相似性，節(jié)點內(nèi)容相似度越高，其標(biāo)簽傳播能力越強。本文通過主題模型對節(jié)點的文本內(nèi)容進行建模，得到網(wǎng)絡(luò)中節(jié)點vi內(nèi)容的主題分布θi，從而節(jié)點之間的內(nèi)容相似度，可以通過計算節(jié)點主題分布之間相似度來獲得。KL散度［15］是計算任意兩個概率分布p、q之間相異度的重要指標(biāo)，如式（7）所示。

本文將KL散度運用于度量節(jié)點內(nèi)容相似度，即節(jié)點上內(nèi)容的主題分布越接近，相似度值越高。因此對上述KL散度加以改造，并用于計算節(jié)點的內(nèi)容相似度，如式（8）所示。

其中θi表示節(jié)點vi上內(nèi)容的主題分布，θj表示節(jié)點vj上內(nèi)容的主題分布。

最后綜合節(jié)點內(nèi)容相似度和節(jié)點結(jié)構(gòu)相似度，可以得到節(jié)點vi，vj的相似度，如式（9）所示。

本文從節(jié)點結(jié)構(gòu)和內(nèi)容相似度角度出發(fā)，結(jié)合SimRank算法和主題模型，提出了多特征融合的標(biāo)簽傳播算法，算法在更新標(biāo)簽時，為鄰接節(jié)點的標(biāo)簽賦予不同的權(quán)重，最終節(jié)點的標(biāo)簽由對應(yīng)標(biāo)簽權(quán)重的加權(quán)和來決定，具體式（10）如下所示。

其中sin(vj，vi)為節(jié)點vj與節(jié)點vi的相似度。

算法的具體步驟如下：

1）初始化：設(shè)置網(wǎng)絡(luò)中的標(biāo)簽數(shù)為主題模型的主題數(shù)，節(jié)點的標(biāo)簽為節(jié)點上用戶的最大概率主題；

2）更新標(biāo)簽：對網(wǎng)絡(luò)中所有的節(jié)點進行標(biāo)簽的更新。標(biāo)簽更新規(guī)則為：計算各個標(biāo)簽在鄰接節(jié)點集合中出現(xiàn)次數(shù)的加權(quán)和，選擇加權(quán)和最大的標(biāo)簽作為該節(jié)點新的標(biāo)簽，如式（10）所示；

3）停止條件：多次迭代計算后，直到達到算法停止條件；

4）社區(qū)劃分：統(tǒng)計各個節(jié)點的標(biāo)簽，具有相同的標(biāo)簽的節(jié)點就處于同一個社區(qū)。

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

為評估本章所提多特征融合的標(biāo)簽傳播算法的有效性，結(jié)合新浪API的編寫的分布式爬蟲程序，從新浪微博上爬取了800個用戶，202042條微博記錄，在此基礎(chǔ)上通過用戶的好友關(guān)系構(gòu)建用戶社交網(wǎng)絡(luò)，并與標(biāo)準的標(biāo)簽傳播算法進行了比較實驗。

實驗過程中，初始社區(qū)個數(shù)為主題模型的主題個數(shù)設(shè)置，網(wǎng)絡(luò)節(jié)點的初始標(biāo)簽為網(wǎng)絡(luò)節(jié)點上用戶主題分布的最大值所對應(yīng)的主題，也就是用戶的興趣標(biāo)簽。

實驗采用模塊度作為衡量算法好壞的指標(biāo)。模塊度［16］衡量的是網(wǎng)絡(luò)節(jié)點分布在完全隨機下的結(jié)構(gòu)分布情況與檢測得到的社團結(jié)構(gòu)分布之間的差異情況，差值越大，說明得到的結(jié)果越不隨機化，說明社團檢測結(jié)果越有效，其式（11）如下：

其中，m為算法檢測的整個社區(qū)個數(shù)；L為網(wǎng)絡(luò)結(jié)構(gòu)中邊的總連接個數(shù)；ls為社區(qū)內(nèi)部邊的連接個數(shù)；ds為社團中所有節(jié)點的度的總和。

實驗分別從算法的檢測社區(qū)的精度和算法的穩(wěn)定性兩方面進行驗證，算法精度方面采用模塊度均值進行比較；算法穩(wěn)定性方面模塊度的方差進行比較。本次實驗分別在兩種算法上運行10次。實驗結(jié)果如圖2所示。

圖2 算法對比圖

圖2可以看出，本章提出的融合多特征標(biāo)簽傳播算法在模塊度均值方面，明顯高于傳統(tǒng)的標(biāo)簽傳播算法；在模塊度方差方面，低于傳統(tǒng)的標(biāo)簽傳播算法。實驗表明本文提出的多特征融合標(biāo)簽傳播算法在算法的精度和穩(wěn)定性上都有所提升。

5 結(jié)語

本文充分考慮在標(biāo)簽傳播的過程中，節(jié)點與節(jié)點之間結(jié)構(gòu)和內(nèi)容的相似度對標(biāo)簽傳播影響，首先利用SimRank算法計算標(biāo)簽的結(jié)構(gòu)相似度，其次運用主題模型得到節(jié)點上內(nèi)容的主題分布，以此來計算節(jié)點內(nèi)容的相似度，最后融合兩類信息的相似度，用以改進標(biāo)簽的傳播策略。該算法弱化了結(jié)構(gòu)不相同、內(nèi)容不相似的節(jié)點對標(biāo)簽傳播的影響，同時加強結(jié)構(gòu)相同、內(nèi)容相似的節(jié)點對標(biāo)簽傳播的影響，從而有效地促進社團形成。實驗證明，本文所提出的算法比原有的標(biāo)簽傳播算法有著較好的準確性和穩(wěn)定性。