·430 智能系统学报 第11卷 表2不同数据集上聚类结果的比较 Table 2 The comparison of the clustering results among different datasets 数据集 顶点数 边数 原始社区个数 算法 聚类个数 未聚类节点数 Q 运行时间/ms BDSG 2 0.8205 93 CPM 3 22 0.1923 87 空手道 俱乐部 304 78 k-dense 2 22 0.2948 129 CPM+CE 3 3 0.4102 117 k-dense+CE 0.8205 165 BDSG 0 0.7735 149 CPM 4 34 0.4088 175 海豚 社交网络 159 k-dense 4 34 04088 568 CPM+CE 4 16 0.5911 202 k-dense+CE 16 0.5911 599 BDSG 12 0 0.6390 480 CPM 13 2 0.5951 920 大学生 115 613 k-dense 12 2 0.6370 足球网络 1860 CPM+CE 13 0 0.6010 1028 k-dense+CE 12 0 0.6480 1986 BDSG 28 34 0.7224 60797 CPM 55 562 0.2687 592410 电子 邮件网络 11335451 k-dense 6 558 0.2517 55240 CPM+CE 55 341 0.2897 601835 k-dense+CE 6 14 0.5034 63938 BDSG 134 657 0.7828 21273 CPM 159 843 0.5201 97161 合作网络 1589 2742 k-dense 91 843 0.7305 15352 CPM+CE 159 688 0.5675 120927 A-dense+CE 91 790 0.7631 23451 实验结果表明BDSG算法在这些网络数据上均 类性能。实验结果（见表2）表明CPM与k-dense算 具有较好的性能表现。BDSG算法在空手道俱乐部 法的聚类有效性均显著提高。在空手道俱乐部、海 和大学生足球网络上所得到社区个数与网络实际的 豚社交网络、电子邮件网络和合作网络中，在CPM 社区个数相同，而电子邮件网络和合作网络缺乏原 与k-dense算法运行时间略有增大的情况下，CE算 始社区个数信息，无法进行比较：海豚社交网络和大 法的加入使得其未聚类结点个数降幅较大，社区模 学生足球网络中，BDSG算法所用时间明显少于 块性具有较为明显的提高。同时CPM与k-dense算 CPM与k-dense算法：在电子邮件网络和合作网络 法在加入扩展策略CE之后与BDSG算法相比， 中，BDSG运行时间比k-dense算法慢，但最终未聚 BDSG算法在未聚类结点数以及社区模块性方面优 类结点数少于k-dense算法：在这些实验数据集上， 势依然较为明显。 本算法所产生的未聚类结点个数明显较少、社区模 综上所述，BDSG算法在空手道俱乐部、海豚社 块性较高。 交网络、大学生足球网络、电子邮件网络和合作网络 此外，本文给出的中心社区扩展算法也可应用 等数据集上，与CPM、k-dense算法相比运行时间较 于CPM、k-dense等算法以处理未聚类节点，提高聚 短、未聚类结点个数较少、社区模块性较高，具有良表 ２ 不同数据集上聚类结果的比较 Ｔａｂｌｅ ２ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ａｍｏｎｇ ｄｉｆｆｅｒｅｎｔ ｄａｔａｓｅｔｓ 数据集 顶点数 边数 原始社区个数 算法 聚类个数 未聚类节点数 Ｑ 运行时间／ ｍｓ 空手道 俱乐部 ３４ ７８ ２ ＢＤＳＧ ２ １ ０．８２０ ５ ９３ ＣＰＭ ３ ２２ ０．１９２ ３ ８７ ｋ⁃ｄｅｎｓｅ ２ ２２ ０．２９４ ８ １２９ ＣＰＭ＋ＣＥ ３ ３ ０．４１０ ２ １１７ ｋ⁃ｄｅｎｓｅ＋ＣＥ ２ １ ０．８２０ ５ １６５ 海豚 社交网络 ６２ １５９ ２ ＢＤＳＧ ４ ０ ０．７７３ ５ １４９ ＣＰＭ ４ ３４ ０．４０８ ８ １７５ ｋ⁃ｄｅｎｓｅ ４ ３４ ０４０８ ８ ５６８ ＣＰＭ＋ＣＥ ４ １６ ０．５９１ １ ２０２ ｋ⁃ｄｅｎｓｅ＋ＣＥ ４ １６ ０．５９１ １ ５９９ 大学生 足球网络 １１５ ６１３ １２ ＢＤＳＧ １２ ０ ０．６３９ ０ ４８０ ＣＰＭ １３ ２ ０．５９５ １ ９２０ ｋ⁃ｄｅｎｓｅ １２ ２ ０．６３７ ０ １ ８６０ ＣＰＭ＋ＣＥ １３ ０ ０．６０１ ０ １ ０２８ ｋ⁃ｄｅｎｓｅ＋ＣＥ １２ ０ ０．６４８ ０ １ ９８６ 电子 邮件网络 １ １３３ ５ ４５１ — ＢＤＳＧ ２８ ３４ ０．７２２ ４ ６０ ７９７ ＣＰＭ ５５ ５６２ ０．２６８ ７ ５９２ ４１０ ｋ⁃ｄｅｎｓｅ ６ ５５８ ０．２５１ ７ ５５ ２４０ ＣＰＭ＋ＣＥ ５５ ３４１ ０．２８９ ７ ６０１ ８３５ ｋ⁃ｄｅｎｓｅ＋ＣＥ ６ １４ ０．５０３ ４ ６３ ９３８ 合作网络 １ ５８９ ２ ７４２ — ＢＤＳＧ １３４ ６５７ ０．７８２ ８ ２１ ２７３ ＣＰＭ １５９ ８４３ ０．５２０ １ ９７ １６１ ｋ⁃ｄｅｎｓｅ ９１ ８４３ ０．７３０ ５ １５ ３５２ ＣＰＭ＋ＣＥ １５９ ６８８ ０．５６７ ５ １２０ ９２７ ｋ⁃ｄｅｎｓｅ＋ＣＥ ９１ ７９０ ０．７６３ １ ２３ ４５１ 实验结果表明 ＢＤＳＧ 算法在这些网络数据上均 具有较好的性能表现。 ＢＤＳＧ 算法在空手道俱乐部 和大学生足球网络上所得到社区个数与网络实际的 社区个数相同，而电子邮件网络和合作网络缺乏原 始社区个数信息，无法进行比较；海豚社交网络和大 学生足球网络中，ＢＤＳＧ 算法所用时间明显少于 ＣＰＭ 与 ｋ⁃ｄｅｎｓｅ 算法；在电子邮件网络和合作网络 中，ＢＤＳＧ 运行时间比 ｋ⁃ｄｅｎｓｅ 算法慢，但最终未聚 类结点数少于 ｋ⁃ｄｅｎｓｅ 算法；在这些实验数据集上， 本算法所产生的未聚类结点个数明显较少、社区模 块性较高。 此外，本文给出的中心社区扩展算法也可应用 于 ＣＰＭ、ｋ⁃ｄｅｎｓｅ 等算法以处理未聚类节点，提高聚 类性能。 实验结果（见表 ２）表明 ＣＰＭ 与 ｋ⁃ｄｅｎｓｅ 算 法的聚类有效性均显著提高。 在空手道俱乐部、海 豚社交网络、电子邮件网络和合作网络中，在 ＣＰＭ 与 ｋ⁃ｄｅｎｓｅ 算法运行时间略有增大的情况下，ＣＥ 算 法的加入使得其未聚类结点个数降幅较大，社区模 块性具有较为明显的提高。 同时 ＣＰＭ 与 ｋ⁃ｄｅｎｓｅ 算 法在加入扩展策略 ＣＥ 之后与 ＢＤＳＧ 算法相比， ＢＤＳＧ 算法在未聚类结点数以及社区模块性方面优 势依然较为明显。 综上所述，ＢＤＳＧ 算法在空手道俱乐部、海豚社 交网络、大学生足球网络、电子邮件网络和合作网络 等数据集上，与 ＣＰＭ、ｋ⁃ｄｅｎｓｅ 算法相比运行时间较 短、未聚类结点个数较少、社区模块性较高，具有良 ·４３０· 智 能 系 统 学 报 第 １１ 卷