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

范超然 ，黃曙光 ，李永成

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

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

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

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

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

2 關系分析

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

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

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

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

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

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

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

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

3 構建網(wǎng)絡

3.1 網(wǎng)絡簡化

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

3.2 邊權值計算

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

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

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

則A和B鏈接的權重為：

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

4 算法與實驗

4.1 算法改進

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

（1）一個用來存儲每對有連接的點的 ΔQij，矩陣的每一行又同時用平衡二叉樹（因此插入和查詢每個點的時間為O（logn）和一個大頂堆來（最大的元素可以最快找到）存放。

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

（3）一個存儲 ai的向量組。

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

為了適用于無向加權網(wǎng)絡，對模塊度計算方法做相應改動。ΔQij表示節(jié)點i加入到鄰居節(jié)點j所在社團時模塊度的變化，ΔQij定義如下：

表1 加權CNM算法

4.2 實驗結果與分析

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

圖4 模塊度變化曲線圖

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

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

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

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

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

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

[1]李瑗瑗.微博輿論的形成機制及特點分析[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，等.復雜網(wǎng)絡聚類方法[J].軟件學報，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]燕飛，張銘，譚裕韋，等.綜合社會行動者興趣和網(wǎng)絡拓撲的社區(qū)發(fā)現(xiàn)方法 [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.