許云峰，趙 寧，郝雪君，李 兵，劉慧娟

(1.河北科技大學(xué)信息科學(xué)與工程學(xué)院，河北石家莊 050018；2.河北科技大學(xué)人事處，河北石家莊 050018)

基于三元閉包和會員閉包的社區(qū)發(fā)現(xiàn)算法研究

許云峰1，趙 寧2，郝雪君1，李 兵1，劉慧娟1

(1.河北科技大學(xué)信息科學(xué)與工程學(xué)院，河北石家莊 050018；2.河北科技大學(xué)人事處，河北石家莊 050018)

隨著網(wǎng)絡(luò)的發(fā)展和人們溝通方式的擴(kuò)展，社交網(wǎng)絡(luò)影響了人們的生活，改變了人們傳播與分享消息的方式，吸引了越來越多的人關(guān)注和研究社交網(wǎng)絡(luò)。社交網(wǎng)絡(luò)即社交網(wǎng)絡(luò)服務(wù)，源自英文SNS(social network service)的翻譯，社交網(wǎng)絡(luò)有多種表現(xiàn)平臺，比如QQ、微博、Facebook和微信。本文主要研究微博這一新興的社交平臺,研究微博的主要目的是搞清用戶之間的種種關(guān)系。當(dāng)代人一般認(rèn)為，微博中存在5種關(guān)系即關(guān)注關(guān)系、提及關(guān)系、轉(zhuǎn)發(fā)關(guān)系、評論關(guān)系以及好友關(guān)系。由于社交網(wǎng)絡(luò)中人數(shù)眾多，關(guān)系錯(cuò)綜復(fù)雜，因而產(chǎn)生的社交數(shù)據(jù)和傳統(tǒng)的數(shù)據(jù)相比具有數(shù)據(jù)量大、結(jié)構(gòu)復(fù)雜、語義豐富等特點(diǎn)，針對這種情況，依據(jù)用戶之間的關(guān)系，提出了一種基于三元閉包的社區(qū)劃分算法。

該算法首先設(shè)初始社區(qū)為空，在所有的頂點(diǎn)中，選擇度最大的頂點(diǎn)作為初始頂點(diǎn)；然后求初始頂點(diǎn)與其鄰接頂點(diǎn)的三元閉包數(shù)和頂點(diǎn)屬于該社區(qū)的概率PS，取它們最大的鄰接頂點(diǎn)加入初始頂點(diǎn)所在社區(qū)，形成新的社區(qū)，繼續(xù)迭代，當(dāng)剩余的頂點(diǎn)很少時(shí)，可以使用會員閉包和三元閉包這種歸集算法把剩余的頂點(diǎn)劃分到不同的社區(qū)，直到把整個(gè)社區(qū)劃分完畢；最后以圖形這種直觀、形象的方式把每一個(gè)社區(qū)表示出來。在該算法中，三元閉包數(shù)、頂點(diǎn)屬于某社區(qū)的概率、擴(kuò)張度的差是評估復(fù)雜網(wǎng)絡(luò)中頂點(diǎn)劃分的關(guān)鍵。該方法綜合了頂點(diǎn)全局重要性的特點(diǎn), 即在復(fù)雜網(wǎng)絡(luò)中,三元閉包數(shù)越大，它們處在一個(gè)社區(qū)的可能性就越大；頂點(diǎn)的會員閉包越大,該頂點(diǎn)就會越優(yōu)先被劃分；擴(kuò)張度的差是確定第i個(gè)社區(qū)是否被劃分完畢的關(guān)鍵。

社交網(wǎng)絡(luò)的研究不僅可以幫助人們了解網(wǎng)絡(luò)結(jié)構(gòu)、分析網(wǎng)絡(luò)結(jié)構(gòu)特性、探測分析網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，而且還可以把虛擬世界中這種關(guān)系鏈接到現(xiàn)實(shí)世界中，即把虛擬關(guān)系轉(zhuǎn)化成利潤，為企業(yè)提供有價(jià)值的關(guān)系網(wǎng)絡(luò)，從而挖掘出潛藏在社交網(wǎng)絡(luò)背后的巨大的經(jīng)濟(jì)價(jià)值，具體體現(xiàn)在：1)幫助企業(yè)找到潛在的商機(jī)，比如分析某個(gè)用戶的評論和發(fā)表內(nèi)容，可知他的消費(fèi)能力、喜好和最近的購買習(xí)慣，從而知道他購買自己產(chǎn)品的概率；2)危機(jī)預(yù)警，根據(jù)用戶的消息內(nèi)容可以知道他對自己產(chǎn)品的滿意度；3)帶動(dòng)了消息的傳播速度和廣度。企業(yè)可以利用這一點(diǎn)，為自己的產(chǎn)品更好地做宣傳。

