基于社區改變量估計的非均勻時間片劃分方法

羅香玉，閆克，盧琰，王甜，辛剛

基于社區改變量估計的非均勻時間片劃分方法

羅香玉1*，閆克1，盧琰1，王甜1，辛剛2

（1.西安科技大學 計算機科學與技術學院，西安 710054； 2.中國航空工業集團公司西安航空計算技術研究所，西安 710119）（ ? 通信作者電子郵箱luoxiangyu@xust.edu.cn）

動態網絡時間片劃分方法對社區演化分析結果的準確性具有重要影響，但社區隨時間及網絡拓撲改變呈現非線性的變化，現有均勻時間片劃分以及基于網絡拓撲改變量的非均勻時間片劃分方法在捕捉社區演化事件方面均效果不佳。為此，提出一種基于社區改變量估計的非均勻時間片劃分方法，其中社區改變量通過變化后網絡期望達到的社區模塊度與直接應用網絡變化前的社區發現結果獲得的社區模塊度之差來定量描述。首先，基于時間序列分析建立社區模塊度預測模型；其次，使用該模型預測變化后網絡期望達到的社區模塊度，并求得社區改變量的估計值；最后，當該估計值超過預先設置的閾值時即生成一個新的時間片。在兩個真實網絡數據集上的實驗結果顯示，相較于傳統的均勻時間片劃分方法和基于網絡拓撲改變量的非均勻時間片劃分方法，所提方法在動態網絡數據集Arxiv HEP-PH上的識別社區消失事件方面分別提早1.10 d和1.30 d，識別社區形成事件方面分別提早8.34 d和3.34 d，識別出的社區縮小、擴大事件總數分別增加10個和1個；在Sx-MathOverflow數據集上的識別社區消失事件方面分別提早3.30 d和1.80 d，識別社區形成事件方面分別提早6.41 d和2.97 d，識別出的社區縮小、擴大事件總數分別增加15個和7個。

動態網絡；時間片劃分；社區演化；時間序列分析；社區發現；社區模塊度

0 引言

近年來，社區演化分析已成為動態網絡的研究熱點［1-4］。它旨在發現動態網絡潛在的演化規律，為預測社區的演化行為提供依據和信息。社區演化分析在眾多領域都有廣泛的應用。例如，應用于蛋白質交互網絡時［5-6］，可以根據已知的蛋白質拓撲結構和交互關系對未知蛋白質的功能和行為進行預測；應用于輿情監測和引導時［7-8］，有助于掌握負面輿論的傳播路徑；應用于公共衛生領域時，可以為預測傳染病的傳播提供有價值的信息，提前制定應對措施，防止傳染病蔓延［9］。

社區演化分析過程主要分為三個階段［10］：第一階段將動態網絡劃分為一系列能夠準確捕獲社區演化事件的快照，這一階段主要依賴合理的時間片劃分方法；第二階段對劃分得到的網絡快照分別進行社區發現，獲取各個快照上的全部社區；第三階段通過比較兩個相鄰快照的社區發現結果識別社區演化事件。其中后兩個階段社區發現和社區演化事件識別已得到較深入的研究，但第一階段時間片劃分研究尚不充分。

時間片劃分方法對社區演化分析結果的準確性具有重要影響［11-14］。理想的時間片劃分方法能夠以最少數量的快照捕獲所有的社區演化事件，設計出理想的時間片劃分方法是一項極具挑戰性的工作。由于社區并非隨時間勻速變化，均勻時間片劃分方法［15-18］效果不佳，最佳時間片長度應根據社區演化速度不斷調整，呈現出非均勻的分布。

現有的非均勻時間片劃分方法通過計算網絡拓撲的改變量獲得時間片劃分結果。當網絡拓撲改變量超過預先設置的閾值時，則生成一個新的時間片。衡量網絡拓撲改變量的一個典型指標是網絡變化前后邊集的Jaccard系數［19］，該系數值越小，則網絡拓撲改變量越大。然而，社區隨網絡拓撲改變呈非線性變化。在一些情況下，刪除或添加大量邊仍不會導致社區演化，但在另一些情況下，刪除或添加少量邊即會導致社區演化。因此，基于網絡拓撲改變量的非均勻時間片劃分方法可能會產生不捕獲任何演化事件的冗余快照或者跳過存在演化事件的有效快照。

