基于時(shí)間交互偏置影響傳播模型的弱連接重疊社區(qū)檢測(cè)

許小媛,黃 黎,李海波

(1.江蘇開放大學(xué) 信息工程學(xué)院,南京 210017; 2.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京 211106)

0 概述

目前,社交網(wǎng)絡(luò)已經(jīng)成為人們?nèi)粘Ｉ畹闹匾M成部分,如臉譜網(wǎng)、Twitter和LinkedIn等。約68%的在線用戶擁有社交信息,用以獲取新聞或與其他人進(jìn)行聯(lián)系,大量用戶加入到在線社區(qū)中,使得社區(qū)檢測(cè)成為社會(huì)網(wǎng)絡(luò)挖掘領(lǐng)域中的一項(xiàng)熱門工作[1-2]。社區(qū)內(nèi)的用戶之間具有緊密的連接關(guān)系,社區(qū)檢測(cè)指在給定網(wǎng)絡(luò)中對(duì)所有社區(qū)進(jìn)行識(shí)別,其具有較多重要的現(xiàn)實(shí)應(yīng)用,包括有效的信息傳播、目標(biāo)市場(chǎng)識(shí)別和感染控制等[3]。

傳統(tǒng)的社區(qū)檢測(cè)方法,如Louvain方法、infomap方法、標(biāo)簽傳播或Newman主要特征向量方法等[4],主要關(guān)注用戶之間的關(guān)系連接,采用連接關(guān)系強(qiáng)弱量化指標(biāo)。這些方法將網(wǎng)絡(luò)表示為具有穩(wěn)定連接的靜態(tài)結(jié)構(gòu),原因是這些連接將持續(xù)很長(zhǎng)時(shí)間。文獻(xiàn)[5]基于Louvain方法提出一種不相交重疊社區(qū)檢測(cè)方法,其考慮具有可接受時(shí)間成本的社會(huì)網(wǎng)絡(luò)中的圖分割過程實(shí)現(xiàn)方式。文獻(xiàn)[6]引入加權(quán)社區(qū)聚類度量,采用infomap指標(biāo)實(shí)現(xiàn)了大規(guī)模圖社區(qū)模型的可擴(kuò)展社區(qū)檢測(cè),該指標(biāo)的設(shè)定依賴于社區(qū)中的三角結(jié)構(gòu)。文獻(xiàn)[7]基于標(biāo)簽傳播算法模型,采用PageRank方法,提出一種大規(guī)模社區(qū)檢測(cè)過程中解決處理器負(fù)載均衡問題的方法。文獻(xiàn)[8]基于Newman主要特征向量方法將社區(qū)檢測(cè)過程優(yōu)化為一個(gè)NP難優(yōu)化問題,然后采用啟發(fā)式搜索算法實(shí)現(xiàn)對(duì)社區(qū)結(jié)構(gòu)的有效檢測(cè)。上述算法均取得了良好的效果,但是,在Twitter數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果表明,多數(shù)用戶不依賴他們的用戶關(guān)系連接進(jìn)行交互操作。

社區(qū)邊緣攜帶的關(guān)系可提供更有意義的信息,并更準(zhǔn)確地反映關(guān)系的強(qiáng)度,這些關(guān)系可以通過邊緣權(quán)重的分配來量化,從而提升社區(qū)的時(shí)間交互測(cè)量性能。在社區(qū)信息提取中關(guān)注動(dòng)態(tài)結(jié)構(gòu)而非靜態(tài)結(jié)構(gòu),能提高聚合性度量的準(zhǔn)確性并識(shí)別出更有意義的社區(qū)。

本文研究動(dòng)態(tài)加權(quán)圖模型社區(qū)檢測(cè)問題,通過預(yù)測(cè)有影響力的用戶未來的活躍趨勢(shì),構(gòu)建一種影響傳播模型,以確定用戶的高頻率相互作用并度量其對(duì)鄰近用戶的影響。同時(shí),為提高社區(qū)檢測(cè)的準(zhǔn)確率,針對(duì)圖社區(qū)劃分過程引入一個(gè)目標(biāo)函數(shù),并行處理這些分區(qū)劃分過程以求解影響傳播模型。在此基礎(chǔ)上,提出一種時(shí)間交互偏置(TIB)社區(qū)檢測(cè)方法,以對(duì)重疊社區(qū)進(jìn)行檢測(cè)。

