微博用戶模型復(fù)雜網(wǎng)絡(luò)中多維有向社區(qū)發(fā)現(xiàn)

劉大?！埐╀h　鄒國兵　顧程偉

(上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院　上海 200444)

?

微博用戶模型復(fù)雜網(wǎng)絡(luò)中多維有向社區(qū)發(fā)現(xiàn)

劉大海張博鋒鄒國兵顧程偉

(上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院上海 200444)

摘要大多數(shù)社區(qū)發(fā)現(xiàn)是基于一種信息的，即從一個(gè)維度來劃分社區(qū)。但在現(xiàn)實(shí)場景中，用戶之間社區(qū)構(gòu)成是受興趣、社交關(guān)系、地域、教育背景等諸多因素共同影響形成的。這些多維信息有些是無向的，如興趣相似度等;有些是有向的，如關(guān)注關(guān)系等。根據(jù)有向社區(qū)發(fā)現(xiàn)的原理，將多個(gè)維度的信息融合，提出一種面向多維復(fù)雜網(wǎng)絡(luò)的有向社區(qū)發(fā)現(xiàn)(MDCD)算法。通過實(shí)驗(yàn)證明，MDCD算法相對于傳統(tǒng)的多維社區(qū)發(fā)現(xiàn)方法AMM算法，社區(qū)發(fā)現(xiàn)結(jié)果準(zhǔn)確率提高了17.7%、F-measure值提高了0.068；與一維的興趣相似度網(wǎng)絡(luò)進(jìn)行對比，MDCD算法的三維復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)結(jié)果的準(zhǔn)確率提高了36.1%、召回率提高了25.3%。由于多維有向社區(qū)發(fā)現(xiàn)綜合考慮了多維的信息，得到的社區(qū)結(jié)構(gòu)具有更重要的社會(huì)意義。

關(guān)鍵詞用戶模型復(fù)雜網(wǎng)絡(luò)多維有向社區(qū)發(fā)現(xiàn)

0引言

以Twitter、新浪微博、騰訊微博為代表的社交網(wǎng)絡(luò)及微博客服務(wù)網(wǎng)站已經(jīng)成為一種社會(huì)媒體的代表，已經(jīng)在人們的生活中成為重要的信息交流平臺(tái)?，F(xiàn)在微博用戶模型是以用戶作為社交網(wǎng)絡(luò)的節(jié)點(diǎn)，好友相互關(guān)注關(guān)系、用戶喜歡的內(nèi)容、地理位置作為社交網(wǎng)絡(luò)的邊，以此形式構(gòu)成了多個(gè)維度的復(fù)雜網(wǎng)絡(luò)，進(jìn)而進(jìn)行社交網(wǎng)絡(luò)的社區(qū)劃分。

復(fù)雜網(wǎng)絡(luò)中存在的社區(qū)結(jié)構(gòu)是以子網(wǎng)絡(luò)內(nèi)部存在多條相互關(guān)聯(lián)的邊，每個(gè)子網(wǎng)絡(luò)與其他網(wǎng)絡(luò)之間存在少量相互關(guān)聯(lián)的邊構(gòu)成的。子網(wǎng)絡(luò)本身構(gòu)成一個(gè)社區(qū)，網(wǎng)絡(luò)內(nèi)部的節(jié)點(diǎn)也具有相同或者相似的屬性[1]?，F(xiàn)在的社交發(fā)現(xiàn)算法在劃分復(fù)雜網(wǎng)絡(luò)過程中，大多是基于單維度因素進(jìn)行社區(qū)劃分的。但現(xiàn)實(shí)場景中，用戶間社區(qū)是受興趣、社交關(guān)系、地域、教育背景等諸多因素共同影響的，所以只考慮了一個(gè)維度的信息的社區(qū)劃分不符合現(xiàn)實(shí)應(yīng)用的。同時(shí)，鑒于用戶關(guān)系和用戶信息具有數(shù)據(jù)關(guān)系冗雜、數(shù)據(jù)存儲(chǔ)量巨大、數(shù)據(jù)分布離散等特點(diǎn)，復(fù)雜網(wǎng)絡(luò)劃分算法根據(jù)其屬性特點(diǎn)，對其進(jìn)行綜合利用、融合分析，是現(xiàn)在研究的主要方面。

現(xiàn)有社區(qū)劃分算法主要有GN算法[2]、譜平分法[3]、近似GN算法[4]、結(jié)構(gòu)相似度算法[5]、最大化模塊度算法[6]、優(yōu)化模塊度算法[7]、基于模塊度快速算法[10]、多維信息融合的社區(qū)劃分方法[11]等。

