國　琳,左萬利,彭　濤

(1.吉林大學計算科學與技術(shù)學院,吉林長春130012;2.吉林大學符號計算與知識工程教育部重點實驗室,吉林長春130012)

?

基于隸屬度的社會化網(wǎng)絡重疊社區(qū)發(fā)現(xiàn)及動態(tài)集群演化分析

國琳1,2,左萬利1,2,彭濤1,2

(1.吉林大學計算科學與技術(shù)學院,吉林長春130012;2.吉林大學符號計算與知識工程教育部重點實驗室,吉林長春130012)

摘要：社會化網(wǎng)絡中節(jié)點的復合屬性可能為臨時或過時狀態(tài),并且節(jié)點擁有一定能力維持固有狀態(tài),所以不可單純依據(jù)新增數(shù)據(jù)或節(jié)點現(xiàn)有特征確定社區(qū)劃分.本文提出可重疊社區(qū)發(fā)現(xiàn)算法及集群動態(tài)更新方案,根據(jù)網(wǎng)絡歷史數(shù)據(jù)分析節(jié)點對原始集群的隸屬程度,并結(jié)合新增數(shù)據(jù)確定節(jié)點變化趨勢,實現(xiàn)網(wǎng)絡結(jié)構(gòu)分析及社區(qū)動態(tài)更新.本文分別在不同數(shù)據(jù)集中測試聚類效果,實驗結(jié)果證明算法既保持對新增數(shù)據(jù)的敏感度,也防止了節(jié)點短暫特征或節(jié)點維持固有狀態(tài)的能力對劃分結(jié)果的負面影響.

關(guān)鍵詞:社區(qū)發(fā)現(xiàn);社會化網(wǎng)絡;聚類;重疊社區(qū);自適應算法

1引言

社會化網(wǎng)絡中用戶的多重社會屬性導致用戶可同時從屬于多個社區(qū),因此基于可重疊聚類的社區(qū)發(fā)現(xiàn)算法效果更佳.另外,社會化網(wǎng)絡的實時動態(tài)性可導致節(jié)點經(jīng)常出現(xiàn)短暫性特征,該特征將影響社區(qū)劃分結(jié)果的穩(wěn)定性.本文充分分析節(jié)點維持固有狀態(tài)的能力,并判斷新增數(shù)據(jù)變化程度,結(jié)合不同時期節(jié)點狀態(tài),綜合確定社區(qū)劃分方案.

本文所做工作分為以下幾個方面:

(1)關(guān)聯(lián)強度分析及權(quán)重設定.以被分析節(jié)點為中心節(jié)點,依據(jù)其相鄰節(jié)點集合構(gòu)建的網(wǎng)絡計算節(jié)點權(quán)重,由此獲得的權(quán)重表示節(jié)點被設定為中心節(jié)點的概率.

(2)隸屬度分析.根據(jù)節(jié)點變化趨勢和節(jié)點從屬于原社區(qū)的能力,分析變化的數(shù)據(jù)是否導致節(jié)點自身狀態(tài)和社區(qū)特征的改變.

(3)可重疊社區(qū)劃分及集群動態(tài)更新.分析節(jié)點是否脫離固有狀態(tài)及是否形成新的穩(wěn)定狀態(tài),進而更新原有的劃分結(jié)果.

2相關(guān)工作

社區(qū)發(fā)現(xiàn)[1]根據(jù)元素間的關(guān)聯(lián)關(guān)系劃分數(shù)據(jù)集為若干社區(qū).社區(qū)中的用戶通過興趣、行為、社會屬性等特征建立連接,分析社區(qū)劃分結(jié)果可有效識別網(wǎng)絡結(jié)構(gòu)、精確分析用戶角色.社會化網(wǎng)絡分析[2,3]的一般方法為基于特征向量、稀疏矩陣、分區(qū)技術(shù)、小世界網(wǎng)絡分析等.多數(shù)傳統(tǒng)社區(qū)發(fā)現(xiàn)算法可處理靜態(tài)數(shù)據(jù),但由于網(wǎng)絡的實時變化性使社區(qū)劃分需適應動態(tài)數(shù)據(jù),所以要求算法對變化數(shù)據(jù)既保證一定的適應性,又要求有較強的甄別臨時特征的能力,因此社區(qū)發(fā)現(xiàn)算法不能僅局限于靜態(tài)數(shù)據(jù)處理.

