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

复杂网络中的社团检测问题研究

作　者: 杨树忠
导　师: 罗四维
学　校: 北京交通大学
专　业: 计算机应用技术
关键词: 复杂网络社团检测模块化函数Q 分辨率极限模块密度D 负社团正则化模块密度函数NMD 扩散核自适应仿射传播可视化
分类号: O157.5
类　型: 博士论文
年　份: 2009年
下　载: 328次
引　用: 0次
阅　读: 论文下载

内容摘要

近年来,由于信息技术的飞速发展,科学家和学者们能够越来越容易地在现实世界中收集到高通量的网络数据,这使得复杂网络的研究变得炙手可热起来。除了Watts和Strogatz在1998年发现的小世界特性以及Barabasi和Albert在1999年发现的无标度(尺度)特性外,网络的社团(社区、模块)结构特性被认为是复杂网络中最重要的统计特性之一。目前,关于网络中的社团仍然不存在统一的定义,通常指的是满足下面条件的节点子集：子集内部节点之间具有稠密的连接,而与子集外部的节点具有稀疏的连接。研究表明,网络的这种社团结构与某些功能属性有着紧密的联系,比如网络的鲁棒性和信息快速传递特性等。因此在网络中描述和检测这些社团结构具有重要的实际意义并已成为近几年来的研究热点。本论文中,我们主要关注复杂网络中社团结构检测相关问题的研究,取得的主要研究成果如下：1.提出了一种新的社团检测方法-JEOMD。该方法以加入惩罚项的模块密度函数D作为指标函数,并使用跳跃极值最优化方法来优化该指标函数,能够得到网络的层次分割结果。在一组真实网络上的实验表明,与基于模块化函数Q的优化方法相比,JEOMD方法能够更有效地检测出网络中存在的不同层次和不同规模的社团结构。在该组真实网络及其对应的随机网络上的对比实验表明,加入惩罚项的模块密度函数D作为社团检测的指标函数在一定程度上比模块化函数Q更有效。2.提出了一个新的衡量社团划分质量的指标函数,称之为标准化模块密度(normalized modularity density-NMD)。在示例网络中证明了NMD能够改善模块化函数Q中存在的分辨率极限问题；证明了NMD与图分割中广泛应用的normalized-cut目标函数存在着紧密的联系,即当社团数目m已知时,最大化标准化模块密度相当于最小化目标函数normalized-cut。使用改进的模拟退火算法优化指标NMD。在一组模拟网络上的实验表明,与基于模块化函数Q的优化方法相比,基于NMD的方法能够取得更高的检测正确率；在一组真实网络上的实验表明,基于NMD的方法能够检测出网络中更精细的模块结构,从而为NMD能够改善Q的分辨率问题提供了更进一步的证据；把指标函数NMD和D推广到其加权形式NMDω和Dw,并用于在加权网络中进行社团检测。分析了加权模块化函数Qw同样存在分辨率极限问题；指出了加权模块密度函数Dw存在的负社团问题；在两个实例网络上证明了NMDω不仅能够克服Qw中存在的分辨率极限问题,而且能够避免Dw中出现的负社团问题。为了比较指标NMDω与Qw和Dw在加权网络社团检测中的性能,使用模拟退火算法实现三个指标的优化。在一组模拟网络上的实验表明,优化NMDω指标能够取得比优化Qw和Dw更高的检测正确率；在一组真实网络上的实验表明,优化NMDω指标,不仅能够从加权网络中检测出精细尺度下的社团,尤其是优化Qw所不能检测出来的小而稠密的社团,而且能够避免优化Dw时出现的负社团问题。3.提出了一种基于自适应核仿射传播的网络社团检测方法-AKAP。在该方法中,标准化的马尔可夫扩散核(Markov diffusion kernel)被用来隐式地衡量节点之间的非相似度,引入自适应仿射传播方法优化得到的非相似度矩阵。在模拟网络上的实验表明,与Newman快速算法相比,AKAP方法能够取得更高的检测正确率；在一组真实网络上的实验表明,AKAP方法能够有效地检测出网络中存在的有意义的社团结构和包含的社团数目。4.提出了一种有效的网络节点的可视化方法。在该方法中,定义了一种新的节点间距离,将得到的距离矩阵作为全局保形映射Isomap的测地线距离,应用Isomap方法得到网络的二维可视化结果。在模拟网络上的实验表明,与基于能量模型的可视化方法相比,我们的方法能够更好地保持原始网络中节点的局部和全局相似性,且当网络具有清晰的社团结构时,得到的二维可视化点集也具有紧凑的聚类特性,因此能够从可视化结果中判断原始网络是否具有社团结构特性,也可以对可视化的结果继续采用传统的聚类方法进行聚类以得到网络每个社团的具体成员。