GN算法[2]是優(yōu)先刪除邊介數(shù)最大的邊，直至整個(gè)網(wǎng)絡(luò)退化成一個(gè)社區(qū)為止。此類算法不需要預(yù)先知曉社區(qū)個(gè)數(shù)，針對層級結(jié)構(gòu)社區(qū)劃分較為友好，但其計(jì)算復(fù)雜度較高。

近似GN算法[4]是Tyler等人將統(tǒng)計(jì)方法引入GN算法中，Radicchi等人提出近似GN的層次算法，繼續(xù)對GN算法進(jìn)行的改良，其算法是以邊聚系數(shù)Edge Clustering Coefficient作為判斷環(huán)路個(gè)數(shù)的參數(shù)。

結(jié)構(gòu)相似度算法[5]是由劉大有等人提出的，其算法思想由結(jié)構(gòu)相似度代替GN算法中的邊介數(shù)概念，但是該方法主要是針對社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)的，不適用于其他類型的復(fù)雜網(wǎng)絡(luò)。

最大模塊度算法[6]是根據(jù)社區(qū)模塊度指標(biāo)來衡量社區(qū)分類是否符合實(shí)際的社區(qū)劃分。模塊度作為社區(qū)劃分的目標(biāo)函數(shù)，其主要思想是將實(shí)際網(wǎng)絡(luò)中的社區(qū)內(nèi)部已經(jīng)存在的邊減去偽隨機(jī)網(wǎng)絡(luò)中連接社區(qū)內(nèi)部節(jié)點(diǎn)所需的邊的期望值。

優(yōu)化模塊度算法[7]不局限于無向圖網(wǎng)絡(luò)，實(shí)際生活中關(guān)聯(lián)往往是有方向性的。所以，Newman又提出了有向網(wǎng)絡(luò)的模塊度，如式(1)所示：

(1)

Chauhan[8]等人通過網(wǎng)絡(luò)的鄰近矩陣的最大特征值來劃分社區(qū)。Newman[9]將已有的社區(qū)劃分方法例如譜分析法映射到圖的最小割方法中，并使用最大似然估計(jì)將全局搜索變?yōu)榫植克阉鳎?shí)現(xiàn)對無向圖的社區(qū)劃分。

基于模塊度的快速算法[10]是Blondel等人提出的一種在大規(guī)模復(fù)雜網(wǎng)絡(luò)中的快速社區(qū)發(fā)現(xiàn)算法，算法是基于模塊度最優(yōu)的探索式算法，首先將社區(qū)中每個(gè)節(jié)點(diǎn)視為一個(gè)社區(qū)，之后將此節(jié)點(diǎn)置入鄰近節(jié)點(diǎn)社區(qū)中，計(jì)算其相應(yīng)的模塊度，如果模塊度增加，則將此節(jié)點(diǎn)社區(qū)并入鄰近社區(qū)中；否則保持不變。以此類推，循環(huán)執(zhí)行這個(gè)過程，直至所有社區(qū)達(dá)到穩(wěn)定程度。之后，構(gòu)建上層網(wǎng)絡(luò)，重復(fù)進(jìn)行上述社區(qū)合并過程，直到模塊度不再增加為止。該算法過程簡單，但其僅考慮無向網(wǎng)絡(luò)的社區(qū)劃分情況。

Lei Tang等人提出了多維信息融合的社區(qū)劃分方法AMM[11]。該方法是將多維信息網(wǎng)絡(luò)先融合成一個(gè)維度網(wǎng)絡(luò)，然后用經(jīng)典的方法進(jìn)行社區(qū)劃分。它的融合方法是非常粗糙的，只是進(jìn)行了多個(gè)維度網(wǎng)絡(luò)的簡單加和求平均，它的結(jié)果優(yōu)劣主要側(cè)重在之后的單維劃分方法的效果。

上述各類算法都是經(jīng)典的社區(qū)劃分方法，但它們都是針對單一維度的信息進(jìn)行劃分或粗糙地進(jìn)行多維融合劃分的。對此，本文針對微博用戶模型復(fù)雜網(wǎng)絡(luò)，提出了一種多維有向社區(qū)發(fā)現(xiàn)方法(MDCD)，并通過實(shí)驗(yàn)對MDCD算法進(jìn)行了測試和對比，相比其他多維算法和單維網(wǎng)絡(luò)，得到了比較良好和有意義的社區(qū)劃分結(jié)果。

1多維用戶模型網(wǎng)絡(luò)的構(gòu)建

通過騰訊微博收集了12 761個(gè)用戶的信息、微博和相互關(guān)注關(guān)系，然后對其中用戶進(jìn)行篩選，選出活躍用戶3 856個(gè)。對此3 856個(gè)用戶進(jìn)行用戶模型網(wǎng)絡(luò)的建立。本文采用用戶社交關(guān)系、地理位置信息和興趣相似度三個(gè)維度構(gòu)建多維用戶模型復(fù)雜網(wǎng)絡(luò)。