本文提出一種基于社區改變量估計的非均勻時間片劃分方法。該方法不計算網絡拓撲的改變量，而是直接估計相鄰兩個時間片之間的社區改變量，當社區改變量超過某個閾值，則生成一個新的時間片。主要挑戰是在網絡動態變化之后社區未知條件下如何估計社區的改變程度。

本文的主要工作如下：

1）分析現有時間片劃分方法導致社區演化分析結果不準確的原因。由于社區演化與時間、網絡拓撲改變量均呈非線性關系，均勻時間片劃分方法和基于網絡拓撲改變量的非均勻時間片劃分方法均會降低社區演化分析結果的準確性。

2）提出一種基于社區改變量估計的非均勻時間片劃分方法，其中社區改變量通過變化后網絡期望達到的社區模塊度與直接應用網絡變化前的社區發現結果獲得的社區模塊度之差來定量描述。期望達到的社區模塊度則通過建立基于時間序列分析的社區模塊度預測模型進行估計。

3）在真實數據集上對所提方法的有效性進行驗證，結果表明，與現有時間片劃分方法相比，本文方法能夠更及時地發現社區生成和社區消失事件，并發現更多數量的社區擴大和社區縮小事件，社區演化分析結果的準確性得到有效提升。

1 相關工作

社區演化分析過程的三個階段相關工作分別總結如下。

1.1　時間片劃分

時間片劃分旨在將動態網絡離散化為一系列的快照。它對社區演化分析結果的準確性具有重要影響。現有的動態網絡時間片劃分方法一般分為兩類［20］：均勻時間片劃分方法和非均勻時間片劃分方法。均勻時間片劃分方法采用固定時間間隔將動態網絡離散為若干個快照，因實現機制簡單而被廣泛使用；非均勻時間片劃分方法則會將動態網絡離散為不等時間間隔的若干個快照，實現機制相對復雜。

根據時間片長度的確定方式，均勻時間片劃分可以進一步細分為兩個子類：基于人工經驗的方法和基于網絡特征分析的方法。

基于人工經驗確定時間片長度的方法應用最為廣泛。Bhat等［21］提出了用于跟蹤在線社交網絡中分層和重疊社區演變的框架HOCTracker，實驗中時間片的長度指定為5 a。Wang等［22］提出了基于拓撲勢場中核心節點變化的社區演化事件跟蹤方法，實驗中時間片長度指定為1 d。Qiao等［23］提出了基于強弱事件的社區演化分析框架，實驗中使用了兩個數據集，時間片長度分別指定為1 a和1個月（使用的是2008年的數據集，該時間片長度為自然月）。Xu等［24］提出了一種兩階段社區演化分析方法（Error Accumulation Sensitive-Superspreaders And Superblockers， EAS-SAS），解決了社區發現中增量算法導致的累積誤差問題以及社區演化事件識別中核心節點貢獻度異構性的問題，實驗中兩個數據集的時間片長度分別指定為1 a和1 d。

基于網絡特征分析的均勻時間片劃分方法也被廣泛使用。對于預設的每個時間片長度值，Tajeuna等［11］分析了相鄰快照間新增節點、離開節點和保持節點各自所占的比例，最終選擇的時間片長度能夠保證相鄰快照在新增和離開節點比例以及保持節點比例間取得最佳的平衡。

非均勻時間片劃分方法通常會持續評估網絡拓撲的改變量，當改變量超過某個閾值時生成一個新的時間片。?olak等［25］和Orman等［26］通過計算兩個相鄰快照的Jaccard系數評估網絡拓撲的改變程度。Jaccard系數值越大，網絡拓撲改變量越小。

