基于二分网络社区划分的算法研究

论文摘要

网络科学的发展带给了人们很多崭新的思维方式,点燃了我们深入研究的热情,并拉近了人们之间的距离。本文将通过探索二分网络来助力于网络科学的成长。研究社区结构对于理解整个二分网络的结构和功能都具有重要作用,目前已有很多的研究人员提出了关于二分网络社区划分的不同算法,本文从新视角分别提出两种不同的算法,成果如下:(1)提出了基于亲密度和吸引力的算法(Intimacy and Attraction Algorithm,简称IAA),其目的是提高社区划分准确性。首先选取U类型中的每个节点划分为不同的社区,创造性的提出了亲密度和吸引力的计算公式,合并社区。然后V类型节点划分进现有社区,计算此时模块度值Q。直到Q不再增加或合并条件不成立。这样,就产生了完整的社区结构。分别在计算机模拟生成的人工二分网络数据集和真实的二分网络数据集上采用互信息和模块度进行实验分析。由实验结果得出:IAA算法不用输入任何参数,并相比于其他算法得到较高的精确性。(2)提出了相似度聚类的算法(Similarity Clustering Algorithm,简称SCA)。该算法首先选取某类型中的全部节点,计算该类节点彼此之间的相似度来获得核心节点集合,依次将核心节点及其邻域中的节点不断地拓展得到社区,这样就得到了该类型节点的社区,最后,另一种类型节点聚类到现有社区从而获得最终的结果。通过实验分析,SCA可以得到良好的社区分类结果。随后分析了在不同数据集下的参数取值。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 国内外研究现状
•   1.3 社区划分算法面临的难关
•   1.4 本文研究内容
• 第二章 二分网络及其社区划分的相关知识
•   2.1 二分网络
•     2.1.1 二分网络的度与度分布
•     2.1.2 二分网络节点的最短路径
•   2.2 二分网络符号表示
•   2.3 二分网络社区结构
•   2.4 二分网络的常用数据集
•   2.5 二分网络的评价指标
•     2.5.1 模块度
•     2.5.2 互信息
•   2.6 二分网络社区划分算法
•     2.6.1 基于标签传播算法
•     2.6.2 基于边集聚系数算法
•     2.6.3 基于距离动力学的二分网络快速社区检测方法
•     2.6.4 基于资源分布的二分网聚类算法
•     2.6.5 BRIM算法
•   2.7 本章小结
• 第三章 基于亲密度和吸引力的二分网络社区划分算法
•   3.1 IAA算法
•     3.1.1 相关概念
•     3.1.2 算法介绍
•   3.2 算法复杂度分析
•   3.3 实验结果分析
•     3.3.1 关于人工二分网络的实验
•     3.3.2 关于真实网络的实验
•   3.4 本章小结
• 第四章 基于相似度聚类的二分网络社区划分算法
•   4.1 SCA算法
•     4.1.1 相关概念
•     4.1.2 算法介绍
•   4.2 算法复杂度分析
•   4.3 实验结果分析
•     4.3.1 关于人工二分网络的实验
•     4.3.2 关于真实网络的实验
•   4.4 本章小结
• 第五章 总结与展望
•   5.1 总结
•   5.2 展望
• 参考文献
• 攻读学位期间取得的研究成果
• 致谢
• 个人情况及联系方式

文章来源

类型: 硕士论文

作者: 刘莉楠

导师: 张晓琴

关键词: 二分网络,社区划分,亲密度,吸引力,互信息,模块度,相似度

来源: 山西大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 山西大学

分类号: O157.5

DOI: 10.27284/d.cnki.gsxiu.2019.000252

总页数: 60

文件大小: 3471K

下载量: 42