胡北辰

(安徽電子信息職業(yè)技術(shù)學(xué)院，安徽蚌埠 233000)

移動通信網(wǎng)絡(luò)、淘寶等電子商務(wù)網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等都有一個特性，即它們都是動態(tài)的。根據(jù)eMarketer的最新統(tǒng)計預(yù)測，2017年，80%的中國網(wǎng)民經(jīng)常訪問社交網(wǎng)絡(luò)，大概為6.62億人，其中4.83億網(wǎng)民常用手機訪問社交媒體。如此龐大的網(wǎng)絡(luò)結(jié)構(gòu)已經(jīng)很難憑直觀來挖掘有用的信息，社區(qū)發(fā)現(xiàn)算法能夠?qū)ι鐓^(qū)內(nèi)某些具有共性的信息特征進行分析，使得人們能夠更好地利用社區(qū)發(fā)現(xiàn)研究結(jié)果，例如，在疾病控制中心網(wǎng)中，可以根據(jù)社區(qū)結(jié)構(gòu)有針對性地加強對疫苗的控制，從而降低成本。

1 經(jīng)典動態(tài)社區(qū)發(fā)現(xiàn)算法

1.1 GraphScope算法

GraphScope算法[1-3]，是通過合并不同時間片的圖結(jié)構(gòu)從而獲取到新圖，并對生成的新圖應(yīng)用社區(qū)發(fā)現(xiàn)。算法的具體過程：判斷新的時間片是否為改變點，若是則開始新的時間片并單獨進行發(fā)現(xiàn)社區(qū)，且不對網(wǎng)絡(luò)的變化進行關(guān)注；若不是則合并當前時刻和該時間的圖結(jié)構(gòu)來獲取新的圖，并在新圖中應(yīng)用社區(qū)發(fā)現(xiàn)算法，合并后的新圖擁有網(wǎng)絡(luò)變化的各時刻信息，同時會持續(xù)考慮網(wǎng)絡(luò)的動態(tài)變化情況。

1.2 FaceNet算法

FaceNet算法[4-6]，是當前時間片t執(zhí)行社區(qū)發(fā)現(xiàn)算法，隨之根據(jù)t-1時刻來調(diào)整時間t的社區(qū)結(jié)構(gòu)。該算法分為兩個步驟：首先對當前時間片執(zhí)行社區(qū)發(fā)現(xiàn)算法；應(yīng)用極值優(yōu)化方法調(diào)整t時刻社區(qū)結(jié)構(gòu)，將社區(qū)結(jié)構(gòu)劃分成二分圖，得到節(jié)點相似度矩陣，最終社區(qū)發(fā)現(xiàn)算法轉(zhuǎn)化為最小化cost目標函數(shù)問題。

1.3 QCA算法

QCA算法[7-8]，是經(jīng)典的自適應(yīng)增量式處理網(wǎng)絡(luò)動態(tài)變化的方法，其t時刻的社區(qū)結(jié)構(gòu)是基于上一時刻t-1和t時刻兩者之間的網(wǎng)絡(luò)變化而演化生成的。

2 QCA算法的優(yōu)化

GraphScope算法和FaceNet算法在每一個時間片都需更新網(wǎng)絡(luò)圖和重新劃分社區(qū)，但一般情況下相鄰的社區(qū)不會發(fā)生很大的變化，因此這些算法會造成社區(qū)劃分計算時間過長。QCA算法應(yīng)用的是時間片遞增變化處理方法，僅對變化的網(wǎng)絡(luò)部分進行計算，因此可以提高算法的效率，但會降低算法的準確率。因此接下來將對QCA算法進行優(yōu)化。

2.1 符號定義

定義社會網(wǎng)絡(luò)是無向圖G=〈V,E〉，V={v1,v2,…,vn}是網(wǎng)絡(luò)節(jié)點集，vi表示i節(jié)點；E={eij|vi,vj∈V,i≠j}是網(wǎng)絡(luò)邊集。社區(qū)結(jié)構(gòu)為C=C1∪C2∪…∪Ci，i=1,2,…,k，Ci表示i社區(qū)。由于動態(tài)網(wǎng)絡(luò)任一時刻都在變化，因此定義Gt為t時刻的社會網(wǎng)絡(luò)，Ct為t時刻的社區(qū)結(jié)構(gòu)。