處理不同離散時間點的社區(qū)結(jié)構(gòu)或根據(jù)不同時刻網(wǎng)絡快照獲得網(wǎng)絡特征動態(tài)分析社區(qū)結(jié)構(gòu)[4],為動態(tài)社會網(wǎng)絡分析的主要研究方向.分析動態(tài)網(wǎng)絡理論模型一般為自旋模型、同步算法、隨機游走,其中依據(jù)擴散規(guī)律計算節(jié)點間距離和相互吸引能力分析動態(tài)網(wǎng)絡變換趨勢的隨機游走理論的方法較多[2,5].將圖信息轉(zhuǎn)換成矩陣形式,通過矩陣分解、變換等方法分析節(jié)點間距離關(guān)系并實現(xiàn)不同集群的劃分[6,7],其劃分結(jié)果精確,并且便于執(zhí)行多網(wǎng)融合及異構(gòu)網(wǎng)絡分析[8].這些傳統(tǒng)聚類算法劃分的集群是互不相交的,但社會網(wǎng)絡中的節(jié)點擁有多重社會屬性并導致多數(shù)節(jié)點從屬于多個社區(qū)[9],因此傳統(tǒng)聚類算法無法處理擁有復雜關(guān)系的網(wǎng)絡節(jié)點.

由于用戶通常同時屬于多個網(wǎng)絡,因此將節(jié)點劃分到某一特定簇的算法不能滿足社會化網(wǎng)絡的現(xiàn)實要求.文獻[10]構(gòu)建模塊函數(shù)將網(wǎng)絡中節(jié)點映射到歐幾里得空間,以構(gòu)建重疊社區(qū)結(jié)構(gòu).文獻[11]可檢測高密度重疊網(wǎng)絡和不重疊網(wǎng)絡,發(fā)現(xiàn)重疊區(qū)域內(nèi)節(jié)點連接密度更高,進而提出節(jié)點連接概率公式以識別社區(qū).文獻[6]分析節(jié)點對不同社區(qū)的從屬強度或受控水平以確定節(jié)點劃分到相應社區(qū)的合理性.通過社區(qū)的可重疊聚類算法將節(jié)點不唯一的劃分到多個聚類中以體現(xiàn)用戶多重社會特征,有利于全面分析用戶在網(wǎng)絡中的不同角色,以及發(fā)現(xiàn)社區(qū)間關(guān)聯(lián)關(guān)系和重疊區(qū)域,使更合理描述網(wǎng)絡架構(gòu).

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

用戶關(guān)系分布圖G=,其中V表示節(jié)點集合,每個節(jié)點代表一個用戶,E表示邊集合,描述節(jié)點間通過某種途徑存在的關(guān)聯(lián)關(guān)系(如共同關(guān)注某類事物),R表示邊權(quán)重集合,描述節(jié)點間相互關(guān)聯(lián)的強度.

3.1關(guān)聯(lián)強度分析

分析用戶對不同主題的關(guān)注情況生成用戶-項目矩陣A,其中任意αi=(αi1,αi2,…,αir)表示矩陣A的第i行向量,αi描述用戶i對r個項目關(guān)注次數(shù).由于不同用戶對不同主題關(guān)注程度和關(guān)注類型都不一致,因此為方便數(shù)據(jù)比較需統(tǒng)一矩陣中的度量標準,即計算用戶對不同項目的關(guān)注度比,以方便不同用戶間比較,計算公式為:

(1)

其中eic∈(0,1]描述用戶i對項目c的關(guān)注程度.如果用戶僅和一個主題有關(guān)聯(lián),則eic的計算結(jié)果為1,并且eic=1表示用戶對主題的最高關(guān)注程度.如果用戶沒有產(chǎn)生任何社交數(shù)據(jù),則eic的計算結(jié)果為0,說明該節(jié)點既不瀏覽信息也不產(chǎn)生數(shù)據(jù),即不為網(wǎng)絡提供任何貢獻.

