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

基于先验知识的有向复杂网络社团探测算法

作　者: 刘洋
导　师: 刘大有
学　校: 吉林大学
专　业: 计算机应用技术
关键词: 有向网络社团结构社团探测算法电子邮件网络 web链接网络模块函数
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 130次
引　用: 0次
阅　读: 论文下载

内容摘要

复杂系统是21世纪科学研究的重要任务之一,而复杂网络的研究作为复杂系统研究的一个重要部分,它对于理解复杂系统的结构和行为至关重要。近年来复杂网络研究受到了物理和其它学科领域的研究人员的广泛关注。随着研究者对复杂网络性质的物理意义和数学特性的研究的逐步深入,人们发现许多现实世界中存在的网络都具有一个共同性质—社团结构。探测出复杂网络中的社团结构,对于理解网络结构与分析网络特性具有非常重要的意义。社团结构分析在生物学、物理学、计算机图形学和社会学中都有广泛的应用。目前提出的大多数算法存在着一个普遍的缺陷,即算法主要适用于无向网络。对于有向网络这些算法的效果不尽如人意。针对这种情况,我们在对适用于无向网络的社团探测算法分析研究的基础上提出了一种基于节点度先验知识的思想来发现有向网络社团结构的算法,并将该算法应用于已知社团结构的计算机生成有向网络和真实有向网络。我们首先阐述了论文的研究背景,提出研究任务和全文的结构安排。其次系统概述复杂网络的结构特性以及社团结构研究现状。接下来对复杂网络的社团探测算法进行了分析。最后是本文的重点,详细介绍了我们提出来的一种适用于有向网络的社团探测算法。并在实验中我们将算法应用于计算机生成网络,真实网络,获得了满意的结果。

全文目录

提要  4-7
第1章绪论  7-12
  1.1 复杂网络及其社团探测算法的发展  7-9
  1.2 国内外研究动态及面临的挑战  9-10
    1.2.1 国内外研究动态  9
    1.2.2 面临的挑战  9-10
  1.3 本文的研究内容以及论文的结构安排  10-12
第2章复杂网络的结构特征及社团结构研究  12-25
  2.1 复杂网络的结构特性  12-21
    2.1.1 度和度分布  12-13
    2.1.2 小世界性  13-14
    2.1.3 聚集系数和分层指数  14-15
    2.1.4 无标度性  15-17
    2.1.5 路径长度，直径和边介数  17-18
    2.1.6 连通性  18-19
    2.1.7 规则网络模型和随机网络模型  19-20
    2.1.8 复杂网络的阵理论  20-21
  2.2 复杂网络的社团结构研究  21-25
    2.2.1 社团结构的定义  22
    2.2.2 社团划分思路及社团划分的相关问题  22-23
    2.2.3 社团结构划分的评价  23-25
第3章复杂网络的社团探测算法分析  25-32
  3.1 Kernighan-Lin算法  25-26
  3.2 谱二分法  26-27
  3.3 Newman快速算法  27
  3.4 DBSCAN聚类算法  27-28
  3.5 GN算法及改进的算法  28-29
  3.6 Radicchi与Wu-Huberman算法  29-30
  3.7 派系过滤算法  30-32
第4章一种基于先验知识的有向网络社团探测新方法  32-48
  4.1 相关知识  32-37
    4.1.1 先验知识  32-33
    4.1.2 有向网络社团结构的度量函数  33-34
    4.1.3 点的中心性评估  34-37
  4.2 算法实现  37-39
  4.3 算法的测试  39-48
    4.3.1 计算机生成网络  39-40
    4.3.2 真实网络  40-48
第5章总结与展望  48-50
  5.1 总结  48-49
  5.2 展望  49-50
参考文献  50-52
致谢  52-53
摘要  53-55
Abstract  55-57

基于先验知识的有向复杂网络社团探测算法

内容摘要

全文目录

相似论文