由于社區演化與時間以及與網絡拓撲的改變量均呈非線性關系，均勻時間片劃分方法和基于網絡拓撲改變量的非均勻時間片劃分方法效果不佳。為此，本文提出一種基于社區改變量估計的非均勻時間片劃分方法。該方法直接估計社區改變的程度，并在改變程度超過一定閾值時生成新的時間片。本文方法旨在不增加快照數量的情況下更全面更及時地識別社區演化事件。

1.2　社區發現

社區發現旨在找出每個網絡快照上的全部社區。現有研究主要包括三類方法：基于邊消除策略的方法、基于社區質量指標優化策略的方法以及基于標簽傳播策略的方法。基于邊消除策略的方法通過逐一識別和消除社區之間的邊，將網絡劃分為若干社區，代表性算法是GN（Girvan-Newman算法）［27］；基于社區質量指標優化策略的方法定義模塊度等度量指標評價社區質量，通過不斷優化度量指標進行社區發現，代表性算法是Louvain算法［28］；基于標簽傳播策略的方法先把每個節點的標簽傳播給它的鄰居節點，然后該節點獲取鄰居節點的標簽從而更新自身標簽，重復上述標簽傳播過程，最后各節點根據標簽獲得所屬社區，代表性算法是LPA（Label Propagation Algorithm）［29］。

1.3　社區演化事件識別

社區演化事件識別旨在找出兩個相鄰快照上社區之間的演化關系。GED（Group Evolution Discovery）模型［30］中定義歸屬度用于衡量相鄰快照上兩個社區的相似性，歸屬度考慮公共節點的數量及其在網絡中的位置。GED模型根據相似性結果和社區規模定義7種社區演化事件，包括持續、縮小、擴大、分裂、合并、消失和生成。

2 問題描述

2.1　基本術語

時間片劃分點：為動態網絡建立快照的每個時刻稱為一個時間片劃分點。兩個相鄰時間片劃分點決定一個時間片的長度。因此，時間片劃分結果可以表示為一系列時間片劃分點的集合。

社區改變閾值：最近時間片劃分點與當前檢查時刻之間社區改變程度的上限。當社區改變程度超過時，將當前檢查時刻作為新的時間片劃分點。

2.2　非均勻時間片劃分問題

3 非均勻時間片劃分方法

3.1　主要思想

3.2　非均勻時間片劃分方法概述

算法1 基于社區改變量估計的非均勻時間片劃分。

輸出。

4） forfrom 1 todo

11） end if

12） end for

13） return

算法1中包含三個重要函數：第一個函數是Louvain，用于在給定的網絡快照上進行社區發現，以找出全部社區，具體算法可參考文獻［28］；第二個函數是Modularity，利用模塊度評價所找到社區結果的質量，具體計算方式可參考文獻［32］；第三個函數是ARIMAForecast，基于時間序列分析模型ARIMA進行模塊度預測。3.3節將重點描述ARIMA預測模型的訓練方法。

3.3　模塊度預測模型訓練方法

基于算法2獲取的訓練數據集，確定ARIMA預測模型的參數：、和。參數是模型中的滯后觀測數；參數表示確保模塊度時序數據平穩所需的差分階數；參數是移動平均窗口的大小。本文通過實驗選擇ARIMA預測模型的最佳參數。

算法2 獲取訓練集數據。

輸出 社區模塊度值的時間序列。

3） forfrom 0 todo

8） end for

9） return

基于訓練數據集和模型參數、和，獲得ARIMA模塊度預測模型。模型公式如下：

3.4　時間復雜度分析

4 實驗與結果分析

4.1　實驗環境

所有實驗均在配置為Intel Core i5-10210U處理器、16 GB RAM、Windows 10（64 bit）操作系統的計算機上進行。本文采用Python 3.7.8實現了基于多種時間片劃分方法的社區演化分析系統。

