動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)研究綜述

李永寧，吳 曄，張 倫

(北京師范大學(xué) a.系統(tǒng)科學(xué)學(xué)院，北京 100875；b.計(jì)算傳播學(xué)研究中心，廣東 珠海 519085；c.新聞傳播學(xué)院，北京 100875； d.藝術(shù)與傳媒學(xué)院，北京 100875)

0 引言

社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的拓?fù)涮匦灾?，發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)研究的基礎(chǔ)性問題[1-2]。社團(tuán)結(jié)構(gòu)作為介于宏觀網(wǎng)絡(luò)和微觀個(gè)體之間的中觀結(jié)構(gòu)，網(wǎng)絡(luò)在社團(tuán)層面所具有的特性是網(wǎng)絡(luò)層面的特性所不能替代的，忽視社團(tuán)結(jié)構(gòu)可能會(huì)遺漏很多網(wǎng)絡(luò)特征[3]。

隨著復(fù)雜網(wǎng)絡(luò)研究的發(fā)展，越來越多的領(lǐng)域借助網(wǎng)絡(luò)分析的方式探究網(wǎng)絡(luò)的結(jié)構(gòu)與性能之間的關(guān)聯(lián)[4-5]。早期的網(wǎng)絡(luò)分析方法將網(wǎng)絡(luò)觀察數(shù)據(jù)進(jìn)行疊加以發(fā)現(xiàn)靜態(tài)社團(tuán)結(jié)構(gòu)，這種做法雖然可以識(shí)別社團(tuán)特征，但是節(jié)點(diǎn)和邊隨時(shí)間變化的信息被忽略，無(wú)法發(fā)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)演化過程。近年來，隨著大型社交網(wǎng)絡(luò)的興起和網(wǎng)絡(luò)數(shù)據(jù)可得性的增強(qiáng)，動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)及演化研究成為當(dāng)前在線社會(huì)網(wǎng)絡(luò)研究的熱點(diǎn)。社團(tuán)作為動(dòng)態(tài)網(wǎng)絡(luò)分析的重要基礎(chǔ)結(jié)構(gòu)，關(guān)注動(dòng)態(tài)網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)問題及社團(tuán)演化機(jī)制，在信息傳播、影響力研究、網(wǎng)絡(luò)群體事件等研究中都能提供新的分析視角。實(shí)際科研工作也表明，在電子商務(wù)、輿情傳播、知識(shí)傳播等多個(gè)領(lǐng)域，動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)研究的可應(yīng)用性不斷加強(qiáng)[6]，動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)與演化等問題將成為復(fù)雜網(wǎng)絡(luò)分析的重要關(guān)注點(diǎn)之一。

1 社團(tuán)發(fā)現(xiàn)

通常認(rèn)為，社團(tuán)結(jié)構(gòu)是指網(wǎng)絡(luò)中的節(jié)點(diǎn)可以被劃分為多個(gè)分組，組內(nèi)節(jié)點(diǎn)連邊相對(duì)緊密，組間節(jié)點(diǎn)連邊相對(duì)稀疏[7]。社團(tuán)發(fā)現(xiàn)是識(shí)別網(wǎng)絡(luò)中節(jié)點(diǎn)群組關(guān)系的過程，社團(tuán)發(fā)現(xiàn)往往能夠揭示網(wǎng)絡(luò)更深層次的特征，為理解網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu)和生成機(jī)制提供了極具意義的研究視角[8]。

2002年GN算法[7]提出，引起了社團(tuán)發(fā)現(xiàn)研究的熱潮，來自生物、物理、計(jì)算機(jī)等多個(gè)學(xué)科的學(xué)者為社團(tuán)發(fā)現(xiàn)算法提供了不同的思路，并將社團(tuán)發(fā)現(xiàn)算法應(yīng)用于各個(gè)領(lǐng)域。許多學(xué)者對(duì)社團(tuán)發(fā)現(xiàn)算法進(jìn)行了歸納和整理[9-11]，1)按照社團(tuán)劃分的出發(fā)點(diǎn)將算法歸納為三類，基于全局的劃分[3,12]，基于節(jié)點(diǎn)相似性的劃分[13]，和基于局部的劃分[14]；2)按照社團(tuán)結(jié)構(gòu)的形成過程，可以分為凝聚算法[15]、分裂算法[7]、搜索算法[16]和其他算法；3)按照算法的物理背景，可以分為基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的算法[17]、基于網(wǎng)絡(luò)動(dòng)力學(xué)的算法[18]、基于Q函數(shù)優(yōu)化的算法[3,19]及其它算法；4)按照社團(tuán)劃分結(jié)果，即劃分后每個(gè)節(jié)點(diǎn)是否只屬于一個(gè)社團(tuán)，可以分為互斥的[20-21]和重疊社團(tuán)發(fā)現(xiàn)算法[22-23]。社團(tuán)發(fā)現(xiàn)算法可以有多種分類方式，實(shí)際研究過程中往往需要考慮網(wǎng)絡(luò)的數(shù)據(jù)特征、形成機(jī)制和具體研究背景等問題，針對(duì)不同的網(wǎng)絡(luò)和研究問題選擇適宜的算法。

