動態(tài)社團發(fā)現(xiàn)研究綜述

李永寧，吳 曄，張 倫

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

0 引言

社團結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的拓撲特性之一，發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)研究的基礎(chǔ)性問題[1-2]。社團結(jié)構(gòu)作為介于宏觀網(wǎng)絡(luò)和微觀個體之間的中觀結(jié)構(gòu)，網(wǎng)絡(luò)在社團層面所具有的特性是網(wǎng)絡(luò)層面的特性所不能替代的，忽視社團結(jié)構(gòu)可能會遺漏很多網(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ù)進行疊加以發(fā)現(xiàn)靜態(tài)社團結(jié)構(gòu)，這種做法雖然可以識別社團特征，但是節(jié)點和邊隨時間變化的信息被忽略，無法發(fā)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的動態(tài)演化過程。近年來，隨著大型社交網(wǎng)絡(luò)的興起和網(wǎng)絡(luò)數(shù)據(jù)可得性的增強，動態(tài)社團發(fā)現(xiàn)及演化研究成為當(dāng)前在線社會網(wǎng)絡(luò)研究的熱點。社團作為動態(tài)網(wǎng)絡(luò)分析的重要基礎(chǔ)結(jié)構(gòu)，關(guān)注動態(tài)網(wǎng)絡(luò)中社團發(fā)現(xiàn)問題及社團演化機制，在信息傳播、影響力研究、網(wǎng)絡(luò)群體事件等研究中都能提供新的分析視角。實際科研工作也表明，在電子商務(wù)、輿情傳播、知識傳播等多個領(lǐng)域，動態(tài)網(wǎng)絡(luò)社團研究的可應(yīng)用性不斷加強[6]，動態(tài)網(wǎng)絡(luò)的社團發(fā)現(xiàn)與演化等問題將成為復(fù)雜網(wǎng)絡(luò)分析的重要關(guān)注點之一。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 動態(tài)社團演化事件

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

表1 社團演化事件歸納

續(xù)表1

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

4 動態(tài)社團演化研究

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

5 動態(tài)社團研究未來方向

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

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

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

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