基于情感網(wǎng)絡(luò)的社群發(fā)現(xiàn)與增長(zhǎng)?

馬 力 張思敏

（西安郵電大學(xué)計(jì)算機(jī)學(xué)院 西安 710061）

1 引言

隨著以社交和資訊分享為主的在線社交應(yīng)用（如微博、微信、facebook等）及在線評(píng)論的興起，不同人員之間已經(jīng)構(gòu)筑起了一個(gè)無(wú)縫的信息共享與交流平臺(tái)。它們一方面增強(qiáng)了人們信息交流的多媒體性與時(shí)效性體驗(yàn)，另一方面還使人們對(duì)信息的需求從簡(jiǎn)單的獲取與共享上升到情感表達(dá)層面。因此，進(jìn)一步拓寬人們信息利用的深度，引起了眾多學(xué)者的廣泛關(guān)注。

情感是人類智能或認(rèn)知的重要標(biāo)志，是驅(qū)動(dòng)人類行為發(fā)生的內(nèi)在心理動(dòng)因。它影響著人們的決策、學(xué)習(xí)和交流，并在人們的決策行為中起重要甚至決定性作用。認(rèn)知心理學(xué)研究表明：人們的信息交流行為是受情感影響的。真實(shí)社會(huì)中人們的情感隨其行為表示出來(lái)，并通過(guò)社會(huì)關(guān)系鏈傳播。

當(dāng)嘗試著描述某一系統(tǒng)中元素以及元素之間相互連接的概念時(shí)，“網(wǎng)”這一形式成為了自然的選擇，所以研究情感在個(gè)體之間如何傳播這一問(wèn)題時(shí)，在復(fù)雜網(wǎng)絡(luò)理論基礎(chǔ)上提出了情感網(wǎng)絡(luò)的構(gòu)建方法，基于在線網(wǎng)絡(luò)數(shù)據(jù)讀取進(jìn)行網(wǎng)絡(luò)生成、網(wǎng)絡(luò)社群劃分，提出基于網(wǎng)絡(luò)社群的網(wǎng)絡(luò)增長(zhǎng)算法。

2 情感網(wǎng)絡(luò)構(gòu)建

采用圖的概念來(lái)構(gòu)建情感網(wǎng)絡(luò)。由文獻(xiàn)［3］和［5］定義情感網(wǎng)絡(luò)圖結(jié)構(gòu)：用圖結(jié)構(gòu)表示，一個(gè)情感網(wǎng)絡(luò)圖G=（V，E，P），其中V表示情感網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合（nodes），E表示為情感網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間連接關(guān)系的集合（edges），而P則用來(lái)表示情感網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)情感的屬性（emotion）。

在構(gòu)建社交網(wǎng)絡(luò)的過(guò)程中經(jīng)常采用讀取已有網(wǎng)絡(luò)數(shù)據(jù)和模擬網(wǎng)絡(luò)生成的兩種方式，但在線爬取的網(wǎng)絡(luò)數(shù)據(jù)往往又很難做到數(shù)據(jù)的完整性，模擬生成的網(wǎng)絡(luò)又難以說(shuō)明現(xiàn)實(shí)網(wǎng)絡(luò)復(fù)雜問(wèn)題。所以參考構(gòu)建社交網(wǎng)絡(luò)的過(guò)程，根據(jù)文獻(xiàn)［1］，我們對(duì)于構(gòu)建情感網(wǎng)絡(luò)設(shè)計(jì)了如圖1的流程。

圖1 情感網(wǎng)絡(luò)流程圖

3 基于在線讀取的網(wǎng)絡(luò)生成

由文獻(xiàn)［10］建立一個(gè)模擬的微博用戶關(guān)系表，記錄了7位用戶之間的關(guān)注與被關(guān)注的關(guān)系。例如，關(guān)系id=1則說(shuō)明了a用戶對(duì)于c用戶進(jìn)行了關(guān)注，把關(guān)系記做edge（c，a）。關(guān)系id=3則說(shuō)明了e用戶對(duì)于c用戶同時(shí)也進(jìn)行了關(guān)注的行為edge（c，e）。而關(guān)系id=9則說(shuō)明了c用戶對(duì)于e用戶同時(shí)也進(jìn)行了關(guān)注的行為edge（e，c）。

表1 模擬數(shù)據(jù)集

