社交網(wǎng)絡(luò)上的社團(tuán)發(fā)現(xiàn)方法綜述

王英奎　郭洪亮　朱鵬飛

摘 要：近年來(lái)社交網(wǎng)絡(luò)快速發(fā)展，例如新浪微博、微信、各種在線論壇等，這類網(wǎng)絡(luò)是互聯(lián)網(wǎng)重要的組成部分。對(duì)社交網(wǎng)絡(luò)的研究已成為熱點(diǎn)，其中一項(xiàng)重要的研究?jī)?nèi)容是社團(tuán)發(fā)現(xiàn)，即探測(cè)社交網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，其主要方法是對(duì)社交網(wǎng)絡(luò)中的用戶進(jìn)行劃分，處于同一個(gè)社團(tuán)的用戶具有高度的交互關(guān)系，而社團(tuán)之間的用戶交互十分稀疏。目前，研究人員已提出大量的社團(tuán)發(fā)現(xiàn)方法，本文對(duì)現(xiàn)有的經(jīng)典方法進(jìn)行分析綜述。

關(guān)鍵詞：社交網(wǎng)絡(luò) 社團(tuán)發(fā)現(xiàn) 社團(tuán)結(jié)構(gòu)

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1003-9082（2018）06-000-01

一、社團(tuán)發(fā)現(xiàn)背景

1.社交網(wǎng)絡(luò)

當(dāng)今社會(huì)中，我們無(wú)法離開網(wǎng)絡(luò)，人與人在網(wǎng)絡(luò)中的溝通成為我們?nèi)粘Ｉ钪胁豢扇鄙俚穆?lián)系方式，諸如騰訊QQ、微信、新浪微博、在線論壇、郵件服務(wù)等等。我們稱這類網(wǎng)絡(luò)為社交網(wǎng)絡(luò)SNS（Social Network Service），社交網(wǎng)絡(luò)由用戶和用戶之間的交互關(guān)系構(gòu)成，用戶既是網(wǎng)絡(luò)內(nèi)容的生產(chǎn)者也是消費(fèi)者，使得網(wǎng)絡(luò)呈現(xiàn)社會(huì)化，成為現(xiàn)實(shí)社會(huì)的縮影。我們可以把網(wǎng)絡(luò)中的每個(gè)用戶抽象為節(jié)點(diǎn)，用戶之間的關(guān)系（例如粉絲關(guān)系、轉(zhuǎn)發(fā)、回復(fù)）抽象成邊，這樣社交網(wǎng)絡(luò)可以抽象為圖的形式進(jìn)行研究。

社交網(wǎng)絡(luò)是一種復(fù)雜網(wǎng)絡(luò)，因此它有諸多特性：小世界效應(yīng)、無(wú)尺度性、聚類性，具有社團(tuán)結(jié)構(gòu)等等。對(duì)于大規(guī)模網(wǎng)絡(luò)而言，很難對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行完整的研究，而社團(tuán)結(jié)構(gòu)描述了網(wǎng)絡(luò)成員的聯(lián)系模式，即同一個(gè)社團(tuán)內(nèi)的成員聯(lián)系緊密，而不同社團(tuán)之間的成員聯(lián)系松散[1，2]，網(wǎng)絡(luò)中的大量成員可以劃分到不同的社團(tuán)中，社團(tuán)結(jié)構(gòu)是網(wǎng)絡(luò)的一個(gè)重要的特征。

1.1社團(tuán)發(fā)現(xiàn)的意義

對(duì)社交網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)的研究具有十分重要的意義。通過(guò)社團(tuán)結(jié)構(gòu)我們能夠獲得用戶的喜好，如喜歡旅游還是電子產(chǎn)品？是偏愛IOS系統(tǒng)的蘋果品牌手機(jī)還是基于安卓系統(tǒng)的手機(jī)？獲得這一信息有利于廣告的精準(zhǔn)投放。