根據(jù)矩陣A構(gòu)建描述用戶關(guān)系圖G.如果某兩個用戶存在共同興趣,則G中該節(jié)點間存在邊,并且根據(jù)邊權(quán)重信息衡量節(jié)點關(guān)聯(lián)強度.邊權(quán)重計算公式為:

λc=1{Ic(i,j)}

(2)

(3)

其中式(2)為Heaviside方程,當邏輯判斷為真時,其返回值為1,否則為0.Ic(i,j)判斷節(jié)點i與j是否存在共同關(guān)注主題c.wij表示節(jié)點i和j的連接概率,其與用戶i和j的相關(guān)主題的關(guān)注程度有關(guān).由此G中的任意兩個相連節(jié)點,都是通過關(guān)注共同主題而導致其存在邊相連接的,因此如果兩個用戶共同關(guān)注主題越多,其連接權(quán)重設定值越大,所以式(3)表示通過不同主題建立連接的權(quán)重和.為方便數(shù)據(jù)比較將邊權(quán)值設定在特定數(shù)值區(qū)間內(nèi),因此采用函數(shù)1-exp(-x)將變量x映射到(0,1)范圍內(nèi).

3.2節(jié)點權(quán)重設定

計算節(jié)點權(quán)重時視當前分析節(jié)點為中心節(jié)點,以其鄰接節(jié)點構(gòu)成的網(wǎng)絡(記為v-社區(qū),其中v表示中心節(jié)點)為依據(jù)設定節(jié)點權(quán)重.節(jié)點v的權(quán)重受兩個因素影響:(1)節(jié)點v與鄰接節(jié)點的平均連接強度;(2)鄰接節(jié)點間的關(guān)聯(lián)密度.分別采用strength和density表示上述因素以計算節(jié)點權(quán)重,其計算方法分別如下所述.

v-社區(qū)關(guān)聯(lián)強度:

(4)

其中│v.edge│表示節(jié)點v的鄰接節(jié)點數(shù)量,∑v.edge表示連接節(jié)點v的邊的權(quán)重和.

v-社區(qū)稀疏度:

(5)

(6)

其中│Com.edge│表示v-社區(qū)中節(jié)點間(包含節(jié)點v)存在邊的數(shù)量,n表示v-社區(qū)中節(jié)點數(shù)量.v.sparsity為中間計算結(jié)果,表示v-社區(qū)的網(wǎng)絡密度,但其數(shù)據(jù)表達不規(guī)范.因此v.density為稀疏度的最終度量參數(shù),其將v.sparsity映射到(0,1)區(qū)間.

證明

v.sparsity分別與網(wǎng)絡聚合系數(shù)和v的鄰接節(jié)點數(shù)量呈正比關(guān)系,因此v.sparsity的計算公式為:

v.sparsity=v.net×|v.edge|

(7)

v.net為v-社區(qū)的聚合系數(shù),其計算公式為:

(8)

(9)

為便于數(shù)據(jù)對比,將v.sparsity映射在(0,1)范圍內(nèi),則最終計算公式為:

(10)

以度為1的節(jié)點為中心節(jié)點的網(wǎng)絡應是低密度的,但根據(jù)上述公式計算的sparsity值為1,與實際要求不符,因此為該節(jié)點設定一個最低參數(shù)值以防止誤認為是高密度網(wǎng)絡,則公式適用條件為n≥2.

僅根據(jù)網(wǎng)絡密度設定節(jié)點權(quán)重將導致社區(qū)密度大的中心節(jié)點權(quán)重大,而忽視了網(wǎng)絡間的連接強度.因此綜合v.density和v.strength參數(shù),提出節(jié)點權(quán)重計算公式:

v.weight=η(v.density,v.strength)

(11)

根據(jù)density和strength對節(jié)點權(quán)重的不同影響程度設置η.在高密度網(wǎng)絡環(huán)境下,節(jié)點權(quán)重更依賴于strength.相反在低密度網(wǎng)絡環(huán)境下,節(jié)點權(quán)重更依賴于density.本文簡單設置η(x,y)=(x+y)/2,均衡各參數(shù)對節(jié)點權(quán)重的影響程度[12].