2 動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)算法

動(dòng)態(tài)網(wǎng)絡(luò)是一種處在變化過程中的特殊的演化復(fù)雜網(wǎng)絡(luò)[24]，例如網(wǎng)絡(luò)節(jié)點(diǎn)的加入或移除，或是節(jié)點(diǎn)間連邊關(guān)系的改變，這些變化或許對(duì)整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的影響甚微，但是從動(dòng)態(tài)演化的角度來看，隨著時(shí)間的推移，細(xì)小的變化的累積可能最終會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)及其社團(tuán)結(jié)構(gòu)等特征的改變。近年來，隨著在線社會(huì)網(wǎng)絡(luò)的蓬勃發(fā)展，動(dòng)態(tài)網(wǎng)絡(luò)演化中的社團(tuán)發(fā)現(xiàn)成為一個(gè)應(yīng)用需求強(qiáng)烈且具有挑戰(zhàn)性的研究領(lǐng)域[25-26]。

為了實(shí)現(xiàn)對(duì)動(dòng)態(tài)社團(tuán)的演化追蹤，按照動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法輸入的網(wǎng)絡(luò)數(shù)據(jù)類型，Dakiche N等人[8]將算法分為兩大類：第一大類是對(duì)網(wǎng)絡(luò)數(shù)據(jù)按照時(shí)間步進(jìn)行切片，得到一組網(wǎng)絡(luò)切片序列，將其作為輸入數(shù)據(jù)然后進(jìn)行社團(tuán)發(fā)現(xiàn)及演化追蹤；第二大類社團(tuán)發(fā)現(xiàn)算法的輸入數(shù)據(jù)是時(shí)態(tài)網(wǎng)絡(luò)，時(shí)態(tài)網(wǎng)絡(luò)是通過以邊流的形式實(shí)時(shí)收集信息來實(shí)現(xiàn)的，對(duì)于時(shí)態(tài)網(wǎng)絡(luò)上的動(dòng)態(tài)社團(tuán)檢測(cè)，不需要每次都從零開始對(duì)網(wǎng)絡(luò)進(jìn)行社團(tuán)發(fā)現(xiàn)，而是根據(jù)網(wǎng)絡(luò)中點(diǎn)與邊的變化，對(duì)之前已發(fā)現(xiàn)的社團(tuán)進(jìn)行更新，即，時(shí)態(tài)網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)是由一個(gè)初始的靜態(tài)社團(tuán)和對(duì)此社團(tuán)的一系列修改(例如節(jié)點(diǎn)的加入和刪除)組成的。但是網(wǎng)絡(luò)切片序列和時(shí)態(tài)網(wǎng)絡(luò)這兩種數(shù)據(jù)類型是可以互相轉(zhuǎn)換的，時(shí)態(tài)網(wǎng)絡(luò)雖然在數(shù)據(jù)類型上是以“初始網(wǎng)絡(luò)”和“每個(gè)時(shí)間點(diǎn)的網(wǎng)絡(luò)變動(dòng)”的形式存儲(chǔ)，但是其數(shù)據(jù)反映的還是在每個(gè)時(shí)間點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)，和網(wǎng)絡(luò)切片序列所包含的信息是一致的，只是分析單位不同。

圖1 動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法分類圖

綜合來看，動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)算法最本質(zhì)的區(qū)別在于是否使用歷史信息推斷當(dāng)前時(shí)刻的社團(tuán)結(jié)構(gòu)。例如Samie M E和Hamzeh A[27]將“網(wǎng)絡(luò)結(jié)構(gòu)的劇烈改變”作為檢測(cè)網(wǎng)絡(luò)社團(tuán)的特征之一，其研究模型首先要判斷各個(gè)時(shí)刻的網(wǎng)絡(luò)切片是否發(fā)生了劇烈變化，如果是，則只使用當(dāng)前切片數(shù)據(jù)進(jìn)行社團(tuán)發(fā)現(xiàn)，如果不是，則結(jié)合歷史切片數(shù)據(jù)對(duì)當(dāng)前切片進(jìn)行社團(tuán)劃分。因此，本文將綜合以往學(xué)者對(duì)社團(tuán)發(fā)現(xiàn)算法的分類方式[8,28-29]，按照發(fā)現(xiàn)當(dāng)前時(shí)刻社團(tuán)時(shí)是否考察網(wǎng)絡(luò)歷史信息這一差異，對(duì)動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)算法歸納為獨(dú)立的社團(tuán)發(fā)現(xiàn)算法和基于歷史的社團(tuán)發(fā)現(xiàn)算法。

