复杂网络半监督的社区发现算法研究

随着大数据时代的到来,复杂网络的社区发现已成为一个重要研究方向。层次聚类算法作为社区发现的经典算法受到了广泛应用,然而该算法具有较高的时间复杂度和较低的运行效率。为提高社区发现算法的运行效率,提出了一种基于节点相似度的半监督社区发现新算法--SSGN算法。充分利用先验知识must-link、cannot-link约束集合,将先验信息通过衍生规则进行扩展,并对扩展的信息通过基于距离度量的方式加以验证。采用人工网络和真实网络进行验证,UCI 数据集和大型真实数据集上的实验结果表明, 基于节点相似度的半监督社区发现算法较其他半监督聚类算法更准确,也更高效。

Research algorithm of semi-supervised general community detection on complex networks

With the advent of the era of big data, complex network community detection has become an important research direction. Based on the similarity of the community detection methods attractions GN algorithm fast and accurate but has higher time complexity. In order to overcome the deficiency of GN efficiency, this paper presents a semi-supervised GN algorithm based on node similarity, takes full advantage of the known node, cannot link constraints, a priori information combined with the similarity information between nodes, and validated using artificial and real networks. It is proved that the algorithm proposed in this paper reduces the GN algorithm"s time complexity and improve the efficiency.