TSCAN:利用并行策略改进的图结构聚类算法

• 作者: 乔少杰 李振军 李荣华 毛睿 陈亚中
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 社区探测 结构聚类算法 重叠社区 OpenMP 并行算法
• 年，卷（期）: 2019,（1）
• 所属期刊栏目: 大数据与云计算
• 页码范围: 76-83,114
• 页数: 9页
• 分类号: TP302.8
• 字数: 6610字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1710-0230

摘要

近年来,图数据聚类在学术界引起了广泛的关注,许多优秀的聚类方法,如模块度优化算法、谱聚类,以及基于密度的聚类算法在图数据上取得了很好的效果.SCAN是一种著名的基于密度的图聚类算法,该算法不仅能够找出图中的聚类,而且还能够发现不同聚类间的Hub节点,以及图中的离群点.然而,该算法存在两方面的局限性:首先,在大规模图数据上,该算法需要耗费大量的时间用于计算图中每条边的结构相似性;另一方面,该算法存在两个参数ε和μ ,并且对这两个参数比较敏感.为了解决其局限性,提出了一种基于OpenMP的并行算法来求解节点相似性,并且提出了两种有效的负载均衡策略;其次,提出一种基于三角形的新型图结构聚类算法TSCAN.该模型能够有效降低算法对参数的敏感性,而且还能够发现重叠以及更稠密的社区.在多个大规模数据集上实验发现,基于多核的并行算法能够达到近乎线性的加速比,而且TSCAN算法对参数不敏感,能有效发现重叠社区.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	毛睿	深圳大学计算机与软件学院	18	81	5.0	8.0
2	乔少杰		34	171	6.0	12.0
3	陈亚中	深圳大学计算机与软件学院	1	0	0.0	0.0
4	李振军	深圳大学计算机与软件学院	4	11	2.0	3.0
5	李荣华	深圳大学计算机与软件学院	4	16	3.0	4.0