此外，現(xiàn)實(shí)社會(huì)中的犯罪行為也逐步轉(zhuǎn)移到社交網(wǎng)絡(luò)中，犯罪分子會(huì)在網(wǎng)絡(luò)中互相聯(lián)絡(luò)，準(zhǔn)備實(shí)施犯罪行為，這樣他們形成在線犯罪團(tuán)伙，這就是一個(gè)社團(tuán)，對(duì)犯罪社團(tuán)組織的檢測(cè)已經(jīng)開始輔助公安系統(tǒng)打擊犯罪。

近期美國(guó)的Facebook用戶信息泄露，進(jìn)而影響美國(guó)大選事件鬧得沸沸揚(yáng)揚(yáng)，這就是一個(gè)研究機(jī)構(gòu)充分利用社交網(wǎng)絡(luò)引導(dǎo)輿情的現(xiàn)實(shí)例子。如果能夠在網(wǎng)絡(luò)中利用社團(tuán)結(jié)構(gòu)監(jiān)控和引導(dǎo)輿情，對(duì)社會(huì)的穩(wěn)定發(fā)展具有十分重要的意義。

二、社團(tuán)發(fā)現(xiàn)方法

1.社交網(wǎng)絡(luò)建模

社交網(wǎng)絡(luò)中的用戶抽象為節(jié)點(diǎn)，用戶之間的聯(lián)系抽象為邊，因此大多數(shù)社團(tuán)發(fā)現(xiàn)方法把社交網(wǎng)絡(luò)抽象為圖的形式。圖1顯示了一個(gè)樣例網(wǎng)絡(luò)，具有8個(gè)節(jié)點(diǎn)，它對(duì)應(yīng)的鄰接矩陣如圖2所示。

2.經(jīng)典的社團(tuán)發(fā)現(xiàn)方法

2.1 Girvan和Newman的社團(tuán)發(fā)現(xiàn)方法[5]

Girvan和Newman首次提出了GN社團(tuán)發(fā)現(xiàn)算法，該算法基于一個(gè)簡(jiǎn)單的方法：逐步刪除社團(tuán)之間的邊，最后得到的聯(lián)通分支就是社團(tuán)。它的算法如下：

a） 計(jì)算所有邊的中心度，中心度用邊的介數(shù)來(lái)衡量，其定義為網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間的最短路徑經(jīng)過(guò)當(dāng)前邊的條數(shù)。

b） 刪除具有最大中心度的邊，如果多條邊的中心度相同，則隨機(jī)選擇一條。

c） 重新計(jì)算網(wǎng)絡(luò)所有邊的中心度。

d） 迭代執(zhí)行b）

GN方法是社團(tuán)發(fā)現(xiàn)領(lǐng)域非常著名的方法，其優(yōu)點(diǎn)是理論簡(jiǎn)單可行，但缺點(diǎn)是計(jì)算的時(shí)間復(fù)雜度過(guò)大，假設(shè)網(wǎng)絡(luò)中邊的條數(shù)為m，節(jié)點(diǎn)個(gè)數(shù)為n，它的時(shí)間復(fù)雜度為。因此GN算法無(wú)法處理大規(guī)模網(wǎng)絡(luò)。

2.2基于模塊度模型的Louvain方法[3]

Newman和Girvan提出了模塊度模型，Q函數(shù) [4]能夠衡量對(duì)網(wǎng)絡(luò)社團(tuán)劃分的優(yōu)劣。其定義如公式1所示。

（1）

其中，A為鄰接矩陣，為節(jié)點(diǎn)i的度，為節(jié)點(diǎn)i所在的社團(tuán)，為邊數(shù)。

Louvain的主要優(yōu)點(diǎn)是能夠處理大規(guī)模的網(wǎng)絡(luò)，盡管它不能保證最優(yōu)的圖劃分。它的處理過(guò)程如下：在初始化階段，假設(shè)每個(gè)節(jié)點(diǎn)自己構(gòu)成一個(gè)社團(tuán)。接下來(lái)，對(duì)每個(gè)節(jié)點(diǎn)，計(jì)算把它放入它的鄰居節(jié)點(diǎn)所在的社團(tuán)時(shí)的模塊度，選取模塊度最大的社團(tuán)作為該節(jié)點(diǎn)的社團(tuán)，下一步處理時(shí)，把已經(jīng)形成的社團(tuán)視為一個(gè)新的節(jié)點(diǎn)，并計(jì)算該新節(jié)點(diǎn)和其余節(jié)點(diǎn)的度，即社團(tuán)內(nèi)所有節(jié)點(diǎn)和其它節(jié)點(diǎn)的度之和，重復(fù)迭代上述過(guò)程，知道模塊度不再增大為止。