1 問題描述

本文研究一個(gè)加權(quán)無向簡(jiǎn)單圖G=(V,E,W),其中,V表示節(jié)點(diǎn)集合,E表示邊緣集合,W是權(quán)函數(shù)集,ω∈W[8-9]。針對(duì)每個(gè)邊e=(u,v)?E,權(quán)重w(e)=∑(IInteractions)≥0表示隨機(jī)選擇的時(shí)間間隔為t的節(jié)點(diǎn)u和v之間相互作用的總頻率。例如,在Twitter數(shù)據(jù)集中,權(quán)重為w(e)=∑(@+IRTs),其表示在給定時(shí)間間隔t內(nèi)交互作用的總和,@表示上一時(shí)刻交互作用總和,IRTs表示當(dāng)前時(shí)刻的交互作用。表1所示為本文相關(guān)數(shù)學(xué)符號(hào)的定義。

表1 數(shù)學(xué)符號(hào)定義

問題1(時(shí)間交互偏置問題) 尋找社區(qū)C(V,E,W)?G,其為k個(gè)連通群落集,使得:1)?e∈E,其中,e是活躍或者半活躍邊;2)活躍偏密度度量指標(biāo)ρ(C)最大化。

為求解連接的k群落約束,首先給出clique的定義:clique是一個(gè)完全連通的子圖,PC是相鄰clique集,這意味著兩者共享k-1個(gè)節(jié)點(diǎn)。例如,對(duì)于k群落,如果k=3可視為三角形,則k=3情形下的PC可以被可視化為連接三角形。

在已有研究中,邊緣的相關(guān)性權(quán)重表示網(wǎng)絡(luò)邊緣的活躍程度。在Twitter網(wǎng)絡(luò)中,邊緣加權(quán)為40,意味著它含有40個(gè)交互過程,并且很可能被視為活躍邊緣。但非活躍邊緣也有可能是重要邊緣,比如其多數(shù)鄰居是高度活躍邊緣的情況。本文定義了一個(gè)鄰居頂點(diǎn)的活躍邊緣,稱為偏置活躍邊緣。在以往研究中,邊緣加權(quán)值3通常認(rèn)為是不活躍的,然而,如果其具有活躍鄰居,則它可能成為偏置的活躍邊緣,因?yàn)樵撨吘墝⑼ㄟ^傳播這些鄰居的權(quán)重來重新定義加權(quán)值。

在檢測(cè)時(shí)間交互偏置的社區(qū)檢測(cè)背景下,可以認(rèn)為弱連接邊非常重要。雖然在當(dāng)前時(shí)間間隔中其影響很小,但是在后續(xù)社區(qū)檢測(cè)過程中,其影響可能被放大,即如果它們的鄰域節(jié)點(diǎn)高度交互,它們可能在一定時(shí)間之后變得活躍。因此,本文提出一種影響傳播模型來解決第1個(gè)約束,即e可以是活躍的或接近活躍的邊緣,它決定邊緣的潛在權(quán)重并重新定義活躍邊緣。

2 時(shí)間交互偏置社區(qū)檢測(cè)傳播模型

考慮圖的每個(gè)邊緣e,本文模型通過2個(gè)步驟確定邊緣的權(quán)重。第1步基于以下標(biāo)準(zhǔn)對(duì)邊緣e的權(quán)重w(e)進(jìn)行歸一化[10-11]:

(1)

其中,0≤N(e)≤1,非零值參數(shù)表示不同的活躍程度。當(dāng)N(e)=1時(shí),表示邊緣的活躍程度為100%。式(1)中的參數(shù)m和n是實(shí)數(shù),且滿足m

定義1(活躍邊緣ei) 當(dāng)N(e)=1時(shí),社區(qū)的邊緣ei稱為活躍邊緣[12]。

定義2(近似活躍邊緣) 活躍邊緣ei在h跳內(nèi)的相鄰邊緣稱為近似活躍邊緣。

