第3期 郑文萍，等：基于稠密子图的社区发现算法 ·429. 1V(U:)1表示子图U:中的顶点个数。元素M:= |V(U)nV(U)|,i≠j,表示子图U,和U,的公共顶 4实验与结果分析 点数。对2个不同稠密子图，若M:> 为了分析研究BDSG算法在真实网络中社区发 min(U:l,U) 现的有效性，将BDSG算法分别应用于空手道俱乐 则合并2个子图为一个新社区 部(Karate)[]、海豚社交网络(Dolphin)[24]、大学生 U'=[V(U)UV(U)]c,此过程迭代进行，直到不产 足球网络(Football)[2]、电子邮件网络(Email)[] 生新的社区。得到的社区称为初始中心社区，社区 和合作网络(NetScience)I]等5个数据集。实验所 个数k为算法的聚类个数。图2中4个稠密子图的 用计算机配置为Inter Core i5CPU2.5GHz,6GB内 存，Windows7操作系统。程序采用java编程语言 重叠矩阵表示为 并在Eclipse环境下运行。依经验选择密度阈值d= [42007 0.9,调节参数a=0.8。 240 0 M= 图3~5分别给出了本文BDSG算法在空手道 0054 俱乐部、海豚社交网络和大学生足球网络的聚类结 L0045 果。表2给出了BDSG算法与CPM、k-dense算法分 进行稠密子图合并操作后可得到2个初始中心社 别在聚类个数、未聚类结点数、社区模块性(Q)【测 区：C,=[UUU2]c,C2=[U3UU]c,聚类个数k=2。 以及运行时间等方面的比较结果。 算法确定了聚类个数和初始中心社区数之后， 不属于任何中心社区的结点就是未聚类结点。由于 初始中心社区寻找过程中关注于网络中相对稠密的 子图，网络中存在大量未聚类结点，需要设计合理的 中心社区扩展策略，对未聚类结点进一步处理。 3.2中心社区扩展策略 设聚类个数为k,当前中心社区分别为C1,C2,…, Ck,则当前未聚类结点集合T=V(G)-U,V(C:)。根 图3BDSG算法在空手道俱乐部得到的聚类结果 据式(2)给出的结点对社区的归属度定义，计算T Fig.3 Clustering results on zachary's karate club ob- 中结点与中心社区C:的归属度，并对相关中心社区 tained by BDSG 进行扩展，具体过程如算法1。 算法1中心社区扩展算法(core community extended strategy,CE) 输入图G=(V,E),聚类个数k,初始中心社区 集合Co)={Co),C),…,C)},其中CoSV。 输出社区集合C={C,C2,…,C4}。 1)令集合To=V(G)-UV(Co),B。=0.7, t=0。 2)令t=t+1,对每个社区C),C-),…, 图4BDSG算法在海豚社交网络上得到的聚类结果 CD,执行下列操作： Fig.4 Clustering results on dolphins social network ob- tained by BDSG ①Co=C-)(1≤i≤k),Ne(C,)= {ulu∈Ne(x)Ax∈C,-D}。 ②对任意元素vETONc(C)(1≤i≤k),如 果b(u,C-))≥B1,则C0=C0U{}。 ③令B.=B--0.1,T=V(G)-U(C), 若B,≥0.3，且T≠☑，返回步骤2)。 3)结束，输出社区集合C= {C0,C,…,C}。 图3给出了BDSG算法在空手道俱乐部数据集 图5BDSG算法在大学生足球网络上得到的聚类结果 上的聚类结果，共得到2个社区，空白结，点表示未聚 Fig.5 Clustering results on college football network ob- 类结点。 tained by BDSG｜ Ｖ（Ｕｉ） ｜表示子图 Ｕｉ 中的顶点个数。 元素 Ｍｉ，ｉ ＝ Ｖ Ｕｉ ( ) ∩Ｖ Ｕｊ ( ) ，ｉ≠ｊ，表示子图 Ｕｉ 和 Ｕｊ 的公共顶 点 数。 对 ２ 个 不 同 稠 密 子 图， 若 Ｍｉ，ｉ ＞ ｍｉｎ Ｕｉ ， Ｕｊ ( ) ２ ，则合并 ２ 个子图为一个新社区 Ｕ′＝ ［Ｖ（Ｕｉ）∪Ｖ Ｕｊ ( ) ］ Ｇ ，此过程迭代进行，直到不产 生新的社区。 得到的社区称为初始中心社区，社区 个数 ｋ 为算法的聚类个数。 图 ２ 中 ４ 个稠密子图的 重叠矩阵表示为 Ｍ ＝ ４ ２ ０ ０ ２ ４ ０ ０ ０ ０ ５ ４ ０ ０ ４ ５ é ë ê ê ê ê ê ù û ú ú ú ú ú 进行稠密子图合并操作后可得到 ２ 个初始中心社 区：Ｃ１ ＝ ［Ｕ１∪Ｕ２ ］ Ｇ ，Ｃ２ ＝ ［Ｕ３∪Ｕ４ ］ Ｇ ，聚类个数ｋ ＝ ２。 算法确定了聚类个数和初始中心社区数之后， 不属于任何中心社区的结点就是未聚类结点。 由于 初始中心社区寻找过程中关注于网络中相对稠密的 子图，网络中存在大量未聚类结点，需要设计合理的 中心社区扩展策略，对未聚类结点进一步处理。 ３．２ 中心社区扩展策略 设聚类个数为 ｋ，当前中心社区分别为 Ｃ１，Ｃ２，…， Ｃｋ，则当前未聚类结点集合 Ｔ ＝Ｖ（Ｇ）－∪ｋ ｉ＝１Ｖ（Ｃｉ）。 根 据式（２） 给出的结点对社区的归属度定义，计算 Ｔ 中结点与中心社区 Ｃｉ 的归属度，并对相关中心社区 进行扩展，具体过程如算法 １。 算法 １ 中心社区扩展算法 （ ｃｏｒｅ ｃｏｍｍｕｎｉｔｙ ｅｘｔｅｎｄｅｄ ｓｔｒａｔｅｇｙ，ＣＥ） 输入 图 Ｇ＝ (Ｖ，Ｅ) ，聚类个数 ｋ，初始中心社区 集合 Ｃ (０ ) ＝ Ｃ (０ ) １ ，Ｃ (０ ) ２ ，…，Ｃ (０ ) ｋ { } ，其中 Ｃ (０ ) ｉ ⊆Ｖ。 输出 社区集合 Ｃ ＝ Ｃ１ ，Ｃ２ ，…，Ｃｋ { } 。 １）令集合 Ｔ (０ ) ＝ Ｖ(Ｇ) －∪ｋ ｉ ＝ １Ｖ Ｃ (０ ) ｉ ( ) ，β０ ＝ ０．７， ｔ ＝ ０。 ２） 令 ｔ ＝ ｔ ＋ １，对每个社区 Ｃ (ｔ－１ ) １ ，Ｃ (ｔ－１ ) ２ ，…， Ｃ (ｔ－１ ) ｋ ，执行下列操作： ① Ｃ (ｔ) ｉ ＝ Ｃ (ｔ－１ ) ｉ (１≤ｉ≤ｋ) ， ＮＧ Ｃ (ｔ－１ ) ｉ ( ) ＝ ｛ｕ ｜ ｕ∈ＮＧ (ｘ) ∧ｘ∈Ｃ (ｔ－１ ) ｉ ｝。 ②对任意元素 ｖ∈Ｔ∩ＮＧ Ｃ (ｔ－１ ) ｉ ( ) (１≤ｉ≤ｋ) ，如 果 ｂ（ｖ，Ｃ (ｔ－１ ) ｉ ）≥βｔ－１ ，则 Ｃ (ｔ) ｉ ＝Ｃ (ｔ) ｉ ∪{ｖ} 。 ③令 βｔ ＝ βｔ－１ －０．１，Ｔ (ｔ) ＝ Ｖ (Ｇ) －∪ｋ ｉ ＝ １Ｖ Ｃ (ｔ) ｉ ( ) ， 若 βｔ≥０．３，且 Ｔ (ｔ) ≠∅，返回步骤 ２）。 ３ ） 结 束， 输 出 社 区 集 合 Ｃ ＝ Ｃ (ｔ) １ ，Ｃ (ｔ) ２ ，…，Ｃ (ｔ) ｋ { } 。 图 ３ 给出了 ＢＤＳＧ 算法在空手道俱乐部数据集 上的聚类结果，共得到 ２ 个社区，空白结点表示未聚 类结点。 ４ 实验与结果分析 为了分析研究 ＢＤＳＧ 算法在真实网络中社区发 现的有效性，将 ＢＤＳＧ 算法分别应用于空手道俱乐 部（Ｋａｒａｔｅ） ［２３］ 、海豚社交网络（Ｄｏｌｐｈｉｎ） ［２４］ 、大学生 足球网络（ Ｆｏｏｔｂａｌｌ） ［２５］ 、电子邮件网络（ Ｅｍａｉｌ） ［２６］ 和合作网络（ＮｅｔＳｃｉｅｎｃｅ） ［２７］等 ５ 个数据集。 实验所 用计算机配置为 Ｉｎｔｅｒ Ｃｏｒｅ ｉ５ ＣＰＵ ２．５ ＧＨｚ，６ ＧＢ 内 存，Ｗｉｎｄｏｗｓ ７ 操作系统。 程序采用 ｊａｖａ 编程语言 并在 Ｅｃｌｉｐｓｅ 环境下运行。 依经验选择密度阈值 ｄ ＝ ０．９，调节参数 α＝ ０．８。 图 ３ ～ ５ 分别给出了本文 ＢＤＳＧ 算法在空手道 俱乐部、海豚社交网络和大学生足球网络的聚类结 果。 表 ２ 给出了 ＢＤＳＧ 算法与 ＣＰＭ、ｋ⁃ｄｅｎｓｅ 算法分 别在聚类个数、未聚类结点数、社区模块性（Ｑ） ［２８］ 以及运行时间等方面的比较结果。 图 ３ ＢＤＳＧ 算法在空手道俱乐部得到的聚类结果 Ｆｉｇ．３ Ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｎ ｚａｃｈａｒｙ􀆳ｓ ｋａｒａｔｅ ｃｌｕｂ ｏｂ⁃ ｔａｉｎｅｄ ｂｙ ＢＤＳＧ 图 ４ ＢＤＳＧ 算法在海豚社交网络上得到的聚类结果 Ｆｉｇ．４ Ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｎ ｄｏｌｐｈｉｎｓ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ｏｂ⁃ ｔａｉｎｅｄ ｂｙ ＢＤＳＧ 图 ５ ＢＤＳＧ 算法在大学生足球网络上得到的聚类结果 Ｆｉｇ．５ Ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｎ ｃｏｌｌｅｇｅ ｆｏｏｔｂａｌｌ ｎｅｔｗｏｒｋ ｏｂ⁃ ｔａｉｎｅｄ ｂｙ ＢＤＳＧ 第 ３ 期 郑文萍，等：基于稠密子图的社区发现算法 ·４２９·