基于谱聚类的复杂网络社团发现算法  

Community-finding Algorithm in Complex Networks Based on Spectral Clustering

作　　者：蔡晓妍[1] 戴冠中[1] 杨黎斌[1] 

机构地区：[1]西北工业大学自动化学院,西安710072

出　　处：《计算机科学》2009年第9期49-50,95,共3页Computer Science

基　　金：国家863计划项目(2005AA147030)资助

摘　　要：复杂网络社团发现的研究对于控制疾病传播、网络病毒的传播等具有重大意义。针对已有社团发现算法时间复杂度过高,不适用于结构未知的大型网络等问题,结合谱聚类在识别未知分布数据集聚类方面的优势,以及模块度函数能够在大型网络中搜寻出最佳社团数目的能力,提出了基于谱聚类的社团发现算法——SCCF算法。实验结果表明,与已有的社团发现算法相比,SCCF算法效率更高,并且能够在网络节点数上万的大型网络中得到高质量的社团结构。Research on community finding is very helpful to control virus spreading in networks. Most of the proposed community-finding algorithms are not suitable for very large networks because of their time-complexity. Combined with the advantage of solving the clustering of unknown distributed data set of the spectral clustering,and the ability of modularity function in finding good community number in large networks, a community-finding algorithm based on spectral clustering was proposed. Experimental results indicate that the new algorithm is efficient and effective at finding good community structure in large networks.

关 键 词：复杂网络 社团结构 谱聚类 模块度 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TP393.08[自动化与计算机技术—计算机科学与技术]