基于模块度最大化的社区发现算法的研究

发布时间：2017-10-18 06:16

  本文关键词：基于模块度最大化的社区发现算法的研究

  更多相关文章： 复杂网络 模块度 社区结构 标签传播 社区发现

【摘要】：随着网络的迅速发展,对复杂网络的研究在许多领域都备受关注。社区结构是复杂网络的一个普遍特征,对社区结构的挖掘成为了网络分析中的研究热点。复杂网络由许许多多个社区构成,社区发现对于了解复杂网络中的社区结构有着重要的意义。从计算角度而言,社区划分相当于将任务分解,可以降低计算复杂度;从实际应用而言,社区发现“产生”了推荐,方便了人们的生活。本文针对社区发现问题,结合社区结构这个重要属性,利用模块度最大化方法对社区发现算法中的时间复杂度以及社区结构的强弱展开了深入研究。首先,针对基于模块度最大化这类标签传播算法中时间复杂度高的问题,本文依据“先传播,后合并”的原则,降低了社区合并导致整个网络需要更新带来的较高时间复杂度;结合社区结构的概念提出了基于模块度最大化的标签传播算法CDMM-LPA。基于社区结构的重要性,本文将社区结构作为一个重要的考虑因素融入CDMM-LPA算法中,使得最终获得的社区属于强结构社区。其次,提出了基于模块度最大化的双向合并的社区发现算法CDPM。CDPM算法是基于混合式合并的社区发现的改进算法。该算法通过计算节点之间的相似度,减少算法初始阶段生成的子社区数目。通过检查生成的社区是否含有弱结构社区来决定CDPM算法的运行次数,避免了通过设置参数来控制算法的执行次数,从而降低了CDPM算法的时间复杂度。最后,基于真实网络数据集和模拟生成的网络数据集,验证并分析了两种算法的可行性。
【关键词】：复杂网络 模块度 社区结构 标签传播 社区发现
【学位授予单位】：燕山大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6;O157.5
【目录】：

• 摘要5-6
• Abstract6-9
• 第1章 绪论9-15
• 1.1 研究的背景及意义9-10
• 1.2 国内外研究现状10-14
• 1.2.1 国外研究现状11-12
• 1.2.2 国内研究现状12-14
• 1.3 本文研究的内容14
• 1.4 本文组织结构14-15
• 第2章 社区发现算法中的相关概念15-23
• 2.1 社区15
• 2.1.1 社区概述15
• 2.1.2 社区性质15
• 2.2 社区结构15-16
• 2.3 社区结构评价标准16-18
• 2.3.1 模块度16-18
• 2.4 基于层次聚类的相关算法18-20
• 2.4.1 GN算法18-19
• 2.4.2 基于混合式合并的社区发现算法19-20
• 2.5 基于标签传播的相关算法20-22
• 2.5.1 基于标签传播的社区发现算法20-21
• 2.5.2 LPAm+算法21-22
• 2.6 本章小结22-23
• 第3章 基于模块度最大化的标签传播算法23-33
• 3.1 算法描述23-26
• 3.1.1 相关定义23-26
• 3.2 算法实现过程26-32
• 3.2.1 划分网络27
• 3.2.2 更新标签27
• 3.2.3 算法部分伪代码27-29
• 3.2.4 实例说明29-32
• 3.3 本章小结32-33
• 第4章 基于双向合并的社区发现算法33-40
• 4.1 双向合并的社区发现算法的描述33-35
• 4.1.1 层次聚类思想33
• 4.1.2 选取相似度33-34
• 4.1.3 双向合并34-35
• 4.2 算法的实现35-36
• 4.2.1 算法举例35-36
• 4.3 算法的部分伪代码36-39
• 4.4 本章小结39-40
• 第5章 算法的实验结果分析40-51
• 5.1 实验环境的基本配置40
• 5.2 CDMM-LPA算法40-45
• 5.2.1 实验数据40-44
• 5.2.2 不同算法之间的比较44-45
• 5.3 CDPM算法45-50
• 5.3.1 真实数据集实验46-48
• 5.3.2 模拟数据集实验48-50
• 5.4 本章小结50-51
• 结论51-53
• 参考文献53-57
• 攻读硕士学位期间承担的科研任务与主要成果57-58
• 致谢58-59
• 作者简介59