本文模型中的第2步是基于活躍邊緣ei向其鄰居節(jié)點(diǎn)e傳播歸一化權(quán)重,過程如下:

U(e)=λh·N(ei)

(2)

其中,λ(0<λ<1)是一個(gè)衰減因子,h是當(dāng)前邊緣和其鄰居節(jié)點(diǎn)之間的跳數(shù),N(ei)是ei活躍鄰居的權(quán)重。對(duì)于邊緣ei的h跳內(nèi)的下鄰域邊緣,重復(fù)計(jì)算U(e),然后,將U(e)的結(jié)果存儲(chǔ)在一個(gè)散列表中,該散列表被用來計(jì)算邊緣e的最終權(quán)重f(e),表示為[13]:

(3)

f(e)將哈希表中的值相乘,以確定邊緣e的新權(quán)重。

該學(xué)習(xí)模型考慮邊緣的鄰居節(jié)點(diǎn),有助于基于鄰居的活躍度來重新定義邊緣權(quán)重。此外,通過非活躍邊緣的相鄰邊緣權(quán)重來計(jì)算時(shí)間交互的邊緣權(quán)重,因此,其不僅考慮當(dāng)前時(shí)間間隔,而且關(guān)注相鄰邊緣的影響概率。

示例1考慮圖1所示的具體示例,其中,線上數(shù)字表示權(quán)重,方框中數(shù)字表示歸一化權(quán)重。圖1(a)所示為原始加權(quán)圖。利用N(e)從0到1重新定義權(quán)重,當(dāng)執(zhí)行式(3)(?e∈E∧N(e)≠1)時(shí),將結(jié)果存儲(chǔ)在哈希表中,如圖1(b)所示,此處省略了一些細(xì)節(jié)以避免混亂。使用哈希表來計(jì)算每個(gè)邊的最終權(quán)重,如圖1(c)所示,其中,采用f(e)進(jìn)行計(jì)算。本文考慮k群落的基本定義以檢測(cè)重疊社區(qū)。

圖1 權(quán)重賦值示例

定義3(活躍偏置密度) 活躍偏置社區(qū)的密度指標(biāo)可表示為:

(4)

活躍偏置社區(qū)的密度為社區(qū)內(nèi)權(quán)重的總和除以社區(qū)的大小|C|,可基于閾值限制群落來評(píng)估社區(qū)的質(zhì)量。因此,基于C群落可進(jìn)行社區(qū)發(fā)現(xiàn),其中,ρ(C)可實(shí)現(xiàn)最大化。

示例2考慮圖2所示的示例,設(shè)有一個(gè)重構(gòu)的加權(quán)圖,在圖中找到所有的群落并利用式(4)計(jì)算它們的偏置密度值。然后,利用式(4)計(jì)算PCs的偏置密度值,結(jié)果如圖中線上數(shù)字。PCs僅在其偏置密度得分高于每個(gè)社區(qū)的偏置密度分?jǐn)?shù)時(shí)形成一個(gè)社區(qū);否則,每個(gè)群落本身就是社區(qū)。圖2給出2種情況:左側(cè)的2個(gè)PCs在聯(lián)合時(shí)具有較小的密度值,右側(cè)部分是交互作用情況。顏色深淺表示密度值大小。

圖2 社區(qū)偏置密度值

問題2(基于群落的圖劃分) 查找社區(qū)集R,其中,?r∈R包含2個(gè)約束:1)節(jié)點(diǎn)和邊屬于群落結(jié)構(gòu);2)分布在處理器組(P)上的均衡數(shù)據(jù)(節(jié)點(diǎn)和邊緣)負(fù)載。

上述問題中的第2個(gè)約束是對(duì)處理器上的分區(qū)進(jìn)行平衡,并確保每個(gè)處理器具有可接受的數(shù)據(jù)量。該問題是NP難問題,可采用啟發(fā)式算法進(jìn)行求解。本文分配每個(gè)PC到一個(gè)分區(qū),分區(qū)數(shù)量等于處理器的數(shù)量,每個(gè)分區(qū)將被分配給處理器。