2.1 獨(dú)立的社團(tuán)發(fā)現(xiàn)算法

獨(dú)立社團(tuán)發(fā)現(xiàn)算法針對(duì)的是網(wǎng)絡(luò)切片序列數(shù)據(jù)，該類算法在對(duì)每個(gè)時(shí)間切片發(fā)現(xiàn)社團(tuán)時(shí)，不考慮以往時(shí)間切片，對(duì)于變動(dòng)較大的動(dòng)態(tài)網(wǎng)絡(luò)也可以應(yīng)用。該算法分為兩個(gè)階段，第一階段，對(duì)每一個(gè)時(shí)間步的網(wǎng)絡(luò)切片分別進(jìn)行社團(tuán)發(fā)現(xiàn)，第二階段，將當(dāng)前時(shí)間切片的社團(tuán)發(fā)現(xiàn)結(jié)果與上一時(shí)間切片的社團(tuán)發(fā)現(xiàn)結(jié)果按照一定的相似性規(guī)則進(jìn)行匹配，從而得出社團(tuán)的演化過程。該方法將動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)轉(zhuǎn)化為傳統(tǒng)的靜態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)問題，第一階段可以根據(jù)不同的數(shù)據(jù)背景選擇合適的算法，第二階段可以根據(jù)社團(tuán)的結(jié)構(gòu)和語(yǔ)義等維度的相似性指標(biāo)，匹配不同切片中的社團(tuán)。該類方法不但可以根據(jù)實(shí)際網(wǎng)絡(luò)在兩步中選擇合適的方法進(jìn)行組合，而且可以處理重疊和非重疊的社團(tuán)發(fā)現(xiàn)。例如Wang等人[30]利用節(jié)點(diǎn)的結(jié)構(gòu)特征、點(diǎn)權(quán)等信息評(píng)估出社團(tuán)內(nèi)核心節(jié)點(diǎn)，然后利用社團(tuán)的核心節(jié)點(diǎn)匹配每個(gè)獨(dú)立切片網(wǎng)絡(luò)中的社團(tuán)。Sun Y等人[31]利用經(jīng)典Louvain算法對(duì)每個(gè)網(wǎng)絡(luò)切片劃分社團(tuán)，然后對(duì)相鄰切片劃分的社團(tuán)兩兩計(jì)算相關(guān)矩陣，進(jìn)而匹配和判別社團(tuán)演化事件。Bródka P等人[32]采用GED(Group Evolution Discovery)方法，考慮了社團(tuán)節(jié)點(diǎn)的質(zhì)量和數(shù)量，計(jì)算出社團(tuán)間的包容性，根據(jù)此指標(biāo)匹配相鄰網(wǎng)絡(luò)切片的社團(tuán)。該類算法的優(yōu)點(diǎn)是思路簡(jiǎn)單、靈活，本質(zhì)是在以往對(duì)靜態(tài)網(wǎng)絡(luò)社團(tuán)劃分后增加了網(wǎng)絡(luò)切片的匹配問題，將動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)問題轉(zhuǎn)化為靜態(tài)網(wǎng)絡(luò)中的社團(tuán)匹配問題，能夠適用于多種類型的網(wǎng)絡(luò)。但是此類方法在匹配前后網(wǎng)絡(luò)切片的社團(tuán)時(shí)，如果相鄰切片網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)的結(jié)果變化較大，則匹配起來誤差大、難度高[33]，并且在當(dāng)前網(wǎng)絡(luò)切片社團(tuán)發(fā)現(xiàn)的過程中，沒有考慮到歷史網(wǎng)絡(luò)的信息，每次都要重新對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行計(jì)算，計(jì)算過程存在大量的重復(fù)性，消耗計(jì)算成本較高。

2.2 基于歷史的社團(tuán)發(fā)現(xiàn)算法

基于歷史的社團(tuán)發(fā)現(xiàn)算法，包括針對(duì)網(wǎng)絡(luò)切片序列數(shù)據(jù)的增量社團(tuán)挖掘、同步社團(tuán)挖掘和針對(duì)時(shí)態(tài)網(wǎng)絡(luò)作為輸入數(shù)據(jù)的社團(tuán)發(fā)現(xiàn)算法。

