复杂网络重叠社团划分算法研究与实现

发布时间：2017-06-14 19:02

  本文关键词：复杂网络重叠社团划分算法研究与实现，由笔耕文化传播整理发布。

【摘要】：在大数据时代,随着复杂网络数据持续爆发式地增长,复杂网络所带来的影响已经进入我们生活的方方面面。因此,对这些复杂网络进行社团结构划分研究有着重要的价值和意义。复杂网络社团结构可以分为非重叠社团结构和重叠社团结构,与非重叠社团结构相比,重叠社团结构更贴近网络的真实社团组织结构。然而,重叠社团结构的研究目前处于起步阶段,同时由于重叠社团划分算法的复杂度较高,因此需要研究者们付出更大的努力。本文致力于探索准确、有效的复杂网络社团划分算法。提出了一种非重叠社团划分算法和两种有效的重叠社团划分算法。本论文取得的主要创新性成果如下:(1)注重于网络边在复杂网络社团结构划分中的重要意义,提出了一种新的基于节点亲密度和度的边权重度量方法(Weight Measure based on Intimacy and Degree,WMID)。将此度量方法应用在复杂网络的社团划分中,设计了划分非重叠社团结构的社团划分算法和划分重叠社团结构的社团划分算法,在社团划分中,该方法将任意一个复杂网络转化为一个加权网络,然后对网络进行社团划分。本文在多组真实网络数据集上进行了大量的实验。实验结果表明,基于节点亲密度和度的边权重社团划分方法可以快速、有效地划分网络社团结构。WMID方法为有向和无向网络的重叠和非重叠社团划分提供了一种实用、灵活且可靠的方法。(2)由于基于种子节点的重叠社团划分方法具有复杂度低、速度快、划分结果贴近真实社团等优点,本文提出了一种新的基于剪枝和种子节点的重叠社团发现算法(Overlapping Algorithm based on Cutting and Seeds Expansion,OACSE)。该算法创新性地将双连通图理论与网络社团划分结合起来,同时采用电导值评估方法与基于邻居节点的社团传播方法扩张种子节点进行社团划分。本文在人工数据集和真实网络数据集上进行了多组实验。实验证明,OACSE算法可以在中小型网络中有效地发现社团结构。OACSE算法为重叠社团划分研究提供了另一种可行的方法。
【关键词】：重叠社团划分 加权网络 种子节点 模块度 电导值
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6;O157.5
【目录】：

• 摘要5-6
• ABSTRACT6-10
• 第一章 绪论10-19
• 1.1 复杂网络社团划分研究背景10-12
• 1.2 复杂网络社团划分的发展概况12-14
• 1.2.1 非重叠社团划分简介12-13
• 1.2.2 重叠社团划分简介13-14
• 1.3 重叠社团划分研究现状14-16
• 1.4 本课题的研究意义与创新工作16-19
• 1.4.1 本课题的研究意义16-17
• 1.4.2 本文的创新点与文章结构17-19
• 第二章 复杂网络社团划分基础19-31
• 2.1 复杂网络的图论模型19-21
• 2.2 社团划分算法理论21-27
• 2.2.1 非重叠社团划分算法22-25
• 2.2.1.1 Newman快速算法22-24
• 2.2.1.2 Louvain算法24-25
• 2.2.2 重叠社团划分算法25-27
• 2.2.2.1 Copra重叠社团划分算法25-27
• 2.2.2.2 基于种子节点的重叠社团划分算法27
• 2.3 社团划分算法评价指标27-30
• 2.3.1 模块度28-29
• 2.3.2 NMI指标29-30
• 2.4 本章小结30-31
• 第三章 基于节点亲密度和度的加权社团划分算法31-57
• 3.1 网络的加权处理31-34
• 3.1.1 边权重的重要性31-32
• 3.1.2 边权处理方法32-34
• 3.2 WMID加权方法34-37
• 3.2.1 节点亲密度的定义34-36
• 3.2.2 WMID加权处理36-37
• 3.3 基于WMID的非重叠社团划分算法37-47
• 3.3.1 CDID算法37-40
• 3.3.2 实验结果及分析40-47
• 3.3.2.1 有向网络社团划分实验40-42
• 3.3.2.2 无向网络社团划分实验42-45
• 3.3.2.3 CDID准确度性验证实验45-47
• 3.4 基于WMID的重叠社团划分算法47-56
• 3.4.1 OCDID算法47-49
• 3.4.2 实验结果及分析49-56
• 3.4.2.1 空手道俱乐部网络实验分析49-51
• 3.4.2.2 海豚网络实验分析51-56
• 3.5 本章小结56-57
• 第四章 基于剪枝和种子节点的重叠社团划分算法研究57-72
• 4.1 复杂网络剪枝和种子节点分析57-59
• 4.2 OACSE算法59-65
• 4.2.1 网络剪枝60-62
• 4.2.2 寻找种子节点62
• 4.2.3 种子节点扩张62-64
• 4.2.4 社团传播64-65
• 4.3 实验结果及分析65-70
• 4.3.1 人工数据集实验分析66-67
• 4.3.2 真实数据集实验分析67-70
• 4.4 OACSE算法问题讨论70-71
• 4.5 本章小结71-72
• 第五章 总结72-74
• 致谢74-75
• 参考文献75-79
• 攻硕期间取得的研究成果79-80

