学位论文 > 优秀研究生学位论文题录展示

一种加权网络社团结构划分算法

作　者: 王娟
导　师: 王卫华
学　校: 武汉理工大学
专　业: 计算数学
关键词: 加权网络社团结构社团模块度 CNM算法
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 322次
引　用: 0次
阅　读: 论文下载

内容摘要

社团结构是很多实际复杂网络的一个重要属性,研究和分析社团结构有利于更好地了解网络结构和把握网络信息。2006年Sullivan G等人的研究成果,使得复杂网络中的社团发现成为近几年复杂网络领域的一个研究热点并形成了复杂网络中一个重要的研究方向。随着人们陆续发现社会、生物等网络中存在社团结构,社团结构划分算法的研究就已成为复杂网络领域研究的一个热点。研究发展至今,已有多种能够快速而准确地探测到中小规模网络社团结构的算法。但在分析大规模及超大规模网络的过程中仍面临着算法时间复杂度和精确度之间的矛盾。算法时间复杂度低的划分精确度不高,划分精确度高的算法时间复杂度也高,造成大规模网络可靠的社团结构分析难以实现。另外,多数算法都是在布尔关系下的网络中实现的,而现实存在的网络中节点间大都存在着一些不容忽视的客观信息,即现实网络多为加权网络。所以设计可以解决算法时间复杂度和精确度之间矛盾,并能对加权网络社团结构分析的算法是十分必要的。基于以上问题,本文研究了社团结构划分算法及具有社团结构的加权网络建模,并改进Clauset、Newman和Moore等人提出的贪婪算法(简称为CNM算法)对计算机生成的网络进行算法测试,且以股票市场为例进行加权网络社团结构分析的数值实验。结果表明,本文所提出的算法能够很好地解决上述问题,并取得较好的效果。论文的主要贡献如下：1.采取自下而上的凝聚法解决较大规模网络社团结构分析过程中,小规模社团丢失和网络中节点未被正确划分的问题,即提高了算法的精确度。2.在社团结构划分算法中,用边的归属替代点的归属划分社团结构,不仅可以解决“骑墙节点”错误划分,还能有效地减小存储空间,提高运行速度,也有利于解决时间复杂度与精确度之间的矛盾。3.改进CNM算法,引入点权和边权使其适用于大规模加权网络的社团结构划分,并将此算法引入到股票市场价格波动分析中。

一种加权网络社团结构划分算法

内容摘要

全文目录

相似论文