增量社團(tuán)挖掘算法在一定程度上兼顧了以往時(shí)刻網(wǎng)絡(luò)切片的信息，適合處理網(wǎng)絡(luò)結(jié)構(gòu)相對(duì)比較穩(wěn)定的動(dòng)態(tài)網(wǎng)絡(luò)。該類算法認(rèn)為，在社團(tuán)結(jié)構(gòu)的動(dòng)態(tài)演化中，一定時(shí)間間隔內(nèi)出現(xiàn)劇烈改變的可能性很小，因此當(dāng)前時(shí)刻的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)，一定程度上是依賴于前一時(shí)刻甚至前幾個(gè)時(shí)刻中的社團(tuán)結(jié)構(gòu)。例如，He J和Chen D[34]將當(dāng)前時(shí)刻網(wǎng)絡(luò)切片中和上一時(shí)刻切片中連邊情況相同的節(jié)點(diǎn)，按照一定的規(guī)則，壓縮為一個(gè)新節(jié)點(diǎn)并替換原有節(jié)點(diǎn)，然后對(duì)改造后的網(wǎng)絡(luò)切片采用Blondel算法劃分社團(tuán)，最后再將壓縮節(jié)點(diǎn)還原。Shang J等人[35]借助機(jī)器學(xué)習(xí)的方法，增加了分類器來判斷網(wǎng)絡(luò)中新增節(jié)點(diǎn)或連邊有變化的節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)是否需要重新劃分社團(tuán)，從而只通過對(duì)局部的修改便能得到當(dāng)前網(wǎng)絡(luò)切片的社團(tuán)發(fā)現(xiàn)結(jié)果，降低了算法的時(shí)間復(fù)雜度。Zhao Z等人[36]首先檢測(cè)網(wǎng)絡(luò)初始狀態(tài)下的社團(tuán)結(jié)構(gòu)，然后在后續(xù)時(shí)刻查找網(wǎng)絡(luò)的增量，根據(jù)新增節(jié)點(diǎn)的類型(例如新增節(jié)點(diǎn)構(gòu)成了完全獨(dú)立的連通集團(tuán)，或是新增節(jié)點(diǎn)被包含在以往某個(gè)社團(tuán)內(nèi)等)，決定社團(tuán)結(jié)果的更新策略，同時(shí)該算法還引入了邊權(quán)的時(shí)間衰退效應(yīng)，以調(diào)整歷史信息對(duì)當(dāng)前網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)的影響程度。Wang Z等人[37]提出了面向重疊社團(tuán)發(fā)現(xiàn)的DOCET算法，同樣是借助核心節(jié)點(diǎn)和拓?fù)浣Y(jié)構(gòu)，根據(jù)在時(shí)序網(wǎng)絡(luò)切片中的增量變化更新節(jié)點(diǎn)社團(tuán)發(fā)現(xiàn)結(jié)果。

同步社團(tuán)發(fā)現(xiàn)算法是針對(duì)所有時(shí)刻的網(wǎng)絡(luò)切片同時(shí)進(jìn)行社團(tuán)發(fā)現(xiàn)，其基本思想是通過耦合網(wǎng)絡(luò)檢測(cè)社團(tuán)結(jié)構(gòu)。例如通過在不同時(shí)刻網(wǎng)絡(luò)切片中耦合相同節(jié)點(diǎn)之間的邊，將所有的時(shí)間切片重新構(gòu)建為一個(gè)新的網(wǎng)絡(luò)，也就是將所有的時(shí)間切片之間通過加邊的方式綁定為一個(gè)單獨(dú)的網(wǎng)絡(luò)，然后在此網(wǎng)絡(luò)上進(jìn)行經(jīng)典的社團(tuán)發(fā)現(xiàn)算法[38]。Aynaud T和Guillaume J L[39]通過新定義一個(gè)平均模塊度來修改Louvain算法，以達(dá)到在網(wǎng)絡(luò)切片中識(shí)別出長(zhǎng)期存在的社團(tuán)的目標(biāo)。Mitra B等人[40]在引文網(wǎng)絡(luò)數(shù)據(jù)中，按照作者文章發(fā)布時(shí)間和引用等關(guān)系，重新構(gòu)建出一個(gè)合并網(wǎng)絡(luò)，實(shí)現(xiàn)了對(duì)不同時(shí)刻網(wǎng)絡(luò)關(guān)系的耦合，最后利用靜態(tài)社團(tuán)發(fā)現(xiàn)算法實(shí)現(xiàn)了在合并網(wǎng)絡(luò)中識(shí)別社團(tuán)結(jié)構(gòu)。雖然這類算法依舊需要先采用切片的方式切割數(shù)據(jù)，并且在構(gòu)建不同切片網(wǎng)絡(luò)的關(guān)聯(lián)上計(jì)算成本高于前兩類算法，但是其優(yōu)點(diǎn)是在社團(tuán)發(fā)現(xiàn)時(shí)所有時(shí)刻的切片被同時(shí)考慮，社團(tuán)劃分結(jié)果的一致性得到最大程度的保留[8]。

