多維社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)算法研究

朱家磊　馬強(qiáng)　邢玲

摘 要：多維社交網(wǎng)絡(luò)中蘊(yùn)含著多個維度的信息，若單獨(dú)選擇其中一維進(jìn)行社區(qū)發(fā)現(xiàn)顯然是不合理的。為解決這個問題，提出一種綜合社交關(guān)系（包括好友關(guān)系、評論關(guān)系、推薦轉(zhuǎn)發(fā)關(guān)系等）和興趣相似的社區(qū)發(fā)現(xiàn)方法。首先研究用戶的社交行為關(guān)系，定義用戶社交強(qiáng)弱度，推出用戶緊密度公式；然后使用主題模型研究用戶博文主題特性，定義主題相似度公式；再推出用戶總相關(guān)度公式，并用其計算節(jié)點(diǎn)間的傳遞概率，使用Label Propagation算法對用戶進(jìn)行劃分；最終劃分出綜合用戶社交聯(lián)系緊密且興趣相似的社區(qū)，在真實(shí)微博上驗(yàn)證該方法的合理性和有效性。

關(guān)鍵詞：多維社交網(wǎng)絡(luò)；微博；社區(qū)發(fā)現(xiàn)；主題模型；興趣相似

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2018）03-00-04

0 引 言

新浪微博已經(jīng)成為國內(nèi)重要的社交網(wǎng)絡(luò)，為了對社交網(wǎng)絡(luò)進(jìn)行分析[1]，可以將網(wǎng)絡(luò)畫成圖，圖中的節(jié)點(diǎn)表示用戶，圖中的邊表示用戶的關(guān)系，這種網(wǎng)絡(luò)中所表現(xiàn)出的結(jié)構(gòu)稱為社區(qū)結(jié)構(gòu)[2，3]。社區(qū)發(fā)現(xiàn)可以研究社交網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)[4]，而且已發(fā)展成為數(shù)據(jù)挖掘領(lǐng)域中的熱點(diǎn)。

在社會媒體中，人們與其他人的聯(lián)絡(luò)比以前更方便。通過觀察社會媒體上的用戶行為，可以看到用戶之間存在著多個以不同方式交互的網(wǎng)絡(luò)。以微博為例，兩個用戶可以互相關(guān)注而建立“朋友”關(guān)系，也可以互相“評論”或 “推薦轉(zhuǎn)發(fā)”所發(fā)的微博，這些不同類型的行為方式會形成一個多維的社交網(wǎng)絡(luò)。多維網(wǎng)絡(luò)是指一個網(wǎng)絡(luò)中的不同節(jié)點(diǎn)間有不同的聯(lián)系方式，每一種聯(lián)系方式構(gòu)成一維網(wǎng)絡(luò)[5]。用戶間的以上行為（本文概括為社交關(guān)系）就構(gòu)成了一個三維有向網(wǎng)絡(luò)（好友關(guān)系網(wǎng)絡(luò)，評論關(guān)系網(wǎng)絡(luò)，推薦轉(zhuǎn)發(fā)網(wǎng)絡(luò)）。同時，基于用戶所發(fā)的博文、相互之間所討論的內(nèi)容以及共同關(guān)注的話題，利用LDA主題模型[6]挖掘出共同的興趣愛好，衍生出第四維網(wǎng)絡(luò)——興趣相似網(wǎng)絡(luò)。在這種多維網(wǎng)絡(luò)中，若只考慮其中一維而進(jìn)行社區(qū)發(fā)現(xiàn)是不準(zhǔn)確的，因?yàn)閮H僅一維很難概括出整個多維網(wǎng)絡(luò)的信息，前人已提出或總結(jié)出一些經(jīng)典的算法。K-L算法[7]由Kernighan和Lin提出，算法中定義了一個增益函數(shù)Q，然后用貪婪算法原理交換節(jié)點(diǎn)對，使Q值達(dá)到最大，最后劃分出兩個大小已知的社區(qū)，該算法的缺點(diǎn)在于只能劃分出兩個社區(qū)且必須知道這兩個社區(qū)成員的數(shù)量；2002年，Girvan和Newman提出了GN算法[8]，GN算法是通過不斷地移除介數(shù)最大的邊，直到整個網(wǎng)絡(luò)退化成一個社區(qū)為止，該算法的優(yōu)點(diǎn)在于無需預(yù)先知道社區(qū)的數(shù)目，但其計算復(fù)雜度較高；Lei Tang等[9]提出了先將多維網(wǎng)絡(luò)集成（主要有4種，即網(wǎng)絡(luò)集成、效用集成、特征集成、劃分集成），然后利用譜聚類方法、隨機(jī)塊模型方法或隱含空間模型將上述集成后的網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，但缺點(diǎn)是都只能針對中等規(guī)模的無向網(wǎng)絡(luò)，并不適于復(fù)雜的有向多維社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。因此，為了能夠在多維有向社交網(wǎng)絡(luò)中進(jìn)行準(zhǔn)確有效的社區(qū)發(fā)現(xiàn)，本文提出了一種基于多維社交網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法，并采用真實(shí)的微博社交媒體網(wǎng)絡(luò)[10]數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本文方法能夠更加有效地進(jìn)行社區(qū)發(fā)現(xiàn)。

