微博社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法研究

范超然 ，黃曙光 ，李永成

（1.合肥電子工程學(xué)院 研究生管理大隊(duì)，安徽 合肥 230037；2.合肥電子工程學(xué)院 網(wǎng)絡(luò)工程系，安徽 合肥 230037）

微博作為一種新興的社交媒體，其用戶以及影響力越來(lái)越廣泛，微博從一開(kāi)始的社交娛樂(lè)工具到現(xiàn)在的重要營(yíng)銷手段，得到了前所未有的關(guān)注。微博不同于傳統(tǒng)的社交媒體一對(duì)多的信息傳播模式，它的傳播具有迅捷性和裂變性[1]，這種信息傳播的模式使得微博在突發(fā)事件的傳播以及輿論的擴(kuò)散方面具有更強(qiáng)的作用力。隨著復(fù)雜網(wǎng)絡(luò)研究的不斷深入，以此為基礎(chǔ)理論的社交媒體研究正成為社會(huì)網(wǎng)絡(luò)研究的一大分支。復(fù)雜網(wǎng)絡(luò)中的一個(gè)主要特征是社區(qū)性[2]，社區(qū)的一般定義是同一社區(qū)內(nèi)的節(jié)點(diǎn)與節(jié)點(diǎn)之間的連接很緊密，而社區(qū)與社區(qū)之間的連接比較稀疏[3]。社區(qū)發(fā)現(xiàn)對(duì)于挖掘網(wǎng)絡(luò)中的功能模塊以及研究網(wǎng)絡(luò)的演化是非常重要的。本文提出了一種基于關(guān)系分析的社區(qū)發(fā)現(xiàn)方法。

1 社區(qū)發(fā)現(xiàn)相關(guān)研究

社區(qū)發(fā)現(xiàn)從算法的角度可以分為兩種[4]：（1）基于優(yōu)化的算法，其中包括著名的譜方法，基本思想是采用二次型優(yōu)化技術(shù)最小化預(yù)定義的“截”函數(shù)，具有最小“截”的劃分被認(rèn)為是最優(yōu)的網(wǎng)絡(luò)劃分。（2）Kernighan和Lin在 1970年提出 KL算法[5]，該算法是一種試探優(yōu)化算法，它將網(wǎng)絡(luò)分割成兩個(gè)大小已知的子網(wǎng)絡(luò)即社區(qū)，并且應(yīng)用了貪婪算法的原理。由于以上兩種算法的開(kāi)銷較大，Newman提出了一種快速聚類算法[6]，該算法優(yōu)化的目標(biāo)是模塊度函數(shù)Q，該函數(shù)定義為簇內(nèi)實(shí)際連接數(shù)目與隨機(jī)連接情況下簇內(nèi)期望連接數(shù)目之差，用來(lái)衡量社區(qū)劃分的質(zhì)量，該算法通過(guò)合并使ΔQ最大的點(diǎn)的方法形成一個(gè)自底向上的聚類過(guò)程，該算法在效率上有了很大的提高。AaronClauset等人提出的 CNM算法[7]在效率上有了更進(jìn)一步的提高，算法復(fù)雜度為 O（n×log2n），接近線性復(fù)雜度，這也是本文采用此算法的重要原因。除了優(yōu)化方法以外還有一種基于啟發(fā)式的方法，該類算法能夠快速找到網(wǎng)絡(luò)中社區(qū)的近似最優(yōu)解，其中包括最經(jīng)典的GN算法[8]，它通過(guò)計(jì)算迭代分割有最大邊介數(shù)邊的方法來(lái)劃分網(wǎng)絡(luò)。除了以上兩類方法以外有學(xué)者還提出了一類基于模型的社區(qū)發(fā)現(xiàn)方法，其中包括標(biāo)簽傳播算法LPA[9]，基于隨機(jī)游走的Infomap算法[10]等。傳統(tǒng)意義上的社區(qū)發(fā)現(xiàn)方法僅僅從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)出發(fā)挖掘連接緊密的簇結(jié)構(gòu)，隨著復(fù)雜網(wǎng)絡(luò)研究的不斷擴(kuò)展特別是在線社交網(wǎng)絡(luò)的深入研究，相關(guān)學(xué)者試圖利用節(jié)點(diǎn)和邊的內(nèi)容來(lái)發(fā)現(xiàn)在線社交網(wǎng)絡(luò)社區(qū)。燕飛[11]等人提出了一種綜合興趣和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的社區(qū)發(fā)現(xiàn)方法，Yang Tianbao等人[12]提出了一種將內(nèi)容與鏈接結(jié)合的概率模型。針對(duì)Twitter的社區(qū)發(fā)現(xiàn)，Mohit Naresh Kewalramani[13]在他的碩士論文中利用Twitter多個(gè)屬性的相似性并通過(guò)傳統(tǒng)聚類算法的方法發(fā)現(xiàn)社區(qū)。