通過與寬吻海豚網(wǎng)和Zachary空手道俱樂部的社區(qū)網(wǎng)絡(luò)作比較，證明了該算法的有效性和可行性。

社交網(wǎng)絡(luò)； 三元閉包； 社區(qū)劃分

近年來，隨著時(shí)代的進(jìn)步，社交網(wǎng)絡(luò)的發(fā)展逐漸被人們所關(guān)注，社交網(wǎng)絡(luò)已成為人們生活的一部分，并對人們的信息獲得、思考和生活產(chǎn)生巨大的影響，社交網(wǎng)絡(luò)在人們的生活中扮演著重要的角色，社交網(wǎng)絡(luò)成為人們獲取信息、展現(xiàn)自我、營銷推廣的窗口。社交網(wǎng)絡(luò)即社交網(wǎng)絡(luò)服務(wù)，源自英文SNS(social network service)的翻譯，中文直譯為社會性網(wǎng)絡(luò)服務(wù)或社會化網(wǎng)絡(luò)服務(wù)，意譯為社交網(wǎng)絡(luò)服務(wù)。社交網(wǎng)絡(luò)含義包括硬件、軟件、服務(wù)及應(yīng)用，由于四字構(gòu)成的詞組更符合中國人的構(gòu)詞習(xí)慣，因此人們習(xí)慣上用社交網(wǎng)絡(luò)來代指SNS。Web 2.0 的廣泛應(yīng)用和新型社會化網(wǎng)絡(luò)媒體的盛行，促使網(wǎng)絡(luò)服務(wù)從以數(shù)據(jù)為核心的模式開始轉(zhuǎn)變?yōu)橐杂脩艋蛴脩絷P(guān)系為核心的模式。

社交網(wǎng)絡(luò)中的微博是近年來剛剛興起的一種信息交流媒體，每個(gè)用戶可以通過手機(jī)、QQ等多種方法來改變微博的狀態(tài)，發(fā)表自己當(dāng)前的心情，而每一條微博可以是一個(gè)符號，一個(gè)表情，一張圖片，一段視頻等。與傳統(tǒng)社會媒體相比較，具有信息實(shí)時(shí)、內(nèi)容簡潔、用戶交互等特點(diǎn)，它作為一種新型媒體，是一個(gè)基于草根用戶的關(guān)系構(gòu)建及個(gè)性化用戶信息的即時(shí)傳播、共享和獲取的平臺，它的發(fā)展趨勢更加迅速，已經(jīng)表現(xiàn)出后來居上的趨勢，由于微博具有以上特點(diǎn)成為當(dāng)今國內(nèi)外的主流社交媒體。

具體的講，關(guān)注關(guān)系是指用戶以粉絲的形式關(guān)注另外一個(gè)用戶，這種關(guān)注形式是以單向微博作為一個(gè)新的平臺，對于它的研究具有廣闊的前景，尤其是在信息傳播、用戶關(guān)系等方面。研究微博的主要目的就是搞清用戶之間的種種關(guān)系，比如，用戶之間的關(guān)注關(guān)系、社區(qū)中的好友或親情關(guān)系、實(shí)時(shí)交互過程中因共同購買或評論產(chǎn)品而結(jié)成的共同興趣關(guān)系等。GRANOVETTER提出社會網(wǎng)絡(luò)中普遍存在的兩種關(guān)系：強(qiáng)關(guān)系與弱關(guān)系[1]，社會學(xué)家普遍認(rèn)為強(qiáng)關(guān)系是一種基于信任的關(guān)系，而弱關(guān)系是一種信息流通的渠道。人們一般認(rèn)為，微博社交網(wǎng)絡(luò)中存在5種關(guān)系：關(guān)注關(guān)系、提及關(guān)系、轉(zhuǎn)發(fā)關(guān)系、好友關(guān)系以及評論關(guān)系，微博社交網(wǎng)絡(luò)是一種單向關(guān)系與雙向關(guān)系并存的網(wǎng)絡(luò)，這種關(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)系鏈接。好友關(guān)系是用戶互為關(guān)注的關(guān)系模式。評論關(guān)系是一種以好友關(guān)系為基礎(chǔ)的關(guān)系，這種關(guān)系是由于用戶評價(jià)好友的信息產(chǎn)生的關(guān)系。

