基于结构与属性的社区划分方法.PDFVIP

第27卷摇 第8期 计 算机 技 术 与发 展 Vol.27摇 No.8 2017年8月 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 COMPUTERTECHNOLOGY AND DEVELOPMENT摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 Aug. 摇 2017 基于结构与属性的社区划分方法 万新贵,李玲娟 (南京邮电大学计算机学院,江苏 南京210003) 摘摇 要:目前通行的社区划分方法大多基于结构,但单纯基于结构的划分不能挖掘出社区对象的潜在关系,因而不能发现 社区的变化趋势。 为此,提出了基于结构的社区划分算法(Community Division based on Structure,CDS)。 该算法利用度和 节点欧氏距离对社会网络进行结构划分;同时针对经典 -means算法在社区划分中所存在的随机选取初始中心点以及 K k 值选取不合理所导致的聚类结果不佳问题,提出了一种基于社区结构的非人为设定 值的 -means算法—NPCluster(Non k K Presetting Cluster)算法。 该算法基于由CDS算法所提到的社区结构,依次选取度最大的节点作为聚类中心点,以小于平均 特征欧氏距离为基准合并簇集,反复迭代直至聚类完成。 理论分析和对比实验结果表明,CDS算法能够有效划分出社区 结构;相对于 -means算法,NPCluster算法在已划分的社区结构上具有更高的聚类精度和更好的时效性;结构与属性相 K 结合的社区划分方法是有效可行的。 关键词:社区划分;度; -means;中心点;欧氏距离 K 中图分类号:TP301摇 摇 摇 摇 摇 摇 摇 文献标识码:A摇 摇 摇 摇 摇 摇 文章编号:1673-629X(2017)08-0097-05 doi:10.3969/j.issn.1673-629X.2017.08.020 Community Division Method with Structure and Attribute WAN Xin-gui,LI Ling-juan (School of Computer,Nanjing University of Postsand Telecommunications, Nanjing210003,China) Abstract:Most of thecurrentmethodsofcommunity divisionarebasedon structure,butthe structure-baseddivision cannot excavatethe potential relationship of community objects,which isnot to find the tendencies of community variations.Therefore a community-based partitioningalgorithm (Community Divisionbased on Structure,CDS)hasbeen designedwhich appliesdegreeandnode-Euclidean dis鄄 tance to divide social network.Simultaneo