下面首先定義相關(guān)的概念：

網(wǎng)絡(luò)節(jié)點vi在Ck的t時刻：Not(vi)=Ck；

當網(wǎng)絡(luò)節(jié)點vi所在的社區(qū)條件發(fā)生了變化時，ε是用戶定義的menAmount(vi,Cq)比例值：menAmount(vi,Cq)-menAmount(vi,Cp)≥ε.

2.2 QCA優(yōu)化

假設(shè)在動態(tài)網(wǎng)絡(luò)的變化過程中，若相鄰的時間片段變化差異較小則表示僅有少量的網(wǎng)絡(luò)節(jié)點需要重新計算社區(qū)劃分。本文著重研究相鄰社區(qū)的節(jié)點變化，并根據(jù)時間片段的前后變化來計算時刻t的社區(qū)結(jié)構(gòu)。

2.2.1 增加邊

在t時間段，首先在動態(tài)網(wǎng)絡(luò)節(jié)點a、b中間添加一條邊，且Not-1(a)=Cq,Not-1(b)=Cq，接下來討論添加的邊對各節(jié)點的影響。

(1)p=q表示節(jié)點a、b在同一社區(qū)，和其它的社區(qū)沒有連接，且不會對節(jié)點所屬社區(qū)產(chǎn)生影響，但應(yīng)加強節(jié)點間的聯(lián)系來提高緊密性。

(2)p≠q表示節(jié)點a、b屬于不同社區(qū)。接下來進一步分析節(jié)點能否改變社區(qū)的劃分：

Amount(a)=Amount(a)+1;Amount(b)=Amount(b)+1;Amount(a,Cq)=Amount(a,Cq)+1，通過節(jié)點更新比例值來判斷節(jié)點a從Cp轉(zhuǎn)移到Cq的可能性；

(3)若menAmount(a,Cq)-menAmount(a,Cp)<ε，則節(jié)點a不可能轉(zhuǎn)移到Cq，即接下來討論節(jié)點b的可能性：①若Amount(b,Cp)=Amount(b,Cp)+1，則需要看節(jié)點b轉(zhuǎn)移到Cp的可能性；②若menAmount(a,Cq)-menAmount(a,Cp)<ε，則結(jié)束當前操作，節(jié)點b無法進行移動；③若menAmount(a,Cq)-menAmount(a,Cp)≥ε，則將節(jié)點b轉(zhuǎn)移到Cp，并更新相鄰節(jié)點。

2.2.2 刪除邊

若動態(tài)網(wǎng)絡(luò)中，在t時間段，邊eab將被刪除，接下來討論添加的邊對各節(jié)點的影響。

(1)p≠q表示節(jié)點a、b屬于不同社區(qū)，刪除節(jié)點a、b之間的邊不會改變社區(qū)，會降低社區(qū)間的耦合度，因此僅需更新參數(shù)即可。

(2)p=q表示節(jié)點a、b為同一社區(qū)。①刪除節(jié)點a、b之間的邊后，節(jié)點a、b分別會成為獨立的社區(qū)，則變化過程為：Amount(a)=Amount(a)-1;Amount(a,Cq)=Amount(a,Cq)-1,Amount(b)=Amount(b)-1;Amount(b,Cq)=Amount(b,Cq)-1.C=C∪Ck,Not(a)=Ck，同時更新節(jié)點b的社區(qū)值，若有某社區(qū)Ci符合menAmount(b,Ci)-menAmount(n,Cp)≥ε，則更新節(jié)點b的相鄰信息。②刪除節(jié)點a、b之間的邊后，并沒有形成社區(qū)，因此需重新計算節(jié)點a、b的權(quán)值來確定它們的歸屬。判斷節(jié)點a是否滿足移動要求，若menAmount(a,Cq)-menAmount(a,Cp)≥ε，則更新相鄰的節(jié)點，否則對節(jié)點b進行判斷，若menAmount(b,Cq)-menAmount(b,Cp)≥ε，則更新相鄰的節(jié)點。