社區(qū)現(xiàn)象是一種復(fù)雜網(wǎng)絡(luò)中的普遍現(xiàn)象，表述的是多個(gè)個(gè)體之間具有的共同特性。社區(qū)發(fā)現(xiàn)技術(shù)從最初的圖割KL算法[2]、w-H算法[3-4]、GN算法[5-6]等，經(jīng)過逐漸的發(fā)展和改進(jìn)，形成了包括改進(jìn)后的如：基于“邊介數(shù)”概念的GN算法[7]、凝聚CNM算法[8]、CPM算法[9]、LP算法[10]、Louvain算法[11]、多模型聚類算法[12-14]等更具可操作性的方法。網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)可分為個(gè)性化服務(wù)、信息推送等，并提供基本數(shù)據(jù)，尤其是在信息時(shí)代，社區(qū)的存在更加普遍，發(fā)現(xiàn)技術(shù)的應(yīng)用也更加方便，其商業(yè)價(jià)值和服務(wù)價(jià)值更大[15]，所以這個(gè)方向慢慢的成為人們研究的焦點(diǎn)。現(xiàn)在的許多社區(qū)發(fā)現(xiàn)算法復(fù)雜度都很高，只能作用在比較小的網(wǎng)絡(luò)中，而對于大規(guī)模的復(fù)雜網(wǎng)絡(luò)，提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確度也許并非其關(guān)鍵，而提高社區(qū)發(fā)現(xiàn)的速度才是關(guān)鍵。NEWMAN提出的基于Betweenness的算法[16]，是利用多核CPU來加速Betweenness計(jì)算的，通過適當(dāng)?shù)恼{(diào)度算法，可以用分布式的方式來并行計(jì)算Betweenness,從而比在單CPU上的計(jì)算速度提高了3～4倍，這些發(fā)現(xiàn)與研究都為社區(qū)的發(fā)展做出了貢獻(xiàn)。方平等提出了基于共同好友數(shù)的社區(qū)發(fā)現(xiàn)算法[17]，該算法符合社交網(wǎng)絡(luò)的特點(diǎn)，適合對大規(guī)模社交網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，本文在方平等的工作基礎(chǔ)上，根據(jù)三元閉包原理，提出了一種基于三元閉包的大規(guī)模社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，同時(shí)用會員閉包原理加快了社區(qū)劃分的速度。

1 相關(guān)概念

首先將一個(gè)社交網(wǎng)絡(luò)定義為一個(gè)有n個(gè)頂點(diǎn)，m條邊的圖G(V,E),其中n=|V|，m=|E|。S為社區(qū)中的頂點(diǎn)集，其中NS為S中的頂點(diǎn)的數(shù)目,記為NS=|S|，MS為S中邊的數(shù)目，記為MS=|{(u,v):u∈S,v∈S}|;CS是S向外連接的邊的數(shù)目，記為CS=|{(u,v):u∈S,v?S}|。

定義1(圖) 社交網(wǎng)絡(luò)中可以由頂點(diǎn)集和連接2個(gè)頂點(diǎn)之間關(guān)系的邊的集合組成一個(gè)圖來表示。在這個(gè)圖中，頂點(diǎn)代表一個(gè)個(gè)體或組織，頂點(diǎn)之間的邊代表它們之間存在著某種關(guān)系。而在圖形中，頂點(diǎn)之間的關(guān)系可以是任意的，圖中任意2個(gè)個(gè)體之間的關(guān)系都可能是相關(guān)的，根據(jù)每邊之間是否有方向和權(quán)值，圖又可以分為有向圖、無向圖，有全圖、無全圖。本文主要研究無向無權(quán)圖。

定義2(度) 網(wǎng)絡(luò)中頂點(diǎn)的度是指與頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目。網(wǎng)絡(luò)又可分為有向網(wǎng)絡(luò)和無向網(wǎng)絡(luò)，在有向網(wǎng)絡(luò)中，度又有入度和出度之分，入度定義為以頂點(diǎn)為頭的邊的數(shù)目，出度定義為以頂點(diǎn)為尾的邊的數(shù)目。一般認(rèn)為，頂點(diǎn)的度越大，就說明這個(gè)頂點(diǎn)越重要，與其他頂點(diǎn)聯(lián)系越密切。

定義3頂點(diǎn)i的鄰居頂點(diǎn)集合記為NB(i)，頂點(diǎn)i的度記為D(i)，S的鄰居頂點(diǎn)集合為NBS。

定義4(三元閉包) “在一個(gè)社交圈內(nèi)，若2個(gè)人有1個(gè)共同朋友則這2個(gè)人成為朋友的可能性就會提高”。在社交網(wǎng)絡(luò)中，廣泛的存在三元閉包。

定義5(三元閉包數(shù)) 假設(shè)A與B為好友，同時(shí)A與C也為好友，那么B與C的共同好友為A。由三元閉包可知，在一個(gè)社區(qū)網(wǎng)絡(luò)中，2個(gè)人如果有共同的好友，那么他們成為好友的幾率就會增大，所以取2個(gè)頂點(diǎn)間三元閉包數(shù)來衡量這2個(gè)頂點(diǎn)的相似度。

定義6會員閉包是指在一個(gè)社交網(wǎng)絡(luò)中，若一個(gè)人的朋友參加了某個(gè)社團(tuán)則其參加這個(gè)社團(tuán)的可能性就會提高。如果頂點(diǎn)i有x個(gè)朋友在S中，則頂點(diǎn)i相對于S的會員閉包數(shù)x=|NB(i)∩S|。

2 算法描述

本算法首先設(shè)初始社區(qū)為空，在所有的頂點(diǎn)中，選擇度最大的頂點(diǎn)作為初始頂點(diǎn)；然后求初始頂點(diǎn)與其鄰接頂點(diǎn)的三元閉包數(shù)，取三元閉包數(shù)最多的鄰接頂點(diǎn)加入初始頂點(diǎn)所在社區(qū)；之后再求初始社區(qū)中的所有頂點(diǎn)的各鄰接頂點(diǎn)屬于初始社區(qū)概率PS，將PS最大的頂點(diǎn)加入，形成新的初始社區(qū)；繼續(xù)迭代，通過不斷加入與初始社區(qū)會員閉包最大的頂點(diǎn)的方法把社區(qū)刷新，當(dāng)所要加入的頂點(diǎn)的擴(kuò)張度的差大于0或者所剩頂點(diǎn)的個(gè)數(shù)小于w時(shí)，這個(gè)小社區(qū)就劃分完畢。將以上步驟在剩下的網(wǎng)絡(luò)頂點(diǎn)中繼續(xù)執(zhí)行，直到將網(wǎng)絡(luò)中所有頂點(diǎn)都被劃分或者所剩頂點(diǎn)的個(gè)數(shù)小于w。此處的w可根據(jù)|V|的大小來定，例如|V|的1/10,因?yàn)樵诖笠?guī)模社區(qū)中，當(dāng)劃分到圖中的頂點(diǎn)較少時(shí)，此時(shí)真正有價(jià)值的社區(qū)已經(jīng)很少了，此時(shí)再用以上步驟去劃分，找出來的社區(qū)會更小，此時(shí)剩余的頂點(diǎn)可以用更簡單的算法歸集，如用社會學(xué)里的會員閉包通過判斷其好友屬于的社區(qū)來確定其屬于的社區(qū)，最終把整個(gè)社區(qū)劃分完畢。