2.3標(biāo)簽傳播算法[6]

標(biāo)簽傳播算法由Raghavan等人提出，其算法流程如下：

a）初始化階段，初始化所有節(jié)點(diǎn)，給每個(gè)節(jié)點(diǎn)賦值唯一的標(biāo)簽。

b）處理每個(gè)節(jié)點(diǎn)，考慮它的鄰居標(biāo)簽，也就是選取大多數(shù)鄰居具有的標(biāo)簽作為節(jié)點(diǎn)的新標(biāo)簽。

c）迭代處理所有節(jié)點(diǎn)，使得所有節(jié)點(diǎn)都和自己的多數(shù)鄰居具有相同的標(biāo)簽。

標(biāo)簽傳播算法的處理速度很快，只需接近線性時(shí)間。

2.4重疊的社團(tuán)發(fā)現(xiàn)方法

這類方法基于一個(gè)現(xiàn)實(shí)，即網(wǎng)絡(luò)中的成員可能同時(shí)屬于多個(gè)社團(tuán)，因此社團(tuán)之間是有重疊的，并不只是節(jié)點(diǎn)的劃分[7]。

重疊的社團(tuán)發(fā)現(xiàn)方法包括基于團(tuán)滲透的方法（CFinder[9]）、基于鏈接劃分的方法（擴(kuò)展的Infomap[8]）、基于局部擴(kuò)展的方法（LFM[10]）等。

三、社團(tuán)發(fā)現(xiàn)方法評(píng)價(jià)指標(biāo)

對(duì)社團(tuán)發(fā)現(xiàn)算法的效果進(jìn)行評(píng)價(jià)的常用指標(biāo)包括模塊度函數(shù)Q，F(xiàn)-score，Jaccard index和標(biāo)準(zhǔn)互信息NMI（Normalized Mutual Information），其中NMI是最常用的評(píng)價(jià)標(biāo)準(zhǔn)。

四、總結(jié)

本文對(duì)社交網(wǎng)絡(luò)，以及社交網(wǎng)絡(luò)上的社團(tuán)發(fā)現(xiàn)方法進(jìn)行了討論，總言之，社交網(wǎng)絡(luò)是互聯(lián)網(wǎng)上具有重要研究?jī)r(jià)值的目標(biāo)，它是真實(shí)社會(huì)的在線表現(xiàn)形式，社團(tuán)發(fā)現(xiàn)算法能夠探測(cè)出的這些網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，這對(duì)廣告投放、輿情引導(dǎo)、犯罪分子檢測(cè)等領(lǐng)域都具有現(xiàn)實(shí)的意義。

參考文獻(xiàn)

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

[2]劉大有，金弟，何東曉等.復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘綜述[J].算機(jī)研究與發(fā)展， 2013（10）：2140-2154.

[3]Vincent D Blondel， Jean-Loup Guillaume， Renaud Lambiotte， and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics： theory and experiment， 2008（10）：P10008， 2008.

[4]Mark Newman； M. Girvan. Finding and evaluating community structure in networks. Physical Review E， 69（2）， February 2004.

[5]Girvan M； Newman M E J.Community structure in social and biological networks.2002（12）.

[6]Raghavan U N；Albert R； Kumara S.Near linear time algorithm to detect community structures in large scale networks.2007（03）.

[7]Palla G；Derenyi I；Farkas I. Uncovering the overlapping community structures of complex networks in nature and society.2005（7043）.

[8]Rosvall M；Bergstrom C T.Maps of random walks on complex networks reveal community structure. 2008（04）.

[9]Palla G；Derényi I；Farkas I.The software of clique percolation method. 2012.

[10]Lancichinetti A；Fortunato S；Kertesz J.Detecting the overlapping and hierarchical community structure in complex networks.2009（03）.