Abstract:

Dynamic community discovery is an important research area in Social Network Analysis （SNA）. As nodes joining or leaving social networks， the relationships between nodes establish or terminate， which affects community structure changes. The discovery algorithms of static communities in social networks lack of the essential historical information of community nodes， resulting in the insufficient network structure analysis as well as clustering information and the high computational cost. Aiming at these problems， based on the division of the community network evolution events， according to the analysis of the major community events， a Spectral Clustering based Dynamic Community Discovery Algorithm （SC-DCDA） was proposed. Firstly， according to the experimental observation， the dimensionality of high-dimensional data was reduced by using the method of spectral mapping. At the same time， the improved Fuzzy C-Means clustering （FCM） algorithm was adopted to determine the correlation between the nodes in the dynamic social network and the communities to be discovered. Secondly， the community structures were analyzed according to the evolutionary similarity matrix. Finally， the real network datasets and community discovery algorithm indicators， such as modularity score and Silhouette coefficient， were used to evaluate the effects of the proposed algorithm. Experimental results show that the computational cost of SC-DCDA is reduced by 8.37% compared with traditional spectral clustering， the average modularity score of the algorithm on all datasets is 0.49， and the qualitative analysis results of other algorithm metrics are also good， indicating that the proposed algorithm performs well in information interaction， clustering effect， and accuracy.

Key words: Social Network Analysis (SNA), dynamic community discovery algorithm, Fuzzy C-Means clustering (FCM), evolutionary similarity matrix

摘要：

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

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