算法實(shí)現(xiàn)步驟：

1)如果|V|>w，初始社區(qū)Ci=Null,V!=Null,否則跳轉(zhuǎn)到步驟9)；

2)查找V中度最大的頂點(diǎn)Va，加入到社區(qū)Ci中，V=V-Va;

3)根據(jù)定義5查找沒有被分配且與頂點(diǎn)Va三元閉包數(shù)最大的頂點(diǎn)Vb加入到初始社區(qū)Ci中，此時(shí)Ci=Ci+Vb，V=V-Vb；

4)根據(jù)定義9求頂點(diǎn)屬于社區(qū)的概率PS；

5)找到頂點(diǎn)PS最大的頂點(diǎn)Vx;

6)由定義8求ED(Vx)，如果ED(Vx)<0，則令Ci=Ci+Vx,V=V-Vx;

7)循環(huán)步驟5)和步驟6)，當(dāng)ED(Vx)>0時(shí)，這個(gè)社區(qū)的添加頂點(diǎn)完畢，此社區(qū)劃分好；

8)令i=i+1，返回步驟1);

9)當(dāng)|V|

3 算法應(yīng)用

3.1某文學(xué)網(wǎng)站的用戶

本研究將某文學(xué)網(wǎng)站的數(shù)據(jù)用基于三元閉包的算法進(jìn)行劃分，得到了65個(gè)社區(qū)，然后將劃分結(jié)果放到NodeXL中，分別展示每個(gè)小社區(qū)的圖形，但是由于數(shù)據(jù)比較大，雖然很多小的社區(qū)已經(jīng)被大社區(qū)覆蓋掉了，但是小社區(qū)能夠較清晰地體現(xiàn)出來，最終得出的圖形如圖1所示。