基于時(shí)態(tài)網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)算法，不需要對(duì)網(wǎng)絡(luò)進(jìn)行切片，而是在每次網(wǎng)絡(luò)中節(jié)點(diǎn)和邊發(fā)生變化后，根據(jù)一定的規(guī)則，更新和調(diào)整節(jié)點(diǎn)的社團(tuán)結(jié)果，保證了動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)的連續(xù)性。Li J等人[41]通過考察時(shí)態(tài)網(wǎng)絡(luò)中邊的變化，在每一個(gè)時(shí)刻對(duì)變動(dòng)邊所連接的點(diǎn)重新評(píng)估社團(tuán)，根據(jù)點(diǎn)的所有鄰居所屬于的社團(tuán)情況判定該點(diǎn)的新社團(tuán)，評(píng)估機(jī)制非常簡(jiǎn)單。Rossetti G等人[42]基于時(shí)態(tài)網(wǎng)絡(luò)提出了Tiles算法，根據(jù)每個(gè)時(shí)刻網(wǎng)絡(luò)中的變化，對(duì)網(wǎng)絡(luò)使用標(biāo)簽傳播的思想重新評(píng)估變化相關(guān)的節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)的社團(tuán)關(guān)系。Nguyen N P等人[43]針對(duì)時(shí)態(tài)網(wǎng)絡(luò)中的重疊社團(tuán)發(fā)現(xiàn)問題提出了AFOCS算法，該算法在初始時(shí)會(huì)識(shí)別網(wǎng)絡(luò)中內(nèi)部密度大于一定程度的小社團(tuán)，并將高度重合的緊密社團(tuán)合并，在此基礎(chǔ)之上再根據(jù)時(shí)態(tài)網(wǎng)絡(luò)的實(shí)時(shí)變化更新節(jié)點(diǎn)的社團(tuán)結(jié)果。Boudebza S等人[44]基于派系過濾和標(biāo)簽傳播的方法提出了OLCPM算法，先發(fā)現(xiàn)網(wǎng)絡(luò)中的核心社團(tuán)，再通過標(biāo)簽傳播標(biāo)注外圍節(jié)點(diǎn)，該算法在處理網(wǎng)絡(luò)中的變化時(shí)，會(huì)根據(jù)是節(jié)點(diǎn)還是邊的變化，按照不同的規(guī)則更新社團(tuán)結(jié)果。該類算法雖然能很好地保持社團(tuán)發(fā)現(xiàn)的連貫性，但是時(shí)態(tài)網(wǎng)絡(luò)要面臨的網(wǎng)絡(luò)變動(dòng)量是巨大的，所以基于時(shí)態(tài)網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)算法很難在每一步更新時(shí)使用較為復(fù)雜的算法。除此之外，由于每一步的社團(tuán)結(jié)果都是建立在前一步的結(jié)果之上，該類算法不能保證最終得到的社團(tuán)發(fā)現(xiàn)結(jié)果是全局角度的最佳結(jié)果[44]。

整體而言，基于歷史的社團(tuán)發(fā)現(xiàn)算法更適用于結(jié)構(gòu)相對(duì)穩(wěn)定的動(dòng)態(tài)網(wǎng)絡(luò)，能夠較好地利用前一時(shí)刻甚至前幾個(gè)時(shí)刻網(wǎng)絡(luò)切片中的歷史信息，保持社團(tuán)的連貫性。該類算法雖然比獨(dú)立的社團(tuán)發(fā)現(xiàn)算法在社團(tuán)劃分這一步更復(fù)雜，但是該類算法將前一時(shí)刻的結(jié)果作為輸入數(shù)據(jù)來識(shí)別當(dāng)前時(shí)刻的社團(tuán)，避免了不同時(shí)刻網(wǎng)絡(luò)切片間的社團(tuán)匹配的問題；與此同時(shí)，在大規(guī)模網(wǎng)絡(luò)中，該類算法能夠有效降低計(jì)算成本，更適合當(dāng)前大數(shù)據(jù)環(huán)境下的在線社會(huì)網(wǎng)絡(luò)的研究。

