社区发现的模块度问题及其算法研究

发布时间：2017-10-07 22:31

  本文关键词：社区发现的模块度问题及其算法研究

  更多相关文章： 社区发现 模块度 信息传播 亲密度矩阵

【摘要】：随着信息技术的快速发展,人们渐渐发现层出不穷的网络具有相同的特性,例如蛋白质网络、电力网络、社交网络、神经网络,并把这些网络统称为复杂网络。这些网络和人类的生活密切相关,对它们进行研究能够改善人类的生活,促进人类的发展。因此,研究复杂网络具有重要的意义。社区结构是理解复杂网络的一种重要方式。随着对复杂网络的社区结构的研究,出现了很多种类的社区发现算法。模块度最大化算法是这些算法中的一个重要的组成部分,相对其它算法,它能够对社区发现结果的优劣进行量化,从而更好地评价算法结果。但是由于模块度存在分辨率限制问题,使得算法在计算过程中会将某些较小的社区合并,导致算法不准确。为了解决这个问题,本文提出了一种新的算法计算网络中结点的亲密度,并将计算结果导入到模块度局部最优的社区发现算法中,提高了算法的精度。为了计算节点之间的亲密度,本文引入了k路径边中心度,并利用其对网络进行预处理。k路径边中心度能够有效衡量网络中每条边的中心度,反应网络的全局信息。本文首先对k值进行优化,缩短计算时间,并利用边中心度和节点度计算节点之间的亲密度。亲密度将网络的全局信息与局部信息相结合,更好地反映了节点之间的关系。然后,将亲密度矩阵与LM算法结合进行社区发现,得到计算结果。最后进行算法实现,在人工网络和真实网络上进行实验,研究了不同k值下,算法的计算时间以及计算结果,为网络中k值的选取提供参考,并与其它的模块度最大化算法进行对比分析,实验数据表明本文算法的模块度有了一定的提高,并且能够发现更多的社区,有效解决了分辨率限制问题。
【关键词】：社区发现 模块度 信息传播 亲密度矩阵
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要6-7
• Abstract7-11
• 第一章 引言11-16
• 1.1 研究背景和意义11-12
• 1.2 国内外研究现状12-14
• 1.3 关键问题与技术路线14
• 1.4 主要工作与特色之处14-15
• 1.5 本文的组织结构15-16
• 第二章 相关概念介绍16-24
• 2.1 社区结构的定义16-19
• 2.1.1 强社区和弱社区16
• 2.1.2 模块度16-19
• 2.2 模块度最大化算法19-23
• 2.2.1 LM算法19-20
• 2.2.2 CONCLUDE算法20-21
• 2.2.3 COPRA算法21-22
• 2.2.4 OSLOM算法22-23
• 2.3 本章小结23-24
• 第三章 K路径边中心度改进24-29
• 3.0 K路径边中心度定义24-25
• 3.1 ERW-KPATH算法25-28
• 3.2 本章小结28-29
• 第四章 基于亲密度的社区发现算法29-34
• 4.1 亲密度的表示29-32
• 4.2 算法框架32-33
• 4.3 本章小结33-34
• 第五章 实验结果分析与比较34-46
• 5.1 测试数据34-36
• 5.1.1 LFR基准网络34-35
• 5.1.2 真实网络35-36
• 5.2 K值选取36-42
• 5.2.1 LFR基准网络36-38
• 5.2.2 真实网路38-42
• 5.3 算法实验测试42-44
• 5.3.1 LFR基准网络42-44
• 5.3.2 真实网络44
• 5.4 本章小结44-46
• 第六章 总结与展望46-48
• 6.1 本文总结46
• 6.2 未来研究工作展望46-48
• 附录1 攻读学位期间发表的学术论文目录48-49
• 附录2 部分实验数据49-58
• 致谢58-59
• 参考文献59-61

【相似文献】

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

1 ;测测你与伴侣的性匹配度[J];科学大观园;2014年11期

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

1 梁晓燕;黄燕;魏岚;;宿舍亲密度和适应性与大学生孤独感的关系研究[A];全国教育与心理统计测量学术年会论文摘要集[C];2006年

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

1 本报记者 张元章;父母如何教育“不听话”的孩子？[N];珠海特区报;2011年

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

1 王永刚;以数据为中心的在线社会网络若干安全问题研究[D];北京大学;2013年

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

1 华烨;基于相对关系亲密度的局部社团发现算法研究[D];中国科学技术大学;2014年

2 霍丽婕;以增加亲密度为目的的会话分析[D];复旦大学;2013年

3 曹坤宇;基于亲密度及影响力的微博社交兴趣圈挖掘算法研究[D];天津大学;2013年

4 王伟伟;人际亲密度对自我道德行为的影响[D];宁波大学;2014年

5 赵天宸;彩印SNS用户亲密度模型的设计与实现[D];北京邮电大学;2013年

6 张聪;微博用户关注推荐及排名策略研究[D];郑州大学;2012年

7 张家利;社区发现的模块度问题及其算法研究[D];华东师范大学;2015年

，

本文编号：990464