根據(jù)文獻(xiàn)［6］用矩陣表示法首先描述表4.1數(shù)據(jù)集，網(wǎng)絡(luò)當(dāng)中包含了7各節(jié)點(diǎn)，因此可以構(gòu)造一個(gè)7*7的矩陣G=（gi，j）來(lái)描述該網(wǎng)絡(luò)關(guān)系。在這一網(wǎng)絡(luò)當(dāng)中如g1，3=1則表示了關(guān)系id=1，如g1，2=0則表明了a與b之間不存在連接的關(guān)系，在矩陣中所有元素不為0則為1。上表的數(shù)據(jù)就可以轉(zhuǎn)化為以下矩陣G7。

4 網(wǎng)絡(luò)社群的發(fā)現(xiàn)

社群劃分類似于聚類，社群結(jié)構(gòu)特點(diǎn)：社群內(nèi)邊密度要高于社群間邊密度，社群內(nèi)部連接相對(duì)緊密，各個(gè)社群之間連接相對(duì)稀疏。

社群發(fā)現(xiàn)有五種模型：點(diǎn)連接、隨機(jī)游走、自旋玻璃、中間中心度、標(biāo)簽發(fā)現(xiàn)。

評(píng)價(jià)社群三個(gè)指標(biāo)：模塊化指標(biāo)Q、網(wǎng)絡(luò)聚類系數(shù)、網(wǎng)絡(luò)密度。

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

1）將用戶的交互特征作為一個(gè)重要的社會(huì)屬性，引入到社群結(jié)構(gòu)發(fā)現(xiàn)工作中，構(gòu)造了描述社交網(wǎng)絡(luò)中用戶相關(guān)度的模型；

2）提出了相應(yīng)的社群發(fā)掘算法，它能夠?qū)崿F(xiàn)更加細(xì)粒度的社群發(fā)掘。

該方法的具體流程包括用戶相關(guān)度計(jì)算、社區(qū)關(guān)聯(lián)矩陣構(gòu)建、社群聚類樹生成和面向不同粒度的社群分割。通過(guò)用戶相關(guān)度模型計(jì)算用戶之間的相關(guān)度，將社交網(wǎng)絡(luò)中的用戶之間交互操作轉(zhuǎn)化為權(quán)值，進(jìn)而生成社群聚類樹，根據(jù)需求分割為不同粒度的社群。

4.2 用戶相關(guān)度模型

網(wǎng)絡(luò)社群中的用戶通過(guò)社交網(wǎng)站為媒介進(jìn)行聯(lián)系。根據(jù)文獻(xiàn)［2］得知用戶之間的相關(guān)程度，可以通過(guò)他們基于網(wǎng)站的強(qiáng)關(guān)聯(lián)操作和弱關(guān)聯(lián)操作體現(xiàn)。強(qiáng)關(guān)聯(lián)操作指的是用戶之間較為直接的交互關(guān)系，如轉(zhuǎn)發(fā)、評(píng)論、分享等操作。弱關(guān)聯(lián)操作指的是用戶之間不太明顯的交互關(guān)系，如關(guān)注同一個(gè)公共頁(yè)面，經(jīng)常到達(dá)相同的地理位置或共同使用同一個(gè)網(wǎng)站應(yīng)用等。

為了表示用戶之間的相關(guān)程度，本文采用用戶之間的幾個(gè)常見(jiàn)的強(qiáng)關(guān)聯(lián)操作作為依據(jù)來(lái)衡量用戶之間的相關(guān)程度，具體如式（1）所示：

式中，ηij表示用戶i和用戶j的相關(guān)度，αij表示用戶i對(duì)用戶j的評(píng)論次數(shù)，βij表示用戶i對(duì)用戶j的轉(zhuǎn)發(fā)次數(shù)，λij表示用戶i對(duì)用戶j的分享次數(shù)；h1，h2，h3分別表示評(píng)論、轉(zhuǎn)發(fā)、分享這3種操作的權(quán)值。為了確定h1，h2，h3，我們分別隨機(jī)抽取N條評(píng)論、轉(zhuǎn)發(fā)和分享記錄，

分析發(fā)生在好友之間的評(píng)論、轉(zhuǎn)發(fā)和分享的發(fā)生次數(shù)分別記為h1，h2，h3，則h1=n1/（n1+n2+n3），h2=n2/（n1+n2+n3），h3=n3/（n1+n2+n3）。

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

定義向量：

為用戶i社群相關(guān)度向量，則該向量表示用戶i對(duì)于社群中所有用戶的相關(guān)度。

計(jì)算出社群中所有用戶的相關(guān)度向量Ai后。定義矩陣：

