.428 智能系统学报 第11卷 C中相邻点的集合，k,是结点的度。然而结点 α=1（此时重要度对聚类结果不产生影响）时的未 与社区C的关联强度不仅与关联边数有关，也和社 聚类结点数(subordinate vertices)和模块性的比较结 区C中v的相邻点在C中的重要性关系密切。 果，表明通过重要度定义的归属度能够更加准确地 如图1所示，当前聚类结果得到两个社区 表示节点和社区的关系。 C,(▲)和C2(■)，其余结点为未聚类结点。 表1不同x值时聚类结果的比较 Table 1 The comparison of the clustering results among 考虑结点g,可得b(g,C1)=bn(g,C2), different a N,nC,={u33,34},且Ng∩C2={w1,3}。此 未聚类节点 0 时，社区C,中与结点。相邻结点的点介数比 数据集 a=0.8 a=1 ax=0.8 a=1 ∑ 、B(u) 例为 e{e33,34} -=0.95,而社区C2中 空手道 3 0.8205 0.7179 ∑.c,B(o) 俱乐部 与结点，相邻结点的点介数比例为 海豚 0 0.77350.7610 社交网络 =0.83。由于结点，在C,中的相 大学生 ∑.ecBo） 0 0 0.6390 0.6150 足球网络 邻点在网络中重要性更高，可以认为，更倾向归属 电子 于社区C1 34 41 0.72240.7151 邮件网络 合作网络 657 661 0.78280.6473 3基于稠密子图的社区发现算法 基于稠密子图的社区发现算法(BDSG)主要由 2部分构成：首先通过搜索网络中大于指定密度阈 值d的稠密子图得到网络中心社区，确定聚类个数 k,不属于任何一个中心社区的结点为未聚类结点； 图1空手道俱乐部中未聚类结点分析 根据式(2)计算未聚类结点与已有社区的归属度， Fig.1 The analysis of subordinate vertices in zachary's 将一些未聚类结点划分到归属度大于指定阈值的社 karate club 区中，对当前中心社区进行扩展：更新剩余未聚类结 因此，度量未聚类结点和已有社区的归属度，需 点的归属度，若网络中所有未聚类结点对任意社区 要综合考虑该结点与一个社区关联边数以及社区内 的归属度都小于设定阈值，则算法结束。 该结点的相邻结点的重要性。为了更准确地表示未 3.1确定聚类个数 首先，寻找网络中的子图密度大于指定阈值d 聚类结点和社区的关系，首先给出结点，对社区C 的所有稠密子图。图2给出了d=0.9时，算法得到 的归属度定义： 的4个稠密子图，分别记为U1、U2、U3和U40 b(v.c)=ax Iyncl nB(u) +(1-a)× ke ∑，2B） (2) 式(2)中第1项表示结点与社区C关联边数，第 2项表示结点：连接社区C内结点的重要程度： B(u:)表示结点u,的点介数，通过式(1)计算得到； a∈[0,1]为调节参数。b(,C)越大，则u更倾向属 于社区C。如果结点在社区C中无相邻结点，则 图2BDSG算法在空手道俱乐部中得到的稠密子图 b(,C)=0。选择合理的调节参数α可以有效地减 Fig.2 The dense subgraphs in zachary's karate club obtained by BDSG 少最终聚类结果中的未聚类结点个数，提高聚类效 果，表1给出了本文算法BDSG分别在=0.8和 然后，建立子图重叠矩阵M,其中元素M.:=Ｃ 中相邻点的集合，ｋｖ 是结点 ｖ 的度。 然而结点 ｖ 与社区 Ｃ 的关联强度不仅与关联边数有关，也和社 区 Ｃ 中 ｖ 的相邻点在 Ｃ 中的重要性关系密切。 如图 １ 所示，当前 聚 类 结 果 得 到 两 个 社 区 Ｃ１ （ ▲） 和 Ｃ２ （ ■ ） ， 其 余 结 点 为 未 聚 类 结 点。 考 虑 结 点 ｖ ９ ， 可 得 ｂｐ （ ｖ ９ ， Ｃ１ ） ＝ ｂｐ （ ｖ ９ ， Ｃ２ ） ， Ｎｖ９∩Ｃ１ ＝ ｖ ３３ ， ｖ ３４ { } ， 且 Ｎｖ９ ∩ Ｃ２ ＝ ｖ １ ， ｖ ３ { } 。 此 时，社区 Ｃ１ 中与结 点 ｖ ９ 相 邻 结 点 的 点 介 数 比 例为 ∑ｕ∈ ｖ３３ ，ｖ { ３４ } Ｂ (ｕ ) ∑ｗ∈Ｃ１ Ｂ (ｗ ) ＝ ０ ． ９５ ， 而 社 区 Ｃ２ 中 与 结 点 ｖ ９ 相 邻 结 点 的 点 介 数 比 例 为 ∑ｕ∈ ｖ１ ，ｖ { ３ } Ｂ(ｕ) ∑ｗ∈Ｃ２ Ｂ(ｗ) ＝ ０．８３。 由于结点 ｖ９ 在 Ｃ１ 中的相 邻点在网络中重要性更高，可以认为 ｖ９ 更倾向归属 于社区 Ｃ１ 。 图 １ 空手道俱乐部中未聚类结点分析 Ｆｉｇ．１ Ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｓｕｂｏｒｄｉｎａｔｅ ｖｅｒｔｉｃｅｓ ｉｎ ｚａｃｈａｒｙ􀆳ｓ ｋａｒａｔｅ ｃｌｕｂ 因此，度量未聚类结点和已有社区的归属度，需 要综合考虑该结点与一个社区关联边数以及社区内 该结点的相邻结点的重要性。 为了更准确地表示未 聚类结点和社区的关系，首先给出结点 ｖ 对社区 Ｃ 的归属度定义： ｂ（ｖ，Ｃ） ＝ α × Ｎｖ ∩ Ｃ ｋｖ ＋ (１ － α) × ∑ｕｉ∈Ｎｖ∩Ｃ Ｂ ｕｉ ( ) ∑ｖｊ∈Ｃ Ｂ ｖｊ ( ) （２） 式（２）中第 １ 项表示结点 ｖ 与社区 Ｃ 关联边数，第 ２ 项表示结点 ｖ 连接社区 Ｃ 内结点的重要程度； Ｂ ｕｉ ( ) 表示结点 ｕｉ 的点介数，通过式（１）计算得到； α∈ [０，１] 为调节参数。 ｂ（ｖ，Ｃ）越大，则 ｖ 更倾向属 于社区 Ｃ。 如果结点 ｖ 在社区 Ｃ 中无相邻结点，则 ｂ（ｖ，Ｃ）＝ ０。 选择合理的调节参数 α 可以有效地减 少最终聚类结果中的未聚类结点个数，提高聚类效 果，表 １ 给出了本文算法 ＢＤＳＧ 分别在 α ＝ ０． ８ 和 α＝ １（此时重要度对聚类结果不产生影响） 时的未 聚类结点数（ｓｕｂｏｒｄｉｎａｔｅ ｖｅｒｔｉｃｅｓ）和模块性的比较结 果，表明通过重要度定义的归属度能够更加准确地 表示节点和社区的关系。 表 １ 不同 α 值时聚类结果的比较 Ｔａｂｌｅ １ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ａｍｏｎｇ ｄｉｆｆｅｒｅｎｔ α 数据集 未聚类节点 Ｑ α＝ ０．８ α＝ １ α＝ ０．８ α＝ １ 空手道 俱乐部 １ ３ ０．８２０ ５ ０．７１７ ９ 海豚 社交网络 ０ １ ０．７７３ ５ ０．７６１ ０ 大学生 足球网络 ０ ０ ０．６３９ ０ ０．６１５ ０ 电子 邮件网络 ３４ ４１ ０．７２２ ４ ０．７１５ １ 合作网络 ６５７ ６６１ ０．７８２ ８ ０．６４７ ３ ３ 基于稠密子图的社区发现算法 基于稠密子图的社区发现算法（ＢＤＳＧ）主要由 ２ 部分构成：首先通过搜索网络中大于指定密度阈 值 ｄ 的稠密子图得到网络中心社区，确定聚类个数 ｋ，不属于任何一个中心社区的结点为未聚类结点； 根据式（２）计算未聚类结点与已有社区的归属度， 将一些未聚类结点划分到归属度大于指定阈值的社 区中，对当前中心社区进行扩展；更新剩余未聚类结 点的归属度，若网络中所有未聚类结点对任意社区 的归属度都小于设定阈值，则算法结束。 ３．１ 确定聚类个数 首先，寻找网络中的子图密度大于指定阈值 ｄ 的所有稠密子图。 图 ２ 给出了 ｄ ＝ ０．９ 时，算法得到 的 ４ 个稠密子图，分别记为 Ｕ１ 、Ｕ２ 、Ｕ３ 和 Ｕ４ 。 图 ２ ＢＤＳＧ 算法在空手道俱乐部中得到的稠密子图 Ｆｉｇ．２ Ｔｈｅ ｄｅｎｓｅ ｓｕｂｇｒａｐｈｓ ｉｎ ｚａｃｈａｒｙ􀆳ｓ ｋａｒａｔｅ ｃｌｕｂ ｏｂｔａｉｎｅｄ ｂｙ ＢＤＳＧ 然后，建立子图重叠矩阵 Ｍ，其中元素 Ｍｉ，ｉ ＝ ·４２８· 智 能 系 统 学 报 第 １１ 卷