圖1(a)為全連接圖,導致每個節(jié)點的權(quán)重計算結(jié)果相近,則最終影響節(jié)點權(quán)重的因素為節(jié)點間的連接強度.圖1(b)為稀疏網(wǎng)絡,比較節(jié)點7和節(jié)點9可知,雖然節(jié)點7的平均邊連接強度較大,但由于其度為1,導致節(jié)點7的權(quán)重小于節(jié)點9.圖1(c)近于正常的網(wǎng)絡,節(jié)點權(quán)重受節(jié)點連接強度和網(wǎng)絡密度的雙重影響,經(jīng)計算得知節(jié)點6的權(quán)重最大.

4社區(qū)動態(tài)劃分

社區(qū)劃分分為兩個部分.根據(jù)已有的網(wǎng)絡數(shù)據(jù)執(zhí)行第一次社區(qū)劃分,體現(xiàn)用戶歷史行為信息.第二次社區(qū)劃分新增數(shù)據(jù),根據(jù)節(jié)點對社區(qū)的隸屬度和變化趨勢實現(xiàn)社區(qū)動態(tài)劃分.通常第一次劃分是預先完成的工作,所以算法的總工作量是較小的,僅處理增量數(shù)據(jù)即可.

4.1社區(qū)劃分及隸屬度計算

第一次社區(qū)劃分(算法1)根據(jù)節(jié)點權(quán)重選擇當前網(wǎng)絡的中心節(jié)點,并將該點的鄰接節(jié)點加入網(wǎng)絡,循環(huán)執(zhí)行直到被發(fā)現(xiàn)的節(jié)點全覆蓋或大部分覆蓋網(wǎng)絡時算法終止,合并多余的社區(qū)劃分以簡潔網(wǎng)絡描述.第一次社區(qū)劃分算法描述如算法1.

社區(qū)融合將被融合社區(qū)的所有節(jié)點加入覆蓋范圍更廣的社區(qū).由于density公式中分母的限制,可導致鄰接節(jié)點少的節(jié)點比鄰接節(jié)點多的節(jié)點的density值大,甚至大很多,因此可能產(chǎn)生多個小社區(qū)網(wǎng)絡.本文根據(jù)節(jié)點數(shù)量衡量社區(qū)權(quán)威度,并用權(quán)威度衡量社區(qū)被單獨劃分的價值.當權(quán)威度小于閾值時允許節(jié)點和中心節(jié)點不完全覆蓋的條件下與其他社區(qū)融合.

若節(jié)點在每個時隙過程中均以獨立概率P接入信道，那么可以在退避過程中建立以時隙為單位的離散條件下的二進制退避階數(shù)s(t)和碰撞窗口b(t)的馬爾科夫過程[13]，如圖4所示.

算法1的時間復雜度為O(mlog2m)+O(k(r+1)/2),其中m為節(jié)點數(shù)量,k為集群數(shù)量,r為集群內(nèi)平均節(jié)點數(shù)量.

定義1核心節(jié)點:該節(jié)點與社區(qū)中大量節(jié)點存在高度關(guān)聯(lián)關(guān)系.

定義2游離節(jié)點:從屬于多個社區(qū)并且在每個社區(qū)中存在少量邊的節(jié)點.

定義3普通節(jié)點:社區(qū)中除核心節(jié)點和游離節(jié)點外的其余節(jié)點.

核心節(jié)點存在極小概率遷移到其他社區(qū),游離節(jié)點所屬社區(qū)經(jīng)常變化(注:與重疊區(qū)域的節(jié)點不同,游離節(jié)點可能在下一時刻完全被劃分到新社區(qū)中),因此需分析節(jié)點對社區(qū)的隸屬度,以確定節(jié)點變化趨勢和維持原狀態(tài)的能力.節(jié)點v針對某社區(qū)的隸屬度受以下幾個因素影響:(1)社區(qū)中節(jié)點v的鄰接節(jié)點數(shù)量;(2)節(jié)點v的權(quán)重;(3)節(jié)點v與社區(qū)中心節(jié)點的距離;(4)節(jié)點v從屬于的社區(qū)數(shù)量.綜合上述,隸屬度計算公式為:

節(jié)點v隸屬于c-社區(qū)的程度為:

(12)

(13)

其中│v.adj│表示v的鄰接節(jié)點數(shù)量,│Nv│表示v隸屬于不同社區(qū)數(shù)量,len(v,c)表示v到c-社區(qū)的距離,即v到c的距離.p表示從v到c最短路徑中的節(jié)點編號,p+1表示最短路徑中p的下一個節(jié)點,wpq表示節(jié)點p與q之間邊的權(quán)重.中心節(jié)點對社區(qū)的隸屬度最高,因此中心節(jié)點的隸屬度賦值為1.度為1的節(jié)點對社區(qū)的隸屬度最低,但由于該節(jié)點只屬于一個社區(qū),導致其隸屬度較高,可能誤認為社區(qū)核心節(jié)點甚至中心節(jié)點,因此需賦予一個較低的隸屬值,本文將其賦值為0.

4.2集群動態(tài)更新

P為m×n矩陣,用于描述m個用戶對n個社區(qū)的隸屬度.αu為P的某一行向量,表示節(jié)點u對n個社區(qū)的隸屬度(式(8)).第一次社區(qū)劃分生成隸屬度矩陣Ppref,分析N時刻用戶關(guān)系計算隸屬度矩陣Pupdate.顯然Ppref和Pupdate為維數(shù)不同矩陣,所以需統(tǒng)一Ppref和Pupdate維數(shù).中心節(jié)點/非中心節(jié)點信息補充方案是在相應位置添加參數(shù)0,因為被補充的節(jié)點信息不出現(xiàn)在原矩陣中,所以僅增加原矩陣維度而不增加有效信息即可.經(jīng)過處理后的矩陣記為T,其生成過程為:

(14)

其中exist(x,Y)判斷向量x是否出現(xiàn)在矩陣Y中,如果是則返回1,否則返回0.

融合矩陣Ptrans:

Ptrans?λTpref+(1-λ)Tupdate+Pre

(15)

(16)

(17)

其中Ptrans為節(jié)點隸屬于不同社區(qū)的程度.λ為不同時期數(shù)據(jù)采集時間比值,即新增數(shù)據(jù)采集時間越長,其描述用戶關(guān)系穩(wěn)定性越強.節(jié)點有一定能力維持原狀態(tài),除非節(jié)點與原社區(qū)距離過遠.根據(jù)隨機游走原理分析用戶回歸原始狀態(tài)的概率矩陣Pre,Pre的任意行向量βu表示節(jié)點u對不同中心節(jié)點維持原狀態(tài)的能力.c∈(0,1)表示節(jié)點返回原始狀態(tài)的概率,│Nr│表示節(jié)點r的邊數(shù)量,Wpq表示節(jié)點p和節(jié)點q間邊的權(quán)重.

舉例計算圖2中三種結(jié)構(gòu)的Pre(s,e)值(設定c=0.2):

分析結(jié)果可知普通節(jié)點對中心節(jié)點的忠誠程度不僅受最短路徑長度影響,同時受連接強度影響.

分析動態(tài)網(wǎng)絡需間隔固定時間采集網(wǎng)絡數(shù)據(jù),當數(shù)據(jù)發(fā)生變化時,根據(jù)原始數(shù)據(jù)構(gòu)建Tpref,其方法有兩種:(1)執(zhí)行第一次社區(qū)劃分;(2)將先前建立的Ttrans直接賦給Tpref.通常采用方法2,僅在無先驗知識條件下采用方法1,因此算法僅需處理新增數(shù)據(jù)構(gòu)建Tupdate以計算Ptrans,進而執(zhí)行第二次社區(qū)劃分.

動態(tài)網(wǎng)絡分析及集群動態(tài)更新算法描述如下:

degree(n,Com)根據(jù)節(jié)點n與集群Com的核心節(jié)點的平均距離計算其關(guān)聯(lián)程度.函數(shù)DO-Cluster的時間復雜度為O(mlog2m)+O(k(r+1)/2)+O(m),其中m為Gn中節(jié)點數(shù)量,k為集群數(shù)量,r為集群內(nèi)平均節(jié)點數(shù)量.