為社群Q的相關(guān)度矩陣。矩陣RMQ包含了社群Q中所有用戶之間的相關(guān)度數(shù)據(jù)，反映了所有用戶之間的相關(guān)性情況。

通過(guò)用戶相關(guān)度模型，根據(jù)文獻(xiàn)［6］，將網(wǎng)絡(luò)社群內(nèi)的用戶之間的關(guān)系表示為向量空間的形式。如果矩陣中兩個(gè)用戶的相關(guān)度向量相似性越高，說(shuō)明他們的交際圈重合度越高，則他們屬于一個(gè)社群的概率也越大。因此，社群挖掘就轉(zhuǎn)化為了向量聚類問(wèn)題。將社群內(nèi)的用戶分為N個(gè)不同的社群，即將相關(guān)度模型中的用戶矩陣聚類為N個(gè)向量集合。考慮到聚類的數(shù)量無(wú)法事先得知，本文提出了一種考慮噪音過(guò)濾的層次聚類方法，其可以根據(jù)需求，給定不同的聚類數(shù)量，得到不同粒度的聚類結(jié)果。

層次聚類方法是對(duì)給定的集中的數(shù)據(jù)，通過(guò)計(jì)算兩兩之間的距離，進(jìn)行層次的分解或合并，直到某種條件滿足為止。傳統(tǒng)的層次聚類方法的結(jié)果是將一棵二叉樹根據(jù)需求分割為若干數(shù)量的子樹，這種方法的缺陷是對(duì)樣本信息的完備性依賴太強(qiáng)，無(wú)法區(qū)分噪音數(shù)據(jù)。

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

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

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

在網(wǎng)絡(luò)中社群的一般結(jié)構(gòu)特點(diǎn)為：屬于統(tǒng)一社群的內(nèi)的節(jié)點(diǎn)之間邊的密度要大于與其他社群之間的邊密度，即同一社群內(nèi)部的節(jié)點(diǎn)之間相互連接更為密切，而不同社群之間邊的連接相對(duì)稀疏。模塊化的指標(biāo)Q更多地用來(lái)衡量節(jié)點(diǎn)之間社群化的程度，Q的核心思想就是期望同一社群內(nèi)之間的節(jié)點(diǎn)關(guān)聯(lián)盡可能地多，而對(duì)于不同社群之間的節(jié)點(diǎn)關(guān)聯(lián)盡可能地少，公式如下：

其中，m表示整個(gè)關(guān)系網(wǎng)絡(luò)中所有連接關(guān)系的總數(shù)目，eii為社群i里所有線的數(shù)目/m。eij表示了社群i內(nèi)所有節(jié)點(diǎn)度數(shù)/2m。

依據(jù)文獻(xiàn)［13］和［14］，本節(jié)在已經(jīng)讀取生成的社群基礎(chǔ)之上，設(shè)計(jì)了基于社群的網(wǎng)絡(luò)增長(zhǎng)算法。通過(guò)網(wǎng)絡(luò)社群的劃分可以看出，在同一社群的網(wǎng)絡(luò)節(jié)點(diǎn)具有較高的聚類特征，社群之間的節(jié)點(diǎn)連接與不同社群之間的節(jié)點(diǎn)連接關(guān)系緊密的多，所有網(wǎng)絡(luò)的增長(zhǎng)特征也應(yīng)滿足這一特征，同時(shí)也要符合網(wǎng)絡(luò)的小世界特性。因此設(shè)計(jì)基于社群的網(wǎng)絡(luò)增長(zhǎng)算法，算法設(shè)計(jì)的基本流程如圖2。由文獻(xiàn)［12］第一步對(duì)已有網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行隨機(jī)游走的社區(qū)發(fā)現(xiàn)，第二步根據(jù)已發(fā)現(xiàn)的社群結(jié)構(gòu)進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)分割，第三步進(jìn)行社群內(nèi)的網(wǎng)絡(luò)擴(kuò)增，最后對(duì)于擴(kuò)增完成的網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)合并，完成網(wǎng)絡(luò)的增長(zhǎng)過(guò)程。

圖2 網(wǎng)絡(luò)擴(kuò)增流程圖

