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

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

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

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

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

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

動態(tài)網(wǎng)絡(luò)；時間片劃分；社區(qū)演化；時間序列分析；社區(qū)發(fā)現(xiàn)；社區(qū)模塊度

0 引言

近年來，社區(qū)演化分析已成為動態(tài)網(wǎng)絡(luò)的研究熱點［1-4］。它旨在發(fā)現(xiàn)動態(tài)網(wǎng)絡(luò)潛在的演化規(guī)律，為預(yù)測社區(qū)的演化行為提供依據(jù)和信息。社區(qū)演化分析在眾多領(lǐng)域都有廣泛的應(yīng)用。例如，應(yīng)用于蛋白質(zhì)交互網(wǎng)絡(luò)時［5-6］，可以根據(jù)已知的蛋白質(zhì)拓撲結(jié)構(gòu)和交互關(guān)系對未知蛋白質(zhì)的功能和行為進行預(yù)測；應(yīng)用于輿情監(jiān)測和引導(dǎo)時［7-8］，有助于掌握負面輿論的傳播路徑；應(yīng)用于公共衛(wèi)生領(lǐng)域時，可以為預(yù)測傳染病的傳播提供有價值的信息，提前制定應(yīng)對措施，防止傳染病蔓延［9］。

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

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

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

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

本文的主要工作如下：

1）分析現(xiàn)有時間片劃分方法導(dǎo)致社區(qū)演化分析結(jié)果不準確的原因。由于社區(qū)演化與時間、網(wǎng)絡(luò)拓撲改變量均呈非線性關(guān)系，均勻時間片劃分方法和基于網(wǎng)絡(luò)拓撲改變量的非均勻時間片劃分方法均會降低社區(qū)演化分析結(jié)果的準確性。

2）提出一種基于社區(qū)改變量估計的非均勻時間片劃分方法，其中社區(qū)改變量通過變化后網(wǎng)絡(luò)期望達到的社區(qū)模塊度與直接應(yīng)用網(wǎng)絡(luò)變化前的社區(qū)發(fā)現(xiàn)結(jié)果獲得的社區(qū)模塊度之差來定量描述。期望達到的社區(qū)模塊度則通過建立基于時間序列分析的社區(qū)模塊度預(yù)測模型進行估計。

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

1 相關(guān)工作

社區(qū)演化分析過程的三個階段相關(guān)工作分別總結(jié)如下。

1.1　時間片劃分

時間片劃分旨在將動態(tài)網(wǎng)絡(luò)離散化為一系列的快照。它對社區(qū)演化分析結(jié)果的準確性具有重要影響?，F(xiàn)有的動態(tài)網(wǎng)絡(luò)時間片劃分方法一般分為兩類［20］：均勻時間片劃分方法和非均勻時間片劃分方法。均勻時間片劃分方法采用固定時間間隔將動態(tài)網(wǎng)絡(luò)離散為若干個快照，因?qū)崿F(xiàn)機制簡單而被廣泛使用；非均勻時間片劃分方法則會將動態(tài)網(wǎng)絡(luò)離散為不等時間間隔的若干個快照，實現(xiàn)機制相對復(fù)雜。

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

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

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

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

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

1.2　社區(qū)發(fā)現(xiàn)

社區(qū)發(fā)現(xiàn)旨在找出每個網(wǎng)絡(luò)快照上的全部社區(qū)。現(xiàn)有研究主要包括三類方法：基于邊消除策略的方法、基于社區(qū)質(zhì)量指標優(yōu)化策略的方法以及基于標簽傳播策略的方法?；谶呄呗缘姆椒ㄍㄟ^逐一識別和消除社區(qū)之間的邊，將網(wǎng)絡(luò)劃分為若干社區(qū)，代表性算法是GN（Girvan-Newman算法）［27］；基于社區(qū)質(zhì)量指標優(yōu)化策略的方法定義模塊度等度量指標評價社區(qū)質(zhì)量，通過不斷優(yōu)化度量指標進行社區(qū)發(fā)現(xiàn)，代表性算法是Louvain算法［28］；基于標簽傳播策略的方法先把每個節(jié)點的標簽傳播給它的鄰居節(jié)點，然后該節(jié)點獲取鄰居節(jié)點的標簽從而更新自身標簽，重復(fù)上述標簽傳播過程，最后各節(jié)點根據(jù)標簽獲得所屬社區(qū)，代表性算法是LPA（Label Propagation Algorithm）［29］。