圖1 基于三元閉包的算法Fig.1 An algorithm based on triadic closure

由CNM算法劃分的社區(qū)如圖2所示，使用這種算法劃分出的社區(qū)比較少，并且包含了數(shù)據(jù)量巨大的社區(qū)，這說明使用CNM算法實(shí)現(xiàn)的社區(qū)劃分對具有包含類似于節(jié)點(diǎn)1這樣的度很大的用戶的網(wǎng)絡(luò)進(jìn)行細(xì)分有些不足；而根據(jù)三元閉包數(shù)所劃分成的社區(qū)則相對平均，劃分出的社區(qū)數(shù)目相對大些，所以這樣劃分出的社區(qū)才更具有研究價(jià)值。

圖2 CNM 算法劃分的社區(qū)Fig.2 Community structure found by CNM algorithm

為了更形象的對CNM算法與基于三元閉包的算法作比較，分別對這兩種算法所得到的社區(qū)數(shù)據(jù)進(jìn)行詳細(xì)統(tǒng)計(jì)，結(jié)果如表1所示。

表1 CNM算法與基于三元閉包算法的比較Tab.1 Comparison of CNM algorithm and the algorithm based on triadic closure

3.2寬吻海豚網(wǎng)

該網(wǎng)絡(luò)為一個(gè)動(dòng)物社會關(guān)系網(wǎng)絡(luò)，數(shù)據(jù)來自網(wǎng)絡(luò)公開數(shù)據(jù)集。LNSSEAU等人對新西蘭Doubtful Sound峽灣的一個(gè)寬吻海豚群體進(jìn)行長達(dá)7年的觀察所構(gòu)造出該海豚關(guān)系網(wǎng)，見圖3。該網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)代表一個(gè)海豚，邊表示2個(gè)海豚之間有頻繁的接觸，在該網(wǎng)絡(luò)中共有62個(gè)節(jié)點(diǎn)、159條邊。本文基于三元閉包的社區(qū)發(fā)現(xiàn)算法對該數(shù)據(jù)集的劃分結(jié)果與實(shí)際社區(qū)劃分相吻合。

圖3 寬吻海豚網(wǎng)Fig.3 Bottlenose dolphins network

3.3Zachary空手道俱樂部網(wǎng)絡(luò)

Zachary空手道俱樂部的關(guān)系網(wǎng)共有34個(gè)節(jié)點(diǎn)、78條邊，見圖4。本文基于三元閉包的社區(qū)發(fā)現(xiàn)算法對該數(shù)據(jù)集的劃分結(jié)果與實(shí)際社區(qū)劃分相吻合。

圖4 Zachary空手道俱樂部網(wǎng)絡(luò)Fig.4 Zachary of karate club network

