基于共同邻居的复杂网络社团检测算法研究

基于共同邻居的复杂网络社团检测算法研究

论文摘要

随着信息技术的发展,现实世界中的许多复杂系统能够以网络的形式呈现。网络中的节点表示系统中的实体,而节点之间的连接表示实体之间的联系。由于现实世界网络的统计特征不同于规则网络和随机网络,因而将描述它们的理论模型称为复杂网络。复杂网络的社团结构表现为:紧密联系的局部节点属于同一社团,属于不同社团的节点之间联系较少。研究网络的社团结构有助于分析网络的结构特点、功能模块、信息传递、演化过程等,以及解决工程应用中的相关问题。因此,有关复杂网络社团检测的研究一直是热点问题。层次聚类方法能够实现多粒度的社团检测,揭示网络内部的层次化结构。但是,在部分应用中,非层次聚类方法给出的一种特定的社团划分方案就足以解决问题。社团划分的质量和速度一直是评价社团检测方法的关键。为了从复杂网络中挖掘出高质量的社团结构,同时保证较快的执行速度,本文提出了两个社团检测算法,分别是基于共同邻居的层次化社团结构检测算法和基于共同邻居约束标签传播的社团检测算法。本文的创新点如下:1)根据均值聚类的思想,从简单的邻接关系中提取关于共同邻居的信息,定义了节点亲密度以衡量相邻节点的相似性。基于节点亲密度,本文提出了一种分裂算法以层次化的方式分析网络的社团结构。该算法采用堆存储数据及索引,能够快速实现搜索最小亲密度、更新局部亲密度。实验结果表明该算法在层次化社团结构检测方面的良好效果,以及在节点度分布较为均匀的网络中执行速度较快。2)将社团检测问题用两个优化目标来描述:社团内的联系尽可能多,以及同一社团内的节点尽量共享邻居。在此基础上,本文提出了采用标签传播策略优化两个目标的算法。为了减弱过多节点标签趋于一致的倾向,引入了已有的关于社团内边数的约束和提出的关于社团内共同邻居数的约束。结合实验对比结果和理论分析,选择合适的约束强度和加权系数。实验结果验证了该算法在社团划分质量和速度方面的优势,特别是在社团结构模糊的情况下。