社團(tuán)發(fā)現(xiàn)結(jié)果的穩(wěn)定性和可靠性會(huì)影響后續(xù)對(duì)于動(dòng)態(tài)社團(tuán)演化事件的判定和預(yù)測(cè)，因此，在社團(tuán)發(fā)現(xiàn)階段，應(yīng)該盡可能保證結(jié)果的穩(wěn)定性和可靠性。需要注意的是，在動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)算法中，如果使用切片數(shù)據(jù)，在將網(wǎng)絡(luò)按照時(shí)間窗口切分時(shí)，切片策略會(huì)直接影響到后期社團(tuán)發(fā)現(xiàn)和演化的研究結(jié)果。時(shí)間窗口切分方式可以分為按照等時(shí)間長(zhǎng)度切分，按照每個(gè)時(shí)間窗口具有等量的關(guān)系數(shù)切分，以及根據(jù)數(shù)據(jù)的具體背景按照任意長(zhǎng)度切分。Saganowski等人[45]指出網(wǎng)絡(luò)切片可以分為互斥的、重疊的和累積的，在切分網(wǎng)絡(luò)過程中，應(yīng)該注意：1)對(duì)于變化較快較大的網(wǎng)絡(luò)，建議采用重疊的時(shí)間窗口，通常采用30%的偏移量以保證能獲取到足夠的時(shí)間窗之間的連續(xù)事件(例如連邊變化)；2)窗口大小應(yīng)該和實(shí)際數(shù)據(jù)的背景相結(jié)合；3)如果研究的對(duì)象是持續(xù)存在的社團(tuán)，建議采用累積的時(shí)間窗口，盡量保存網(wǎng)絡(luò)的持續(xù)性和增長(zhǎng)性的事件；4)在處理相對(duì)稠密并且節(jié)點(diǎn)間的關(guān)系會(huì)反復(fù)出現(xiàn)的網(wǎng)絡(luò)時(shí)，可以嘗試使用互斥的時(shí)間窗口來降低計(jì)算量；5)在設(shè)計(jì)時(shí)間窗口的類型和大小時(shí)，可以通過多次嘗試以達(dá)到最佳的切分結(jié)果。

網(wǎng)絡(luò)的切分、數(shù)據(jù)的處理和社團(tuán)發(fā)現(xiàn)的算法都可以有多種選擇，因此，需要有合適的社團(tuán)發(fā)現(xiàn)效果評(píng)價(jià)指標(biāo)，才能選擇出最合適的算法。在社團(tuán)發(fā)現(xiàn)算法的評(píng)估方面，無(wú)論是靜態(tài)網(wǎng)絡(luò)還是動(dòng)態(tài)網(wǎng)絡(luò)，都是主要以模塊度和NMI為評(píng)價(jià)指標(biāo)。模塊度考察的是社團(tuán)結(jié)構(gòu)的強(qiáng)度，通過比較網(wǎng)絡(luò)中各社團(tuán)的邊密度和隨機(jī)網(wǎng)絡(luò)中對(duì)應(yīng)子圖邊密度之間的差異來度量社團(tuán)結(jié)構(gòu)的顯著性，而NMI是通過社團(tuán)發(fā)現(xiàn)結(jié)果和真實(shí)社團(tuán)結(jié)構(gòu)之間的相似性。同時(shí)，常用的基準(zhǔn)圖包括空手道俱樂部網(wǎng)絡(luò)[46]、海豚間關(guān)系網(wǎng)絡(luò)[47]、美國(guó)大學(xué)生足球俱樂部網(wǎng)絡(luò)[7]、政治書籍網(wǎng)絡(luò)[48]，和大學(xué)電子郵件網(wǎng)絡(luò)[49]等。這些經(jīng)典的公開數(shù)據(jù)集雖然具有很好的質(zhì)量，但是由于其數(shù)據(jù)年份較早，和當(dāng)前的眾多實(shí)際在線網(wǎng)絡(luò)數(shù)據(jù)相比，在數(shù)據(jù)量級(jí)和網(wǎng)絡(luò)性質(zhì)方面還是有一定差異。由于真實(shí)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)數(shù)據(jù)往往難以獲取，相比之下，模塊度作為評(píng)估社團(tuán)的指標(biāo)應(yīng)用范圍更廣，但是模塊度的計(jì)算復(fù)雜度較高[50]，因此也有學(xué)者提出對(duì)模塊度算法的優(yōu)化，或針對(duì)不同的網(wǎng)絡(luò)類型[51]，或通過降低算法的時(shí)間復(fù)雜度以適用于大規(guī)模網(wǎng)絡(luò)[28,52]，或解決模塊度優(yōu)化中存在的分辨率問題[53]。

3 動(dòng)態(tài)社團(tuán)演化事件

