基于情感網絡的社群發現與增長?

馬 力 張思敏

（西安郵電大學計算機學院 西安 710061）

1 引言

隨著以社交和資訊分享為主的在線社交應用（如微博、微信、facebook等）及在線評論的興起，不同人員之間已經構筑起了一個無縫的信息共享與交流平臺。它們一方面增強了人們信息交流的多媒體性與時效性體驗，另一方面還使人們對信息的需求從簡單的獲取與共享上升到情感表達層面。因此，進一步拓寬人們信息利用的深度，引起了眾多學者的廣泛關注。

情感是人類智能或認知的重要標志，是驅動人類行為發生的內在心理動因。它影響著人們的決策、學習和交流，并在人們的決策行為中起重要甚至決定性作用。認知心理學研究表明：人們的信息交流行為是受情感影響的。真實社會中人們的情感隨其行為表示出來，并通過社會關系鏈傳播。

當嘗試著描述某一系統中元素以及元素之間相互連接的概念時，“網”這一形式成為了自然的選擇，所以研究情感在個體之間如何傳播這一問題時，在復雜網絡理論基礎上提出了情感網絡的構建方法，基于在線網絡數據讀取進行網絡生成、網絡社群劃分，提出基于網絡社群的網絡增長算法。

2 情感網絡構建

采用圖的概念來構建情感網絡。由文獻［3］和［5］定義情感網絡圖結構：用圖結構表示，一個情感網絡圖G=（V，E，P），其中V表示情感網絡中所有節點的集合（nodes），E表示為情感網絡中所有節點之間連接關系的集合（edges），而P則用來表示情感網絡中每個節點情感的屬性（emotion）。

在構建社交網絡的過程中經常采用讀取已有網絡數據和模擬網絡生成的兩種方式，但在線爬取的網絡數據往往又很難做到數據的完整性，模擬生成的網絡又難以說明現實網絡復雜問題。所以參考構建社交網絡的過程，根據文獻［1］，我們對于構建情感網絡設計了如圖1的流程。

圖1 情感網絡流程圖

3 基于在線讀取的網絡生成

由文獻［10］建立一個模擬的微博用戶關系表，記錄了7位用戶之間的關注與被關注的關系。例如，關系id=1則說明了a用戶對于c用戶進行了關注，把關系記做edge（c，a）。關系id=3則說明了e用戶對于c用戶同時也進行了關注的行為edge（c，e）。而關系id=9則說明了c用戶對于e用戶同時也進行了關注的行為edge（e，c）。

表1 模擬數據集

根據文獻［6］用矩陣表示法首先描述表4.1數據集，網絡當中包含了7各節點，因此可以構造一個7*7的矩陣G=（gi，j）來描述該網絡關系。在這一網絡當中如g1，3=1則表示了關系id=1，如g1，2=0則表明了a與b之間不存在連接的關系，在矩陣中所有元素不為0則為1。上表的數據就可以轉化為以下矩陣G7。

4 網絡社群的發現

社群劃分類似于聚類，社群結構特點：社群內邊密度要高于社群間邊密度，社群內部連接相對緊密，各個社群之間連接相對稀疏。

社群發現有五種模型：點連接、隨機游走、自旋玻璃、中間中心度、標簽發現。

評價社群三個指標：模塊化指標Q、網絡聚類系數、網絡密度。

4.1 基于交互特征的層次聚類算法

1）將用戶的交互特征作為一個重要的社會屬性，引入到社群結構發現工作中，構造了描述社交網絡中用戶相關度的模型；

2）提出了相應的社群發掘算法，它能夠實現更加細粒度的社群發掘。

該方法的具體流程包括用戶相關度計算、社區關聯矩陣構建、社群聚類樹生成和面向不同粒度的社群分割。通過用戶相關度模型計算用戶之間的相關度，將社交網絡中的用戶之間交互操作轉化為權值，進而生成社群聚類樹，根據需求分割為不同粒度的社群。

4.2 用戶相關度模型

網絡社群中的用戶通過社交網站為媒介進行聯系。根據文獻［2］得知用戶之間的相關程度，可以通過他們基于網站的強關聯操作和弱關聯操作體現。強關聯操作指的是用戶之間較為直接的交互關系，如轉發、評論、分享等操作。弱關聯操作指的是用戶之間不太明顯的交互關系，如關注同一個公共頁面，經常到達相同的地理位置或共同使用同一個網站應用等。

