胡北辰

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

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

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

1.1 GraphScope算法

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

1.2 FaceNet算法

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

1.3 QCA算法

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

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

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

2.1 符號定義

定義社會網(wǎng)絡(luò)是無向圖G=〈V,E〉，V={v1,v2,…,vn}是網(wǎng)絡(luò)節(jié)點(diǎn)集，vi表示i節(jié)點(diǎn)；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ū)。由于動(dòng)態(tài)網(wǎng)絡(luò)任一時(shí)刻都在變化，因此定義Gt為t時(shí)刻的社會網(wǎng)絡(luò)，Ct為t時(shí)刻的社區(qū)結(jié)構(gòu)。

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

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

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

2.2 QCA優(yōu)化

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

2.2.1 增加邊

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

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

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

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

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

2.2.2 刪除邊

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

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

(2)p=q表示節(jié)點(diǎn)a、b為同一社區(qū)。①刪除節(jié)點(diǎn)a、b之間的邊后，節(jié)點(diǎn)a、b分別會成為獨(dú)立的社區(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，同時(shí)更新節(jié)點(diǎn)b的社區(qū)值，若有某社區(qū)Ci符合menAmount(b,Ci)-menAmount(n,Cp)≥ε，則更新節(jié)點(diǎn)b的相鄰信息。②刪除節(jié)點(diǎn)a、b之間的邊后，并沒有形成社區(qū)，因此需重新計(jì)算節(jié)點(diǎn)a、b的權(quán)值來確定它們的歸屬。判斷節(jié)點(diǎn)a是否滿足移動(dòng)要求，若menAmount(a,Cq)-menAmount(a,Cp)≥ε，則更新相鄰的節(jié)點(diǎn)，否則對節(jié)點(diǎn)b進(jìn)行判斷，若menAmount(b,Cq)-menAmount(b,Cp)≥ε，則更新相鄰的節(jié)點(diǎn)。

2.2.3 添加點(diǎn)

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

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

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

2.2.4 刪除點(diǎn)

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

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

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

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

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

將動(dòng)態(tài)網(wǎng)絡(luò)靜態(tài)化，采用GN算法將社區(qū)劃分為10個(gè)時(shí)間的靜態(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時(shí)刻，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ū)是不同的。

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

表5 三種算法比較

4 結(jié)語

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