然而，類似于微博的在線社交網(wǎng)絡(luò)是典型的有向網(wǎng)絡(luò)，用戶之間的指向關(guān)系反映了用戶與用戶之間的緊密聯(lián)系。單純地利用用戶之間興趣以及聯(lián)系內(nèi)容的相似度來(lái)發(fā)現(xiàn)社區(qū)，會(huì)伴隨用戶興趣和用戶的活躍程度的波動(dòng)產(chǎn)生劃分的歧義，此類劃分還會(huì)造成大量的重疊社區(qū)。微博用戶之間轉(zhuǎn)發(fā)等關(guān)于內(nèi)容的聯(lián)系是基于用戶關(guān)注關(guān)系之上的，用戶之間關(guān)注關(guān)系往往是穩(wěn)定的，針對(duì)此項(xiàng)特點(diǎn)本文首先對(duì)微博用戶之間的關(guān)系進(jìn)行分析構(gòu)建網(wǎng)絡(luò)，然后利用用戶之間基于內(nèi)容聯(lián)系的頻繁程度定義用戶之間的緊密程度，再利用加權(quán)社區(qū)發(fā)現(xiàn)算法來(lái)完成社區(qū)發(fā)現(xiàn)。

2 關(guān)系分析

Granovetter[14]提出社會(huì)網(wǎng)絡(luò)中普遍存在的兩種關(guān)系：強(qiáng)關(guān)系與弱關(guān)系，社會(huì)學(xué)家普遍認(rèn)為強(qiáng)關(guān)系是一種基于信任的關(guān)系，而弱關(guān)系是一種信息流通的渠道。微博社交網(wǎng)絡(luò)中從類型上講有四種關(guān)系：關(guān)注關(guān)系、提及關(guān)系、轉(zhuǎn)發(fā)關(guān)系以及互粉關(guān)系，關(guān)注關(guān)系是指用戶以粉絲的形式關(guān)注另外一個(gè)用戶，這種關(guān)注形式是單向的，關(guān)系展現(xiàn)的是一種拓?fù)浣Y(jié)構(gòu)。而提及關(guān)系以及轉(zhuǎn)發(fā)關(guān)系是一種以關(guān)注關(guān)系為基礎(chǔ)的關(guān)系，這種關(guān)系是用戶因關(guān)注者的內(nèi)容吸引而產(chǎn)生的關(guān)系鏈接?；シ坳P(guān)系是用戶雙向關(guān)注的關(guān)系模式，由此可見(jiàn)在微博社交網(wǎng)絡(luò)中是一種單向關(guān)系與雙向關(guān)系并存的網(wǎng)絡(luò)，為了能夠在這樣的網(wǎng)絡(luò)中發(fā)現(xiàn)關(guān)系緊密的社區(qū)，首先必須對(duì)關(guān)注關(guān)系與互粉關(guān)系對(duì)關(guān)系的緊密程度的影響進(jìn)行分析。

本文所采用的數(shù)據(jù)集是通過(guò)Twitter API的方式爬取2012年一月份部分用戶關(guān)注關(guān)系網(wǎng)絡(luò)以及用戶之間的轉(zhuǎn)發(fā)和提及關(guān)系，所爬取的網(wǎng)絡(luò)包括12 563個(gè)用戶和716 129條關(guān)系數(shù)據(jù)，此網(wǎng)絡(luò)記為 G（V，E），V代表網(wǎng)絡(luò)中的節(jié)點(diǎn)，E代表網(wǎng)絡(luò)中的邊。首先分析互粉關(guān)系在用戶關(guān)系中的比重，圖1是粉絲數(shù)與互粉數(shù)在所有用戶中所占比重的分布情況。