1 基于社交關(guān)系和興趣相似的微博社區(qū)發(fā)現(xiàn)

微博的社交模式讓交友更加便捷，用戶與用戶之間可以互相關(guān)注成為好友，也可以互相評論、轉(zhuǎn)發(fā)、推薦取得聯(lián)系。通常在社交網(wǎng)絡(luò)中，互動頻繁的用戶更容易在一起，也更容易被劃分到同一個社區(qū)；另外，微博中的用戶喜歡發(fā)一些博文或者轉(zhuǎn)發(fā)一些自己喜愛的微博，通過分析博文主題可以找到相似性，而博文相似度較高的用戶也更容易被劃分到同一個社區(qū)。因此通過分析研究微博用戶間的社交行為模式以及微博主題的相似性，即可歸納出用戶社交關(guān)系緊密程度和主題相似程度。本文算法首先將三維有向網(wǎng)絡(luò)融合成一維無向帶權(quán)網(wǎng)絡(luò)，并計算其緊密度；然后利用LDA模型計算出主題相似度；再使用用戶總相關(guān)度公式計算每對用戶的相關(guān)度，并將其作為網(wǎng)絡(luò)圖中節(jié)點(diǎn)間邊的權(quán)值，最終發(fā)現(xiàn)社區(qū)。

1.1 社交關(guān)系緊密度計算

1.1.1 好友關(guān)系由有向無權(quán)網(wǎng)絡(luò)轉(zhuǎn)化為無向帶權(quán)網(wǎng)絡(luò)

用戶社交關(guān)系網(wǎng)絡(luò)主要有三種，分別是好友關(guān)系網(wǎng)、評論關(guān)系網(wǎng)以及推薦轉(zhuǎn)發(fā)關(guān)系網(wǎng)。首先分析好友關(guān)系，在微博社交網(wǎng)絡(luò)中，用戶A關(guān)注用戶B（在網(wǎng)絡(luò)圖中表示為A指向B）稱A為B的粉絲，若B也關(guān)注A，則A與B為好友關(guān)系（在網(wǎng)絡(luò)圖中表示為A指向B，B也指向A），這是一種強(qiáng)關(guān)系，且有些在現(xiàn)實(shí)生活中也可能是朋友關(guān)系。這種強(qiáng)關(guān)系非有即無，所以若A與B互相關(guān)注，則定義A與B之間邊的權(quán)值為1；若只有A關(guān)注B或只有B關(guān)注A，則定義A與B之間邊的權(quán)值為0.5。轉(zhuǎn)化圖如圖1所示。

1.1.2 評論關(guān)系、轉(zhuǎn)發(fā)推薦關(guān)系網(wǎng)絡(luò)融合

用戶間的“評論”和“推薦轉(zhuǎn)發(fā)”往往帶有方向且次數(shù)較為頻繁。例如，在微博中，用戶A評論用戶B所發(fā)的博文，用網(wǎng)絡(luò)圖表示就是A指向B。通常，人們將多維網(wǎng)絡(luò)中的有向網(wǎng)絡(luò)當(dāng)做無向網(wǎng)絡(luò)，然后將多維網(wǎng)絡(luò)中邊的權(quán)值進(jìn)行加權(quán)平均得到集成網(wǎng)絡(luò)[11，12]，這種處理多維有向網(wǎng)絡(luò)的方式顯然不太合理。文獻(xiàn)[13]提出社交網(wǎng)絡(luò)中用戶間聯(lián)系的頻繁性、緊密性等關(guān)系和節(jié)點(diǎn)間的方向、邊的權(quán)值大小有著密切的聯(lián)系[13]。根據(jù)這種思想，結(jié)合真實(shí)微博情況，定義用戶關(guān)系強(qiáng)弱度：

其中：Recij=min（wij，wji）/max（wij，wji）；，wij表示用戶i與用戶j之間發(fā)生的wij次“評論”或“推薦轉(zhuǎn)發(fā)”。Recij2寫為平方的形式是為了側(cè)重微博用戶間相互性的重要性，因?yàn)楫?dāng)兩個用戶間的互動更加頻繁時才有更大的概率被劃分到同一個社區(qū)。例如，在明星和粉絲的微博關(guān)系中，粉絲可能會對其關(guān)注的明星所發(fā)的博文評論轉(zhuǎn)發(fā)上萬次，但明星可能只回復(fù)一兩次，甚至無回復(fù)，這種情況是單向的，通過式（2）計算得出的關(guān)系強(qiáng)弱度就很小。只有當(dāng)兩者之間的互動次數(shù)非常接近時，關(guān)系強(qiáng)弱度才更大。式（2）具有以下性質(zhì)：

