加权复杂网络中的社区发现算法研究

发布时间：2017-10-13 02:05

  本文关键词：加权复杂网络中的社区发现算法研究

  更多相关文章： 加权复杂网络 社区发现 标签传播 相对介数

【摘要】：近年来,随着互联网技术和计算机技术的飞速发展,特别是Web2.0时代的不断纵深,使得能够表示人与人之间、人与物之间、物与物之间关系的复杂网络的规模呈现出飞速增长的态势。针对复杂网络的研究已经成为学术界和工业界共同关注的热点问题。复杂网络不仅具有小世界、无标度等特点,而且具有明显的社区结构特性,研究复杂网络中的社区发现能够解决很多实际应用领域中的具体问题。现有的研究成果大多针对无权的复杂网络展开研究。然而,在现实生活中,很多复杂网络中的关系并非完全是简单的存在与否的布尔关系,往往存在诸如节点之间距离的差异、权限的高低、执行的先后等定量描述的相互关系,即加权复杂网络。因此,研究针对加权复杂网络的社区发现问题具有更加广泛的实际应用意义和重要的研究价值。本文即针对现实的复杂网络展开研究,特别针对加权复杂网络,运用有权图方法进行加权复杂网络的社区发现算法研究。首先,针对加权复杂网络的特点,结合标签传播原理,提出了利用有权图的基于标签传播的加权复杂网络社区发现算法。该算法通过不断地调整节点的标签,删除权值最大的边,最终达到收敛,实现对有权图的快速社区发现。其次,针对加权复杂网络的特点,通过分析Girvan-Newman算法中边介数的概念和应用场景,针对加权复杂网络,提出了有权图的相对介数的新概念。基于相对介数不断删除相对介数最小的边,并获取连通子图,最终达到收敛条件,进而实现对加权复杂网络的社区发现,大大提高了社区发现的有效性。最后,利用三种真实数据集建立的加权图对本文提出的算法和GN算法进行对比,实验表明本文提出的算法具有良好的社区发现性能。
【关键词】：加权复杂网络 社区发现 标签传播 相对介数
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-9
• 第1章 引言9-17
• 1.1 研究背景及意义9-13
• 1.1.1 研究背景9-10
• 1.1.2 研究意义10-13
• 1.2 国内外研究现状13-14
• 1.3 主要研究内容14-15
• 1.4 本文组织结构15-17
• 第2章 社区发现相关技术17-26
• 2.1 图和复杂网络17-19
• 2.1.1 图17-18
• 2.1.2 复杂网络18-19
• 2.2 社区与社区发现19-25
• 2.2.1 社区19-21
• 2.2.2 社区发现算法21-25
• 2.3 本章小结25-26
• 第3章 基于标签传播的加权复杂网络社区发现算法26-35
• 3.1 问题描述26-27
• 3.2 标签赋予算法27-30
• 3.2.1 算法思想27-28
• 3.2.2 算法描述28-30
• 3.3 标签传播与社区发现算法30-34
• 3.3.1 算法思想30-31
• 3.3.2 算法描述31-34
• 3.4 算法分析34
• 3.5 本章小结34-35
• 第4章 基于相对介数的加权复杂网络社区发现算法35-43
• 4.1 问题定义35-36
• 4.2 相对介数统计算法36-39
• 4.2.1 预备知识36-37
• 4.2.2 算法描述37-39
• 4.3 社区发现算法39-41
• 4.3.1 算法思想39-40
• 4.3.2 算法描述40-41
• 4.4 算法分析41-42
• 4.5 本章小结42-43
• 第5章 实验与分析43-51
• 5.1 实验环境43
• 5.2 实验数据集43-45
• 5.3 实验评估与分析45-50
• 5.3.1 算法运行时间45-47
• 5.3.2 算法有效性47-50
• 5.4 本章小结50-51
• 第6章 总结与展望51-53
• 6.1 总结51
• 6.2 展望51-53
• 致谢53-54
• 参考文献54-56
• 攻读学位期间发表的学术论文及参加科研情况56-57

【参考文献】

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

1 赵卓翔;王轶彤;田家堂;周泽学;;社会网络中基于标签传播的社区发现新算法[J];计算机研究与发展;2011年S3期

2 季青松;赵郁忻;陈乐生;陈秀真;李生红;;有效改善标签传播算法鲁棒性的途径[J];信息安全与通信保密;2012年09期

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

1 曲鹏程;动态社会网络挖掘算法研究[D];吉林大学;2008年

，

本文编号：1022189