定義4(目標(biāo)函數(shù)J) 如果滿足如下3個(gè)條件,可將PCs均勻分配到可用分區(qū):1)分區(qū)R的數(shù)量大于處理器P的數(shù)量,即R≥P;2)每個(gè)分區(qū)r∈R?G具有幾乎相同數(shù)量的PCs;3)目標(biāo)函數(shù)J取值最小。

為滿足上述3個(gè)條件,為每個(gè)未賦值的參數(shù)pc∈PCs進(jìn)行如下的賦值計(jì)算:

(5)

(6)

(7)

示例3考慮圖3(a)所示的示例。為對(duì)該圖進(jìn)行分割,首先找到群落然后查找PCs,其中,PCs見圖3(b)虛線部分所示。假定處理器數(shù)量P=2,需要2個(gè)分區(qū),每個(gè)處理器分配一個(gè)分區(qū)。為將3個(gè)PCs盡可能均勻地劃分為2個(gè)分區(qū),需要計(jì)算目標(biāo)函數(shù)J。首先將PC1分配給分區(qū)1,將PC2分配給分區(qū)2,而對(duì)于PC3的分配,將根據(jù)目標(biāo)函數(shù)J的取值進(jìn)行設(shè)置。當(dāng)添加PC3到分區(qū)1中的PC1時(shí),目標(biāo)函數(shù)J的計(jì)算結(jié)果為54。當(dāng)添加PC3到分區(qū)2中的PC2時(shí),目標(biāo)函數(shù)J的計(jì)算結(jié)果為44?；谠撚?jì)算結(jié)果,PC3的分區(qū)方式將采取后一種情形,將其分配給處理器2。

圖3 PCs圖分割過程示例

3 算法框架

圖4所示為本文算法框架,該算法分為3個(gè)階段:1)基于PCs和目標(biāo)函數(shù)J進(jìn)行圖分割,此處不屬于群落的節(jié)點(diǎn)和邊緣將被消除;2)計(jì)算每個(gè)分區(qū)的影響傳播模型;3)利用TIB社區(qū)檢測(cè)方法檢測(cè)社區(qū)。算法開始時(shí),輸入社區(qū)檢測(cè)的圖模型G=(V,E,W),并給定處理器的數(shù)量,輸出是社區(qū)劃分集。

圖4 本文算法框架

本文社區(qū)檢測(cè)算法各階段的詳細(xì)過程如下:

1)圖分割,該過程的計(jì)算步驟如算法1所示。算法輸入是無向加權(quán)圖、鄰域跳數(shù)以及處理器P的數(shù)目。首先,查找群落(第1行)和PCs(第2行)。然后,收集PCs中每個(gè)邊緣h跳范圍內(nèi)的鄰域節(jié)點(diǎn)(第3行～第7行),以計(jì)算影響傳播模型。接著,分配一些PCs到分區(qū),如果有6個(gè)分區(qū),則分配6個(gè)PCs(第9行)。隨后,基于目標(biāo)函數(shù)J的計(jì)算結(jié)果,將剩余的PCs分配到分區(qū)中(第10行～第13行)。當(dāng)所有PCs在分區(qū)上被平均分配時(shí),算法的分區(qū)劃分過程結(jié)束(第14行～第15行)。

算法1圖分割算法

1.輸入:G(V,E,W),hops,P

2.C←FindCliques(G);

3.PC←FindPercolatedCliques(C);

4.h←1;

5.for e∈PCand h

6.NP←FindNeighbours(e);

7.h←h+1;

8.end for

9.repeat

10.將n個(gè)PCs分配給n個(gè)處理器Ps;

11.if PCi未賦值給Pithen

12.J(Pi,PCi+n);

13.將具有最低評(píng)估值的PCi賦值給Pi;

14.end if

15.until 所有PCs賦值給Pi;

16.return P集合

算法2影響傳播模型計(jì)算算法

1.輸入:集合P

3.for all e∈E do

4.P(e)←w(e);

5.end for

6.for 所有e滿足P(e)<1 do

7.h←1,N←{ }HashTable={ };

8.while h<4 do

9.N←FindNeighbours(e);

