实时变化的移动社区挖掘算法的研究与实现

论文摘要

随着信息技术的迅速发展,社会网络变得无处不在,从生物学到互联网,从大型的电力网到人际关系网等等。从大量的数据中提取有效的、可信的、新颖的信息的数据挖掘成为了当今的热点课题,将数据挖掘有效的应用于社会网络分析成为了数据挖掘的一个新方向。大量的研究实验证明,很多的网络结构都是异构的,即社会网络是由许多性质不一样的节点连接在一起的。我们的目的就是为了将性质相同,类型一致的节点所构成的社会网络的子图,即社区结构找出来。本文主要将社区挖掘技术应用于移动社会网络上。我们首先通过编程的手段采集移动用户网站上的通话记录,根据移动用户的通话记录中的数据,提出了一种加权的关系度量方法。由于移动通话是一种直接的端到端的通信方式,因此,能够成一个社区的成员是一些直接沟通彼此联系密切的用户,所以,我们采用派系即完全子图作为社区的结构基础。本文中首先采用带有权重的派系过滤算法(CPMw)生成移动社区结构,为了能够很好的观察移动社区结构的衍变,接着提出了一种基于加减边的社区更新算法(ACUM),为了提高算法的执行效率,我们在此基础上做了些改进,提出了并行执行的思想,从而改善了算法的效率。通过实验研究表明了,本文采用的CPMw算法在发现移动社区结构具有较好的效果,在此社区结构基础上提出的基于加减边的社区更新算法,能够很好的展现社区的更新结果。对其改进的社区更新算法,提高了算法的执行效率并且具有较高的准确率。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 研究内容
• 1.4 论文组织结构
• 第2章 相关理论知识
• 2.1 社会网络的涵义
• 2.2 数据挖掘分析
• 2.2.1 数据挖掘的涵义
• 2.2.2 数据挖掘引擎
• 2.2.3 经典社区挖掘算法概述
• 2.2.4 基于图分割的算法
• 2.2.5 基于层次聚类的算法
• 2.2.6 其他社区挖掘算法
• 2.3 本章小结
• 第3章 基于CPMW算法的移动社区发现
• 3.1 移动社会网络的构建
• 3.1.1 社会网络分析
• 3.1.2 移动社会网络的特点
• 3.1.3 移动社会网络的构建
• 3.1.3.1 数据源
• 3.1.3.2 数据抽取
• 3.1.3.3 数据清洗和规范化
• 3.1.3.4 节点关系的度量方法
• 3.1.3.5 移动社会网络的表示
• 3.2 社区的定义
• 3.3 基于CPMw算法的社区发现
• 3.3.1 基于CPM的派系发现
• 3.3.2 CPM算法的分析
• 3.3.3 CPM改进算法的实现——CPMw
• 3.3.4 CPM与CPMw算法比较
• 3.3.5 基于CPMw的社区生成
• 3.4 本章小结
• 第4章 基于ACUM算法的社区更新及改进
• 4.1 社区实时更新算法—ACUM
• 4.1.1 规则定义和方法
• 4.1.2 社区的粗化
• 4.1.3 ACUM算法的设计与实现
• 4.2 ACUM算法的改进与实现
• 4.2.1 社区的并行更新
• 4.2.2 ACUM改进算法的设计与实现
• 4.3 本章小结
• 第5章 实验
• 5.1 实验环境
• 5.2 数据集
• 5.3 评价指标
• 5.4 实验结果分析
• 5.5 本章小结
• 第6章 总结与展望
• 6.1 工作总结
• 6.2 展望
• 参考文献
• 致谢