基于增量分析的动态社区发现研究

发布时间：2017-07-03 16:08

  本文关键词：基于增量分析的动态社区发现研究

  更多相关文章： 社区划分 动态网络 网络增量分析 CFIA

【摘要】：社会网络大量存在于现实世界中,如朋友关系网,科学家网络,信息网络等等。近些年来,又出现了诸如Facebook,人人网和博客等新形成的社会网络。而在这些网络中,往往存在某些节点之间的关系比较密切同时某些节点之间的关系相对稀疏的现象,这些关系紧密的节点形成的结构被称为社区结构。掌握网络中的社区结构对我们来说意义重大。社区结构对我们发展更多的带有社会意识策略的社会网络问题能产生很多有用的信息；然而,理解这种社区结构是非常困难的,尤其是在社会活动和互动非常活跃的动态社会网络中。 大多数的复杂网络往往是随着时间的变化在不断的变化,动态网络中社区发现具有很大的挑战性,在现有的动态网络社区划分的算法中,大体出现了两种方式。一种是将所有时间片序列上的静态网络合并成唯一的一个静态网络,然后在所得到的唯一的静态网络上进行社区发现；另一种是对各个时间片上的静态网络分别进行社区发现。事实上,网络不是静态的,动态性是网络的本质属性,在这个动态变化的过程中,往往会有一些社区结构并没有发生太大的变化,假如每次要知道网络中的社区结构,我们对整个网络中的个体全部重新划分会有很大的时间复杂度,在这样庞大的社会网络中也远远达不到我们对信息快速检测的要求。 本文针对于以上的不足,本文作者在充分研究社区挖掘算法,尤其是动态社会网络中的社区发现方向做了大量研究工作基础上提出了一种基于增量分析的动态社区发现算法CFIA (Community Finding on Incremental Analysis);它用于动态在线社会网络中识别社区结构。这种方法,在网络发生一系列的变化后,它能依据先前的网络快照和增量变化并考虑一旦节点社区归属改变对其所有邻节点影响的情况下快速有效地通过更新网络中的社区结构。为了达到较高的时效性,我们引进了网络增量这个概念,对网络增量进行分析,来确定当前网络的社区划分结构。通过在实际动态网络IkeNet-em6ail-long. net数据集进行实验,并且在社区划分质量上和时间上与传统的MKBCD, IC算法进行比较。MKBCD算法有较高的模块度Q和准确度AC,但是时间过长,而IC算法时间较短,但是模块度Q和准确度AC都比较低,CFIA算法所划分社区结果在模块度Q和准确度AC方面高于IC算法接近MKBCD算法,在时间T上高于IC算法但是远远低于MKBCD。这种比较性的结果表明：基于增量分析的动态社区发现算法CFIA能在保证社区划分质量的情况下,同时缩短了划分社区所需时间,说明CFIA算法在动态网络中发现社区结构的优越性。 本文的创新点在于,在考虑增量对邻节点社区归属影响来保证社区划分质量的情况下,利用增量变化和历史网络拓扑结构在动态网络中来发现社区,避免了通常在每个时刻对整个动态网络所有节点进行划分带来的高复杂度,从而基于增量分析大大减小了时间复杂度,提高了社区划分的时效性。
【关键词】：社区划分 动态网络 网络增量分析 CFIA
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要3-5
• Abstract5-7
• 目录7-9
• 第一章 绪论9-16
• 1.1 研究背景与意义9-12
• 1.2 国内外研究现状12-14
• 1.3 本文主要工作14-15
• 1.4 本文章节安排15
• 1.5 本章小结15-16
• 第二章 社区挖掘算法概论16-28
• 2.1 相关概念及符号定义16-19
• 2.1.1 社会网络16
• 2.1.2 社区结构16-18
• 2.1.3 动态网络特性18
• 2.1.4 模块度Q18
• 2.1.5 准确率AC18-19
• 2.1.6 稳定度S19
• 2.2 静态社会网络中社区发现的主要算法19-23
• 2.2.1 基于图分解的方法19-20
• 2.2.2 基于社会学的方法20-21
• 2.2.3 Girvan-Newman算法21-23
• 2.3 动态网络社区发现的主要算法23-27
• 2.3.1 基于改进k-均值的高质量社区发现算法23-26
• 2.3.2 动态社会关系网络社区结构的IC算法26-27
• 2.4 本章小结27-28
• 第三章 基于增量分析的动态社区发现算法28-42
• 3.1 相关知识28-30
• 3.1.1 定义与符号表示28-29
• 3.1.2 网络增量29-30
• 3.2 算法的主要思想30
• 3.3 算法的分析与具体实现30-40
• 3.3.1 改变某个节点的社区归属30-32
• 3.3.2 增加边32-34
• 3.3.3 删除边34-37
• 3.3.4 增加点37-38
• 3.3.5 删除点38-39
• 3.3.6 CFIA算法39-40
• 3.4 算法复杂度分析40-41
• 3.5 本章小结41-42
• 第四章 实验结果与分析42-53
• 4.1 实验数据描述42-43
• 4.2 参数选择43-44
• 4.3 结果分析44-52
• 4.3.1 时间片上的动态网络44-46
• 4.3.2 社区结构的可视化46-49
• 4.3.3 基于增量分析的动态网络社区发现算法CFIA与其他传统算法比较49-52
• 4.4 本章小结52-53
• 第五章 总结与展望53-55
• 5.1 总结53-54
• 5.2 展望54-55
• 参考文献55-59
• 研究生期间参加的项目59-60
• 致谢60

【参考文献】

中国期刊全文数据库 前3条

1 于卓尔;周春光;杨滨;王建园;才华;徐昊;王U，

本文编号：514287