基于随机游走的复杂网络聚类算法研究

发布时间：2017-05-22 15:09

  本文关键词：基于随机游走的复杂网络聚类算法研究，，由笔耕文化传播整理发布。

【摘要】：现实世界中存在诸多复杂网络,如生物网、科技网和社交网等。近年来复杂网络的研究吸引了来自计算机、物理、数学和生物等众多领域的研究者,已成为多学科交叉研究的热点之一。复杂网络聚类旨在揭示出复杂网络中真实存在的网络社团结构,主要包括对无符号网络、符号网络、有权网络和有向网络等不同类型的复杂网络进行社团结构检测。复杂网络之所以在当前的研究课题中具有如此重要的社会价值和应用价值,是因为对复杂网络的聚类分析,在对预测复杂网络的网络行为、分析网络拓扑结构和挖掘网络潜在功能方面起到积极作用。本文分别针对无符号网络和符号网络的社团结构检测问题进行了研究,提出了基于随机游走算法的社团结构检测方法。本文的主要研究工作如下：(1)在无符号网络中,根据社团结构是否明显,可以将社团分为强社团和弱社团等多种类型。现有的社团结构检测算法在挖掘强社团结构时,可以表现出优异的性能,在挖掘弱社团结构时,算法性能仍存在略微不足。本文基于假设---社团中的点游走到社团内其他点的概率大于游走到社团外点的概率,提出一种利用随机游走算法检测社团结构的方法。该方法从全局网络出发找到局部最大度节点,根据该局部最大度节点找到局部最小完全子图视为局部社团,并将网络中节点根据是否在局部社团中分为聚类节点以及未聚类节点。进而,利用基于随机游走的条件概率模型,计算未聚类节点属于每个社团的概率,并将该未聚类节点加入其最可能归属的社团。最后,对己聚类社团进行优化。在随机网络和真实网络上,利用NMI值和F1值作为算法性能衡量指标,对算法性能进行评估,并与经典的网络聚类算法进行了比较。实验结果表明该算法能够较好地检测出网络社团结构,尤其在检测弱社团结构方面,大大的提高了检测精度,相比其他社团结构检测算法具有明显优势。(2)在符号网络中,边既包括表示“友好、联盟”等关系的正向边,又包括表示“敌视、竞争””等关系的负向边。现有的部分符号网络社团结构检测算法由于未充分利用网络的负边信息,导致对社团的检测精度存在一定的影响。针对上述问题,本文提出一种基于网络中的正负边信息,利用随机游走模型,检测符号网络中社团结构的方法。该方法将网络中每个节点的正度和负度的绝对值之和加起来作为该节点的度。根据节点的度找到局部最小社团,以网络中节点是否在局部社团内,将节点分为聚类节点以及未聚类节点。利用随机游走算法计算出每个未聚类节点加入局部社团的正概率和负概率。通过比较正概率与负概率的大小来判断该未聚类节点是否加入局部社团或是否由该未聚类节点动态挖掘一个新的局部社团。利用社团优化方法对聚类社团进行优化,形成最终的网络划分结果。本文所提方法充分利用了符号网络中负边的信息,保证了算法的稳定性。在真实符号网络和随机符号网络上验证了本文所提方法的可行性和有效性。同时,与其他符号网络社团结构检测算法相比,该算法检测精度更高。
【关键词】：网络聚类 社团结构 随机游走 局部社团 符号网络
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13;O157.5
【目录】：

• 摘要3-5
• Abstract5-12
• 第一章 绪论12-21
• 1.1 研究背景与意义12-15
• 1.2 国内外研究现状15-18
• 1.2.1 无符号网络聚类算法的国内外研究现状15-17
• 1.2.2 符号网络聚类算法的国内外研究现状17-18
• 1.3 本文的工作与安排18-21
• 第二章 复杂网络聚类相关基础21-33
• 2.1 复杂网络社团结构的定义21-26
• 2.1.1 无符号网络社团结构的定义21-22
• 2.1.2 符号网络社团结构的定义22-24
• 2.1.3 性能评价指标24-26
• 2.2 基于随机游走的算法介绍26-27
• 2.3 无符号网络社团结构检测经典算法27-30
• 2.3.1 GN算法28
• 2.3.2 FN算法28-29
• 2.3.3 GAS算法29-30
• 2.4 符号网络社团结构检测经典算法30-32
• 2.4.1 FEC算法30-31
• 2.4.2 MEAs-SN算法31-32
• 2.5 本章小结32-33
• 第三章 基于随机游走的无符号网络社团结构检测算法33-49
• 3.1 基于随机游走的无符号网络社团结构检测算法33-39
• 3.1.1 随机游走模型33-36
• 3.1.2 基于随机游走的无符号网络社团结构检测算法思想36-37
• 3.1.3 基于随机游走的无符号网络社团结构检测算法流程37-39
• 3.2 实验与分析39-48
• 3.2.1 实验数据40-41
• 3.2.2 RWA算法性能分析41-45
• 3.2.3 局部完全子图性能分析45-48
• 3.3 本章小结48-49
• 第四章 基于随机游走的符号网络社团结构检测算法49-66
• 4.1 基于随机游走的符号网络社团结构检测算法49-54
• 4.1.1 基于随机游走的符号网络社团结构检测算法思想49-50
• 4.1.2 基于随机游走的符号网络社团结构检测算法流程50-54
• 4.2 实验与分析54-64
• 4.2.1 实验数据54-57
• 4.2.2 SRWA算法性能分析57-64
• 4.3 本章小结64-66
• 第五章 总结和展望66-68
• 参考文献68-73
• 致谢73-74
• 攻读硕士学位期间发表的学术论文74-75
• 攻读硕士学位期间参加的科研项目75

