多維社交網絡中的社區發現算法研究

朱家磊　馬強　邢玲

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

關鍵詞：多維社交網絡；微博；社區發現；主題模型；興趣相似

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2018）03-00-04

0 引 言

新浪微博已經成為國內重要的社交網絡，為了對社交網絡進行分析[1]，可以將網絡畫成圖，圖中的節點表示用戶，圖中的邊表示用戶的關系，這種網絡中所表現出的結構稱為社區結構[2，3]。社區發現可以研究社交網絡中的社區結構[4]，而且已發展成為數據挖掘領域中的熱點。

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

1 基于社交關系和興趣相似的微博社區發現

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

1.1 社交關系緊密度計算

1.1.1 好友關系由有向無權網絡轉化為無向帶權網絡

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

1.1.2 評論關系、轉發推薦關系網絡融合

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

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

①當wij=0或wji=0時，得到的Sij為0；

②當wij=wji時，關系強弱程度為wij。

由于關系強弱度Sij值的范圍會大于1，為了后面方便導出關系緊密度公式，故先將Sij標準化。令D=max（Sij），則標準化后的Dij=Sij/D，Dij的取值范圍為[0，1]。

1.1.3 三網集成后的社交關系緊密度計算

在得到Fij和Dij后，二維網絡已變為無向網絡，因此需要再次降維，降成一維無向網絡。定義社交關系緊密度為：

其中： Cij是大于0小于1的值，并且0和1都可能取到，根據實驗，調整參數α與β，當取α=0.618，β=0.382時，實驗結果最佳。

1.2 主題相似度計算

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

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

現設如下矩陣：矩陣DT為D×T矩陣，行D表示網絡中節點的數目，列T表示用戶的主題數量。對DT進行標準化，使‖DT‖=1，則Dij表示用戶文檔對每個主題的占有比例。根據DT所列出的比例即可看出每個用戶的興趣所在。

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

1.3 總相關度計算及社區劃分

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

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

（1）根據式（6）計算每對節點間的相關度。

（2）隨機選擇一個節點Q，并以此初始化一個標簽，計算節點Q到所有鄰近點的傳遞概率。

（3）利用傳遞概率對所有節點進行標簽迭代更新，迭代的標準為該節點的標簽由其所有鄰近點標簽中數量最多的那個標簽代替。

（4）將所有節點的標簽進行更新，若有多個標簽的數量同為最大，則隨機選取一個標簽作為該節點的標簽。

（5）重復步驟（3）和（4），直至每個節點鄰近點的標簽變化趨于穩定。

（6）將標簽相同的節點劃分到同一個社區中。

2 實驗結果及評價

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

先利用社交關系緊密度公式（3）對“好友關系網”“評論關系網”“推薦轉發關系網”進行融合得到社交關系網（主題相似網不變），見表2所列。

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

首先分別單獨對社交關系網和興趣相似網進行社區劃分，并結合真實的5個社區進行評價，結果見表3所列。

從表3可以看出，依據社交關系網絡劃分出的社區結果準確率比依據興趣相似的要高，比較符合實際情況。在現實生活中，我們和朋友在微博上互相關注，即使沒有相似興趣，也很難取消互相關注，除非有很大的矛盾；反過來，在興趣相似網中，本來因為興趣相似或在某段時間和對方聊得火熱而互相關注，但隨著雙方興趣度轉移或雙方沒有太多話可聊可能會取消關注，當然，也有因為持久的共同興趣而不會取消關注的。所以綜合社交關系與興趣相似能夠更加有效地進行社區劃分。

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

從最終實驗結果可知，綜合社交聯系與興趣相似劃分社區效果更好。在實驗中，調整γ閾值，大概取0.57時得到的準確率最高。

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