动态网络局部社区演化过程溯源方法

Local community evolution process tracing method in dynamic network

随着网络规模的增大,全局社区演化分析越来越困难。考虑在某些场景中人们只关心某一局部社区的形成过程,即局部社区演化过程溯源,提出一种动态网络局部社区演化过程溯源方法,包括社区形成时刻识别、候选前驱社区集合检测和社区演化关系分析这3个环节。通过构造真伪社区分类器识别前驱社区形成时刻,在前驱社区形成时刻的网络快照上进行社区检测,获得包含待溯源社区中任意顶点的候选前驱社区;利用演化事件模型找出真正的前驱社区并识别对应演化事件。在真实网络数据集上的实验结果表明,所提方法优于基于均匀时间片划分的溯源方法,得到的待溯源社区形成路径图能够与真实路径图精准匹配,即社区形成时刻、前驱社区和演化事件均识别准确。

As the network scale expands,global community evolution analysis becomes increasingly difficult.Considering that people only concentrate on the formation process of a certain local community which needs tracing local community evolution process in some scenarios,a local community evolution process tracing method in dynamic networks was proposed.The proposed method is composed of identification of community formation moments,detection of candidate precursor communities and analysis of community evolution relationships.The identification of precursor community formation moments was based on a true-false community classifier.Community detection was performed on the corresponding network snapshot at the moment when the precursor community was formed,and candidate precursor communities containing any vertices in the community to be traced were obtained.The community evolutionary event model was applied to determine the real precursor communities and the corresponding evolution relationships.Experimental results on real network dataset show that the proposed method outperforms the local community evolution tracing method based on uniform time slicing.The obtained path diagram of the communities to be traced can accurately match the real path diagram,meaning that at the community formation moments,precursor communities and evolutionary events are all identified accurately.