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

复杂网络社团模型与结构研究

作　者: 汪大明
导　师: 谭东风
学　校: 国防科学技术大学
专　业: 管理科学与工程
关键词: 复杂网络节点特征社团模型随机游走社团探测
分类号: C912.6
类　型: 硕士论文
年　份: 2010年
下　载: 307次
引　用: 0次
阅　读: 论文下载

内容摘要

现实世界中大量的复杂系统都可以用网络来表示和分析,复杂网络研究在近10年来取得了长足的进展。作为本文关注的对象,社团结构是许多实际复杂网络特别是复杂社会网络的重要结构特征,吸引了各个领域众多研究者的兴趣。当前研究复杂网络社团结构的具体问题主要包括:怎样合理地构造具有社团结构的网络模型以及如何快速、准确地从众多大规模的实际网络中寻找社团结构。本文在总结已有成果的基础上做了如下工作:一、提出了基于节点特征向量的社团网络(NPCN)生成模型。传统上,对复杂网络的研究着力于分析节点间复杂的连接关系,有别于此,NPCN模型将网络节点视为具有多种特征的内容主体。在开放、生长的网络环境中,新节点将优先与具有相近特征的节点相连,对于很多实际网络而言,NPCN模型更符合我们理解上的直觉。数值分析表明,NPCN具有度的幂率分布,体现了大多实际网络中“适者更富”的特点,同时,NPCN呈现“物以类聚,人以群分”的抱团特性,社团结构清晰。进一步的分析表明,经典的BA无标度网络模型只是NPCN模型的一个特例。NPCN模型规则简单、自然,为诸如引文网、合作网等很多实际网络的建模提供了描述上的借鉴。二、研究了基于随机游走的社团探测方法。研究了Rosvall等提出的基于随机游走的社团探测方法,将网络邻接矩阵作一定变换后构造了随机游走的转移概率矩阵,该转移概率矩阵定义了一个非周期不可约的马尔科夫过程,而随机游走路径可以表示为相应的马尔科夫链。在此转移概率矩阵的约束下,用乘幂法(Power Method)得到平稳态的马尔科夫链中各个状态的稳定概率分布,对应了节点在随机游走过程中的访问概率。以此为基础定义了社团划分的指标函数并设计了可回退贪心优化算法(RGA)用于对该函数进行优化。RGA在社团探测的准确性和复杂性之间取得了更好的平衡,同时也能用于其它采用不同指标函数的社团探测方法。三、对社团网络的抗毁性进行了研究。将社团探测应用于复杂网络抗毁性研究,分析了不同攻击策略对网络的毁伤效果,仿真表明,优先攻击社团网络中的“桥梁”具有较好的毁伤效果,这为网络攻击和防护提供了新的思路,从而在军事应用的角度更加明确了社团研究的意义。

全文目录

摘要  8-9
ABSTRACT  9-11
第一章绪论  11-15
  1.1 引言  11-12
  1.2 国内外研究现状  12-13
  1.3 研究内容与方法  13-14
  1.4 论文组织结构  14-15
第二章复杂网络社团研究概述  15-32
  2.1 复杂网络理论  15-21
    2.1.1 网络的表示  16-17
    2.1.2 网络的特征参数  17-18
    2.1.3 从随机图到复杂网络理论  18-21
  2.2 复杂网络社团划分算法  21-28
    2.2.1 社团划分的定量描述  21-23
    2.2.2 社团划分算法综述  23-28
  2.3 具有社团结构的网络模型  28-32
    2.3.1 合并派系的演化模型  28-29
    2.3.2 社团内部度优先连接的演化模型  29-30
    2.3.3 局域世界网络演化模型  30-32
第三章基于兴趣特征偏好的社团网络模型  32-41
  3.1 基于权重向量的节点兴趣特征表示  32-33
  3.2 模型描述  33-37
  3.3 模型的数值分析  37-41
    3.3.1 度及度分布  37-38
    3.3.2 聚集系数  38
    3.3.3 社团结构分析  38-41
第四章基于随机游走的社团探测方法  41-62
  4.1 算法思想及理论模型  41-53
    4.1.1 随机游走与PageRank  41-47
    4.1.2 基于PageRank 的网络节点Huffman 编码  47-49
    4.1.3 对社团和节点的二级编码方法  49-53
  4.2 可回退的贪心优化算法  53-57
    4.2.1 相关优化方法介绍  53-55
    4.2.2 可回退的贪心优化算法  55-57
  4.3 社团探测与社团网络抗毁性  57-62
    4.3.1 复杂网络抗毁性分析  58-59
    4.3.2 社团网络抗毁性研究  59-62
第五章总结与展望  62-66
  5.1 本文的主要工作  62-63
  5.2 本文的研究意义与创新  63-64
  5.3 研究的不足与展望  64-66
结束语  66-67
致谢  67-69
参考文献  69-73
作者在学期间取得的学术成果  73

复杂网络社团模型与结构研究

内容摘要

全文目录

相似论文