網(wǎng)絡(luò)加入新節(jié)點(diǎn)h，首先隨機(jī)分配進(jìn)入網(wǎng)絡(luò)的一個(gè)社群范圍，根據(jù)該社群內(nèi)節(jié)點(diǎn)的平均影響力大小即平均度數(shù)決定h節(jié)點(diǎn)的度數(shù)，隨機(jī)按所給定的度數(shù)連接本社群內(nèi)節(jié)點(diǎn)個(gè)數(shù)。下一節(jié)點(diǎn)i延續(xù)h節(jié)點(diǎn)增長(zhǎng)策略繼續(xù)進(jìn)行增長(zhǎng)。節(jié)點(diǎn)的增長(zhǎng)在同一社群內(nèi)使用BA網(wǎng)絡(luò)模型的增長(zhǎng)方式，通過(guò)文獻(xiàn)［7］網(wǎng)絡(luò)新增加一個(gè)節(jié)點(diǎn)，新增節(jié)點(diǎn)和已經(jīng)存在節(jié)點(diǎn)vi相互連接的概率值∏i和節(jié)點(diǎn)vi的度ki以及節(jié)點(diǎn)vj的度kj滿足如下關(guān)系：

首先對(duì)60位微博用戶的關(guān)聯(lián)關(guān)系進(jìn)行了數(shù)據(jù)讀取，使用該數(shù)據(jù)構(gòu)建基礎(chǔ)情感網(wǎng)絡(luò)G=（E，V，P），對(duì)基于數(shù)據(jù)讀取的情感網(wǎng)絡(luò)可視化如圖4所示。

圖3 隨機(jī)游走社群網(wǎng)絡(luò)擴(kuò)增

圖4 在線讀取情感網(wǎng)絡(luò)圖

基于文獻(xiàn)［15］對(duì)于所生成的網(wǎng)絡(luò)按照隨機(jī)游走的社群劃分可視化結(jié)果如圖5所示。

圖5 基于隨機(jī)游走的社群劃分圖

由圖5可以看出基于隨機(jī)游走的社群發(fā)現(xiàn)方法情感網(wǎng)路劃分為了六個(gè)大小各異的社群，采用基于社群的網(wǎng)絡(luò)增長(zhǎng)算法對(duì)于劃分好的情感網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)增長(zhǎng)，使原有的情感網(wǎng)絡(luò)節(jié)點(diǎn)變?yōu)?40個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。

5 基于社群的網(wǎng)絡(luò)增長(zhǎng)

算法：基于社群的網(wǎng)絡(luò)增長(zhǎng)算法

輸入：初始情感網(wǎng)絡(luò)G，每一社群擴(kuò)展節(jié)點(diǎn)數(shù)N

方法：

1）Enet←Init_Enet（G）；//輸入情感網(wǎng)絡(luò)

2）Num ← ｛N｝；//輸入網(wǎng)絡(luò)擴(kuò)增數(shù)量

3） Mark.groups；//社群的發(fā)現(xiàn)

4） Separate_groups；//社群分割

5） for i→N｛

6） node_i← BArandom//按照BA網(wǎng)絡(luò)規(guī)律在社群內(nèi)增長(zhǎng)

7） end for｝

8） Merge_groups；//社群合并

9）END；

輸出：增長(zhǎng)完成的情感網(wǎng)絡(luò)

算法說(shuō)明：由文獻(xiàn)［9］輸入一個(gè)網(wǎng)絡(luò)，具有機(jī)器學(xué)習(xí)功能，對(duì)網(wǎng)絡(luò)進(jìn)行社群發(fā)現(xiàn)，按照已經(jīng)發(fā)現(xiàn)社群網(wǎng)絡(luò)進(jìn)行分割，得到若干子網(wǎng)絡(luò)。根據(jù)文獻(xiàn)［15］，在每個(gè)子網(wǎng)絡(luò)內(nèi)進(jìn)行網(wǎng)絡(luò)增長(zhǎng)，增長(zhǎng)結(jié)束后再重新合并網(wǎng)絡(luò)。

6 社群劃分分析比較

表2 社群劃分比較

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

圖6 微博用戶關(guān)系網(wǎng)絡(luò)圖（a）與主要關(guān)系圖（b）

7 結(jié)語(yǔ)

基于傳統(tǒng)復(fù)雜網(wǎng)絡(luò)圖論的研究方法，構(gòu)建了一個(gè)具有情感特征的網(wǎng)絡(luò)，主要包含了情感網(wǎng)絡(luò)的概念定義、網(wǎng)絡(luò)的生成算法，網(wǎng)絡(luò)的動(dòng)態(tài)分析展示。最后用實(shí)驗(yàn)對(duì)情感網(wǎng)絡(luò)的構(gòu)建方法進(jìn)行了驗(yàn)證。