网络是呈现复杂系统的一种有效方法。学者们将那些包含庞大数量的节点和由这些繁多节点连接起来的边组合在一起的最终形态称为复杂网络。与常规网络相比,大规模复杂系统网络(如社交网络、交通系统、工程基础设施等)的通用结构特性更不寻常。按照性质的不同,复杂网络可以分为许多个由节点和边组成的聚类簇或模块,这些聚类簇模块也可称为社区。复杂网络聚类有助于学者们开展挖掘复杂网络结构、研究复杂网络的内在属性及预测复杂网络趋势等方面的工作。由于密度聚类算法可以在不预先知道其包含的聚类数量的情况下找到不规则形状的聚类和聚类数据,因此更适用于现实世界中的复杂网络。SCAN算法是密度聚类算法中的典型代表,然而该算法的时间复杂度过高,并不适用于大规模复杂网络。为了处理大规模复杂网络中的社区结构,本文提出一种基于SCAN算法的密度聚类算法——QSCAN算法。为了减少算法的时间复杂度,本文引入了新的数据集D,D是给定节点的所有双层节点集合。QSCAN算法通过使用以下两种方法保持聚类的高效性。首先,为了降低算法的时间复杂度,它仅仅计算数据集D中相邻节点的节点相似性;其次,通过数据集D的一部分已知节点相似度,它也可以有效计算出整个数据集中的节点相似度。因此,QSCAN算法可以在节省时间的情况下从大规模图中检测到与SCAN算法完全相同聚类,在聚类初步完成后QSCAN算法将不属于此聚类簇的剩余节点重新分类为孤立点与噪音点。