2.2.3 添加點

若設(shè)在t+1時刻時，在動態(tài)網(wǎng)絡(luò)中插入節(jié)點v，接下來探討兩種情況：

(1)節(jié)點v不與任何社區(qū)相連，則將節(jié)點v設(shè)置為社區(qū)Ck，且E不變，需要進行如下計算：V=V∪v;C=C∪Ck。

(2)節(jié)點v和某一個或多個社區(qū)中的一個或多個節(jié)點相連。在添加節(jié)點v之前，需要計算節(jié)點v原來社區(qū)的權(quán)重值，若Amount(v,Ck)為最大值，則v∈Ck。若網(wǎng)絡(luò)中的總社區(qū)不變，則設(shè)w為v的任一連接節(jié)點，需要進行如下計算：V=V∪v;E=E∪evw。

2.2.4 刪除點

若設(shè)在t+1時刻時，在動態(tài)網(wǎng)絡(luò)中刪除節(jié)點v，接下來將探討兩種情況：

(1)節(jié)點v不與任何社區(qū)相連，即?w∈V,?evw?E，則將節(jié)點v設(shè)置為社區(qū)Ck，且E不變，需要進行如下計算：V=V-v;C=C-Ck。

(2)節(jié)點v和某一個或多個社區(qū)中的一個或多個節(jié)點相連，則?w∈V,?evw∈E。若網(wǎng)絡(luò)中的總社區(qū)不變，設(shè)w為v的任一連接節(jié)點，需要進行如下計算：V=V-v;E=E-evw。

3 實驗結(jié)果分析

將真實的網(wǎng)絡(luò)結(jié)構(gòu)作為研究對象，收集動態(tài)網(wǎng)絡(luò)中電子郵件的發(fā)送情況，時間為不同的10個時間段，相鄰的時刻網(wǎng)絡(luò)變化極少。通過文獻[9-10]分析可知，當ε=0.1時，社區(qū)結(jié)構(gòu)的穩(wěn)定性和社區(qū)特征能夠達到很好的效果。

將動態(tài)網(wǎng)絡(luò)靜態(tài)化，采用GN算法將社區(qū)劃分為10個時間的靜態(tài)網(wǎng)絡(luò)，劃分后的社區(qū)結(jié)果如表1所示。

表1 GN社區(qū)劃分表

采用優(yōu)化后的QCA算法與經(jīng)典的GraphScope算法和FaceNet算法比較社區(qū)劃分情況(表2、表3、表4)。

表2 GraphScope算法社區(qū)劃分表

表3 NetFace算法社區(qū)劃分表

表4 優(yōu)化后的QCA算法社區(qū)劃分表

T=9時刻，GraphScope算法的社區(qū)劃分分別為：[6，9，13，15]，[3，7，8，11，12]，[1，2，4，5，10，14]；NetFace算法的社區(qū)劃分分別為：[6，9，15]，[3，7，8，11，12]，[1，2，4，5，10，13，14]；優(yōu)化后的QCA算法的社區(qū)劃分分別為：[6，9，13，15]，[3，7，8，11，12]，[1，2，4，5，10，13]。這表明不同的算法劃分的社區(qū)是不同的。

運用社區(qū)結(jié)構(gòu)質(zhì)量、準確率、平均時間來直觀地比較各種算法，如表5所示。采用優(yōu)化后的QCA算法能夠得到較好的社區(qū)結(jié)構(gòu)質(zhì)量、較好的準確率和更少的平均時間。

表5 三種算法比較

4 結(jié)語

本文對動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法進行研究。首先對經(jīng)典的社區(qū)發(fā)現(xiàn)算法進行簡單的介紹，并對經(jīng)典的OCA算法進行優(yōu)化，優(yōu)化后的社區(qū)劃分結(jié)構(gòu)質(zhì)量更佳、準確率較好、計算時間更少。但由于動態(tài)網(wǎng)絡(luò)的多樣性，還需對算法作進一步的適應(yīng)性研究。