10.HashTable←U(e);

11.h←h+1;

12.end while;

13.end for

14.for all U(e)∈HashTable do

16.end for

3)TIB群落檢測(cè)。該過程計(jì)算算法輸入為社區(qū)圖模型G=(V,E,W),算法基于連通群落識(shí)別重疊的社區(qū)結(jié)構(gòu)。如圖2(a)所示,首先獲得一組不能進(jìn)一步擴(kuò)展到超出大小k的所有最大群落。在文獻(xiàn)[10]中,考慮共享k-1個(gè)節(jié)點(diǎn)的所有相鄰群落,群落選取的標(biāo)準(zhǔn)是密度指標(biāo)I(G)大于閾值θ,I(G)計(jì)算如下:

(8)

該函數(shù)允許k群落包含比閾值弱的連接,因此,所產(chǎn)生的社區(qū)包含強(qiáng)度大于I的k群落。

TIB群落檢測(cè)的計(jì)算過程如算法3所示。本文采用前述ρ(C)指標(biāo)替代I(G)進(jìn)行算法設(shè)計(jì),偏置密度測(cè)量指標(biāo)可找到不一定相連的TIB社區(qū)群落。然后,計(jì)算PCs的密度值ρ(C)并作為最大可達(dá)的k群落(第3行～第8行)。同時(shí),計(jì)算ρ(pli),?pli∈PL,通過密度比對(duì)確定最終的TIB社區(qū)識(shí)別結(jié)果(第9行～第17行)。

算法3TIB群落檢測(cè)算法

2.CL←{ },PL←{ };

3.CL←FindClique(G,k);

4.for all cli∈CLdo

5.D←ρ(cli);

6.if cli∪cl(i+1)do

7.PL[pli]←cli∪cl(i+1);

8.D←ρ(pli);

9.end if

10.for all cli∈pcido

11.if D[pli]≥D[cli]do

12.C←pli;

13.else

14.C←cli,cl(i+1);

15.end if

16.end for

17.end for

18.return TIB社區(qū)集C={C0,C1,…}

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

本文選取的社區(qū)檢測(cè)質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)為標(biāo)準(zhǔn)化互信息(NMI)評(píng)價(jià)指標(biāo)和F1評(píng)估指標(biāo)。NMI可評(píng)估檢測(cè)社區(qū)的相似性,F1可對(duì)社區(qū)檢測(cè)精度進(jìn)行評(píng)估。

4.1 實(shí)驗(yàn)對(duì)象生成

本文選取的實(shí)驗(yàn)對(duì)象生成方法是MMSB和LFR,具體生成策略可見文獻(xiàn)[14]。根據(jù)網(wǎng)絡(luò)參數(shù)的設(shè)定,對(duì)生成網(wǎng)絡(luò)的稀疏程度進(jìn)行調(diào)整,以獲得不同特性的網(wǎng)絡(luò),具體如下:

1)MMSB對(duì)象生成方法:該社區(qū)生成方法的基礎(chǔ)是概率理論,得到p和q間的社區(qū)連接,其具有Y(p,q)分布特性[15]:

(9)

其中,參數(shù)β為社區(qū)檢測(cè)過程中所使用的交互矩陣,Z為社區(qū)檢測(cè)過程中所呈現(xiàn)出的分布形式,其具有多項(xiàng)式特性[16]:

(10)

(11)

其中,參數(shù)α的作用是對(duì)生成模型社區(qū)的重疊度進(jìn)行控制。根據(jù)實(shí)驗(yàn)結(jié)果,如果要獲得稀疏的重疊社區(qū)網(wǎng)絡(luò)模型,可將模塊度指標(biāo)調(diào)整為大于等于0.5;反之,如果要獲得稠密的重疊社區(qū)網(wǎng)絡(luò)模型,可將模塊度指標(biāo)調(diào)整為小于0.5。表2所示為采用MMSB方法生成的網(wǎng)絡(luò)實(shí)驗(yàn)對(duì)象的屬性數(shù)據(jù)。

表2 采用MMSB方法生成的網(wǎng)絡(luò)對(duì)象屬性