為了表示用戶之間的相關程度，本文采用用戶之間的幾個常見的強關聯操作作為依據來衡量用戶之間的相關程度，具體如式（1）所示：

式中，ηij表示用戶i和用戶j的相關度，αij表示用戶i對用戶j的評論次數，βij表示用戶i對用戶j的轉發次數，λij表示用戶i對用戶j的分享次數；h1，h2，h3分別表示評論、轉發、分享這3種操作的權值。為了確定h1，h2，h3，我們分別隨機抽取N條評論、轉發和分享記錄，

分析發生在好友之間的評論、轉發和分享的發生次數分別記為h1，h2，h3，則h1=n1/（n1+n2+n3），h2=n2/（n1+n2+n3），h3=n3/（n1+n2+n3）。

基于用戶相關度，我們可以對社交網絡中的任何兩個用戶之間的交互相似度進行度量，確定用戶之間的強交互的相似程度。下面對于該問題進行形式化描述。對于一個含有n個用戶的社群Q，設其中的用戶分別為U1，U2，…，Ui，…，Un，對于其中任意用戶Ui，通過式（1）的用戶相關度公式，可以計算出他和其它N-1個用戶的相關度。

定義向量：

為用戶i社群相關度向量，則該向量表示用戶i對于社群中所有用戶的相關度。

計算出社群中所有用戶的相關度向量Ai后。定義矩陣：

為社群Q的相關度矩陣。矩陣RMQ包含了社群Q中所有用戶之間的相關度數據，反映了所有用戶之間的相關性情況。

通過用戶相關度模型，根據文獻［6］，將網絡社群內的用戶之間的關系表示為向量空間的形式。如果矩陣中兩個用戶的相關度向量相似性越高，說明他們的交際圈重合度越高，則他們屬于一個社群的概率也越大。因此，社群挖掘就轉化為了向量聚類問題。將社群內的用戶分為N個不同的社群，即將相關度模型中的用戶矩陣聚類為N個向量集合?？紤]到聚類的數量無法事先得知，本文提出了一種考慮噪音過濾的層次聚類方法，其可以根據需求，給定不同的聚類數量，得到不同粒度的聚類結果。

層次聚類方法是對給定的集中的數據，通過計算兩兩之間的距離，進行層次的分解或合并，直到某種條件滿足為止。傳統的層次聚類方法的結果是將一棵二叉樹根據需求分割為若干數量的子樹，這種方法的缺陷是對樣本信息的完備性依賴太強，無法區分噪音數據。

為了解決這個問題，本文提出了一種改進的層次聚類算法，如圖所示。首先，基于采集的用戶之間的交互操作信息，對于一個包含n個用戶在線社交網絡Q，可以計算出其用戶之間彼此的相關度矩陣RMQ。

對n個相關度向量層次聚類，首先計算彼此之間的馬氏距離，從而得到一個n*n維的距離矩陣DMQ，顯而易見，該矩陣相對于對角線對稱且對角線元素為O，其他的元素dij就代表了向量和向量之間的馬氏距離?；趯哟尉垲惖乃枷?，我們選取DMQ的下三角矩陣DMQ'，選取其中最小的元素dpq，這說明了向量和向量距離最接近，將這兩個向量合并為一個新向量，在中去掉對應于的兩行兩列，再加上與其余向量之間的距離，其中與其他向量的距離取與該向量距離的較小值。這樣，就把用戶p和用戶q合并成了一個名為用戶r的子樹，反復重復此過程，最終會形成整個社交網絡所有用戶的聚類樹。

在得到聚類樹后，我們可以將這棵聚類樹裁剪為任意數量若干子樹，每個子樹就對應了一個社群，通過聚類數量的改變就實現了不同粒度的社群發掘。具體裁剪方法是：不斷地選取根節點距離最大的兩個左右子樹，將其拆分為兩個子樹，或者將根節點距離最小的兩個子樹合并，直到數量和給定的聚類數量相等。在裁剪的過程中，我們不斷刪除子節點數量小于一定閾值的子樹，視其為游離于社群之外的噪音數據。

