許小媛,黃 黎,李海波

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

0 概述

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

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

(2)

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

(3)

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

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

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

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

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

(4)

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

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

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

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

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

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

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

(5)

(6)

(7)

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

圖3 PCs圖分割過程示例

3 算法框架

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

圖4 本文算法框架

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

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

11.if PCi未賦值給Pithen

12.J(Pi,PCi+n);

13.將具有最低評估值的PCi賦值給Pi;

14.end if

15.until 所有PCs賦值給Pi;

16.return P集合

算法2影響傳播模型計算算法

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群落檢測。該過程計算算法輸入為社區(qū)圖模型G=(V,E,W),算法基于連通群落識別重疊的社區(qū)結(jié)構(gòu)。如圖2(a)所示,首先獲得一組不能進一步擴展到超出大小k的所有最大群落。在文獻[10]中,考慮共享k-1個節(jié)點的所有相鄰群落,群落選取的標準是密度指標I(G)大于閾值θ,I(G)計算如下:

(8)

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

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

算法3TIB群落檢測算法

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 實驗結(jié)果與分析

本文選取的社區(qū)檢測質(zhì)量評價標準為標準化互信息(NMI)評價指標和F1評估指標。NMI可評估檢測社區(qū)的相似性,F1可對社區(qū)檢測精度進行評估。

4.1 實驗對象生成

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

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

(9)

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

(10)

(11)

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

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

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

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

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

圖5 實驗對象模型結(jié)構(gòu)

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

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

(12)

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

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

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

4.3 準確性對比結(jié)果

對算法的社區(qū)檢測準確性進行實驗分析,選取NMI作為評估指標。對于社區(qū)A和B,NMI具體定義為:

(13)

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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