全文目录

致谢  5-6
摘要  6-8
ABSTRACT  8-14
第一章绪论  14-35
  1.1 引言  14-15
  1.2 复杂网络的发展历程  15-16
  1.3 复杂网络的研究意义及其应用前景  16-19
  1.4 复杂网络的基本概念  19-24
    1.4.1 复杂网络的定义及表示方式  19
    1.4.2 网络的小世界特性  19-22
    1.4.3 网络的无标度特性  22-23
    1.4.4 网络的社团结构特性  23-24
  1.5 复杂网络中的社团检测  24-32
    1.5.1 社团检测的重要意义  24-26
    1.5.2 社团检测的研究现状  26-32
  1.6 本文的研究内容及组织  32-35
第二章基于跳跃极值最优化的网络社团检测方法  35-47
  2.1 引言  35-37
  2.2 加入了惩罚项的模块密度函数D  37
  2.3 跳跃极值最优化  37-41
    2.3.1 极值最优化思想  37-38
    2.3.2 跳跃机制  38-40
    2.3.3 JEOMD方法的流程  40-41
  2.4 实验结果及其分析  41-46
    2.4.1 社团检测的层次性  41-43
    2.4.2 社团检测的尺寸问题  43-45
    2.4.3 D与Q两个指标的有效性比较  45-46
  2.5 小结  46-47
第三章非加权网络中社团检测的新指标  47-62
  3.1 引言  47-48
  3.2 标准化模块密度  48-49
  3.3 NMD改善Q的分辨率极限的证明  49-52
    3.3.1 NMD不会将团分解成两部分  49-50
    3.3.2 优化NMD不会把多个团合并成一个社团  50-51
    3.3.3 优化NMD能够检测出不同大小的社团  51-52
  3.4 模拟退火优化指标NMD  52-53
  3.5 实验结果及其分析  53-60
    3.5.1 模拟网络  54-57
    3.5.2 真实网络  57-60
  3.6 小结  60-62
第四章加权网络中社团检测的指标函数  62-73
  4.1 引言  62-63
  4.2 加权的标准化模块密度  63-64
  4.3 NMD_w改善Q_w的分辨率极限及避免D_w中的负社团问题的证明  64-67
    4.3.1 NMD_w能够改善Q_w的分辨率极限问题  64-66
    4.3.2 NMD_w能够避免D_w中的负社团问题  66-67
  4.4 实验结果及其分析  67-72
    4.4.1 模拟网络  67-70
    4.4.2 真实网络  70-72
  4.5 小结  72-73
第五章基于自适应核仿射传播的社团检测方法  73-85
  5.1 引言  73-74
  5.2 几种常用的图核  74-77
    5.2.1 指数扩散核和Laplacian扩散核  75-76
    5.2.2 Neumann扩散核和Newman结构相似性  76
    5.2.3 交换时间核  76-77
    5.2.4 马尔可夫扩散核  77
  5.3 自适应仿射传播算法  77-79
  5.4 实验结果及其分析  79-83
    5.4.1 模拟网络  79-81
    5.4.2 真实网络  81-83
  5.5 小结  83-85
第六章基于非线性维数缩减的网络节点可视化  85-97
  6.1 引言  85-86
  6.2 图的可视化方法  86-87
  6.3 节点非相似度定义  87-88
  6.4 节点非相似度的有效性检验  88-89
    6.4.1 简单排序算法  88-89
    6.4.2 排序矩阵的亮度图像显示  89
  6.5 使用非线性降维技术进行二维投影  89-90
  6.6 实验结果及其分析  90-95
  6.7 小结  95-97
第七章总结与展望  97-100
  7.1 本文总结  97-98
  7.2 展望及今后的工作  98-100
附录A 几种常用的网络研究及可视化工具  100-101
附录B 文中模拟网络的生成方法  101-104
附录C 社团检测算法性能的两种常用评价指标  104-106
参考文献  106-117
攻读博士期间发表和已录用的学术论文  117-120
学位论文数据集  120

复杂网络中的社团检测问题研究

内容摘要

全文目录

相似论文