一种面向大规模社会信息网络的多层社区发现算法
社区发现旨在挖掘社会信息网络的社区结构,是社会计算及其相关研究的基础.随着交互式社会信息网络规模的快速增长,传统的社区发现算法难以满足大规模网络的可扩展分析需求.多层社区发现算法如PMetis、Graclus等虽然可以分析包含数百万节点规模的网络,但是小于1/2的粗化缩减比率以及社会信息网络的幂律分布特性极大地制约着该类算法的性能优势.本文提出了一种基于三角形内点同一社区性粗化策略的多层社区发现算法TMLCD.TMLCD不仅以大于1/2的粗化缩减比率加快了大规模社会信息网络的粗化过程,而且从基本拓扑结构上保持了初始网络的社区效应,提高了社区发现精度.基于真实网络如Youtube、Orkut等的实验结果表明,TMLCD的计算精度、内存占用以及运行时间均优于目前典型的多层社区发现算法,适用于富含三角形的社会信息网络分析.
社会信息网络 社区发现算法 计算精度 内存占用率 运行时间
康颖 于博 林政 周江 王伟平 孟丹
中国科学院信息工程研究所,北京,中国,100093;中国科学院大学,北京,中国,100049 中国科学院信息工程研究所,北京,中国,100093
国内会议
北京
中文
1-11
2014-12-01（万方平台首次上网日期，不代表论文的发表时间）