论文目录

  • 摘要
  • abstract
  • 第一章 绪论
  •   1.1 研究背景及意义
  •     1.1.1 研究背景
  •     1.1.2 研究意义
  •   1.2 研究现状
  •     1.2.1 层次聚类算法
  •     1.2.2 谱算法
  •     1.2.3 动态算法
  •     1.2.4 其他方法
  •   1.3 研究内容与主要工作
  •   1.4 论文结构安排
  • 第二章 相关理论及算法
  •   2.1 复杂网络的部分理论
  •     2.1.1 图
  •     2.1.2 复杂网络的统计特征
  •     2.1.3 复杂网络的性质
  •   2.2 社团检测的相关研究
  •     2.2.1 社团的定义
  •     2.2.2 社团划分质量的评估
  •     2.2.3 基准网络
  •   2.3 层次聚类算法
  •   2.4 标签传播算法
  •   2.5 本章小结
  • 第三章 基于共同邻居的层次化社团结构检测算法
  •   3.1 引言
  •   3.2 理论基础
  •     3.2.1 分裂算法
  •     3.2.2 均值聚类
  •   3.3 算法设计
  •     3.3.1 定义相邻节点亲密度
  •     3.3.2 搜索最小亲密度
  •     3.3.3 判断是否分裂
  •     3.3.4 快速更新亲密度
  •     3.3.5 算法流程与概述
  •   3.4 实验验证与讨论
  •     3.4.1 实验环境和数据集
  •     3.4.2 关于计算机合成网络的实验
  •     3.4.3 关于现实世界网络的实验
  •   3.5 本章小结
  • 第四章 基于共同邻居约束标签传播的社团检测算法
  •   4.1 引言
  •   4.2 理论基础
  •     4.2.1 标签传播
  •     4.2.2 目标优化
  •   4.3 算法设计
  •     4.3.1 优化目标
  •     4.3.2 约束强度
  •     4.3.3 更新序列
  •     4.3.4 更新规则
  •     4.3.5 算法流程与概述
  •   4.4 实验验证与讨论
  •     4.4.1 实验环境和数据集
  •     4.4.2 关于计算机合成网络的实验
  •     4.4.3 关于现实世界网络的实验
  •   4.5 本章小结
  • 第五章 总结与展望
  •   5.1 总结
  •     5.1.1 主要工作
  •     5.1.2 创新点
  •   5.2 展望
  • 致谢
  • 参考文献
  • 攻读硕士学位期间取得的成果
  • 文章来源

    类型: 硕士论文

    作者: 叶磊

    导师: 罗俊海

    关键词: 复杂网络,社团检测,共同邻居,层次聚类,标签传播

    来源: 电子科技大学

    年度: 2019

    分类: 基础科学,信息科技

    专业: 数学,计算机软件及计算机应用

    单位: 电子科技大学

    分类号: O157.5;TP301.6

    总页数: 82

    文件大小: 10911K

    下载量: 66

    相关论文文献

    • [1].《算法设计与分析》课程的问题驱动递进启发式教学方法探讨[J]. 科技风 2020(01)
    • [2].融合分治法与支持向量机的“算法设计与分析”教学模式研究[J]. 科教文汇(中旬刊) 2020(02)
    • [3].对分课堂在“算法设计与分析”课程的教学实践[J]. 教育教学论坛 2020(20)
    • [4].算法设计与分析课程以赛励教的教学模式及效果分析[J]. 高教学刊 2020(06)
    • [5].算法在新闻实践过程中的伦理问题[J]. 三明学院学报 2019(05)
    • [6].算法“塑造世界”客观吗[J]. 中国报业 2018(11)
    • [7].算法设计与分析课程全方位实践教学改革探索[J]. 计算机教育 2017(02)
    • [8].基于实践性教学的《算法设计与分析》教学研究[J]. 曲靖师范学院学报 2015(06)
    • [9].在算法设计与分析课程教学中融入计算思维[J]. 价值工程 2016(08)
    • [10].算法设计与分析教学常见问题分析[J]. 电脑知识与技术 2014(24)
    • [11].算法设计与分析课程的教学与实践探索与研究[J]. 科教文汇(上旬刊) 2015(03)
    • [12].构建“算法设计与分析”趣味课堂[J]. 科教文汇(下旬刊) 2013(06)
    • [13].结合科研的计算机辅助几何设计教学[J]. 数学学习与研究 2017(17)
    • [14].聚焦核心素养案例研讨专题二:体验编程计算,初步了解算法[J]. 中国信息技术教育 2017(08)
    • [15].建构主义教学模式与算法设计与分析课程教学[J]. 甘肃科技 2013(24)
    • [16].计算思维与实践编程能力培养并重的算法设计与分析教学[J]. 电脑知识与技术 2020(04)
    • [17].面向算法设计与分析课程的翻转课堂教学模式研究[J]. 计算机教育 2016(08)
    • [18].算法设计与分析课程教学方法探讨[J]. 大学教育 2014(18)
    • [19].《算法设计与分析》的实践方法探索[J]. 新课程研究(中旬刊) 2010(12)
    • [20].算法设计与分析课程教学改革探讨[J]. 黑龙江教育学院学报 2014(08)
    • [21].《算法设计与分析》教学中采用学生讲课模式的改革探索[J]. 轻工科技 2013(06)
    • [22].《算法设计与分析》课程教学改革[J]. 福建电脑 2013(09)
    • [23].计算几何——算法设计与分析实验课改革[J]. 科技创新导报 2012(03)
    • [24].“算法设计与分析”课程教学与实践方法探讨[J]. 计算机教育 2012(06)
    • [25].计算机博弈与“算法设计与分析”实验教学[J]. 中国电力教育 2012(20)
    • [26].《算法设计与分析》课程中“回溯法”教学探讨[J]. 安庆师范学院学报(自然科学版) 2012(03)
    • [27].《算法设计与分析》课程教学方法探索[J]. 陕西教育(高教版) 2011(Z1)
    • [28].算法设计策略与计算思维[J]. 企业科技与发展 2010(08)
    • [29].关于“算法设计与分析”课程的教学探讨与实践[J]. 中国电力教育 2010(S2)
    • [30].《算法设计与分析》实践教学探讨[J]. 福建电脑 2009(10)

    标签:;  ;  ;  ;  ;  

    基于共同邻居的复杂网络社团检测算法研究
    下载Doc文档

    猜你喜欢