①當(dāng)wij=0或wji=0時，得到的Sij為0；

②當(dāng)wij=wji時，關(guān)系強(qiáng)弱程度為wij。

由于關(guān)系強(qiáng)弱度Sij值的范圍會大于1，為了后面方便導(dǎo)出關(guān)系緊密度公式，故先將Sij標(biāo)準(zhǔn)化。令D=max（Sij），則標(biāo)準(zhǔn)化后的Dij=Sij/D，Dij的取值范圍為[0，1]。

1.1.3 三網(wǎng)集成后的社交關(guān)系緊密度計算

在得到Fij和Dij后，二維網(wǎng)絡(luò)已變?yōu)闊o向網(wǎng)絡(luò)，因此需要再次降維，降成一維無向網(wǎng)絡(luò)。定義社交關(guān)系緊密度為：

其中： Cij是大于0小于1的值，并且0和1都可能取到，根據(jù)實(shí)驗(yàn)，調(diào)整參數(shù)α與β，當(dāng)取α=0.618，β=0.382時，實(shí)驗(yàn)結(jié)果最佳。

1.2 主題相似度計算

一般來說，同一個社區(qū)內(nèi)的成員有著相同或者相似的興趣愛好。例如，某人喜歡前NBA巨星科比，那么此人就很有可能和一些同樣喜歡科比的人劃在同一個社區(qū)。

若對微博用戶發(fā)表的每條留言或博文進(jìn)行主題分析會導(dǎo)致工作量很大。為了更加方便快速地抽取出用戶的興趣主題，本文首先將同一用戶的所有評論或博文集中到一篇文檔中；然后用分詞工具去掉文檔中的介詞、感嘆詞等冗余詞匯，只留下部分能夠代表主題的名詞、動詞等；再用LDA模型[6]抽取每篇文檔的主題，然后把主題等信息存儲在矩陣中。

現(xiàn)設(shè)如下矩陣：矩陣DT為D×T矩陣，行D表示網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目，列T表示用戶的主題數(shù)量。對DT進(jìn)行標(biāo)準(zhǔn)化，使‖DT‖=1，則Dij表示用戶文檔對每個主題的占有比例。根據(jù)DT所列出的比例即可看出每個用戶的興趣所在。

其中：Tij的值越小說明相似程度越小，值為0時表示完全不同；值越大說明相似程度越大，值為1時表明主題完全相同。DJS （i， j）是兩個概率分布間的Jensen-Shannon散度 [14]，其計算公式為：

1.3 總相關(guān)度計算及社區(qū)劃分

在社交中，有可能用戶A與用戶B發(fā)生矛盾而取消互相關(guān)注，又或者兩個用戶因?yàn)榕d趣相同而互加關(guān)注。因此，如果只單純地依據(jù)社交關(guān)系或主題相似來劃分社區(qū)是不準(zhǔn)確的，綜合考慮社交關(guān)系和興趣相似來進(jìn)行社區(qū)劃分能夠提高準(zhǔn)確性。根據(jù)社交關(guān)系緊密度Cij和主題相似度Tij推導(dǎo)出總相關(guān)度Rij，其公式為：

根據(jù)式（6）可以得到每對用戶間的相關(guān)度，再根據(jù)概率傳遞公式計算節(jié)點(diǎn)間的傳遞概率。本文采用Label Propagation算法[15]，具體步驟如下：

（1）根據(jù)式（6）計算每對節(jié)點(diǎn)間的相關(guān)度。

（2）隨機(jī)選擇一個節(jié)點(diǎn)Q，并以此初始化一個標(biāo)簽，計算節(jié)點(diǎn)Q到所有鄰近點(diǎn)的傳遞概率。

（3）利用傳遞概率對所有節(jié)點(diǎn)進(jìn)行標(biāo)簽迭代更新，迭代的標(biāo)準(zhǔn)為該節(jié)點(diǎn)的標(biāo)簽由其所有鄰近點(diǎn)標(biāo)簽中數(shù)量最多的那個標(biāo)簽代替。

（4）將所有節(jié)點(diǎn)的標(biāo)簽進(jìn)行更新，若有多個標(biāo)簽的數(shù)量同為最大，則隨機(jī)選取一個標(biāo)簽作為該節(jié)點(diǎn)的標(biāo)簽。

