一种复杂网络重叠社区检测算法

复杂网络可以用来描述互联网、社会关系网络、生物网络、通信网络、WWW等。随着对复杂网络的深入研究，研究者们发现很多实际网络中都具有社区结构，而且社区间存在彼此重叠和相互关联特性。作为研究复杂网络结构的基础，重叠社区划分已成为复杂网络研究的关键问题。 在复杂网络结构中，边反映的是网络中节点之间的互动、合作、相互影响等关系，其只能属于一个社区。因此，利用边特性实现社区划分，可以使划分结果更真实地反映节点在复杂网络中的角色和功能。基于这种考虑，本文提出一种基于边的复杂网络重叠社区检测算法（Spectral Analysis Based on Edge Clustering，SAEC）。算法将社区看作是由边组成的集合，将原始网络中的边表示成线图中的节点。根据基于概率转移矩阵的谱聚类的基本原理，定义节点的相似度并构造核矩阵，得到概率转移矩阵，计算概率转移矩阵的特征值和特征向量，找到最大特征区间对应的k值，提取前k个特征向量，结合K-Means算法进行边聚类，根据聚类结果得到边社区和社区间的重叠节点。 为了验证算法的性能，本文选择在空手道网络、海豚社会网络、词关联网络、科学家合著网等真实网络上进行测试，并与NEWMAN快速算法、CPM、EAGLE、基于边的层次聚类等算法在划分结果、划分精度和运行时间方面进行对比分析。实验结果表明，本文算法能正确实现复杂网络重叠社区划分，并具有较低的时间复杂度。