基于谱聚类的动态网络社区演化分析算法

Community Evolution Analysis Algorithm for Dynamic Networks Based on Spectral Clustering

针对复杂网络社区受到个体兴趣和迁移的影响随着时间推移而演化的问题,提出一种基于谱聚类的动态网络社区演化分析算法,试图揭示动态网络社区结构随时间的演变过程.算法融合当前时刻快照拓扑结构和上一时刻社区结构两个因素,并用随机分块模型和Dirichlet分布分别对上述两个因素建模,从而将社区演化分析形式化为优化问题.从理论上验证了社区演化分析与谱聚类是等价的,为利用谱聚类解决社区演化分析奠定理论基础.在合成数据集上的实验结果表明,相比于以规格化割为目标的谱聚类,所提方法能显著提升动态社区检测的准确性和稳定性.

Due to the transfer of individuals and changes in individuals′interests,communities are complex net-works that evolve over time.We present a community evolution analysis algorithm for dynamic networks with a basis in spectral clustering,so that the evolutionary processes of community structures over time can be re-vealed.A particular focus is placed upon consideration of current time-snapshot observations and upon com-munity evolution.By employing the stochastic block model and the Dirichlet distribution for modeling,the problem of community evolution is formulated as an optimization problem.Our theoretical proof that the com-munity evolution problem is equivalent to spectral clustering lays the theoretical foundation for adopting a spectral clustering framework-based solution for modeling community evolution.Experimental results on a syn-thetic data set show that our proposed method is superior to aspectral clustering approach that takes the nor-malized cut as its objective with regards to accuracy and the detection of the stability of dynamic communities.