用戶社交關(guān)系網(wǎng)絡(luò)，即是用戶之間的關(guān)注與被關(guān)注關(guān)系，這些現(xiàn)實(shí)生活中用戶的主動(dòng)發(fā)出的行為，是一種強(qiáng)關(guān)系，構(gòu)成了用戶社會(huì)關(guān)系網(wǎng)絡(luò)的有向邊。這種強(qiáng)關(guān)系，非有即無，所以，定義邊的權(quán)重為1。即社交關(guān)系網(wǎng)絡(luò)是一個(gè)有向帶權(quán)圖。

用戶地理位置網(wǎng)絡(luò)，既是用戶的基本信息里的地理信息，如果是同一個(gè)地方的則有邊的聯(lián)系。在用戶地理位置信息里，分為三個(gè)粒度：國家、省份和城市。所以定義國家相同為第一等級，國家與省份相同為第二等級，國家、省份和城市相同為第三等級。量化用戶之間的地理關(guān)系φ(x1,x2,y1,y2,z1,z2)如式(2)所示：

(2)

其中，x1、x2表示兩個(gè)用戶所屬的國家，y1、y2表示兩個(gè)用戶所屬的省份，z1、z2表示兩個(gè)用戶所屬的城市。

出于隱私等原因，有些用戶的地理位置信息是不完全的，再者如果存在大量的同一個(gè)國家的用戶，會(huì)造成用戶之間的連接過多從而導(dǎo)致的計(jì)算量過大，所以根據(jù)實(shí)際擁有地理位置的用戶數(shù)與總用戶數(shù)之比，來確定地理關(guān)系φ(x1,x2,y1,y2,z1,z2)的取舍。當(dāng)實(shí)際擁有地理位置的用戶數(shù)與總用戶數(shù)之比大于50%時(shí)，φ(x1,x2,y1,y2,z1,z2)只取等于1(即相同城市)的地理關(guān)系；否則，φ(x1,x2,y1,y2,z1,z2)就取等于1(即相同城市)和0.5(即相同省份)的地理關(guān)系。這樣即構(gòu)建成了一個(gè)地理位置無向帶權(quán)圖。

前兩個(gè)網(wǎng)絡(luò)都很好構(gòu)建，構(gòu)建最復(fù)雜的就是第三個(gè)：用戶興趣相似度網(wǎng)絡(luò)。它是由用戶模型[12]中的用戶興趣度計(jì)算出來的。用戶興趣度則是將用戶的微博內(nèi)容用TF-IDF(Term frequency - inverse document frequency)方法[13,14]和本體庫進(jìn)行結(jié)合計(jì)算得到的。

有些用戶之間的興趣相似度很低，而且如果兩兩用戶的興趣度都放進(jìn)網(wǎng)絡(luò)，那么這個(gè)網(wǎng)絡(luò)就是個(gè)完全圖，這樣不僅增加了計(jì)算量，而且這樣的圖進(jìn)行社區(qū)劃分是沒有意義的。所以，根據(jù)復(fù)雜網(wǎng)絡(luò)的邊數(shù)定義：邊數(shù)=nlnn，n是圖的節(jié)點(diǎn)數(shù)，選定一個(gè)閾值α，小于α的興趣相似度都裁剪掉。然后，再計(jì)算出一些被裁剪掉而沒有邊的孤立節(jié)點(diǎn)的最大相似度邊，將其加入到裁剪后的網(wǎng)絡(luò)中，從而形成了用戶興趣相似度網(wǎng)絡(luò)。這個(gè)網(wǎng)絡(luò)就代表用戶與用戶之間對于某個(gè)領(lǐng)域或某個(gè)話題具有共同的愛好或興趣。所以，用戶興趣相似度網(wǎng)絡(luò)是一個(gè)無向帶權(quán)圖。

2多維有向社區(qū)發(fā)現(xiàn)方法

本文的多維有向社區(qū)發(fā)現(xiàn)方法是對社交關(guān)系(有向)、興趣相似度(無向)和地理位置信息(無向)三個(gè)維度的融合網(wǎng)絡(luò)，充分考慮其邊的方向性，進(jìn)行社區(qū)發(fā)現(xiàn)的。

2.1無向邊分析

在微博網(wǎng)絡(luò)中，用戶與用戶之間的興趣相似度是很重要的關(guān)聯(lián)。興趣相似度是根據(jù)用戶所發(fā)的或者轉(zhuǎn)發(fā)的微博內(nèi)容，經(jīng)過本體庫的基礎(chǔ)計(jì)算出來的語義度，再計(jì)算出來的用戶之間的語義興趣相似度組成用戶之間的網(wǎng)絡(luò)聯(lián)系的，這樣的網(wǎng)絡(luò)圖代表了用戶所感興趣的東西或者話題，是具有很高的價(jià)值的。