2)LFR對(duì)象生成方法:該社區(qū)網(wǎng)絡(luò)生成方法同MMSB對(duì)象生成方法相似,可基于模塊度參數(shù)的設(shè)置控制社區(qū)網(wǎng)絡(luò)模型的稀疏度,其參數(shù)設(shè)定如表3所示。

表3 采用LFR方法生成的網(wǎng)絡(luò)對(duì)象屬性

圖5所示為實(shí)驗(yàn)對(duì)象模型結(jié)構(gòu),其中,圖5(a)、圖5(b)分別對(duì)應(yīng)表2的第1行和表3的第3行參數(shù)。

圖5 實(shí)驗(yàn)對(duì)象模型結(jié)構(gòu)

4.2 穩(wěn)定性對(duì)比結(jié)果

利用F1評(píng)價(jià)指標(biāo)對(duì)社區(qū)發(fā)現(xiàn)過程進(jìn)行質(zhì)量評(píng)估,其指標(biāo)形式為[17-18]:

(12)

其中,參數(shù)FP是真實(shí)網(wǎng)絡(luò)中為正值但社區(qū)檢測(cè)結(jié)果為負(fù)值的比例,參數(shù)FN是真實(shí)網(wǎng)絡(luò)中為負(fù)值但社區(qū)檢測(cè)結(jié)果為正值的比例,參數(shù)TP是真實(shí)網(wǎng)絡(luò)中為正值且社區(qū)檢測(cè)結(jié)果為正值的比例,P表示社區(qū)檢測(cè)的準(zhǔn)確率,R表示社區(qū)檢測(cè)的召回率。

為驗(yàn)證算法的有效性,本文選取文獻(xiàn)[19-20]中的2種重疊社區(qū)檢測(cè)算法作為對(duì)比。F1評(píng)估指標(biāo)實(shí)驗(yàn)結(jié)果如圖6所示。在通常情況下,F1評(píng)估結(jié)果取值區(qū)間在0～1之間,該指標(biāo)取值越大,表明算法的穩(wěn)定性越高。從圖6可以看出,本文算法的F1值優(yōu)于文獻(xiàn)[19-20]2種對(duì)比算法,這表明本文算法的社區(qū)檢測(cè)穩(wěn)定性更優(yōu)。同時(shí),在F1評(píng)估實(shí)驗(yàn)結(jié)果的變化趨勢(shì)上,3種對(duì)比算法均隨著社區(qū)數(shù)量的增加而呈現(xiàn)出逐漸降低的趨勢(shì),這說明3種算法在進(jìn)行社區(qū)檢測(cè)的過程中,其穩(wěn)定性與社區(qū)數(shù)量存在一定的關(guān)聯(lián)性,社區(qū)數(shù)量越多,算法穩(wěn)定性越差。

圖6 3種算法的F1測(cè)試結(jié)果對(duì)比

4.3 準(zhǔn)確性對(duì)比結(jié)果

對(duì)算法的社區(qū)檢測(cè)準(zhǔn)確性進(jìn)行實(shí)驗(yàn)分析,選取NMI作為評(píng)估指標(biāo)。對(duì)于社區(qū)A和B,NMI具體定義為:

(13)

其中,參數(shù)N表示社區(qū)檢測(cè)網(wǎng)絡(luò)中的頂點(diǎn)數(shù),參數(shù)C表示社區(qū)檢測(cè)模型所形成的混淆參數(shù)矩陣,Ci表示i頂點(diǎn)所在社區(qū)檢測(cè)模型形成的混淆參數(shù)矩陣，Cj表示j頂點(diǎn)所在社區(qū)檢測(cè)模型形成的混淆參數(shù)矩陣，參數(shù)Ci.(C.j)表示矩陣C中頂點(diǎn)數(shù)之和，參數(shù)Cij表示同時(shí)屬于不同類型社區(qū)的頂點(diǎn)數(shù)。CA和CB是社區(qū)劃分?jǐn)?shù)量。NMI值越大,表示社區(qū)相似度越高。仍然選取文獻(xiàn)[19-20]中的2種重疊社區(qū)檢測(cè)算法作為對(duì)比,實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 3種算法的NMI測(cè)試結(jié)果對(duì)比

