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

基于拓扑势的网络社区发现方法研究

作　者: 李泓波
导　师: 张健沛
学　校: 哈尔滨工程大学
专　业: 计算机应用技术
关键词: 拓扑势不确定性测度重叠社区发现变规模社区无损网络压缩
分类号: TP393.02
类　型: 博士论文
年　份: 2013年
下　载: 91次
引　用: 0次
阅　读: 论文下载

内容摘要

由于21世纪的第二个十年将是实现人、机、物和信息等要素和谐共生的物联网和社会网络时代，许多国家都将面向网络化社会的研究提升到了国家战略层次，而在各种网络的实际应用中社区发现是一个不可逾越的步骤，所以深入展开网络社区发现研究具有十分重要的意义。拓扑势理论是一种新的社区发现理论。较之传统社区发现方法，基于该理论的社区发现方法具有多方面的优势。针对传统社区发现方法和拓扑势社区发现方法存在的不足，并以对拓扑势理论及其社区发现方法进行改进、完善和发展为主线，本文主要从四个方面展开研究。首先，证明了拓扑势熵最小值点存在性定理。网络中拓扑势熵最小值点的存在性是拓扑势理论及其方法进行社区发现的前提和基础，然而目前对其只限于有限的实证研究。该定理表明了拓扑势熵最小值点在千差万别的网络中存在的一般性，明确了基于拓扑势的网络社区发现方法的应用范围。其次，提出了基于拓扑势的重叠节点社区归属不确定性测度。目前许多社区发现方法为只允许一个节点只能属于一个社区的硬方法，缺乏现实合理性。事实上，众多网络中的节点的社区归属具有亦此亦彼性。重叠社区发现方法虽然允许一个节点可以同时属于多个社区，但目前尚缺乏刻画重叠节点归属不同社区的程度指标。该指标的缺乏严重阻碍了对社区的挖掘和分析。为了验证该测度的有效性和合理性，提出了基于贪婪策略的重叠社区发现方法、基于归属不确定性的社区节点重要度排序算法和基于Pareto原理的重叠社区发现方法。基于贪婪策略的重叠社区发现方法克服了处于社区边缘的节点与其他社区的联系被人为割裂的问题，基于归属不确定性的社区节点重要度排序算法针对社区发现结果难以理解的问题提出解决方案，基于Pareto原理的重叠社区发现方法弥补了基于贪婪策略的重叠社区发现方法中存在的重叠节点数量相对较多的不足。第三，提出了基于重叠节点归属不确定性的变规模重叠社区发现方法。在该方法中，根据力学中的力的分解原理对前面提出的重叠节点归属不确定性测度进行了改进。该方法不但可以达到与目前拓扑势方法相当的发现效果，还能提供较之相对宏观或微观的社区，实现了对社区规模的控制和定制。第四，提出了基于拓扑势社区发现的无损网络压缩方法。为满足不同的需求，此项研究提出了两个网络无损网络压缩方法。一个方法以节点与社区代表点的相对距离为依据进行节点重要性的判断，区分不同距离节点的重要性，进而实现按层次的网络无损压缩；另一个方法以节点在社区构成中所起的作用为依据以判断节点的重要性，并对节点的重要性进行了量化，实现了按压缩比率的网络无损压缩。对比实验表明，两种方法不但可以获得理想的压缩率，保留社区间的关联关系，而且可以根据需要在压缩过程中保留社区中的重要节点或社区基本结构。

全文目录

摘要  5-7
ABSTRACT  7-12
第1章绪论  12-22
  1.1 研究背景和意义  12-13
  1.2 研究现状  13-18
    1.2.1 经典社区发现算法比较分析  13-15
    1.2.2 NBTP 社区发现方法存在的问题  15-17
    1.2.3 BTP 社区发现方法存在的问题  17-18
    1.2.4 NBTP 方法和 BTP 方法存在问题比较  18
    1.2.5 NBTP 方法和 BTP 方法问题汇总  18
  1.3 本文的研究内容  18-20
  1.4 本文的组织结构  20-22