社區演化分析系統由三個組件組成：時間片劃分組件、社區發現組件和演化事件識別組件。時間片劃分組件以動態網絡為輸入，時間片劃分點為輸出，使用三個時間片劃分方法生成時間片劃分點，即基于社區改變量估計的非均勻時間片劃分方法、均勻時間片劃分方法和基于網絡拓撲改變量的非均勻時間片劃分方法；社區發現組件首先根據時間片劃分點生成網絡快照，然后使用Louvain算法對每個快照進行社區發現；演化事件識別組件采用GED模型，通過比較每兩個相鄰快照上的社區識別社區演化事件。

4.2　數據集

為驗證本文方法的有效性，利用兩個真實的公開數據集對傳統方法和本文方法進行比較。數據集描述如表1所示，其中：Arxiv HEP-PH數據集［33］是由1993年至2003年期間發表的高能物理現象學（理論）論文形成的引文網絡，節點表示發表的論文，邊代表論文之間的引用關系；Sx?MathOverflow數據集［34］是StackExchange網站mathflow上2009年至2016年的時間交互網絡，節點表示用戶，邊表示用戶之間的交互關系。

表 1　數據集描述

4.3　對比方法與評價指標

將本文方法與以下兩個傳統時間片劃分方法進行比較。

1）均勻時間片劃分方法。采用固定時間窗口長度將動態網絡數據離散化為若干個網絡快照。

2）基于網絡拓撲改變量的非均勻時間片劃分方法（簡稱為基于網絡拓撲改變量的劃分方法）。利用動態網絡變化前后邊集的Jaccard系數［19］計算網絡拓撲的改變量，當網絡拓撲改變量超過預先設置的閾值時生成一個新的時間片，最后獲得時間片劃分結果。

4.4　實驗結果

4.4.1三種時間片劃分方法的性能對比結果

基于所實現的社區演化分析系統，分別采用三種時間片劃分方法對兩種動態網絡數據集進行社區演化分析，然后計算評價指標完成時間片劃分方法的比較。實驗目的是驗證基于社區改變量估計的非均勻時間片劃分方法的優越性。

圖 1　兩個數據集上三種時間片劃分方法劃分的時間片的長度分布

由表2可以看出，本文方法能夠比其他兩種方法更及時地識別社區消失事件、更及時地識別社區生成事件，以及可以發現最多數量的社區擴大和社區縮小事件。經分析認為：在動態網絡演化過程中，社區的演化與時間呈非線性關系，均勻時間片劃分容易錯過重要的社區演化事件，最終導致不準確的社區演化分析結果；同時，社區的演化與網絡拓撲改變量也呈非線性關系，比如有時刪除或添加大量邊，社區結構仍舊保持不變，而有時刪除或添加少量邊就會導致社區結構發生較大變化，因此，基于網絡拓撲改變量的劃分方法也會降低社區演化分析結果的準確性。本文方法通過直接估計社區的改變量決定何時劃分時間片，從而得到更加準確的社區演化分析結果。

表 2　兩個數據集上三種時間片劃分方法的準確性對比

圖2顯示了Arxiv HEP-PH數據集中1995年4月30日網絡快照的一部分。圖中虛線框內的節點表示該快照上的一個社區。基于本文所提出時間片劃分方法的社區演化分析結果表明，該社區消失的日期是1995年5月11日；但使用其他兩種時間片劃分方法情況下，社區演化分析結果中該社區消失的日期分別是1995年5月12日和1995年5月15日。

圖 2　1995年4月30日網絡快照上的一個社區

圖3顯示了在Arxiv HEP-PH數據集中1995年6月1日網絡快照的一部分。圖中虛線框內的節點表示該快照上的一個社區。基于本文所提出時間片劃分方法的社區演化分析結果表明，該社區形成的日期是1995年6月1日；但使用其他兩種時間片劃分方法情況下，社區演化分析結果中該社區生成的日期分別是1995年6月8日和1995年6月18日。

4.4.2社區發現算法對本文方法性能的影響

為了直觀驗證社區發現方法對所提方法性能影響的程度，以增量式社區發現方法DynaMo［35］和Louvain方法為例，驗證所提方法的執行結果，其中均設置為0.02，實驗結果如表3所示。