【相似文献】

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

1 智源;行飞;;复杂网络社区结构问题综述[J];阴山学刊(自然科学);2011年03期

2 王林;戴冠中;赵焕成;;一种新的评价社区结构的模块度研究[J];计算机工程;2010年14期

3 韩瑞凯;孟嗣仪;刘云;郭英慧;张彦超;;基于兴趣相似度的社区结构发现算法研究[J];铁路计算机应用;2010年10期

4 刘旭;易东云;;基于保守合并策略的复杂网络社区结构发现[J];复杂系统与复杂性科学;2011年04期

5 黄发良;肖南峰;;用于网络重叠社区发现的粗糙谱聚类算法[J];小型微型计算机系统;2012年02期

6 马瑞新;邓贵仕;王晓;;启发式动态社区挖掘算法研究与实现[J];大连理工大学学报;2012年02期

7 梁沙沙;;复杂网络重叠社区结构发现算法研究[J];阴山学刊(自然科学);2013年02期

8 刘大有;金弟;何东晓;黄晶;杨建宁;杨博;;复杂网络社区挖掘综述[J];计算机研究与发展;2013年10期

9 时京晶;;三种经典复杂网络社区结构划分算法研究[J];电脑与信息技术;2011年04期

10 黄发良;肖南峰;;基于线图与PSO的网络重叠社区发现[J];自动化学报;2011年09期

中国重要会议论文全文数据库 前3条

1 刁元波;李梦龙;文志宁;印家健;郑波;;人类细胞信号网络社区结构分析[A];第九届全国计算（机）化学学术会议论文摘要集[C];2007年

2 刘欣;李德毅;李兵;王树良;陶志伟;;复杂网络社区发现研究[A];2006全国复杂网络学术会议论文集[C];2006年

3 单波;姜守旭;张硕;高宏;李建中;;IC:动态社会关系网络社区结构的增量识别算法[A];第26届中国数据库学术会议论文集（A辑）[C];2009年

中国重要报纸全文数据库 前1条

1 记者 熊明 实习生 李瑞莹;度假区不断创新社区结构[N];云南日报;2013年

中国博士学位论文全文数据库 前7条

1 闵磊;复杂网络社区发现算法研究[D];华中师范大学;2015年

2 蔡清;基于群体智能优化的大数据复杂网络结构分析[D];西安电子科技大学;2015年

3 杜楠;复杂网络中社区结构发现算法研究及建模[D];北京邮电大学;2009年

4 李一啸;基于复杂网络和演化博弈理论的社会[D];浙江大学;2010年

5 韩院彬;Web服务网络分析和社区发现研究[D];天津大学;2014年

6 谢辉;基于复杂网络的若干动态机制研究[D];西安电子科技大学;2013年

7 任薇;基于微博的社会网络特征研究[D];西南大学;2014年

中国硕士学位论文全文数据库 前10条

1 王童童;社区框架与隐藏社区的挖掘[D];山东建筑大学;2015年

2 贺成龙;复杂网络中的社区发现算法研究[D];解放军信息工程大学;2015年

3 贾娜;基于矩阵分解的重叠社区探测研究[D];吉林大学;2016年

4 李青云;多阶信息模型及推荐技术研究[D];北京理工大学;2015年

5 万云;基于模块度最大化的社区发现算法的研究[D];燕山大学;2016年

6 戴飞飞;基于进化算法的复杂网络社区结构发现[D];电子科技大学;2008年

7 王熙;复杂网络中的层次重叠社区发现及可视化[D];北京交通大学;2010年

8 徐李恒;复杂网络社区发现方法研究[D];太原理工大学;2011年

9 李兆南;基于距离相似度的复杂网络社区挖掘方法[D];吉林大学;2011年

10 商源纯;复杂网络中的重叠社区发现算法研究[D];北京交通大学;2011年

，

本文编号：1053388