杨煜，段威威

基于谱聚类的社交网络动态社区发现算法

杨煜*，段威威

（电子科技大学 计算机科学与工程学院，成都 611731）（ ∗ 通信作者电子邮箱yangyu2022@std.uestc.edu.cn）

动态社区发现研究是社交网络分析（SNA）的重要研究领域。随着节点加入或离开社交网络，节点间的关系也随之建立或消失，进而影响着社区结构的变化。针对社交网络静态社区发现算法缺少必要的社区节点历史信息而导致的网络结构分析、聚类信息不足和计算开销过大的问题，基于社区网络演化事件的划分并根据主要社区事件的分析，提出一种基于谱聚类的动态社区发现算法（SC-DCDA）。首先，根据实验观察使用谱映射的方法将高维数据降维，并采用改进的模糊C-均值聚类（FCM）算法确定动态社交网络中的节点与待发现社区的关联度；其次，根据演化相似度矩阵分析社区结构。通过使用真实网络数据集以及模块度得分、轮廓系数等社区发现算法衡量指标，评估所提算法的效果。实验结果表明，SC-DCDA的计算开销相较于传统谱聚类降低了8.37%，在所有数据集上的平均模块度得分是0.49，其他衡量指标的定性分析结果也较好，验证了所提算法在信息交互、聚类效果和精确度上表现较好。

社交网络分析；动态社区发现算法；模糊C-均值聚类；演化相似度矩阵

0 引言

社区是社交网络中拓扑结构的重要研究对象，社区发现算法是社交网络分析（Social Network Analysis， SNA）的主要研究领域，研究社区发现算法有助于研究者深入学习社交网络的复杂拓扑结构及其社区行为特征。……