第2章拓扑势熵最小值点存在性研究  22-35
  2.1 拓扑势理论基本思想及相关公式、概念和算法  22-25
    2.1.1 拓扑势理论基本思想  22-23
    2.1.2 拓扑势理论相关公式和概念  23-25
    2.1.3 基于拓扑势理论的社区发现算法 HCD  25
  2.2 拓扑势熵最小值点存在性证明  25-31
    2.2.1 相关引理  26-31
    2.2.2 拓扑势熵最小值点存在性定理  31
  2.3 拓扑势理论相关性质  31-32
  2.4 实例验证  32-34
  2.5 本章小结  34-35
第3章基于拓扑势的重叠节点社区归属不确定性测度研究  35-65
  3.1 重叠节点社区归属不确定性测度  36-37
  3.2 基于贪婪策略的重叠社区发现方法 GS  37-49
    3.2.1 GS 方法基本思想  38-39
    3.2.2 GS 算法描述  39-40
    3.2.3 GS 算法时间复杂度分析  40-41
    3.2.4 GS 算法在经典网络上的应用  41-49
    3.2.5 实验分析  49
  3.3 基于归属不确定性的社区节点重要度排序算法 IS  49-55
    3.3.1 相关工作  50-51
    3.3.2 IS 算法基本思想  51-52
    3.3.3 IS 算法描述  52-53
    3.3.4 IS 算法时间复杂度分析  53
    3.3.5 实验与分析  53-55
  3.4 基于 Pareto 原理的重叠社区发现方法 BPP  55-64
    3.4.1 HCD 问题描述  56-58
    3.4.2 HCD 问题解决方案  58-60
    3.4.3 BPP 算法描述及算法分析  60
    3.4.4 对比实验  60-64
  3.5 本章小结  64-65
第4章基于重叠节点归属不确定性的变规模重叠社区发现  65-89
  4.1 改进的重叠节点社区归属不确定性测度  65-66
  4.2 变规模社区  66-67
    4.2.1 变规模社区定义  66-67
    4.2.2 提出变规模社区的意义  67
  4.3 变规模社区发现算法 VS  67-69
    4.3.1 VS 算法描述  67-69
    4.3.2 VS 算法时间复杂度分析  69
  4.4 社区网络密度与归属不确定性测度关系分析  69-71
  4.5 对比实验  71-85
    4.5.1 VS 方法在空手道俱乐部网络上的应用  71-74
    4.5.2 VS 方法在海豚社会网络上的应用  74-77
    4.5.3 VS 方法在美国政治书籍网络上的应用  77-85
  4.6 实验分析  85-88
    4.6.1 社区规模控制有效性分析  85
    4.6.2 VS 方法社区发现有效性及改进的不确定性测度合理性分析  85-88
  4.7 本章小结  88-89
第5章基于拓扑势社区发现的无损网络压缩  89-107
  5.1 无损社会网络压缩方法 SNC  90-97
    5.1.1 社区节点重要性分析  90-93
    5.1.2 SNC 方法基本思想  93-94
    5.1.3 SNC 方法描述  94-96
    5.1.4 SNC 方法时间复杂度分析  96-97
  5.2 SNC 实验及分析  97-100
    5.2.1 空手道俱乐部网络上的压缩实验  97
    5.2.2 海豚社会网络上的压缩实验  97-100
    5.2.3 实验分析  100
  5.3 SNC 方法存在的问题  100-101
  5.4 无损社会网络压缩方法 NSNC  101-102
    5.4.1 SNC 和 NSNC 中节点重要性的区别  101
    5.4.2 BIV 算法描述  101-102
    5.4.3 NSNC 算法时间复杂度分析  102
  5.5 NSNC 方法与 SNC 方法对比实验及分析  102-105
    5.5.1 对比实验  102-104
    5.5.2 对比实验分析  104-105
  5.6 本章小结  105-107
结论  107-109
参考文献  109-120
攻读博士学位期间发表的论文和取得的科研成果  120-122
致谢  122

基于拓扑势的网络社区发现方法研究

内容摘要

全文目录

相似论文