1.3　社區(qū)演化事件識別

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

2 問題描述

2.1　基本術(shù)語

時間片劃分點：為動態(tài)網(wǎng)絡(luò)建立快照的每個時刻稱為一個時間片劃分點。兩個相鄰時間片劃分點決定一個時間片的長度。因此，時間片劃分結(jié)果可以表示為一系列時間片劃分點的集合。

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

2.2　非均勻時間片劃分問題

3 非均勻時間片劃分方法

3.1　主要思想

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

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

輸出。

4） forfrom 1 todo

11） end if

12） end for

13） return

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

3.3　模塊度預(yù)測模型訓(xùn)練方法

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

算法2 獲取訓(xùn)練集數(shù)據(jù)。

輸出 社區(qū)模塊度值的時間序列。

3） forfrom 0 todo

8） end for

9） return

基于訓(xùn)練數(shù)據(jù)集和模型參數(shù)、和，獲得ARIMA模塊度預(yù)測模型。模型公式如下：

3.4　時間復(fù)雜度分析

4 實驗與結(jié)果分析

4.1　實驗環(huán)境

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

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

4.2　數(shù)據(jù)集

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

表 1　數(shù)據(jù)集描述

4.3　對比方法與評價指標

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

1）均勻時間片劃分方法。采用固定時間窗口長度將動態(tài)網(wǎng)絡(luò)數(shù)據(jù)離散化為若干個網(wǎng)絡(luò)快照。

2）基于網(wǎng)絡(luò)拓撲改變量的非均勻時間片劃分方法（簡稱為基于網(wǎng)絡(luò)拓撲改變量的劃分方法）。利用動態(tài)網(wǎng)絡(luò)變化前后邊集的Jaccard系數(shù)［19］計算網(wǎng)絡(luò)拓撲的改變量，當(dāng)網(wǎng)絡(luò)拓撲改變量超過預(yù)先設(shè)置的閾值時生成一個新的時間片，最后獲得時間片劃分結(jié)果。

4.4　實驗結(jié)果

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

基于所實現(xiàn)的社區(qū)演化分析系統(tǒng)，分別采用三種時間片劃分方法對兩種動態(tài)網(wǎng)絡(luò)數(shù)據(jù)集進行社區(qū)演化分析，然后計算評價指標完成時間片劃分方法的比較。實驗?zāi)康氖球炞C基于社區(qū)改變量估計的非均勻時間片劃分方法的優(yōu)越性。

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

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

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

圖2顯示了Arxiv HEP-PH數(shù)據(jù)集中1995年4月30日網(wǎng)絡(luò)快照的一部分。圖中虛線框內(nèi)的節(jié)點表示該快照上的一個社區(qū)?；诒疚乃岢鰰r間片劃分方法的社區(qū)演化分析結(jié)果表明，該社區(qū)消失的日期是1995年5月11日；但使用其他兩種時間片劃分方法情況下，社區(qū)演化分析結(jié)果中該社區(qū)消失的日期分別是1995年5月12日和1995年5月15日。

圖 2　1995年4月30日網(wǎng)絡(luò)快照上的一個社區(qū)

圖3顯示了在Arxiv HEP-PH數(shù)據(jù)集中1995年6月1日網(wǎng)絡(luò)快照的一部分。圖中虛線框內(nèi)的節(jié)點表示該快照上的一個社區(qū)?；诒疚乃岢鰰r間片劃分方法的社區(qū)演化分析結(jié)果表明，該社區(qū)形成的日期是1995年6月1日；但使用其他兩種時間片劃分方法情況下，社區(qū)演化分析結(jié)果中該社區(qū)生成的日期分別是1995年6月8日和1995年6月18日。

4.4.2社區(qū)發(fā)現(xiàn)算法對本文方法性能的影響

為了直觀驗證社區(qū)發(fā)現(xiàn)方法對所提方法性能影響的程度，以增量式社區(qū)發(fā)現(xiàn)方法DynaMo［35］和Louvain方法為例，驗證所提方法的執(zhí)行結(jié)果，其中均設(shè)置為0.02，實驗結(jié)果如表3所示。

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

表3　社區(qū)發(fā)現(xiàn)算法對本文方法性能的影響

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

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

5 結(jié)語

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

[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] 陳小強，周麗華，程超，等. 動態(tài)網(wǎng)絡(luò)中穩(wěn)定社區(qū)發(fā)現(xiàn)［J］. 小型微型計算機系統(tǒng)， 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；

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

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

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.