5實驗

實驗數(shù)據(jù)集為:MovieLens和Reuters數(shù)據(jù)集.對比算法為:非重疊聚類算法KMeans和可重疊聚類算法DClustR[12],ISC[13],Star[14],Gstar[15]和DHS[16].

表1　符號對照表

從MovieLens數(shù)據(jù)集中分別提取2385條用戶信息和5000條用戶信息構(gòu)建數(shù)據(jù)集ML1和ML2.在ML1數(shù)據(jù)集上做KMeans和DO-Cluster對比實驗,對比數(shù)據(jù)如表2所示.KMeans需設置隨機種子取值和聚類數(shù)量,并經(jīng)過多次迭代才能獲得結(jié)果.從表2可知,KMeans算法設定的集群數(shù)量越多,則CSE值越小,但同時更易出現(xiàn)過度聚類情況.例如,在seed為5的前提下,numC分別設定為10和15的實驗結(jié)果中都存在不必要的集群.DO-Cluster可重疊聚類結(jié)果適中,并不存在過度劃分情況,也不需預先設定參數(shù).表2說明DO-Cluster發(fā)現(xiàn)的集群沒有對節(jié)點實現(xiàn)全覆蓋,其原因是DO-Cluster為基于節(jié)點連接關(guān)系發(fā)現(xiàn)未處理節(jié)點,而存在一定數(shù)量的不活躍節(jié)點,因此需生成大量集群才能發(fā)現(xiàn)不活躍節(jié)點,但該集群中絕大部分節(jié)點都與已發(fā)現(xiàn)集群重疊,并且算法代價呈指數(shù)級別增加.所以將未被發(fā)現(xiàn)節(jié)點聚合為一個低頻節(jié)點集群,其既彌補節(jié)點覆蓋率低,又降低算法執(zhí)行代價.

表3對比多個可重疊聚類算法和DO-Cluster的性能,其中FBCubed為綜合精度和召回率的指標,可有效度量重疊聚類劃分的準確度.數(shù)據(jù)集Reu-1、Reu-2和Reuter為從Reuters-21578中直接獲取,Reu-Dy分為原始數(shù)據(jù)和新增數(shù)據(jù)以構(gòu)建動態(tài)數(shù)據(jù)集.實驗說明DClustR產(chǎn)生過多的不必要聚類結(jié)果,造成大量的重疊區(qū)域,然而DO-Cluster可最大化減少不必要的劃分結(jié)果,以最少的社區(qū)劃分達到最優(yōu)的網(wǎng)絡覆蓋,處理不同類型數(shù)據(jù)集時算法效果穩(wěn)定.

為進一步分析DO-Cluster劃分結(jié)果,在ML2數(shù)據(jù)集上執(zhí)行該算法,分析集群生成過程中數(shù)據(jù)的變化,實驗結(jié)果如圖3所示.

圖3比較了17個集群信息,編號表示生成順序.實驗發(fā)現(xiàn)雖然c-1至c-8中節(jié)點數(shù)量較少,但集群內(nèi)節(jié)點關(guān)聯(lián)度高,導致中心節(jié)點權(quán)重較高,因此以該節(jié)點為中心的社區(qū)較早被發(fā)現(xiàn).c-9的中心節(jié)點存在大量鄰接節(jié)點,但由于網(wǎng)絡密度較低,導致其中心節(jié)點權(quán)重不是最大的(注:c-9包含節(jié)點數(shù)量最多,發(fā)現(xiàn)未處理節(jié)點數(shù)量最多).通常集群內(nèi)節(jié)點數(shù)量的增加導致較低的網(wǎng)絡密度,這是c-9不被首先發(fā)現(xiàn)的原因.雖然c-15至c-17中節(jié)點數(shù)量較多,但未發(fā)現(xiàn)未知節(jié)點,即不增加有效信息,卻增加集群間重疊范圍,因此將其刪除.綜上,刪除多余聚類結(jié)果后,c-1至c-14為DO-Cluster算法發(fā)現(xiàn)的社區(qū).表4為社區(qū)內(nèi)部節(jié)點分布情況.