圖1 粉絲數(shù)與互粉數(shù)在用戶中的比例

通過(guò)圖1可以看出大部分的微博用戶的粉絲數(shù)即雙向關(guān)系在兩種關(guān)系中所占的比例較小大多分布在0.1之內(nèi)。其次分析粉絲數(shù)與互粉率之間的關(guān)系，圖2是統(tǒng)計(jì)曲線圖。

圖2 粉絲數(shù)與互粉數(shù)的關(guān)系

由圖2可以看出粉絲數(shù)與互粉數(shù)之間沒(méi)有必然的線性關(guān)系。最后分析互粉數(shù)與粉絲數(shù)之間的比率和粉絲數(shù)之間的關(guān)系，圖3是統(tǒng)計(jì)結(jié)果。

圖3 互粉數(shù)與粉絲數(shù)比例和粉絲數(shù)的關(guān)系

由圖3可以看出隨著粉絲數(shù)的增加，互粉數(shù)所占的比率越來(lái)越小。綜合以上的統(tǒng)計(jì)分析可以得出單純的關(guān)注關(guān)系其實(shí)是一種很松散的結(jié)構(gòu)，用戶關(guān)注一個(gè)用戶完全是“免費(fèi)”的，所以這種關(guān)系的建立帶有一定的隨意性，或者說(shuō)這種單向關(guān)注關(guān)系是一種弱關(guān)系，而用戶之間的互粉關(guān)系往往需要基于兩者之間的信任關(guān)系或者兩者之間有共同的興趣點(diǎn)，此類是一種強(qiáng)關(guān)系，而一個(gè)社區(qū)內(nèi)的用戶往往聯(lián)系緊密或者具有一定的共同屬性點(diǎn)。

3 構(gòu)建網(wǎng)絡(luò)

3.1 網(wǎng)絡(luò)簡(jiǎn)化

通過(guò)以上分析，可以得出單向的關(guān)注關(guān)系是一種很弱的單向關(guān)系，這種隨意的關(guān)系在一個(gè)強(qiáng)關(guān)系社區(qū)中影響很小，所以在構(gòu)建網(wǎng)絡(luò)的第一步首先過(guò)濾掉網(wǎng)絡(luò)中用戶之間的單向鏈接得到純粹的具有互粉關(guān)系的無(wú)向網(wǎng)絡(luò) G（V，E）。

3.2 邊權(quán)值計(jì)算

邊權(quán)[15]是網(wǎng)絡(luò)中用來(lái)衡量節(jié)點(diǎn)i和節(jié)點(diǎn)j共享的邊的關(guān)聯(lián)度大小的量，記為rij。rij的值越大，說(shuō)明節(jié)點(diǎn)i和j之間傳輸信息的可能性越大，即兩點(diǎn)聯(lián)系的較緊密；反之，則說(shuō)明節(jié)點(diǎn)i和j之間信息傳輸比較困難，即兩點(diǎn)之間的聯(lián)系較稀疏。

具有互粉關(guān)系的微博用戶之間的聯(lián)系有轉(zhuǎn)發(fā)數(shù)和提及數(shù)，設(shè)兩個(gè)微博用戶A和B，A和B之間具有互粉關(guān)系，A轉(zhuǎn)發(fā) B的次數(shù)為 r_sum1，B轉(zhuǎn)發(fā) A的次數(shù)為r_sum2，則轉(zhuǎn)發(fā)權(quán)重為：

A提及B的次數(shù)為 m_sum1，B提及 A的次數(shù)為m_sum2，則提及權(quán)重為：

則A和B鏈接的權(quán)重為：

根據(jù)以上步驟可以構(gòu)建出微博社交網(wǎng)絡(luò)中具有互粉關(guān)系的無(wú)向權(quán)重圖 G′（V，E）。

4 算法與實(shí)驗(yàn)

4.1 算法改進(jìn)

