一种动态网络社区划分算法_万里.pdf

第 37 卷 第 2 期 北 京 工 业 大 学 学 报 Vol． 37 No． 2 2011 年 2 月 JOURNAL OF BEIJING UNIVERSITY OF TECHNOLOGY Feb． 2011 一种 动态 网络社 区划分算 法 1 ，2 1 ，2 1 ，2 ， ， 万 里 廖建新 朱晓民 ( 1． ， 100876; 2 ． ， 100083) 北京 邮电大学 网络与交换技术 国家重点实验室 北京 东信北 邮信息技术有限公 司 北京 摘 要: 基于 MDL( minimum description length) 原则提出一种动态社区划分算法 DCI( dynamic community identifi- cation) ． ， DCI ， 通过定义相邻时刻静态社区 的演化关系 使得 算法不仅能发现具有不同生命周期 的动态社区 并 ． ， ，DCI 且所得结果能准确描述动态社区 的演化过程 实验结果表 明 与已有算法相 比 算法可 以更加准确地划分动 ， ． 态社区 并在可接受 的时间内完成较大规模动态 网络社区划分 关键词: 动态 网络; 动态社区划分; 数据挖掘 中图分类号: TP 181 文献标志码: A 文章编号: 0254 － 0037( 2011) 02 － 0285 － 06 ［1-5］ ， ， 目前 大部分社区划分的研究都集中在静态 网络 中的社区划分 动态 网络 中社区划分最近才受到 ［6］ ． ， ． 关注 动态 网络是一个静态 图序列 序列 中一个静态 图对应动态 网络在某个 时刻 的像 动态 网络 中的 动态社区 由一系列静态 图中的静态社区组成． 动态社区发现算法分为 2 类． 一类算法首先根据 网络 的相似性和连续性将时间序列上 的静态 图分成 ［6］ ， ， ． 段 每段 内的所有静态 图合并在一起形成一个新的静态 图 然后再在这个新的静态 图内划分社区 这种