【相似文献】

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

1 冷明平;孙凌宇;郭恺强;边计年;朱平;;赋权超图划分算法的电路划分实验比较研究[J];计算机工程与应用;2012年16期

2 许金凤;董一鸿;王诗懿;何贤芒;陈华辉;;大规模图数据划分算法综述[J];电信科学;2014年07期

3 李莉杰;陈端兵;王冠楠;;有向网络重叠社区的快速划分算法[J];计算机科学;2014年S1期

4 卢风顺;宋君强;张理论;张卫民;任开军;朱小谦;;面向全球数值天气预报模式的加权等积并行数据划分算法[J];计算机研究与发展;2012年04期

5 喻云峰;赖海涛;;一种基于随机搜索的黑洞二划分算法实现[J];科技广场;2006年04期

6 李晨;葛声;;一种重叠可信社团划分算法的设计与实现[J];微计算机信息;2011年09期

7 李孝伟;陈福才;刘力雄;;一种融合节点与链接属性的社交网络社区划分算法[J];计算机应用研究;2013年05期

8 牛建军;刘上乾;韩宝君;任宝文;;同心圆检测中的区域划分算法[J];光子学报;2006年12期

9 吕德奎;;聚合算法在电力GIS中的应用[J];电力信息化;2012年05期

10 王晓芳;贾宗维;;一种新的图划分算法在PPI网络模块化中的研究[J];山西农业大学学报(自然科学版);2012年06期

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

1 王玲娜;李兴明;;基于最小支撑树的通用区域划分算法[A];2008年中国西部青年通信学术会议论文集[C];2008年

2 徐丹丹;章勇;;一种基于节点度更新的簇划分算法[A];2008通信理论与技术新发展——第十三届全国青年通信学术会议论文集（下）[C];2008年

3 刘培强;谢青松;朱大铭;;用于基因表达谱数据聚类分析的贪心图划分算法研究[A];2006年全国理论计算机科学学术年会论文集[C];2006年

4 刘华伟;全庆一;;能量有效的基于连通度的分布式簇划分算法[A];2011年全国通信安全学术会议论文集[C];2011年

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

1 许金凤;大规模动态自适应图划分算法[D];宁波大学;2015年

2 周爽;面向BSP模型的图数据划分算法的设计与实现[D];东北大学;2013年

3 林慧娴;个性化服务中用户建模及社区划分算法研究[D];南京邮电大学;2015年

4 吴磊;复杂网络的社团划分算法研究[D];太原理工大学;2016年

5 宋俐;基于模糊聚类的社团划分算法研究[D];太原理工大学;2016年

6 刘文杰;基于点分割的平衡图划分算法研究及其在Spark上的实现[D];兰州大学;2016年

7 吴迪;基于微博关注及转发关系的社区划分算法的改进与实现[D];吉林大学;2016年

8 滕跃;面向胚胎型仿生硬件的电路划分算法研究[D];哈尔滨工业大学;2016年

9 康晓慧;复杂网络重叠社团划分算法研究与实现[D];电子科技大学;2016年

10 马静;基于社交网络的社团划分算法研究[D];山东师范大学;2011年

  本文关键词：复杂网络重叠社团划分算法研究与实现，，由笔耕文化传播整理发布。

本文编号：450242