CNM算法采用快速貪婪規(guī)則合并劃分得出社區(qū)結(jié)構(gòu)，是凝聚型算法的典型代表。為了能夠快速地找到模塊度增長(zhǎng)最快的節(jié)點(diǎn)，CNM算法定義了以下數(shù)據(jù)結(jié)構(gòu)：

（1）一個(gè)用來(lái)存儲(chǔ)每對(duì)有連接的點(diǎn)的 ΔQij，矩陣的每一行又同時(shí)用平衡二叉樹(shù)（因此插入和查詢每個(gè)點(diǎn)的時(shí)間為O（logn）和一個(gè)大頂堆來(lái)（最大的元素可以最快找到）存放。

（2）大頂堆H包含ΔQij矩陣中每一行的最大元素，以及標(biāo)簽 i，j標(biāo)志社區(qū)對(duì)。

（3）一個(gè)存儲(chǔ) ai的向量組。

CNM算法具有一個(gè)很好的特性：在整個(gè)算法過(guò)程中，模塊度Q僅有一個(gè)峰值（最大值）。當(dāng)模塊度增量矩陣中最大元素都小于0以后，Q的值就只可能一直下降。因此，只要模塊度增量矩陣中最大由正變負(fù)以后，就可以停止合并，并認(rèn)為此時(shí)的社團(tuán)結(jié)構(gòu)就是網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。

為了適用于無(wú)向加權(quán)網(wǎng)絡(luò)，對(duì)模塊度計(jì)算方法做相應(yīng)改動(dòng)。ΔQij表示節(jié)點(diǎn)i加入到鄰居節(jié)點(diǎn)j所在社團(tuán)時(shí)模塊度的變化，ΔQij定義如下：

表1 加權(quán)CNM算法

4.2 實(shí)驗(yàn)結(jié)果與分析

通過(guò)構(gòu)建網(wǎng)絡(luò)得到微博無(wú)向加權(quán)圖連通網(wǎng)絡(luò)G′（V，E），G′（V，E）包含 98 327 條互粉關(guān)系，通過(guò)式（3）賦予每條邊相應(yīng)的權(quán)值ω。算法通過(guò)迭代劃分網(wǎng)絡(luò)試圖找到最優(yōu)的社區(qū)劃分?jǐn)?shù)量。圖4是模塊度變化趨勢(shì)。

圖4 模塊度變化曲線圖

由圖4可知在社區(qū)劃分?jǐn)?shù)為8的時(shí)候，Q值達(dá)到峰值0.401，而通常社區(qū)結(jié)構(gòu)較明顯的網(wǎng)絡(luò)模塊度介于0.3～0.7之間[16]，這時(shí)網(wǎng)絡(luò)的社區(qū)劃分達(dá)到一個(gè)最優(yōu)的效果，實(shí)驗(yàn)結(jié)果說(shuō)明該算法實(shí)現(xiàn)的網(wǎng)絡(luò)劃分在模塊度衡量上有較強(qiáng)的社區(qū)結(jié)構(gòu)。社區(qū)劃分的可視化效果如圖5所示。

圖5 社區(qū)劃分可視化效果

為了能夠進(jìn)一步評(píng)估社區(qū)劃分的質(zhì)量，依據(jù)以上的社區(qū)劃分結(jié)果，構(gòu)建每個(gè)社Ci區(qū)內(nèi)用戶所發(fā)Tweet中以及轉(zhuǎn)發(fā)和提及當(dāng)中詞頻較高的詞匯集，列出頻率較高（>%10）的詞匯作為社區(qū)的主題標(biāo)注，統(tǒng)計(jì)結(jié)果如表2所示。

表2 社區(qū)內(nèi)用戶Tweet高頻詞匯統(tǒng)計(jì)

依據(jù)表 2 可以發(fā)現(xiàn)社區(qū) 1、2、3、5、7、8 主題相對(duì)集中，主題詞之間的語(yǔ)義相似度較高，就社區(qū)劃分解釋而言，這樣的社區(qū)劃分更接近一個(gè)真實(shí)的社區(qū)劃分即社區(qū)內(nèi)用戶往往關(guān)注同一類的主題。而對(duì)于社區(qū)4、6而言，社區(qū)內(nèi)用戶的關(guān)注主題之間的語(yǔ)義相似度較低，但通過(guò)考察社區(qū)內(nèi)用戶之間的聯(lián)系頻率較高，這樣的社區(qū)劃分解釋是用戶之間的“朋友”關(guān)系而產(chǎn)生社區(qū)。總體而言，社區(qū)劃分后的網(wǎng)絡(luò)中具有明顯的社區(qū)結(jié)構(gòu)。