通過實驗發現，增量式社區發現方法DynaMo一般比Louvain方法得到的Modularity值低平均5%，即兩種社區發現方法下的Modularity幾乎相同，實驗結果表明社區發現方法對本文所提方法的影響較小。原因分析認為，所有社區發現方法的目的是找到拓撲圖中存在的社區，在這些社區中，同一社區內節點之間關系緊密，而社區之間節點關系稀疏。基于社區發現的目的，增量式社區發現方法DynaMo和Louvain方法的社區劃分結果是近乎相同的。在拓撲圖中社區劃分近乎相同，它的Modularity也是近乎相同的，因此社區發現方法對本文所提方法的影響很小。

表3　社區發現算法對本文方法性能的影響

4.4.3社區改變閾值對本文方法性能的影響

表4　閾值θ對本文方法性能的影響

5 結語

為了提高社區演化分析結果的準確性，本文提出一種基于社區改變量估計的非均勻時間片劃分方法。該方法基于時間序列分析模型來預測網絡更新后正確社區劃分下期望獲得的模塊度，通過求解該模塊度值與保持原有社區劃分情況下可獲得的模塊度之差來估計網絡更新后社區改變的程度，一旦社區改變程度超過某個閾值，就會生成一個新的時間片。真實網絡數據集上的實驗結果表明，本文方法優于均勻時間片劃分方法和基于網絡拓撲變化量的非均勻時間片劃分方法。在相同數量的時間片情況下，本文方法能夠更及時地識別社區形成和社區消失事件，并發現更多數量的社區縮小和社區擴大事件，有效提高社區演化分析結果的準確性。

[1] YAN J， LIU G. Two-stage anomaly detection algorithm via dynamic community evolution in temporal graph［J］. Applied Intelligence， 2022， 52（11）： 12222-12240.

[2] JIA X， LI X， DU N， et al. Tracking community consistency in dynamic networks： an influence-based approach［J］. IEEE Transactions on Knowledge and Data Engineering， 2019， 33（2）： 782-795.

[3] PENG H， LI J， SONG Y， et al. Streaming social event detection and evolution discovery in heterogeneous information networks［J］. ACM Transactions on Knowledge Discovery from Data， 2021， 15（5）： No.89.

[4] HU Y， YANG B， LV C. A local dynamic method for tracking communities and their evolution in dynamic networks［J］. Knowledge-Based Systems， 2016， 110： 176-190.

[5] SUN P G， QUAN Y N， MIAO Q G， et al. Identifying influential genes in protein-protein interaction networks［J］. Information Sciences， 2018， 454/455： 229-241.

[6] FREILICH R， ARHAR T， ABRAMS J L， et al. Protein-protein interactions in the molecular chaperone network［J］. Accounts of Chemical Research， 2018， 51（4）： 940-949.

[7] LUO Y， MA J. The influence of positive news on rumor spreading in social networks with scale-free characteristics［J］. International Journal of Modern Physics C， 2018， 29（9）： No.1850078.

[8] JIA J， WU W. A rumor transmission model with incubation in social networks［J］. Physica A： Statistical Mechanics and its Applications， 2018， 491： 453-462.

[9] 陳小強，周麗華，程超，等. 動態網絡中穩定社區發現［J］. 小型微型計算機系統， 2015， 36（9）： 1977-1981.（CHEN X Q， ZHOU L H， CHENG C， et al. Detecting stable communities in dynamic networks［J］. Journal of Chinese Computer Systems， 2015， 36（9）： 1977-1981.）

[10] DAKICHE N， TAYEBA F B S， SLIMANI Y， et al. Tracking community evolution in social networks： a survey［J］. Information Processing and Management， 2019， 56（3）： 1084-1102.

[11] TAJEUNA E G， BOUGUESSA M， WANG S. Modeling and predicting community structure changes in time-evolving social networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 31（6）： 1166-1180.