從圖7可以看出,隨著網(wǎng)絡(luò)頂點(diǎn)數(shù)量的增加,3種算法的社區(qū)識(shí)別精度均呈現(xiàn)出下降的趨勢(shì)。對(duì)于相同規(guī)模的網(wǎng)絡(luò),網(wǎng)絡(luò)越緊密表示網(wǎng)絡(luò)的重疊情況越嚴(yán)重,本文算法NMI精度雖然隨著頂點(diǎn)數(shù)量的增加而下降,但是降低的幅度不大,即該算法的社區(qū)檢測(cè)精度和穩(wěn)定性更強(qiáng)。

4.4 真實(shí)社區(qū)網(wǎng)絡(luò)檢測(cè)結(jié)果

利用API網(wǎng)絡(luò)數(shù)據(jù)爬取工具進(jìn)行真實(shí)數(shù)據(jù)集構(gòu)建,數(shù)據(jù)采集平臺(tái)為新浪微博,在網(wǎng)絡(luò)中設(shè)定一定量的種子賬戶,獲取網(wǎng)絡(luò)的數(shù)據(jù)特征,具體過程為:1)選取5個(gè)相鄰的賬戶作為種子賬戶;2)基于深度搜索策略對(duì)新浪微博中的相鄰頂點(diǎn)進(jìn)行關(guān)注主題的抓取;3)基于基準(zhǔn)網(wǎng)絡(luò)對(duì)抓取過程中的參數(shù)進(jìn)行調(diào)整。

通過上述數(shù)據(jù)抓取過程構(gòu)建的新浪微博網(wǎng)絡(luò)主題為78組,頂點(diǎn)為900個(gè),微博數(shù)據(jù)交互信息為5萬多條。實(shí)驗(yàn)程序選取Java語言進(jìn)行模型構(gòu)建,對(duì)比算法仍然選取文獻(xiàn)[19-20]中的2種重疊社區(qū)檢測(cè)算法,算法性能的評(píng)價(jià)指標(biāo)為準(zhǔn)確率、召回率及F1值。

對(duì)于由網(wǎng)絡(luò)數(shù)據(jù)爬取工具獲得的新浪微博數(shù)據(jù),其邊緣數(shù)高度依賴于數(shù)據(jù)爬取的稀疏度,文獻(xiàn)[19-20]算法以及本文算法對(duì)所抓取數(shù)據(jù)的檢測(cè)結(jié)果如圖8所示。

圖8 3種算法對(duì)新浪微博數(shù)據(jù)的檢測(cè)結(jié)果對(duì)比

從圖8可以看出,在低密度社區(qū)檢測(cè)情況下,3種算法的檢測(cè)結(jié)果差別不大,特別是和文獻(xiàn)[20]算法相比,本文算法優(yōu)勢(shì)并不明顯。但是,隨著社區(qū)稀疏度的增加,社區(qū)之間的重疊和交互程度提升,本文算法因?yàn)榭紤]到了弱連接重疊社區(qū)的時(shí)間交互偏置影響傳播問題,所以其綜合性能上升速度較快,而文獻(xiàn)[19-20]算法性能變化幅度較小。上述實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法在社區(qū)發(fā)現(xiàn)上的性能優(yōu)勢(shì)。

5 結(jié)束語

為提高弱連接重疊社區(qū)的檢測(cè)識(shí)別準(zhǔn)確率,本文提出一種基于時(shí)間交互偏置影響傳播模型的社區(qū)檢測(cè)算法。通過設(shè)計(jì)圖分割問題的目標(biāo)函數(shù)對(duì)計(jì)算資源進(jìn)行均衡優(yōu)化，同時(shí)構(gòu)建一種影響傳播模型，以提高對(duì)弱連接用戶的識(shí)別能力，實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法良好的社區(qū)檢測(cè)性能。下一步將對(duì)用戶交互過程中的時(shí)間間隔模型進(jìn)行研究,結(jié)合影響傳播模型和時(shí)間間隔參數(shù),以提高密集活躍社區(qū)的檢測(cè)識(shí)別性能。