（5）重復(fù)步驟（3）和（4），直至每個節(jié)點(diǎn)鄰近點(diǎn)的標(biāo)簽變化趨于穩(wěn)定。

（6）將標(biāo)簽相同的節(jié)點(diǎn)劃分到同一個社區(qū)中。

2 實(shí)驗(yàn)結(jié)果及評價

新浪微博是目前使用人數(shù)最多且流行度最高的社會媒體之一，因此選擇新浪微博作為研究對象。首先，分別從微博的5個“圈”（如“體育圈”“學(xué)術(shù)圈”“影視圈”“IT圈”“文學(xué)圈”）中選出526個用戶，收集這些用戶的基本信息，包括用戶ID、好友關(guān)系、評論次數(shù)、推薦轉(zhuǎn)發(fā)次數(shù)以及微博內(nèi)容。LDA模型采用貝葉斯統(tǒng)計標(biāo)準(zhǔn)方法[16]，令其中的參數(shù)α=50/T，β=0.01，其中T為Gibbs抽樣中的主題數(shù)，取T=50，迭代次數(shù)設(shè)為100，這里最優(yōu)的主題取值以及最優(yōu)迭代次數(shù)是根據(jù)多次實(shí)驗(yàn)的經(jīng)驗(yàn)值得到的，會在語料庫上有較好的表現(xiàn)。本文得到的具體數(shù)據(jù)見表1所列。

先利用社交關(guān)系緊密度公式（3）對“好友關(guān)系網(wǎng)”“評論關(guān)系網(wǎng)”“推薦轉(zhuǎn)發(fā)關(guān)系網(wǎng)”進(jìn)行融合得到社交關(guān)系網(wǎng)（主題相似網(wǎng)不變），見表2所列。

其中：πa和πb表示兩個不同的社區(qū)劃分，k表示社區(qū)數(shù)量；n表示節(jié)點(diǎn)總數(shù)； nha代表組員屬于πa劃分的第h個社區(qū)的數(shù)量；nlb代表組員屬于πb劃分的第l個社區(qū)的數(shù)量；nh，l代表特定組員的數(shù)量，這些組員屬于nha劃分的第h個社區(qū)，同時屬于nlb劃分的第l個社區(qū)。NMI的取值范圍為0～1，當(dāng)πa和πb相同時，其值為1。

首先分別單獨(dú)對社交關(guān)系網(wǎng)和興趣相似網(wǎng)進(jìn)行社區(qū)劃分，并結(jié)合真實(shí)的5個社區(qū)進(jìn)行評價，結(jié)果見表3所列。

從表3可以看出，依據(jù)社交關(guān)系網(wǎng)絡(luò)劃分出的社區(qū)結(jié)果準(zhǔn)確率比依據(jù)興趣相似的要高，比較符合實(shí)際情況。在現(xiàn)實(shí)生活中，我們和朋友在微博上互相關(guān)注，即使沒有相似興趣，也很難取消互相關(guān)注，除非有很大的矛盾；反過來，在興趣相似網(wǎng)中，本來因?yàn)榕d趣相似或在某段時間和對方聊得火熱而互相關(guān)注，但隨著雙方興趣度轉(zhuǎn)移或雙方?jīng)]有太多話可聊可能會取消關(guān)注，當(dāng)然，也有因?yàn)槌志玫墓餐d趣而不會取消關(guān)注的。所以綜合社交關(guān)系與興趣相似能夠更加有效地進(jìn)行社區(qū)劃分。

為了確定最佳閥值γ，在實(shí)驗(yàn)中分別取值0，0.1，0.2，0.3，…，1.0，發(fā)現(xiàn)準(zhǔn)確率最大的值落在0.5～0.6之間；γ取值0.55，發(fā)現(xiàn)最大值落在0.55～0.6之間，γ再分別取0.56，0.57，0.58，0.59，最終得出取值為0.57的準(zhǔn)確率最高。因此γ的值最終取0.57為最佳，實(shí)驗(yàn)曲線如圖2所示。實(shí)驗(yàn)的最終社區(qū)劃分對比結(jié)果見表4所列，且實(shí)驗(yàn)用Gephi生成結(jié)果如圖3所示。

從最終實(shí)驗(yàn)結(jié)果可知，綜合社交聯(lián)系與興趣相似劃分社區(qū)效果更好。在實(shí)驗(yàn)中，調(diào)整γ閾值，大概取0.57時得到的準(zhǔn)確率最高。

將本文提出的社區(qū)發(fā)現(xiàn)算法分別與經(jīng)典的G-N算法、譜平均法以及Lei Tang等人提出的多維信息融合的AMM算法進(jìn)行比較，獲得的NMI準(zhǔn)確率見表5所列。從表5可以看出，本文提出的算法對于社區(qū)發(fā)現(xiàn)的準(zhǔn)確率有了很大的提高。