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

复杂网络中的社团结构检测算法研究

作　者: 李亚飞
导　师: 于双元
学　校: 北京交通大学
专　业: 计算机科学与技术
关键词: 社团检测 谱分析法 近邻传播 局部社团发现 可视化实验平台
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 158次
引　用: 1次
阅　读: 论文下载
 

内容摘要


摘要随着复杂网络理论研究的不断深入及在各领域的应用,其所具有的社团结构特征吸引了广泛的关注。寻找和分析复杂网络的社团结构对于反映和理解整个网络的构成和功能有重要的意义。本论文主要研究社团结构检测问题,提出了基于谱分析法和近邻传播的算法、基于局部发现的算法两种检测方法,并建立了可视化实验平台。论文对传统的Normal矩阵谱分析法及近邻传播算法进行了研究。传统的Normal矩阵谱分析法在网络社团结构不明显的情况下难以得到理想的结果,针对这个问题,论文提出了一种基于谱分析法和近邻传播的社团检测算法。该算法采用近邻传播算法对多个Normal矩阵特征向量的元素进行聚类分析,根据聚类结果来获得整个网络的社团检测结果。这种基于谱分析法和近邻传播的算法在无需预先知道社团数目的前提下对于社团结构不明显的网络也具有较好的检测效果。论文针对目前部分算法时间复杂度较高、无法对大规模网络进行检测的问题提出了一种基于局部发现的社团结构检测算法。论文设计了一个用于快速寻找指定节点社团成员的局部社团检测算法,通过对该算法进行扩展,不断将检测出的局部社团成员从网络中移除来进行网络整个社团结构的检测。这种基于局部发现的社团检测算法在不需要预先知道社团数目的基础上具有较好的时间复杂度,并且检测效果也比较理想。论文设计和实现了一个可视化实验平台,该平台能够对社团检测结果进行可视化显示,并计算相应数据。使用该平台将论文提出的两种算法与GN算法、CNM算法进行对比,实验数据表明,基于谱分析法和近邻传播的算法在无需预先知道社团数目的基础上无论网络的社团结构是否明显都具有较好的检测效果,基于局部发现的算法具有很好的计算效率、无需知道社团数目并且检测效果也令人满意。

全文目录


致谢  5-6
摘要  6-7
ABSTRACT  7-11
1 绪论  11-15
  1.1 论文研究背景及意义  11
  1.2 国内外研究现状  11-13
  1.3 论文研究的主要内容及组织结构  13-15
2 复杂网络及其社团结构检测  15-29
  2.1 复杂网络基本概念  15-17
    2.1.1 复杂网络的发展  15-16
    2.1.2 复杂网络的表示  16
    2.1.3 复杂网络的小世界特性  16-17
    2.1.4 复杂网络的无标度特性  17
  2.2 复杂网络社团结构检测  17-28
    2.2.1 复杂网络社团结构的定义  17-18
    2.2.2 复杂网络社团结构强度的衡量标准  18-19
    2.2.3 复杂网络社团检测结果的比较方法  19-20
    2.2.4 复杂网络社团结构检测的经典算法  20-26
    2.2.5 复杂网络常用局部社团检测算法  26-28
  本章小结  28-29
3 基于谱分析法和近邻传播的社团检测算法  29-36
  3.1 Normal矩阵谱分析法  29-30
  3.2 近邻传播算法  30-32
  3.3 基于谱分析法和近邻传播的社团检测算法设计  32-34
    3.3.1 算法思想  32
    3.3.2 算法描述  32-34
  3.4 基于谱分析法和近邻传播的社团检测算法分析  34-35
  本章小结  35-36
4 基于局部发现的社团结构检测算法  36-41
  4.1 一种局部社团检测算法设计  36-38
    4.1.1 算法思想  36
    4.1.2 算法描述  36-38
  4.2 基于局部发现的社团结构检测算法设计  38-39
    4.2.1 算法思想  38
    4.2.2 算法描述  38-39
  4.3 基于局部发现的社团结构检测算法分析  39-40
  本章小结  40-41
5 复杂网络社团结构检测算法实验  41-52
  5.1 可视化实验平台  41-44
    5.1.1 实验平台设计  41-42
    5.1.2 实验平台实现  42-44
  5.2 实验结果及性能分析  44-52
    5.2.1 实验网络  44-47
    5.2.2 实验结果  47-50
    5.2.3 性能分析  50-52
6 总结与展望  52-54
  6.1 论文总结  52
  6.2 未来工作展望  52-54
参考文献  54-56
作者简历  56-58
学位论文数据集  58

相似论文

  1. P2P流量识别方法研究,TP393.06
  2. 新闻视频故事单元分割,TP391.41
  3. 小水线面双体船结构疲劳分析及典型节点优化研究,U674.951
  4. 基于电磁波传播理论的围岩电阻率测量方法研究与仪器实现,P631.811
  5. NPC乳鼠Purkinje细胞原代培养及Ca~（2+）动力学特征和小鼠小脑氨基酸测定,R329
  6. 基于近邻传播聚类的点云简化研究,TP391.41
  7. 大型薄膜型LNG船结构疲劳强度分析,U661.43
  8. 超大型矿砂船首部结构强度评估与优化设计,U661.4
  9. 地震荷载作用下高填方路堤动力响应分析,U416.12
  10. 胰岛素的电化学性质与尿酸的相互作用研究,R96
  11. 基于半监督学习的两种聚类算法研究,TP181
  12. 半潜式平台结构强度评估比较研究,U674.941
  13. BBS短文本聚类技术研究,TP393.094
  14. 基于近邻传播和凝聚层次的文本聚类方法,TP391.1
  15. β-TC3细胞膜与胰岛素受体结合G蛋白的鉴定,R587.1
  16. 承压含水层中古咸水体迁移过程的确定性及随机性模拟,P641.2
  17. 大跨度梯形钢屋架双坡屋盖风振响应和风振系数研究,TU391
  18. OLED封装材料气体渗透率的测量,TN312.8
  19. 海上风力机模块整体运输方案设计,TM614
  20. 乌江流域径流演变规律分析及径流预报模型研究,TV121

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com