4 總 結(jié)

以微博用戶的信息數(shù)據(jù)為依據(jù)，提出了一種基于三元閉包和會員閉包的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法，提出頂點(diǎn)會員閉包定義，以網(wǎng)絡(luò)中三元閉包數(shù)最多的2個(gè)頂點(diǎn)為初始社區(qū)，根據(jù)頂點(diǎn)會員閉包和擴(kuò)張度的差不斷增加鄰接頂點(diǎn)，形成局部最優(yōu)初始社區(qū)，適用于比較復(fù)雜的在線社會網(wǎng)絡(luò)。本文算法對寬吻海豚網(wǎng)與實(shí)際網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)基本相符，對“Zachary空手道俱樂部網(wǎng)絡(luò)”的劃分結(jié)果與實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)一致，并且對有關(guān)頂點(diǎn)接近度進(jìn)行了重新定義，這種定義更適用于比較復(fù)雜的網(wǎng)絡(luò)，提高了算法的效率與可行性，使相關(guān)代碼更容易實(shí)現(xiàn)。

/

[1] GRANOVETTER M S. The strength of weak ties[J]. American Journal of Sociology，1973，78(6)：1360-1380.

[2] KERNIGHAN B W，LIN S．An efficient heuristic procedure for partitioning graphs[J]．Bell System Technical Journal,1970，49(1)：291-307．

[3] NEWMAN M E J. A measure of betweenness centrality based on random walks[J]. Social Networks, 2005, 27(1):39-54.

[4] 張 聰, 沈惠璋, 李 峰. 復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)劃分的快速分裂算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2011, 28(4):1242-1244. ZHANG Cong，SHEN Huizhang,LI Feng. Community structure in complex networks rapidly dividing division algorithm[J]. Application Research of Computers, 2011, 28(4):1242-1244.

[5] 肖 晶. 基于WAF的社區(qū)發(fā)現(xiàn)及用戶推薦[D]. 北京：北京郵電大學(xué)，2013. XIAO Jing. Based WAF User Community Discovery[D]. Beijing：Beijing University of Posts and Telecommunications,2013.

[6] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. National Academy of Sciences, 2002, 99(6):7821-7826.

[7] CLAUSET A，NEWMAN M E J，MOORE C．Finding community structure in very large networks[J]．Physical Review E：Statistical，Nonlinear and Soft Matter Physics，2004，70(6)：6111-6116．

[8] PALLA G，DERDNYI I，F(xiàn)ARKAS I，et al．Uncovering the overlapping community structure of complex networks in nature and society[J]．Nature，2005，435：814-818．

[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，76(3)：6106-6111．

[10] BLONDEL V D，GUILLAUME J L，LAMBIOTTE R，et al．Fast unfolding of communities in large networks[J]．Journal of Statistical Mechanics，2008(10)：10008-10018．

[11] TANG L，LIU H，ZHANG J．Identifying evolving groups in dynamic multi-mode networks[J]．IEEE Transactions on Knowledge and Data Engineering，2012，24(1):72-85.

[12] FABER V. Clustering and the continuousk-means algorithm[J]. Los Alamos Science, 1994, 22:138-144.

[13] ZHAO W, MA H, HE Q. Parallelk-means clustering based on mapreduce[A].Cloud Computing[C]. Berlin：Springer, 2009. 674-679.

[14] KRISHNA K, NARASIMHA M M. GeneticK-means algorithm[J]. IEEE Transactions on Systems, Man and Cybernetics, Part B:Cybernetics, 1999, 29(3):433-439.

[15] 淦文燕, 赫 南, 李德毅. 一種基于拓?fù)鋭莸木W(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J]. 軟件學(xué)報(bào), 2009, 20(8):2241-2254. GAN Wenyan, HE Nan, LI Deyi. A network of community-based topology discovery potential method[J]. Journal of Software, 2009, 20(8):2241-2254.

[16] NEWMAN M E J. A measure of betweenness centrality based on random walks[J]. Social Networks, 2005, 27(1):39-54.

