基于相似度的加权复杂网络社区发现方法  

Detecting community in weighted complex network based on similarities

作　　者：王坤[1] 吕光宏[1] 梁召伟 叶茂莹[2] 

机构地区：[1]四川大学计算机学院,成都610065 [2]上海师范大学数理学院,上海200235

出　　处：《四川大学学报（自然科学版）》2014年第6期1170-1176,共7页Journal of Sichuan University(Natural Science Edition)

基　　金：国家"863"高技术发展计划项目(2008AA01Z105)

摘　　要：针对加权复杂网络中的社区结构发现问题,本文定义基于权重关系的相似度,并在此基础上定义了节点中心度和归属度,改进GN算法的模块度评价函数,提出一种基于相似度的中心聚类算法(SCC).该算法通过计算节点间的相似度,选取合理的中心度大的节点作为社区中心节点,最后基于节点归属度来聚集从而形成社区;同时,提出了用相似度代替边介数的改进GN算法SGN.通过理论分析,并在数据集上进行实验验证,结果表明SCC算法与WGN算法、SGN算法相比,速度和精度上均有较大改善.同时与I2C算法相比,社区的划分有效性更好.To detect communities in weighted complex network, this paper defines a local similarity with weighted value, putting forward the node＇s centrality degree and belonging degree, improving the mod- ularity function of the GN algorithm, and propose a central cluster algorithm based on similarity（SCC）. This algorithm refer to use the node＇s belonging degree to cluster nodes to construct communities after calculating the similarities of nodes and selecting the suitable and the larger centrality degree. Mean- while, this paper proposes a new GN algorithm based on similarity （SGN）, which substituted between- ness for similarity. After the theoretical analysis and the experimental verification based on dataset, shows that SCC algorithm has improvement in speed and accuracy compared with WGN and SGN algo- rithms. And the SCC algorithm has better community division compared with I^2C algorithm.

关 键 词：加权复杂网络 社区发现 相似度 SCC算法 SGN算法 

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]