而另一種社交信息組成的網(wǎng)絡(luò)則是不同類型的，用戶與用戶的社交關(guān)系網(wǎng)絡(luò)是有向無權(quán)圖，而用戶之間的興趣相似度網(wǎng)絡(luò)是無向有權(quán)的圖，這其中最關(guān)鍵的是有向圖與無向圖，即邊的方向性。有向圖的方向性代表了非常重要的信息，不能直接將其方向性抹掉。那么思考從無向圖入手，無向圖本身其實(shí)代表的是兩個(gè)用戶之間的關(guān)系，用戶1對用戶2與用戶2對用戶1，都是具有等價(jià)的意義的。所以，就將無向圖的一條邊，拆分成兩條有向邊：一條是用戶1指向用戶2，一條是用戶2指向用戶1，且這兩條有向邊都具有權(quán)重并且權(quán)重相等，如圖1所示。

圖1　無向邊轉(zhuǎn)換成為有向邊

所以，無向圖也就可以轉(zhuǎn)換成有向圖。

在闡述算法之前，先進(jìn)行分析和定義幾個(gè)概念[15,16]，本節(jié)的算法也是根據(jù)文獻(xiàn)[15]中一部分算法改進(jìn)的。

2.2有向邊的影響力分析

在有向圖中，每個(gè)節(jié)點(diǎn)的度分為入度和出度。入度和出度分別代表了不同的意義，對于出度大的節(jié)點(diǎn)，可以看到出度是這個(gè)節(jié)點(diǎn)本身對別的節(jié)點(diǎn)的跟隨，而對于入度大的節(jié)點(diǎn)，入度則是這個(gè)節(jié)點(diǎn)對別的節(jié)點(diǎn)的吸引。很明顯，入度大的節(jié)點(diǎn)在這個(gè)網(wǎng)絡(luò)圖中是更重要的，它們是整個(gè)網(wǎng)絡(luò)中的樞紐，是具有高的影響力的。所以，對于每一個(gè)節(jié)點(diǎn)，入度的意義大于出度的意義，在算法中，入度的統(tǒng)計(jì)是非常重要的，它是節(jié)點(diǎn)之間的相似性的基礎(chǔ)[17]。

在有向帶權(quán)圖中，如果單純只把邊的權(quán)重值算成邊的影響力是不合適的。分析入度對節(jié)點(diǎn)的影響，可以看到一個(gè)節(jié)點(diǎn)如果入度很大，代表在這個(gè)網(wǎng)絡(luò)中對它關(guān)注的人或節(jié)點(diǎn)很多，這個(gè)節(jié)點(diǎn)的影響力很大，它如果改變，關(guān)注它的人必然也會(huì)受到一定的影響。關(guān)注的邊越多，影響范圍越大。那么，它所發(fā)出的邊，即關(guān)注他人的邊，必然要比一個(gè)很少被關(guān)注的人的影響力大。舉個(gè)例子，微博的中的大V用戶，即明星或名人用戶，他被關(guān)注的人很多；微博中的一般用戶，如我，被關(guān)注的人很少?？梢院苊黠@的看到，如果名人用戶的影響力是要大于我的，每天“看著”他的人很多，而我?guī)缀鯖]有。這樣一來，如果名人用戶主動(dòng)關(guān)注了另外一個(gè)人，無論這個(gè)人是否是大V用戶，關(guān)注名人用戶的人，肯定也會(huì)注意到這個(gè)人，至少作用到這個(gè)人的影響力要比我關(guān)注他來的大。所以，定義一個(gè)邊的影響力Ej→i，如式(3)所示：

(3)

這樣，就可以把節(jié)點(diǎn)的影響因素加到邊的上面，使邊在網(wǎng)絡(luò)中的影響力更加合理。

2.3節(jié)點(diǎn)權(quán)重的定義

節(jié)點(diǎn)的入度是關(guān)鍵，那么，節(jié)點(diǎn)的權(quán)重應(yīng)該怎么定義呢？單純用一個(gè)節(jié)點(diǎn)的入度來代表顯然是不夠的。可以看到有向邊對一個(gè)節(jié)點(diǎn)是有很明顯的作用的，同樣的，對于上一節(jié)的例子，名人用戶關(guān)注(指向)的另一個(gè)人，即使這個(gè)人的入度為1，即只有名人用戶關(guān)注他，他的影響力也比有好多個(gè)一般用戶關(guān)注的人大。這說明名人用戶關(guān)注他的那條邊對他(這個(gè)節(jié)點(diǎn))的影響力是巨大的。

所以，定義節(jié)點(diǎn)i的權(quán)重Vi，如式(4)所示：