本文通過(guò)分析微博社交網(wǎng)絡(luò)中關(guān)系的強(qiáng)弱關(guān)系對(duì)于用戶緊密度的影響，通過(guò)過(guò)濾用戶之間單向的關(guān)注關(guān)系以及根據(jù)用戶之間的聯(lián)系對(duì)邊賦值的方法構(gòu)造了社區(qū)發(fā)現(xiàn)的元數(shù)據(jù)：微博無(wú)向加權(quán)圖。再通過(guò)相應(yīng)的加權(quán)社區(qū)發(fā)現(xiàn)算法實(shí)現(xiàn)了在微博社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)，實(shí)驗(yàn)效果顯示這種方法能夠很好地挖掘網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。然而以微博為代表的社交網(wǎng)絡(luò)所包含的信息相當(dāng)豐富，可以說(shuō)微博社交網(wǎng)絡(luò)中不但邊是多屬性的，用戶也是多屬性的，如何利用這些屬性信息挖掘社區(qū)是值得探討的問(wèn)題。另外微博社交網(wǎng)絡(luò)的一個(gè)重要特點(diǎn)是動(dòng)態(tài)性，動(dòng)態(tài)社區(qū)的發(fā)現(xiàn)如何運(yùn)用在微博社交網(wǎng)絡(luò)中也是一個(gè)重要的問(wèn)題。

[1]李瑗瑗.微博輿論的形成機(jī)制及特點(diǎn)分析[J].新聞界，2010（6）：51-52.

[2]LANCICHINETTI A， FORTUNATO S， KERT J.Detecting the overlapping and hierarchicalcommunity structure in complex networks[J].New Journal of Physics， 2009，3（11）：15-33.

[3]NEWMAN M E J.Communities modules and large-scale structure in networks[J].Nature Physics， 2012（1）：25-31.

[4]楊博， 劉大有，Liu Jiming，等.復(fù)雜網(wǎng)絡(luò)聚類方法[J].軟件學(xué)報(bào)，2009，20（1）：54-66.

[5]KERNIGHAN B W， LIN S.An efficientheuristic procedure for partitioning graphs[J].Bell System Technical Journal，1970.49（2）：291-307.

[6]NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E， 2004， 69（6）：1-5.

[7]CLAUSETA，NEWMAN M E J.Findingcommunity structure in very large networks[J].Physics Review E，2004，（70）：71-76.

[8]GIRVAN M，NEWMAN M E J.Community structure in social and biological networks[J].Proc.of the National Academy of Science， 2002， 12（9）：7821-7826.

[9]RAGHAVAN U N，ALBERT R，KUMARA S.Near linear time algorithm to detect community structures in large scale networks[J].Physical Review E， 2007，6（3）：47-58.

[10]ROSVALL M，CARL T.Bergstrom Maps of random walks on complex networks reveal community structure [J].PNAS， 2008，105（4）：1118-1123.

[11]燕飛，張銘，譚裕韋，等.綜合社會(huì)行動(dòng)者興趣和網(wǎng)絡(luò)拓?fù)涞纳鐓^(qū)發(fā)現(xiàn)方法 [J].計(jì)算機(jī)研究與發(fā)展，2010，47：357-362.

[12]Yang Tianbao， Jin Rong， Chi Yun， et al.Combining Link and content for community detection[C].Adiscriminative Approach KDD′09， Paris， France， 2009.

[13]NARESH M，LRAMANIK.Communitydetection in twitter[D].Dept of Comuputer Science of University of Maryland Baltimore County， 2011：1-60.

[14]GRANOVETTER M S.Thestrength ofweak ties[J].American Journal of Sociology，1973，78（6）：1360-1380.

[15]LI M， FAN Y， CHEN J， et al.Weighted networks of scientific communication：The measurement and topological role of weight[J].Physica A，2005，39，（11）：643-656.

[16]NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E，2004， 69（2）：32-46.