社團(tuán)的動(dòng)態(tài)發(fā)展是網(wǎng)絡(luò)科學(xué)尤其是社交網(wǎng)絡(luò)分析的一個(gè)重要領(lǐng)域，關(guān)注的是特定群體如何隨時(shí)間變化[54]。Palla G等人[55]將網(wǎng)絡(luò)演化事件總結(jié)為生長(zhǎng)、萎縮、合并、分裂、出生和死亡。這一歸納被許多學(xué)者沿用[8,35,56]，也有學(xué)者對(duì)此模型進(jìn)行了進(jìn)一步的補(bǔ)充，例如Cazabet R和Rossetti G[57]提出了社團(tuán)的復(fù)活，Tajeuna E G等[58]都使用了社團(tuán)的持續(xù)這一概念；Mohammadmosaferi K K和Naderi H[59]將社團(tuán)演化過程進(jìn)一步細(xì)化，新增了合并且增長(zhǎng)、部分合并、部分合并且增長(zhǎng)、分裂且增長(zhǎng)，和部分存活且生長(zhǎng)。

表1 社團(tuán)演化事件歸納

續(xù)表1

實(shí)際上，社團(tuán)演化事件通常只是為了描述網(wǎng)絡(luò)切片中社團(tuán)的一些發(fā)展?fàn)顟B(tài)，并不適合用來描述精細(xì)時(shí)間粒度下的網(wǎng)絡(luò)復(fù)雜動(dòng)態(tài)[57]。在具體的判定過程中，閾值的設(shè)定會(huì)嚴(yán)重影響演化結(jié)果的判定，例如很多算法通過計(jì)算相鄰網(wǎng)絡(luò)切片中各個(gè)社團(tuán)間的相似性，給定恰當(dāng)?shù)拈撝禌Q定兩個(gè)社團(tuán)是否匹配，假若t時(shí)刻的兩個(gè)社團(tuán)各自流失了小部分節(jié)點(diǎn)，這些節(jié)點(diǎn)在t+1時(shí)刻組成了新社團(tuán)，如果判定社團(tuán)匹配的相似性閾值設(shè)置較高，則新社團(tuán)會(huì)被判定為出生，反之將被視為由前一時(shí)刻兩個(gè)社團(tuán)部分合并而來。

4 動(dòng)態(tài)社團(tuán)演化研究

探究網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)及其演化過程，有助于認(rèn)識(shí)和發(fā)現(xiàn)實(shí)際網(wǎng)絡(luò)中事物的關(guān)聯(lián)和發(fā)展規(guī)律。例如Wang R和Rho S[60]認(rèn)為，合作行為建立了個(gè)體之間的關(guān)聯(lián)網(wǎng)絡(luò)，個(gè)體與所在社團(tuán)內(nèi)外其他個(gè)體的合作行為，推動(dòng)了社團(tuán)和網(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)演化。Varga A[61]建立了1950年到2018年Web of Science中SCI期刊引文網(wǎng)絡(luò)，發(fā)現(xiàn)學(xué)科之間的距離越來越短，學(xué)科之間的交叉現(xiàn)象更加明顯。Singh C K和Jolad S[62]通過建立印度物理學(xué)家1970～2013年間的合作網(wǎng)絡(luò)，追蹤合作社團(tuán)的規(guī)模變動(dòng)，探究了印度物理學(xué)家與外國(guó)物理學(xué)家在不同期刊上的合作關(guān)系，并找出了每個(gè)時(shí)期最有影響力的作者。Atzmueller M等人[63]研究了面對(duì)面接觸網(wǎng)絡(luò)中群體形成和演化，描述了在一個(gè)會(huì)議過程中，個(gè)體交流群組的演化，并發(fā)現(xiàn)群組規(guī)模的分布在茶歇，會(huì)議和空閑時(shí)間差異明顯。齊金山等人[64]在新浪微博網(wǎng)絡(luò)測(cè)量Gnutella等數(shù)據(jù)集上實(shí)驗(yàn)發(fā)現(xiàn)，社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的出現(xiàn)和消失頻繁程度會(huì)影響社團(tuán)穩(wěn)定性以及社團(tuán)結(jié)構(gòu)的演化。社團(tuán)結(jié)構(gòu)的演化作為動(dòng)態(tài)網(wǎng)絡(luò)中的重要特性，對(duì)于網(wǎng)絡(luò)的生存發(fā)展和網(wǎng)絡(luò)中信息的傳播等都具有重要的研究?jī)r(jià)值，但是目前關(guān)于動(dòng)態(tài)社團(tuán)的研究中，更多集中于如何提出更有效的動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)算法，對(duì)社團(tuán)演化問題關(guān)注還不足夠[37]，實(shí)際上，無(wú)論是引文網(wǎng)絡(luò)，還是社交網(wǎng)絡(luò)，隨著數(shù)據(jù)可得性的提高，對(duì)網(wǎng)絡(luò)性質(zhì)和特征的探究還可以被進(jìn)一步挖掘。