(4)

這樣，就能計(jì)算出整個(gè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的權(quán)重值，如果一個(gè)節(jié)點(diǎn)沒有入度，那么它的權(quán)重值就是0。

2.4節(jié)點(diǎn)對社區(qū)的歸屬度

在劃分出一個(gè)社區(qū)之后，為了衡量其周圍的節(jié)點(diǎn)是否會(huì)加入到這個(gè)社區(qū)，這時(shí)候定義一個(gè)節(jié)點(diǎn)i對社區(qū)C的歸屬度A(i,C)。當(dāng)節(jié)點(diǎn)i與社區(qū)C內(nèi)的節(jié)點(diǎn)的邊的聯(lián)系比和非社區(qū)C內(nèi)的節(jié)點(diǎn)邊的聯(lián)系多，那么節(jié)點(diǎn)i就很大可能是屬于社區(qū)C的。所以歸屬度A(i,C)計(jì)算如式(5)所示：

(5)其中，wij和wji分別是節(jié)點(diǎn)i到節(jié)點(diǎn)j的邊的權(quán)重和節(jié)點(diǎn)j到節(jié)點(diǎn)i的邊的權(quán)重。當(dāng)A(i,C)>1時(shí)，節(jié)點(diǎn)i加入到社區(qū)C中，否則，則不加。

2.5算法過程

通過以上分析，MDCD算法描述如下：

1) 將單維的用戶興趣相似度無向帶權(quán)網(wǎng)絡(luò)轉(zhuǎn)換成有向帶權(quán)網(wǎng)絡(luò)；將單維的地理位置無向帶權(quán)網(wǎng)絡(luò)轉(zhuǎn)換成有向帶權(quán)網(wǎng)絡(luò)。

2) 把1)中的用戶興趣相似度有向帶權(quán)網(wǎng)絡(luò)和地理位置有向帶權(quán)網(wǎng)絡(luò)加入到社區(qū)關(guān)系有向帶權(quán)網(wǎng)絡(luò)中，由此形成一個(gè)新的融合三維的有向帶權(quán)網(wǎng)絡(luò)。

3) 統(tǒng)計(jì)新的網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的入度。

4) 根據(jù)式(3)計(jì)算整個(gè)網(wǎng)絡(luò)中每條邊的影響力。

5) 根據(jù)式(4)和上一步中計(jì)算的邊的影響力，計(jì)算整個(gè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的權(quán)重。

6) 對整個(gè)網(wǎng)絡(luò)的所有節(jié)點(diǎn)按照其的權(quán)重值進(jìn)行從大到小的排序。找出權(quán)重值最大的核心節(jié)點(diǎn)，如果有多個(gè)權(quán)重相等的節(jié)點(diǎn)，隨機(jī)選一個(gè)。從這個(gè)核心節(jié)點(diǎn)開始，將與這個(gè)核心節(jié)點(diǎn)相連接的所有其他節(jié)點(diǎn)和這個(gè)核心節(jié)點(diǎn)一起化成初始社區(qū)C。

7) 在剩余節(jié)點(diǎn)中，對和社區(qū)C內(nèi)的節(jié)點(diǎn)有邊相連的節(jié)點(diǎn)逐一計(jì)算其與社區(qū)C的歸屬度，式(5)，如果歸屬度大于1，則加入社區(qū)C，否則，不加入。

8) 對再剩余的節(jié)點(diǎn)，再回到步驟6)，直到所有節(jié)點(diǎn)都被劃分到社區(qū)中為止。如果整個(gè)網(wǎng)絡(luò)中有入度為零的節(jié)點(diǎn)，將其歸入到與之邊聯(lián)系最多的社區(qū)。

9) 由此得到了初始的社區(qū)劃分，然后根據(jù)有向模塊度[7]，對每個(gè)節(jié)點(diǎn)進(jìn)行移動(dòng)操作。即將其重新分別放入與之有邊聯(lián)系的社區(qū)，再計(jì)算網(wǎng)絡(luò)的有向模塊度，選取最大的有向模塊度所對應(yīng)的社區(qū)劃分，成為最終最優(yōu)的社區(qū)劃分。

至此，算法結(jié)束。

算法流程如圖2所示。

圖2　三維復(fù)雜網(wǎng)絡(luò)融合社區(qū)發(fā)現(xiàn)算法

3實(shí)驗(yàn)分析和對比

3.1實(shí)驗(yàn)數(shù)據(jù)準(zhǔn)備

首先通過騰訊微博的API來收集用戶的基本信息、微博內(nèi)容和用戶之間的關(guān)注與被關(guān)注關(guān)系，每隔15天收集一次，然后針對這些數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理，篩選出活躍的用戶。以用戶所發(fā)的微博為標(biāo)準(zhǔn)，選出在本次收集中，發(fā)微博數(shù)超過70以上的用戶作為活躍用戶，而且篩選出來的與之有關(guān)系(不論是地理關(guān)系還是社會(huì)關(guān)系)的用戶，都是活躍用戶，篩選出3856個(gè)活躍用戶。