[12] SAGANOWSKI S， BRóDKA P， KAZIENKO P. Influence of the dynamic social network timeframe type and size on the group evolution discovery［C］// Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway： IEEE， 2012： 679-683.

[13] KADKHODA MOHAMMADMOSAFERI K， NADERI H. Evolution of communities in dynamic social networks： an efficient map-based approach［J］. Expert Systems with Applications， 2020， 147： No.113221.

[14] PAN Y， ZHANG L. Modeling and analyzing dynamic social networks for behavioral pattern discovery in collaborative design［J］. Advanced Engineering Informatics， 2022， 54： No.101758.

[15] GUO C， WANG J， ZHANG Z. Evolutionary community structure discovery in dynamic weighted networks［J］. Physica A： Statistical Mechanics and its Applications， 2014， 413： 565-576.

[16] LI W， ZHU H， LI S， et al. Evolutionary community discovery in dynamic social networks via resistance distance［J］. Expert Systems with Applications， 2021， 171： No.114536.

[17] ORMAN G K， ?OLAK S. Similarity based compression ratio for dynamic network modelling［C］// Proceedings of the IEEE 19th International Conference on Smart Technologies. Piscataway： IEEE， 2021： 227-232.

[18] SULO R， BERGER-WOLF T， GROSSMAN R. Meaningful selection of temporal resolution for dynamic networks［C］// Proceedings of the 8th Workshop on Mining and Learning with Graphs. New York： ACM， 2010： 127-136.

[19] ROSSETTI G， CAZABET R. Community discovery in dynamic networks： a survey［J］. ACM Computing Surveys， 2018， 51（2）： No.35.

[20] WANG Y， ARCHAMBAULT D， HALEEM H， et al. Nonuniform timeslicing of dynamic graphs based on visual complexity［C］// Proceedings of the 2019 IEEE Visualization Conference. Piscataway： IEEE， 2019： 1-5.

[21] BHAT S Y， ABULAISH M. HOCTracker： tracking the evolution of hierarchical and overlapping communities in dynamic social networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2015， 27（4）： 1019-1031.

[22] WANG Z， LI Z， YUAN G， et al. Tracking the evolution of overlapping communities in dynamic social networks［J］. Knowledge-Based Systems， 2018， 157： 81-97.

[23] QIAO S， HAN N， GAO Y， et al. Dynamic community evolution analysis framework for large-scale complex networks based on strong and weak events［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2021， 51（10）： 6229-6243.

[24] XU Z， RUI X， HE J， et al. Superspreaders and superblockers based community evolution tracking in dynamic social networks［J］. Knowledge-Based Systems， 2020， 192： No.105377.

[25] ?OLAK S， ORMAN G K. Aggregating time windows for dynamic network extraction［C］// Proceedings of the 2021 International Conference on Innovations in Intelligent Systems and Applications. Piscataway： IEEE， 2021： 1-6.

[26] ORMAN G K， TüRE N， BALCISOY S， et al. Finding proper time intervals for dynamic network extraction［J］. Journal of Statistical Mechanics： Theory and Experiment， 2021， 2021（3）： No.033414.

[27] GIRVAN M， NEWMAN M E J. Community structure in social and biological networks［J］. Proceedings of the National Academy of Sciences of the United States of America， 2002， 99（12）： 7821-7826.

[28] BLONDEL V D， GUILLAUME J L， LAMBIOTTE R， et al. Fast unfolding of communities in large networks［J］. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008（10）： No.P10008.

[29] RAGHAVAN U N， ALBERT R， KUMARA S. Near linear time algorithm to detect community structures in large-scale networks［J］. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2007， 76（3）： No.036106.

[30] BRóDKA P， SAGANOWSKI S， KAZIENKO P. Tracking group evolution in social networks［C］// Proceedings of the 2011 International Conference on Social Informatics， LNCS 6984. Berlin： Springer， 2011： 316-319.

[31] WHEELWRIGHT S， MAKRIDAKIS S， HYNDMAN R J， Forecasting： Methods and Applications［M］. Hoboken， NJ： John Wiley & Sons， 2008： 335-346.

