動態社團發現研究綜述

李永寧，吳 曄，張 倫

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

0 引言

社團結構是復雜網絡的拓撲特性之一，發現復雜網絡中的社團結構是復雜網絡研究的基礎性問題[1-2]。社團結構作為介于宏觀網絡和微觀個體之間的中觀結構，網絡在社團層面所具有的特性是網絡層面的特性所不能替代的，忽視社團結構可能會遺漏很多網絡特征[3]。

隨著復雜網絡研究的發展，越來越多的領域借助網絡分析的方式探究網絡的結構與性能之間的關聯[4-5]。早期的網絡分析方法將網絡觀察數據進行疊加以發現靜態社團結構，這種做法雖然可以識別社團特征，但是節點和邊隨時間變化的信息被忽略，無法發現網絡結構的動態演化過程。近年來，隨著大型社交網絡的興起和網絡數據可得性的增強，動態社團發現及演化研究成為當前在線社會網絡研究的熱點。社團作為動態網絡分析的重要基礎結構，關注動態網絡中社團發現問題及社團演化機制，在信息傳播、影響力研究、網絡群體事件等研究中都能提供新的分析視角。實際科研工作也表明，在電子商務、輿情傳播、知識傳播等多個領域，動態網絡社團研究的可應用性不斷加強[6]，動態網絡的社團發現與演化等問題將成為復雜網絡分析的重要關注點之一。

1 社團發現

通常認為，社團結構是指網絡中的節點可以被劃分為多個分組，組內節點連邊相對緊密，組間節點連邊相對稀疏[7]。社團發現是識別網絡中節點群組關系的過程，社團發現往往能夠揭示網絡更深層次的特征，為理解網絡的內部結構和生成機制提供了極具意義的研究視角[8]。

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

2 動態網絡的社團發現算法

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

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

圖1 動態網絡社團發現算法分類圖

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

2.1 獨立的社團發現算法

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

2.2 基于歷史的社團發現算法

基于歷史的社團發現算法，包括針對網絡切片序列數據的增量社團挖掘、同步社團挖掘和針對時態網絡作為輸入數據的社團發現算法。

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

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

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

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

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

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

3 動態社團演化事件

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

表1 社團演化事件歸納

續表1

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

4 動態社團演化研究

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

5 動態社團研究未來方向

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

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

再次，盡管目前已有多個經典的網絡社團發現算法檢測的基準圖，但是包含真實社團結構的動態網絡數據還是相對稀缺的[50,72]。在目前大數據的信息環境之下，如何能夠推動真實社團結構的數據庫的建立和共享，如何能夠通過多源數據實現網絡數據中的實體關系推斷以豐富基準圖數據庫，這些問題都需要通過多方協作、共同解決。

最后，在研究過程中應拓寬動態社團發現與演化研究的應用場景，將復雜網絡的研究思想與其它學科相結合。隨著互聯網的發展，社交網絡成為了社會科學、政治經濟、文化傳播等多個領域的研究對象，充分利用信息資源和跨學科的計算方法，能夠將動態社團的研究方法與其它社會系統相結合，為各領域提供新的研究視角和技術支持，尤其是社團演化研究對預測實際社會網絡的生命周期等方面的應用還有很大的發展空間。