3.2二維社區(qū)發(fā)現(xiàn)

首先對社交關(guān)系和興趣相似度通過MDCD算法進(jìn)行二維融合社區(qū)發(fā)現(xiàn)。因?yàn)樯缃魂P(guān)系網(wǎng)絡(luò)是一個(gè)強(qiáng)社區(qū)，所以它呈現(xiàn)除了極高的有向模塊度，而且兩個(gè)維度融合所代表的意義也是不同于一種維度的。本文通過研究它們的準(zhǔn)確率和召回率[18]，并細(xì)化到用戶與用戶之間的關(guān)系，來進(jìn)行對比。本文選擇第二批數(shù)據(jù)當(dāng)作訓(xùn)練集；選擇第六批數(shù)據(jù)作測試集，它們之間相差三個(gè)月。單個(gè)維度網(wǎng)絡(luò)和二維融合網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)對比如表1所示。

表1　單維和二維網(wǎng)絡(luò)的準(zhǔn)確率、召回率對比

首先說明，單維的社交關(guān)系網(wǎng)絡(luò)的準(zhǔn)確率和召回率都非常高，這也是很符合實(shí)際情況的。在實(shí)際生活中，用戶之間的關(guān)注與被關(guān)注這本身就是一個(gè)強(qiáng)關(guān)系，而且用戶對另一個(gè)用戶的關(guān)注或者取消關(guān)注，這本身也是一個(gè)強(qiáng)動(dòng)作，要用戶自身發(fā)出，所以它發(fā)生的頻率會(huì)很低，表現(xiàn)在數(shù)據(jù)上就是高的準(zhǔn)確率和召回率。而用戶的興趣度和興趣相似度是經(jīng)過它們的微博內(nèi)容文本語義計(jì)算出來的，在這三個(gè)月中，用戶無論是關(guān)心的話題還是熱點(diǎn)都是會(huì)發(fā)生漂移的，所以在數(shù)據(jù)上也可以看到，單維興趣相似度網(wǎng)絡(luò)的準(zhǔn)確率和召回率也充分表現(xiàn)了興趣度的漂移。再來看看它們的二維融合網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)的準(zhǔn)確率和召回率，可以發(fā)現(xiàn)，在社交關(guān)系和興趣相似度的共同作用下，二維融合網(wǎng)絡(luò)對比單維的興趣相似度網(wǎng)絡(luò)的準(zhǔn)確率和召回率，提高了2倍以上的百分點(diǎn)，這個(gè)提高是十分可觀的。融合之后的社區(qū)發(fā)現(xiàn)是把社交關(guān)系和興趣相似度一起考慮的，比單純的單維網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)有更好的意義。

通過實(shí)際的數(shù)據(jù)發(fā)現(xiàn)，用戶的社交關(guān)系網(wǎng)絡(luò)是很穩(wěn)定的，不易發(fā)生漂移的，而用戶興趣度是容易改變的，容易發(fā)生漂移。那么，聯(lián)想實(shí)際生活想想，有多少用戶是因?yàn)榕d趣度相似，產(chǎn)生了社交強(qiáng)關(guān)系。例如，我喜歡曼聯(lián)足球俱樂部，你也喜歡；我喜歡讀喬治·R·R·馬丁的小說，你也喜歡讀他的小說，雖然，我和你是實(shí)際生活不認(rèn)識(shí)的，但因?yàn)榕d趣度極度相似，會(huì)產(chǎn)生例如我關(guān)注你、你關(guān)注我或我們相互關(guān)注的強(qiáng)關(guān)系。相似的，也有部分用戶本來相互關(guān)注或單方向關(guān)注，但因?yàn)榕d趣度的轉(zhuǎn)移，興趣度逐漸不同，可能也會(huì)發(fā)生相互取消關(guān)注的行為。興趣度和社交關(guān)系之間的影響正是融合所要研究意義所在。那么，可將用戶之間的這類關(guān)系分成如下兩種：

1) 第二批社交關(guān)系存在，第二批興趣相似度不存在，導(dǎo)致第六批社交關(guān)系不存在；

2) 第二批社交關(guān)系不存在，第二批興趣相似度存在，導(dǎo)致第六批社交關(guān)系存在。