[32] NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks［J］. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2004， 69（2）： No.026113.

[33] LESKOVEC J， KREVL A. High-energy physics citation network［DS/OL］. ［2021-12-15］.http：//snap.stanford.edu/data/cit-HepPh.html.

[34] LESKOVEC J， KREVL A. Math overflow temporal network［DS/OL］. ［2021-12-15］.http：//snap.stanford.edu/data/sx-mathoverflow.html.

[35] ZHUANG D， CHANG J M， LI M. DynaMo： dynamic community detection by incrementally maximizing modularity［J］. IEEE Transactions on Knowledge and Data Engineering， 2021， 33（5）： 1934-1945.

Nonuniform time slicing method based on prediction of community variance

LUO Xiangyu1*， YAN Ke1， LU Yan1， WANG Tian1， XIN Gang2

（1，’，’710054，；2’，’710119，）

Time slicing methods in dynamic networks greatly influence the accuracy of community evolution analysis results. As communities vary nonlinearly with time and network topology， both the existing uniform time slicing method and network topology variance-based nonuniform time slicing method are unsatisfactory in capturing community evolution events. Therefore， a nonuniform time slicing method based on prediction of community variance was proposed， where the community variance is quantitatively described by the difference between the community modularity expected to be achieved by the updated network and the community modularity obtained by directly applying the community detection results of the network before changing. Firstly， the prediction model of community modularity was established on the basis of time series analysis. Secondly， with the established model， the expected community modularity of the updated network was predicted， and the prediction value of community variance was obtained. Finally， once the prediction value surpassed a previously set threshold， a new time slice was generated. Experimental results on two real network datasets show that compared with the traditional uniform time slicing method and the nonuniform time slicing method based on network topology variance， on the dynamic network dataset Arxiv HEP-PH， the proposed method identifies community disappearance events 1.10 days and 1.30 days earlier， respectively， and identifies the community forming events 8.34 days and 3.34 days earlier， respectively， and the total number of identified community shrinking and growing events increased by 10 and 1 respectively. On Sx?MathOverflow dataset， the proposed method identifies community disappearance events 3.30 days and 1.80 days earlier， and identifies the community forming events 6.41 days and 2.97 days earlier respectively， and the total number of identified community shrinking and growing events increased by 15 and 7， respectively.

dynamic network; time slicing; community evolution; time series analysis; community detection; community modularity

1001-9081（2023）11-3457-07

10.11772/j.issn.1001-9081.2022111736

2022?11?22；

2023?02?27；

國家自然科學基金資助項目（12071367）； 陜西省基礎研究計劃面上項目（2022JM?317）。

羅香玉（1984—），女，河北邢臺人，副教授，博士，CCF會員，主要研究方向：圖計算、復雜網絡； 閆克（1994—），男，河南南陽人，碩士研究生，主要研究方向：社區演化分析； 盧琰（1998—），女，河南駐馬店人，碩士研究生，主要研究方向：社區演化分析、傳播動力學分析； 王甜（1999—），女，陜西寶雞人，碩士研究生，主要研究方向：社區演化分析、傳播動力學分析； 辛剛（1984—），男，陜西寶雞人，高級工程師，碩士，主要研究方向：機器學習、大數據。

TP391

A

2023?03?08。

This work is partially supported by National Natural Science Foundation of China （12071367）， Program of Basic Natural Science of Shaanxi Province （2022JM-317）.

LUO Xiangyu， born in 1984， Ph. D.， associate professor. Her research interests include graph computing， complex network.

YAN Ke， born in 1994， M. S. candidate. His research interests include community evolution analysis.

LU Yan， born in 1998， M. S. candidate. Her research interests include community evolution analysis， analysis of spreading dynamics.

WANG Tian， born in 1999， M. S. candidate. Her research interests include community evolution analysis， analysis of spreading dynamics.

XIN Gang， born in 1984， M. S.， senior engineer. His research interests include machine learning， big data.