5 動(dòng)態(tài)社團(tuán)研究未來方向

首先，隨著大規(guī)模的復(fù)雜網(wǎng)絡(luò)越來越多，尤其是多內(nèi)容和動(dòng)態(tài)變化的大型社交網(wǎng)絡(luò)的迅速增長(zhǎng)[60]，如何降低動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的復(fù)雜度是一個(gè)不可避免的難題。動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的復(fù)雜度，與網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量以及網(wǎng)絡(luò)變化的數(shù)量緊密相關(guān)[57]。社團(tuán)發(fā)現(xiàn)算法應(yīng)適用于大型動(dòng)態(tài)網(wǎng)絡(luò)，甚至是采用分布式的計(jì)算方式[10]，以適應(yīng)現(xiàn)實(shí)生活中大規(guī)模、多變動(dòng)、持續(xù)久的復(fù)雜網(wǎng)絡(luò)。與此同時(shí)，在用戶生產(chǎn)內(nèi)容為主的網(wǎng)絡(luò)環(huán)境中，如何去除繁雜網(wǎng)絡(luò)中的噪聲數(shù)據(jù)，乃至在社交網(wǎng)絡(luò)的研究中如何處理社交機(jī)器人等因素的影響，都是值得考慮的問題。

其次，在對(duì)動(dòng)態(tài)網(wǎng)絡(luò)進(jìn)行社團(tuán)發(fā)現(xiàn)時(shí)，應(yīng)注重結(jié)合網(wǎng)絡(luò)的現(xiàn)實(shí)場(chǎng)景，不局限于網(wǎng)絡(luò)的拓?fù)涮卣鳎瑥亩岣呱鐖F(tuán)劃分的準(zhǔn)確度和穩(wěn)定性。社會(huì)網(wǎng)絡(luò)的實(shí)體并非總是單一類型，實(shí)體間的關(guān)系往往也是多樣的[68]，當(dāng)面對(duì)社團(tuán)核心節(jié)點(diǎn)不明顯的、動(dòng)態(tài)變化劇烈的網(wǎng)絡(luò)時(shí)[69]，社團(tuán)發(fā)現(xiàn)的難度大大增加。因此，在社團(tuán)發(fā)現(xiàn)時(shí)要充分挖掘網(wǎng)絡(luò)結(jié)構(gòu)特征，例如結(jié)合網(wǎng)絡(luò)中的高階連接模式[70]，發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)和模體結(jié)構(gòu)之間的關(guān)聯(lián)和特征。實(shí)體在網(wǎng)絡(luò)中呈現(xiàn)的屬性可能是多刻面的、高維的、稀疏的，如何將語(yǔ)義信息、關(guān)系信息、交互信息等多元信息有效綜合進(jìn)行結(jié)構(gòu)推斷和預(yù)測(cè)將成為未來的一個(gè)重要研究領(lǐng)域[71]。

再次，盡管目前已有多個(gè)經(jīng)典的網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法檢測(cè)的基準(zhǔn)圖，但是包含真實(shí)社團(tuán)結(jié)構(gòu)的動(dòng)態(tài)網(wǎng)絡(luò)數(shù)據(jù)還是相對(duì)稀缺的[50,72]。在目前大數(shù)據(jù)的信息環(huán)境之下，如何能夠推動(dòng)真實(shí)社團(tuán)結(jié)構(gòu)的數(shù)據(jù)庫(kù)的建立和共享，如何能夠通過多源數(shù)據(jù)實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)中的實(shí)體關(guān)系推斷以豐富基準(zhǔn)圖數(shù)據(jù)庫(kù)，這些問題都需要通過多方協(xié)作、共同解決。

最后，在研究過程中應(yīng)拓寬動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)與演化研究的應(yīng)用場(chǎng)景，將復(fù)雜網(wǎng)絡(luò)的研究思想與其它學(xué)科相結(jié)合。隨著互聯(lián)網(wǎng)的發(fā)展，社交網(wǎng)絡(luò)成為了社會(huì)科學(xué)、政治經(jīng)濟(jì)、文化傳播等多個(gè)領(lǐng)域的研究對(duì)象，充分利用信息資源和跨學(xué)科的計(jì)算方法，能夠?qū)?dòng)態(tài)社團(tuán)的研究方法與其它社會(huì)系統(tǒng)相結(jié)合，為各領(lǐng)域提供新的研究視角和技術(shù)支持，尤其是社團(tuán)演化研究對(duì)預(yù)測(cè)實(shí)際社會(huì)網(wǎng)絡(luò)的生命周期等方面的應(yīng)用還有很大的發(fā)展空間。