表2　對比實驗結(jié)果1

表3　對比實驗結(jié)果2

表4　ML2劃分結(jié)果分析

圖4展示聚類結(jié)果中最大集群c-9的信息.c-9包含3099個節(jié)點,占整個網(wǎng)絡61.98%的節(jié)點.ML2可由c-9發(fā)現(xiàn)大部分節(jié)點,再由其余規(guī)模較小的社區(qū)進行補充.具體網(wǎng)絡度量指標如圖5所示.

由圖5(a)可知擁有邊越多的節(jié)點數(shù)量越少,并且該集群的中心節(jié)點為擁有邊最多的節(jié)點,其擁有3091條邊.圖5(b)、5(c)分別根據(jù)空間內(nèi)元素間距離和節(jié)點特征值分析節(jié)點在圖中的中心性度量.

c-12與c-14節(jié)點度的取值情況分布相似,即擁有大量邊的節(jié)點數(shù)量較少,并且大多數(shù)節(jié)點擁有少量邊.但c-13與c-12、c-14完全不同,其節(jié)點度取值分布平均,因此網(wǎng)絡密度也較大.實驗發(fā)現(xiàn)網(wǎng)絡內(nèi)節(jié)點數(shù)量較少時易達到網(wǎng)絡內(nèi)部高密度連接,而較大節(jié)點數(shù)量通常導致較低的網(wǎng)絡連接密度,因此c-13的情況較難出現(xiàn).

6結(jié)論

本文提出算法根據(jù)網(wǎng)絡歷史數(shù)據(jù)計算節(jié)點對社區(qū)的隸屬程度，并結(jié)合新增數(shù)據(jù)確定節(jié)點變化趨勢，運用可重疊社區(qū)劃分算法實現(xiàn)網(wǎng)絡結(jié)構(gòu)分析及動態(tài)更新.該算法既保證對新增數(shù)據(jù)的敏感度，也防止節(jié)點臨時特征對劃分結(jié)果的負面影響. 實驗驗證了算法的可行性和社區(qū)劃分結(jié)果的正確性，并說明如果僅根據(jù)節(jié)點覆蓋率確定社區(qū)數(shù)量將導致重疊面積增加，而難以減少未被發(fā)現(xiàn)節(jié)點數(shù)量，因此節(jié)點不完全覆蓋的劃分結(jié)果是合理的.

參考文獻

[1]Flake G W,Lawrence S,Giles C L,et al.Coetzee.Self-organization and identification of web community[J].Computer,2002,35(3):66-70.

[2]Thakur G S,Tiwari R,Thai M T,et al.Detection of local community structures in complex dynamic networks with random walks[J].IET Systems Biolpgy,2009,3(4):266-278.

[3]潘磊,金杰,王琮駿,等.社會網(wǎng)絡中基于局部信息的邊社區(qū)挖掘[J].電子學報,2012,40(11):2255-2262.

Pan Lei,Jin Jie,Wang Chong-jun,et al.Detecting link communities based on local information in social networks[J].Acta Electronica Sinica,2012,40(11):2255-2262.(in Chinese)

[4]Tantipathananandh C,Berger-wolf T,Kempe D.A framework for community identification in dynamic social networks[A].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].California,USA:ACM,2007.717-726.

[5]Wang W,Liu D,Liu X,et al.Fuzzy overlapping community detection based on local random walk and multidimensional scaling[J].Physica A:Statistical Mechanics and Its Applications,2013,392(24):6578-6586.

[6]Christiano T,Zhao L.Uncovering overlapping cluster structures via stochastic competitive learning[J].Information Sciences,2013,247:40-61.

[7]Wang C-D,Lai J-H,Yu P S.NEIWalk:Community discovery in dynamic content-based networks[J].IEEE Transactions on Knowledge and Data Engineering,2013,26(7):1734-1748.

[8]Comar P M,Tan P-N,Jain A K.A framework for joint community detection across multiple related networks[J].Neurocomputing,2012,76(1):93-104.