[17] 方 平，郭正彪，李芝棠，等.基于共同好友數(shù)的在線社會網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法[J]. 計(jì)算機(jī)科學(xué)與探索, 2012,6(5):456-464. FANG Ping, GUO Zhengbiao, LI Zhitang，et al. Online social network community structure detection algorithm based on number of shared friends[J]. Journal of Frontiers of Computer Science & Technology, 2012,6(5):456-464.

[18] RADICCHI F,CASTELLANO C,CECCONI F,et al.Defining and identifying communities in networks[J].National Academy of Sciences,2004,101(9):2658-2663.

A community detection algorithm based on triadic closure and membership closure

XU Yunfeng1, ZHAO Ning2, HAO Xuejun1, LI Bing1, LIU Huijuan1

(1.School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang Hebei 050018, China;2.Personnel Department, Hebei University of Science and Technology, Shijiazhuang Hebei 050018, China)

With the development of network and the expansion of people's communication ways, the social network penetrates into almost every corner of the entire society, and changes the ways of information communicating and news sharing, attracting more and more people's attention and research on it. Social network, also named social networking service, originated from the translation of British SNS (social network service), was literally translated as social network services or social networking service in Chinese. There're many manifestations of social networking platforms, such as:QQ, WeChat, Facebook and Micro-blog.In this paper, we mainly focus on the micro- blog, the emerging social platform. The main purpose of research on micro-blog is to find out the various relationships between users. People generally believe there're mainly 5 relations existing in miro-blog among users:the relationship of concerning, mentioning, forwarding, commenting and being friends. Due to the large number of social network users and the complicated relations among them, the generated social data, compared with the traditional data, has the characteristics of large amount of data, complex structure and semantically rich features. So according to the relationship among users, this paper proposes divided community algorithm based on triadic closure.

In the first instance, this algorithm took the initial community as being empty, in which the vertex degree maximum among all vertices was chosen as the initial vertex, then requesting for the number of Triadic closures between the initial vertex and the adjacent vertex, and requesting for the probability of vertices belonged to the community. The vertex with the maximumPsjoined the initial vertex community, forming a new initial community. With continued iterating, and by using collection algorithm of triadic and membership closure, the remained few vertices could be divided into different communities until the entire community was completely divided. Finally, every community was intuitively and visually presented by Graphics. When using this algorithm, the number of Triadic closure, the probability of vertex belonged to a community and the difference in expansion degree are the keys to value vertices in complex network. This method combines the characteristics of the global importance of vertices. Namely, in complex networks, the greater the number of Triadic closure is, the greater the likelihood of them in a community will be. The greater the vertex membership closures are, the priorer the vertex will be divided. The difference in expansion degree is to determine whether theicommunity is divided completely or not.

The research of social networking can not only help us understand and analyze the network structure, and detect to analyze network, but also can help link the relationship in virtual world to the real world. So the virtual relationship could be transferred into profits, providing valuable network for enterprises, and digging out the great economic value behind the social network. It can be embodied like this:firstly, to help companies find potential business opportunities by analyzing users' comments and published content to learn their consumption power, preferences and recent buying habits, thus to know the probability that he could purchase products. Second, it can give crisis warning message. According to user's information, products satisfaction degree of users can be learnt. Third, it can drive the information propagation speed and message breadth, of which the enterprises take advantage, achieving better product publicity.

Compared with the community network of Bottlenose Dolphin Internet and Zachary, the algorithm mentioned in this paper was proved to be effective and feasible.

social network; number of triadic closure; community divide

1008-1542(2014)01-0103-06

10.7535/hbkd.2014yx01017

2013-11-01；

2013-12-02；責(zé)任編輯：陳書欣

國家自然科學(xué)基金(71271076)

許云峰(1980-),男,河北滄州人,講師,碩士,主要從事網(wǎng)絡(luò)安全、神經(jīng)網(wǎng)絡(luò)等方面的研究。

E-mail：386839300@qq.com

TP391.1

A

許云峰，趙 寧，郝雪君，等.基于三元閉包和會員閉包的社區(qū)發(fā)現(xiàn)算法研究[J].河北科技大學(xué)學(xué)報(bào)，2014，35(1)：103-108.

XU Yunfeng, ZHAO Ning, HAO Xuejun, et al.A community detection algorithm based on triadic closure and membership closure[J].Journal of Hebei University of Science and Technology,2014,35(1):103-108.