【相似文献】

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

1 吴迪;周利娟;林鸿飞;;基于随机游走的就业推荐系统研究与实现[J];广西师范大学学报(自然科学版);2011年01期

2 苏浩航;张义门;张玉明;解敏;满进财;;基于改进的压缩式随机游走算法对静态电源/地网的模拟[J];计算物理;2007年06期

3 宋锐;汤建勋;周健;;工作电流对二频机抖激光陀螺角随机游走影响的研究[J];激光杂志;2010年02期

4 周持中;一类具有吸收点的平面随机游走[J];岳阳大学学报;1996年02期

5 雷钰丽;李阳;王崇骏;刘红星;谢俊元;;基于权重的马尔可夫随机游走相似度度量的实体识别方法[J];河北师范大学学报(自然科学版);2010年01期

6 俞琰;邱广华;;基于局部随机游走的在线社交网络朋友推荐算法[J];系统工程;2013年02期

7 何建军;李仁发;;改进的随机游走模型节点排序方法[J];计算机工程与应用;2011年12期

8 邓贵仕,赖宝全;反馈式随机游走模型及其在股票投资中应用[J];大连理工大学学报;2004年06期

9 戴颖;;深圳股票市场的随机游走检验[J];商业经济;2005年11期

10 周军军;王明文;何世柱;石松;;基于随机游走和聚类平滑的协同过滤推荐算法[J];广西师范大学学报(自然科学版);2011年01期

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

1 郑伟;王朝坤;刘璋;王建民;;一种基于随机游走模型的多标签分类算法[A];NDBC2010第27届中国数据库学术会议论文集A辑一[C];2010年

2 朱松豪;罗青青;梁志伟;;一种改进图像标注的新方法[A];第24届中国控制与决策会议论文集[C];2012年

3 燕飞;张铭;谭裕韦;唐建;邓志鸿;;综合社会行动者兴趣和网络拓扑的社区发现方法[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

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

1 长盛基金管理有限公司研究部副总监 李骥;投资自己熟悉的股票[N];证券时报;2006年

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

1 邓凯英;复杂网络搜索策略及相关模型的数值方法[D];东北师范大学;2015年

2 徐晓华;图上的随机游走学习[D];南京航空航天大学;2008年

3 孙甲申;基于主题模型和随机游走的标签技术研究[D];北京邮电大学;2013年

4 吕强;面向高性能和强表达力的自动规划[D];中国科学技术大学;2013年

5 赵学华;统计网络模型若干关键问题研究[D];吉林大学;2014年

6 廖振;基于查询点击核心图的查询推荐问题研究[D];南开大学;2013年

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

1 何岱洧;Z~d上使Schramm的上界达到的旋转配置[D];复旦大学;2014年

2 田新春;回火老化效应及其扩散方程[D];兰州大学;2015年

3 鞠薇;基于随机游走和图割算法的PET-CT肺肿瘤分割[D];苏州大学;2015年

4 祝霖;基于随机游走的动态社团划分算法[D];上海交通大学;2015年

5 孙星;基于部分吸收随机游走的协同显著性检测[D];大连理工大学;2015年

6 宋文静;基于多条随机游走的图像检索[D];河南大学;2015年

7 汪帮菊;基于随机游走的复杂网络聚类算法研究[D];安徽大学;2016年

8 陆林;图上的智能随机游走分类算法研究及应用[D];扬州大学;2014年

9 王丽莎;基于随机游走模型的个性化信息推荐[D];大连理工大学;2011年

10 胡洁;基于图论的医学图像分割随机游走算法研究[D];南方医科大学;2013年

  本文关键词：基于随机游走的复杂网络聚类算法研究，由笔耕文化传播整理发布。

本文编号：386048