基于社区改变量估计的非均匀时间片划分方法  

Nonuniform time slicing method based on prediction of community variance

作　　者：罗香玉[1] 闫克 卢琰 王甜 辛刚 LUO Xiangyu;YAN Ke;LU Yan;WANG Tian;XIN Gang(College of Computer Science and Technology,Xi’an University of Science and Technology,Xi’an Shaanxi 710054,China;AVIC Xi’an Aeronautics Computing Technique Research Institute,Xi’an Shaanxi 710119,China)

机构地区：[1]西安科技大学计算机科学与技术学院,西安710054 [2]中国航空工业集团公司西安航空计算技术研究所,西安710119

出　　处：《计算机应用》2023年第11期3457-3463,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(12071367);陕西省基础研究计划面上项目(2022JM-317)。

摘　　要：动态网络时间片划分方法对社区演化分析结果的准确性具有重要影响,但社区随时间及网络拓扑改变呈现非线性的变化,现有均匀时间片划分以及基于网络拓扑改变量的非均匀时间片划分方法在捕捉社区演化事件方面均效果不佳。为此,提出一种基于社区改变量估计的非均匀时间片划分方法,其中社区改变量通过变化后网络期望达到的社区模块度与直接应用网络变化前的社区发现结果获得的社区模块度之差来定量描述。首先,基于时间序列分析建立社区模块度预测模型;其次,使用该模型预测变化后网络期望达到的社区模块度,并求得社区改变量的估计值;最后,当该估计值超过预先设置的阈值时即生成一个新的时间片。在两个真实网络数据集上的实验结果显示,相较于传统的均匀时间片划分方法和基于网络拓扑改变量的非均匀时间片划分方法,所提方法在动态网络数据集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个。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.

关 键 词：动态网络 时间片划分 社区演化 时间序列分析 社区发现 社区模块度 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]