[9]Fortunato S.Community detection in graphs[J].Physics Reports,2010,486(3-5):75-174.

[10]Zhang S,Wang R,Zhang X.Identification of overlapping community structure in complex networks using fuzzy cc-means clustering[J].Physica A:Statistical Mechanics and Its Applications,2007,374:483-490.

[11]Yang J,Leskovec J.Overlapping community detection at scale:A nonnegative matrix factorization approach[A].Proceedings of the 6th ACM International Conference on Web Search and Data Mining[C].Roman,Italy:ACM,2013.587-596.

[12]Perez-Suarez A,Martinez-Trinidad J F,Carrasco-Ochoa J A.An algorithm based on density and compactness for dynamic overlapping clustering[J].Pattern Recognition,2013,46(11):3040-3055.

[13]Pons-Porrata A,Ruiz-Shulcloper J,Berlanga-Llavori R,et al.Un algoritmo incremental para la obtención de cubrimientos con datos mezclados[A].Proceedings of the 7th Iberoamerican Conference on Pattern Recognition[C].Mexico:CIARP,2002.405-416.

[14]Aslam J,Pelekhov K,Rus D.Static and dynamic information organization with star clusters[A].Proceedings of the 7th International Conference on Information and Knowledge Management[C].Bethesda,Maryland,USA:ACM,1998.208-217.

[15]Pérez-Suárez A,Medina-Pagola J.A clustering algorithm based on generalized stars[A].Proceedings of the 5th International Conference on Machine Learning and Data Mining in Pattern Recognition[C].Leipzig,Germany:Springer,2007.248-262.

[16]Gil-García R,Pons-Porrata A.Dynamic hierarchical algorithms for document clustering[J].Pattern Recognition Letters,2010,31(6):469-477.

國琳女,1987年8月生于吉林吉林,2013年至今于吉林大學計算機學院攻讀博士學位,從事社會化網(wǎng)絡、知識挖據(jù)及搜索引擎有關(guān)研究.

E-mail:guolin13@mails.jlu.edu.cn

左萬利(通訊作者)男,1957年12月生于吉林省吉林市,現(xiàn)為吉林大學計算機科學與技術(shù)學院教授、博士生導師,ACM職業(yè)會員,從事數(shù)據(jù)庫、Web智能、網(wǎng)絡搜索引擎、自然語言處理等有關(guān)研究.

E-mail:wanli@jlu.edu.cn

Overlapping Community Detection and Dynamic Group Evolution Analysis Based on the Degree of Membership in Social Network

GUO Lin1,2,ZUO Wan-li1,2,PENG Tao1,2

(1.CollegeofComputerScienceandTechnologyofJilinUniversity,Changchun,Jilin130012,China;2.SymbolComputationandKnowledgeEngineerofMinistryofEducationofJilinUniversity,Changchun,Jilin130012,China)

Abstract:The complex social attributes of nodes in the network have a certain ability to maintain the former state,so it is inappropriate to determine community division merely based on newly added data.This paper proposes an overlapping community detection algorithm and dynamic cluster update strategy,which,by fully analyzing historical network data to compute the degree of nodes belonging to communities,determines the evolution tendency of nodes through incorporating incremental data to analyze the structure of the network and update the division results automatically.Experiments on several typical datasets demonstrate that the algorithm not only ensures the sensitivity to incremental data,but also avoids the negative effect of temporary features in maintaining intrinsic states on the clustering results.

Key words:community detection;social internet;clustering;overlapping community;adaptive algorithm

作者簡介

DOI:電子學報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.014

中圖分類號:TP391

文獻標識碼：A

文章編號：0372-2112 (2016)03-0587-08

基金項目:國家自然科學基金(No.60973040);國家自然科學青年基金(No.61300148);吉林省重點科技攻關(guān)項目基金(No.20130206051GX);吉林省科技計劃青年科研基金(No.20130522112JH);中國博士后基金項目(No.2012M510879);吉林大學基本科研業(yè)務費科學前沿與交叉項目(No.201103129)

收稿日期:2014-06-07;修回日期:2014-10-15;責任編輯:覃懷銀