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

来源：计算机工程与应用杂志2019年第1期北京时间：

作者：陈亚中1，李振军1，李荣华1，毛 睿1，乔少杰2

单位：1.深圳大学 计算机与软件学院，广东 深圳 518060；2.成都信息工程大学，成都 610103

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

关键词：社区探测,结构聚类算法,重叠社区,OpenMP,并行算法