结果表 明 ， 已有 的社 团结构 划分算 法相比 ， 于扩散距 离的快速 分裂算 法能够得到 高质 量的社 团结构 ， 时间 与 基 其
复杂度较低 ， 不仅对稀 疏 网络 能够快速 运算 ， 对非稀 疏 网络 更 能 高效求 解 ， 这进 一 步体 现 出算 法具 有较 高的 稳
定 性
关键 词 ：复 杂 网络 ； 团结构 ；分裂 算法 ； 块度 ；扩散 距 离 社 模 中图分 类号 ：Ｔ ｌ ｌ Ｐ ８ 文 献标 志码 ：Ａ 文章编号 ：１０ — ６ ５ ２ １ ）４ １４ —３ ０ １３ ９ （ ０ １ ０ — ２ ２ ０
张 聪 ， 惠璋 ， 沈 李 峰
（ 海 交通 大学 安泰 经济管理 学院 ， 海 ２ ０ ５ ） 上 上 ０ ０ ２ 摘 要 ：针对 已有分裂 算法 时间复杂度较 高 ， 不适用 于社 团数 目未知的 大型 网络 等 问 Ｎ算法 的思想 ， 出以扩散 距 离为分割依 据 ， 提 以模块 度 函数 为社 团结构 划 分满 意度 的快速 分裂 算法 。实验
许 多 研究 领域 中 的复 杂 系 统 都 可 以被 表 述 成 由节 点 或 顶 点 集 通 过线 或 边 的 连 接 而 构 成 的 网 络 ， 现 实 世 界 中 的 互 联 如
第２ ８卷 第 ４期
２１ ０ １年 ４月
计 算 机 应 用 研 究
Ａｐ ｉ ａｉ ｎ Ｒｅ ｅ ｒ ｈ ｏ ｍ ｐｕｅｒ ｐｌｃ ｔｏ ｓ ａ ｃ ｆＣｏ ｔ ｓ
Ｖｏ ＿ ８ Ｎ ． ｌ２ ｏ ４
Ａｐｒ ２０１ ． １
复 杂 网络 中社 团结构 划 分 的 分裂 算 法 术 陕速
ＺＨ ＡＮＧ ｎ Ｃｏ ｇ， Ｓ ＨＥＮ Ｈｕｉｚ ｎｇ，ＬＩＦ ｎｇ —ｈａ ｅ
（ ｎａ ｏｅｅｏ ｃｎｍｃ Ａ ｔｉ ｌｇ Ｅｏｏ ｉ Ｃ ｌ ｆ ｓ＆Ｍａａ ｅ ｅｔ ｈ ｎ ｈｉ ｉｏ ｎ ｎｖｒｔ， ｈｎ ｈ ｉ ００ ２ ｈｎ ｎｇｍ ｎ，Ｓａｇ ａ ａｔ ｇ Ｕ ｉ ｓｙ Ｓ ａｇ ａ ２０ ５ ，Ｃ ｉ Ｊ ｏ ｅｉ ａ）
Ａｂｓｒ ｃ ｔ ａ ｔ： Ｍｏ ｔｏ ｈ ｒ ｐ ｓ ｄ ｓ ｉｔｎ ｌｏ ｉｈ ｒ ｏ ｕ ｔｂ ｅｆｒｖ ｒ ａ ｇ ｅｗｏ ｋ ｅ ａ ｓ ｆｔ ｅｒｈｉｈ ｔ ｏ ｌｘ ｓ ｆｔ ｅｐ ｏ ｏ ｅ ｐｌ ｉ ｇａｇ ｒｔ ｍｓａ ｅｎ ｔｓ ｉａ ｌ ｏ ｅ ｙｌ ｒｅ ｎ ｔ ｒ ｓｂ ｃ ｕ ｅ ｏ ｈ ｉ ｇ ｉ ｃ ｍｐ ｅ — ｔ ｍｅ ｉｙ ａ ｄ ｕ ｎ ｗｎ ｑ ｎｔ ｙ ｏ ｏ ｔ ｎ ｎｋ ｏ ｕａ ｉ ｆｃ ｍｍｕ ｔ ｕｍｂ ｒ Ｒｅｅ ｅ ｃｎ ｈ ｏ ｔｇ ｐ ｃｒ ｍ ｅ ｍｅ ｔｔｏ ｌｏ ｉ ｔ ｎｉ ｎ ｙ ｅ． ｆｒ ｎ ｉｇ ｔ ｅ ｖ ｌａ ｅｓ ｅ ｔｕ ｓ ｇ ｎａ ｉｎ ａｇ ｒｔ ｈｍ ｎ ａ ｄ ＧＮ ｌ ｏｉｈ ， ａｇ ｒｔ ｍ ｔ ｉ ｐ ｒｐ ｏ ｏ ｅ ａ ｔｓ ｌｔｉｇ ａｇ ｒｔｍ ａ ｅ ｎ ｄｆｕ ｉ ｎ ｉｔ ｎ ｅ ａ ｄ ｔｅ ｍｏ ｕａ ｉｙ ｆ ｃｉｎ． Ｉｓｓ ｇ ｎａ ｉｎ ｂａ ｉ ｈｓｐａ ｅ ｒ ｐ ｓ ｄ ａ ｆ ｓ ｐ ｉ ｎ ｌ ｏｉｈ ｂ ｓ ｄ ｏ ｉ ｓｏ ｄｓａ ｃ ｎ ｈ ｄ ｌｒｔ ｕｎ ｔｏ ｔ ｆ ｔ ｅ ｍｅ ｔｔｏ ｓｓ ｗａ ｈ ｉｆｓｏ ｉｔｎ ｅ，ａ ｄ ｔ ｅ ａ ｉｉ ｆｍｏ ｕ ａ ｔ ｕｎ ｔｏ ｏ ｌ ｎ ｈ ｅ ｔｃ ｍｍｕ ｉｙ ｎ ｍｂｅ ｎ ｌｒ ｅ ｎ ｔ ｒ ｓ Ｅｘ ｓｔ ｅ ｄｆｕ ｉｎ ｄ ｓａ ｃ ｎ ｈ ｂｌｔ ｏ ｄ ｌ ｒ ｙ ｆ ｃｉｎ ｃ ｕｄ ｆ ｄ ｔ ｅ ｂ ｓ ｏ ｙ ｉ ｉ ｎｔ ｕ ｒｉ ａ ｇ ｅｗｏ ｋ ． — ｐ ｒｍｅ ａ ｅ ｕｌ ｈ ｗ ｈ ｔｔ ｅ ａｇ ｒｔ ｅ ｉ ｎｔｌｒ ｓ ｔ ｓ ｏ ｔ ａ ｈ ｌｏｉｈｍ ａ ｔｅ ａ ｔ ｉｎ ｎ ｂｌｔ ｎｄ ｌｗｅ ｉ ｏ ｌｘｔ ｈａ ｈｅｐｒ ｐ ｓ ｄ ｐ ｒｉｉ— ｓ ｈ ｓｂｅｔｒｐ ｒｉ ｏ ｉ ｇ ａ ｉｉｙａ ｏ ｒｔｍｅ ｃ ｍｐｅ ｉｙ ｔ ｎ ｔ ｏ ｏ ｅ ａｔｔｏ ｔ ｎｎ ｏ ｉ ｇ ｃ ｍｍ ｕ ｉｙ ｓｒ ｃｕ ｅ ａｇ ｒｔ ｍｓ ｎｔ ｔｕ ｔ ｒ ｌｏ ｉｈ ．Ｎｏ ｎｙ ｉ ｉ ａ ａ ｌ ｆｆ ｓ ｐｅａ ｉｎ ｆｒｔ ｅ ｓ ａ ｓ ｅ ｗｏｋ，ｂ ｔａ ｓ ｒｔｅ ｎ ｎ ｓ ｒｅ ｔｏ ｌ ｔ ｓｃ ｐ ｂ ｅｏ ａ ｔｏ ｒｔｏ ｏ ｈ ｐ ｒｅｎ ｔ ｒ ｕ ｌｏｆ ｈ ｏ —ｐａｓ ｏ ｎｔ ｒ ｅｗｏｋ，ｗｈｉｈ ｒ ｆｅ ｓｔ ｅ ａｇ ｒｔ ｃ ｅｌｃｔ ｈ ｌ ｏｉｈｍ ａ ｇ ｔｈｉｉ ． ｈ ｓｈｉｈ ｓａ ｌｔ ｙ Ｋｅ ｒ ｓ： ｃ ｍｐｅ ｅ ｗｏｋｓ ｃ ｍｍｕｎｔ ｔｕ ｔ ｒ ｙ ｗｏ ｄ ｏ ｌｘ ｎ ｔ ｒ ； ｏ ｉｙ ｓｒ ｃ ｕ ｅ；ｓ ｉｔ ｌｏ ｉｈ ； ｍｏ ｌｒｔ ｐｌ ｉ ａ ｇ ｒｔ ｍ ｔ ｎｇ ｄｕａ ｉｙ；ｄｆｕ ｉｎ ｄｉｔｎ ｅ ｉｆ ｓｏ ｓａ ｃ
ｄ ｉ１ ．９ ９ ｊｉ ｎ １０ —６ ５ ２ １ ．４ ０ ０ ｏ：０ ３ ６ ／．ｓ ．０ １３９ ．０ ０ ． １ ｓ １
Ｆ ｓ ｐ ｉ ｉ ｇ ａｇ ｒｔ ｍ ｏ ａ ｔ ｉ ｎ ｎ ｏ ａ ｔｓ ｌｔ ｎ ｌｏ ｉ ｔ ｈ ｆｒ ｐ ｒｉ ｏ ｉ ｇ ｃ ｍｍｕ ｉｙ ｓｒ ｃｕ ｅ ｉ ｏ ｌｘ ｎ ｔ ｒ ｓ ｔ ｎ ｔ ｔｕ ｔ ｒ ｎ ｃ ｍｐ ｅ ｅｗｏ ｋ