首先來看關(guān)系1)，通過計(jì)算，得到從第二批數(shù)據(jù)到第六批數(shù)據(jù)這段時(shí)間，有4637條社交關(guān)系(含有2894個(gè)用戶)是因?yàn)橛脩糁g沒有興趣相似度改變了。而原來社交關(guān)系中，共有14770條關(guān)系和3856個(gè)用戶，由此可以得到總共有31.4%的關(guān)系被改變了，75.1%的用戶受到了影響。這只是一個(gè)粗略的數(shù)據(jù)，因?yàn)樵谶@里面也會(huì)有興趣度相似的用戶，但可能因?yàn)樵谏缃魂P(guān)系上兩人鬧矛盾等原因，直接取消關(guān)注的情況。再經(jīng)過計(jì)算，得出這其中有138條關(guān)系(包含242個(gè)人)，它們兩兩用戶之間其實(shí)是屬于同一個(gè)興趣度社區(qū)的，也就是說，精確的數(shù)據(jù)是4499條關(guān)系(30.5%)和2652個(gè)用戶(68.8%)，它們的變化是受到了興趣度的影響，這個(gè)比例是非常巨大的。

關(guān)系2)更能精確地表達(dá)出社交關(guān)系和興趣相似度之間的影響，計(jì)算得出，本來沒有社交關(guān)系的用戶，因?yàn)橛泄餐臉O強(qiáng)的興趣相似度，他們最后發(fā)生了關(guān)注的社交關(guān)系，這樣的用戶一共有34個(gè)，他們做出的關(guān)注的強(qiáng)關(guān)系有17條，數(shù)據(jù)如圖3所示。

圖3　受到興趣相似度影響而發(fā)生社交關(guān)系的用戶

可以看到，這34個(gè)用戶共同屬于的興趣度社區(qū)也已經(jīng)標(biāo)識(shí)出來。他們兩兩都是屬于同一個(gè)興趣度社區(qū)的，說明這17條關(guān)系是100%受到興趣度影響而形成的。同樣的，從整個(gè)社區(qū)來看，有0.9%的用戶收到了影響。結(jié)合實(shí)際，這是非常符合現(xiàn)實(shí)社交關(guān)系的，當(dāng)兩個(gè)用戶，要發(fā)出關(guān)注這種很強(qiáng)的需要人為主動(dòng)的社交關(guān)系時(shí)，如果兩個(gè)人只有一點(diǎn)兒興趣度相似是不行的，只有他們有著極強(qiáng)的興趣相似度，他們才有可能發(fā)出關(guān)注的行為。

通過分析可以知道，用戶的社交關(guān)系和興趣相似度是密切相關(guān)的，將它們?nèi)诤显谝黄疬M(jìn)行社區(qū)發(fā)現(xiàn)是非常有意義的，而且結(jié)果也是理想的，本文所做工作也正是為了這些相互有影響的用戶和關(guān)系。

3.3三維社區(qū)發(fā)現(xiàn)

(1) 與二維社區(qū)發(fā)現(xiàn)對比

對社交關(guān)系、地理位置關(guān)系和興趣相似度通過MDCD算法進(jìn)行三維融合社區(qū)發(fā)現(xiàn)。將三維融合和二維融合結(jié)果進(jìn)行對比，如表2所示。

表2　二維和三維網(wǎng)絡(luò)的對比

無論在有向模塊度Q還是準(zhǔn)確率上，三維的社區(qū)發(fā)現(xiàn)結(jié)果都要更好。三維的社區(qū)劃分，不僅在社區(qū)結(jié)構(gòu)上表現(xiàn)的更加好，而且在用戶的準(zhǔn)確率上也提升明顯。召回率雖然有所下降，但其實(shí)差別不大，而且影響也不大。所以三維的融合社區(qū)劃分有著更豐富的意義和理想的結(jié)果。

(2) 與傳統(tǒng)多維社區(qū)發(fā)現(xiàn)對比

本文MDCD算法與Lei Tang等人提出的多維信息融合的社區(qū)發(fā)現(xiàn)方法AMM算法進(jìn)行比較。其中，Lei Tang等的方法中單維的社區(qū)發(fā)現(xiàn)算法選用效果非常好的Blondel等人提出的快速社區(qū)發(fā)現(xiàn)算法[9]。將兩種算法同時(shí)運(yùn)用在三維網(wǎng)絡(luò)中，得到的準(zhǔn)確率、召回率和F-measure值對比如表3所示。

可以得出,MDCD算法在準(zhǔn)確率上比AMM方法高17.7%。本文的MDCD算法將不同維度網(wǎng)絡(luò)的方向性考慮進(jìn)去，并且進(jìn)行了合理的方向分析，有效地規(guī)避了AMM方法的不足。從而得到了不錯(cuò)的社區(qū)結(jié)構(gòu)和劃分結(jié)果。

4結(jié)語