在網絡中社群的一般結構特點為：屬于統一社群的內的節點之間邊的密度要大于與其他社群之間的邊密度，即同一社群內部的節點之間相互連接更為密切，而不同社群之間邊的連接相對稀疏。模塊化的指標Q更多地用來衡量節點之間社群化的程度，Q的核心思想就是期望同一社群內之間的節點關聯盡可能地多，而對于不同社群之間的節點關聯盡可能地少，公式如下：

其中，m表示整個關系網絡中所有連接關系的總數目，eii為社群i里所有線的數目/m。eij表示了社群i內所有節點度數/2m。

依據文獻［13］和［14］，本節在已經讀取生成的社群基礎之上，設計了基于社群的網絡增長算法。通過網絡社群的劃分可以看出，在同一社群的網絡節點具有較高的聚類特征，社群之間的節點連接與不同社群之間的節點連接關系緊密的多，所有網絡的增長特征也應滿足這一特征，同時也要符合網絡的小世界特性。因此設計基于社群的網絡增長算法，算法設計的基本流程如圖2。由文獻［12］第一步對已有網絡結構進行隨機游走的社區發現，第二步根據已發現的社群結構進行網絡結構分割，第三步進行社群內的網絡擴增，最后對于擴增完成的網絡進行網絡合并，完成網絡的增長過程。

圖2 網絡擴增流程圖

網絡加入新節點h，首先隨機分配進入網絡的一個社群范圍，根據該社群內節點的平均影響力大小即平均度數決定h節點的度數，隨機按所給定的度數連接本社群內節點個數。下一節點i延續h節點增長策略繼續進行增長。節點的增長在同一社群內使用BA網絡模型的增長方式，通過文獻［7］網絡新增加一個節點，新增節點和已經存在節點vi相互連接的概率值∏i和節點vi的度ki以及節點vj的度kj滿足如下關系：

首先對60位微博用戶的關聯關系進行了數據讀取，使用該數據構建基礎情感網絡G=（E，V，P），對基于數據讀取的情感網絡可視化如圖4所示。

圖3 隨機游走社群網絡擴增

圖4 在線讀取情感網絡圖

基于文獻［15］對于所生成的網絡按照隨機游走的社群劃分可視化結果如圖5所示。

圖5 基于隨機游走的社群劃分圖

由圖5可以看出基于隨機游走的社群發現方法情感網路劃分為了六個大小各異的社群，采用基于社群的網絡增長算法對于劃分好的情感網絡進行網絡增長，使原有的情感網絡節點變為240個網絡節點。

5 基于社群的網絡增長

算法：基于社群的網絡增長算法

輸入：初始情感網絡G，每一社群擴展節點數N

方法：

1）Enet←Init_Enet（G）；//輸入情感網絡

2）Num ← ｛N｝；//輸入網絡擴增數量

3） Mark.groups；//社群的發現

4） Separate_groups；//社群分割

5） for i→N｛

6） node_i← BArandom//按照BA網絡規律在社群內增長

7） end for｝

8） Merge_groups；//社群合并

9）END；

輸出：增長完成的情感網絡

算法說明：由文獻［9］輸入一個網絡，具有機器學習功能，對網絡進行社群發現，按照已經發現社群網絡進行分割，得到若干子網絡。根據文獻［15］，在每個子網絡內進行網絡增長，增長結束后再重新合并網絡。

6 社群劃分分析比較

表2 社群劃分比較

圖6（a）展示了根據文獻［8］和［11］基于社群的網絡增長算法對于網絡增長做得到的最后結果。為了驗證網絡增長的結果依然符合原始社群劃分，圖6（b）是保留主要用戶關系利用Kamada-Kawai算法生成出的可視化主要關系網絡圖，不難看出增長后的情感網絡依然符合最初的情感網絡社群劃分，具有較好的效果。

圖6 微博用戶關系網絡圖（a）與主要關系圖（b）

7 結語

基于傳統復雜網絡圖論的研究方法，構建了一個具有情感特征的網絡，主要包含了情感網絡的概念定義、網絡的生成算法，網絡的動態分析展示。最后用實驗對情感網絡的構建方法進行了驗證。