复杂网络的相似度表示及应用算法研究

论文摘要

复杂网络这个概念在20世纪90年代末开始使用,许多计算机科学家、生物学家、社会学家、物理学家和数学家开始研究各种现实世界的网络及其模型。直至今日,复杂网络仍然是一个非常炙手可热和具有吸引力的研究方向,其中链路预测和社区发现就是复杂网络研究中两大热点。判断两个网络节点是否有连接或者同属于一个社区的一种运算复杂度较低的方法便是计算连接点的相似度,该方法比较适用于大规模的网络。已经提出的相似度的指标有很多,但往往只考虑到节点自身度数和共同邻居导致预测精度不够或自身计算复杂度过大导致不适用于复杂网络。本文基于Deepwalk和聚类算法对相似度表示进行研究和应用,主要内容如下:（1）由于传统的相似度表示中,全局相似度的计算复杂度较高,局部相似度的预测精度受到限制,为了得到精度高、复杂度又低的相似度表示,本文将传统相似度表示和Deepwalk得到的距离指标相结合,同时引入集群的概念,提出了一个新的相似度表示Deep Affinity（DA）指标。该指标通过Deepwalk得到节点的坐标和各节点之间的欧氏距离,再用K-means算法得到各节点的簇编号,最后通过两个参数α和β协调影响度得到两个节点最终的相似度。通过在不同真实网络数据集和人工生成的PowerLaw数据集上重复实验,结果表明依靠DA的预测算法在预测精确度上得到很大的提升,且网络数据集越大提升越明显。（2）许多已经提出的社区发现算法,只能在小型网络上有较好的结果,却不适用于大规模网络。本文结合DA指标提出了一种新的社区发现算法CBS,该算法通过使用边界节点识别社区之间的边界线来发现社区,并结合LPA算法的思想,在社区检测的过程中将社区用标签来表示,节点根据其邻居的最大利益分数即DA指标来决定其标签。该算法只关注标签传播迭代过程中的边界节点,消除了不必要的步骤,缩短了整体执行时间,它还具有分布式的性质,在未来可以并行地应用于大型网络。经过在真实数据集和人工生成的LFR图上进行实验,结果证明,在所识别社区的质量方面CBS算法的效果要比2018年Tasgin M等人提出的CBB算法更好。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 选题背景
•   1.2 研究意义
•   1.3 国内外研究现状
•     1.3.1 链路预测研究现状
•     1.3.2 社区发现研究现状
•   1.4 主要研究成果
•   1.5 论文组织结构
• 第2章 理论基础
•   2.1 复杂网络
•     2.1.1 复杂网络三大特性
•     2.1.2 网络图表示
•   2.2 链路预测
•     2.2.1 问题概述
•     2.2.2 数据预处理
•     2.2.3 相似度表示
•     2.2.4 衡量标准
•   2.3 社区发现
•     2.3.1 问题概述
•     2.3.2 社区的定义
•     2.3.3 衡量标准
•   2.4 小结
• 第3章 复杂网络的相似度表示及链路预测应用算法
•   3.1 问题描述
•   3.2 基于Deepwalk和聚类算法的相似度表示
•     3.2.1 Deepwalk算法
•     3.2.2 K-means
•     3.2.3 新的相似度表示Deep Affinity
•   3.3 基于DA的链路预测算法
•   3.4 实验分析
•     3.4.1 数据集
•     3.4.2 评价标准
•     3.4.3 数据集预处理
•     3.4.4 实验结果
•   3.5 算法分析与总结
•     3.5.1 时间复杂度
•     3.5.2 优化方向研究
•   3.6 小结
• 第4章 基于相似度表示DA的社区发现算法
•   4.1 标签传播算法
•     4.1.1 基本理论
•     4.1.2 标签传播算法的研究及应用
•   4.2 基于边界点的社区发现算法
•     4.2.1 问题描述
•     4.2.2 算法概述
•     4.2.3 增益分数计算指标
•   4.3 基于DA的社区发现算法
•   4.4 实验分析
•     4.4.1 数据集
•     4.4.2 评价标准
•     4.4.3 实验分析
•   4.5 算法分析与总结
•     4.5.1 运行时间优化讨论
•     4.5.2 算法改进方向讨论
•   4.6 小结
• 结论
• 参考文献
• 附录 A攻读硕士学位期间发表论文目录
• 附录 B攻读学位期间参与的研究项目
• 致谢

文章来源

类型: 硕士论文

作者: 王济彬

导师: 蔡立军,莫继红

关键词: 链路预测,相似度,社区发现

来源: 湖南大学

年度: 2019

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

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

单位: 湖南大学

分类号: O157.5;TP301.6

DOI: 10.27135/d.cnki.ghudu.2019.001780

总页数: 71

文件大小: 1670K

下载量: 17