以往的社區(qū)發(fā)現(xiàn)方法大多都是基于單個(gè)維度的，它們只采用一個(gè)方面信息進(jìn)行社區(qū)發(fā)現(xiàn)。在多維發(fā)現(xiàn)中，也沒有將邊的方向進(jìn)行充分的考慮。本文在多維微博用戶模型網(wǎng)絡(luò)的基礎(chǔ)上，提出了多維有向網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法MDCD，將多個(gè)維度綜合考慮，并且考慮了邊的方向，得到了良好的結(jié)果。在準(zhǔn)確率、召回率和F-measure值上比單維和已有的多維方法有了一定的提升，并且社區(qū)結(jié)構(gòu)也具有更重要的社會(huì)意義。

參考文獻(xiàn)

[1] Radicchi F,Castellano C,Cecconi F,et al.Defining and identifying communities in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(9):2658-2663.

[2] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

[3] Pengli Lu,Shenglong Zhang.Node Similarity Reveals Community Structure in Complex Networks[J].International Journal of Advancements in Computing Technology,2013,5(3):387-392.

[4] Tyler J R,Wilkinson D M,Huberman B A.E-mail as spectroscopy:Automated discovery of community structure within organizations[J].The Information Society,2005,21(2):143-153.

[5] 金弟,劉杰,賈正雪,等.基于 k 最近鄰網(wǎng)絡(luò)的數(shù)據(jù)聚類算法[J].模式識(shí)別與人工智能,2010,23(4):546-551.

[6] Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical review E,2004,69(6):066133.

[7] Leicht E A,Newman M E J.Community structure in directed networks[J].Physical review letters,2008,100(11):118703.

[8] Chauhan S,Girvan M,Ott E.A network function-based definition of communities in complex networks[J].Chaos:An Interdisciplinary Journal of Nonlinear Science,2012,22(3):033129.

[9] Newman M E J.Community detection and graph partitioning[J].EPL,2013,103:330-337.

[10] Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics Theory and Experiment,2008,30(2):155-168

[11] Tang L,Liu H.Uncovering cross-dimension group structures in multi-dimensional networks[C]//SDM workshop on Analysis of Dynamic Networks.2009.

[12] 潘建國.基于語義的用戶建模技術(shù)與應(yīng)用研究[D].上海:上海大學(xué),2009.

[13] 黃承慧,印鑒,侯昉.一種結(jié)合詞項(xiàng)語義信息和TF-IDF方法的文本相似度量方法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(5):856-864.

[14] Chowdhury G.Introduction to modern information retrieval[M].Facet publishing,2010.

[15] 張博.有向網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法研究[D].成都:電子科技大學(xué),2013.

[16] Newman M E J.The mathematics of networks[J].The new palgrave encyclopedia of economics,2008,2:1-12.

[17] Rosvall M,Bergstrom C T.Maps of random walks on complex networks reveal community structure[J].Proceedings of the National Academy of Sciences,2008,105(4):1118-1123.

[18] 李金城.大規(guī)模圖像檢索和識(shí)別中的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)及其應(yīng)用[D].華南理工大學(xué),2013.

收稿日期：2015-02-05。國家自然科學(xué)基金項(xiàng)目(61303096);上海市自然科學(xué)基金項(xiàng)目(13ZR1454600)。劉大海，碩士生，主研領(lǐng)域：復(fù)雜網(wǎng)絡(luò)，數(shù)據(jù)挖掘。張博鋒，研究員。鄒國兵，講師。顧程偉，碩士生。

中圖分類號TP3

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.07.031

MULTI-DIMENSIONAL DIRECTED COMMUNITY DETECTION IN COMPLEX NETWORK OF MICROBLOGGING USER MODEL

Liu DahaiZhang BofengZou GuobingGu Chengwei

(SchoolofComputerEngineeringandScience,ShanghaiUniversity,Shanghai200444,China)

AbstractMost of community detections are based on one kind of information,i.e.to partition the community using one dimension.However in reality scene,the composition of communities between users is formed by the combined effect of many factors,such as interests,social relationships,geography,educational background,etc.Moreover,some of these multi-dimensional information are undirected,for ex.,the similarity of interests,but some others,like the relationship of follow,are directed.Based on the principle of directed community detection,in this paper we fuse the multi-dimensional information and propose a multi-dimensional complex network-oriented directed community detection algorithm (MDCD).It is proved through experiment that the MDCD algorithm,relative to conventional multi-dimensional community discovery algorithm AMM,improves the accuracy of community detection result by 17.7% and the F-measure value by 0.068; Furthermore,by comparing the MDCD algorithm with the one-dimensional interests similarity network,it improves the precision rate of three-dimensional complex network detection result by 36.1% and the recall rate by 25.3%.Since the multi-dimensional directed community detection considers the multi-dimensional information comprehensively,the community structure obtained has more important social significance.

KeywordsUser modelComplex networksMulti-dimensional directed community detection