基于重要节点中心性的社团网络划分

论文摘要

如今我们身处一个网络化的时代,复杂网络在我们生活中无处不在,并日益成为人们关注和研究的重点。通过研究复杂网络,可以帮助人们解决很多现实问题,如:传染病的预防和控制,计算机病毒的传播,电网故障的排除等。社团结构是复杂网络的三大特性之一,另两个为无标度特性及小世界特性,社团内部的点连接相对比较稠密,社团之间的连接相对比较稀疏。挖掘社团结构,是复杂网络的一个重要研究方向。社团结构可以帮助我们更好地认识网络的构成、了解网络的运行机制以及利用网络来更好的服务人类自身。挖掘社团结构实际上就是对复杂网络进行划分,目前已有多种社团划分算法。2014年,A.Rodriguez和A.Laio[1]提出了一种基于密度峰值的聚类算法,该算法的研究对象是多维空间中的点,在未知先验信息的前提下,根据对象的相似性,将对象划分成相似元素的集合。受此启发,我们在本文中提出了一种基于节点重要性的复杂网络的社团划分算法。本文的重点是解决以下两个问题:1.如何度量复杂网络中节点的密度,从而选取聚类的中心;2.如何衡量节点之间的相似性,从而将网络中的节点分配到聚类中心所在的类。针对以上两个问题,本文做了如下工作:1.针对节点的密度问题,我们将把图的边考虑在内,提出了一种加权的子集密度计算公式,可以较好地度量图中一个节点的密度;2.针对节点之间相似性的问题,我们通过考虑网络中特有的共同邻居指标的相似性度量,利用最经典的共同邻居相似度(CN)指标,来刻画顶点对之间的相似性;3.提出了一种新的复杂网络中社团发现算法。该算法通过计算每个顶点的密度,按照一定规则选出网络中的聚类中心,再利用CN相似性指标将剩余顶点分配到每个聚类中心。该算法不需要事先知道聚类的个数,避免了目前大部分存在算法中需要事先给定社团个数k这一难题。4.本文在真实的网络数据集和人工生成的网络数据集上进行了实验,验证了我们算法的有效性。

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
•   1.1 研究背景与意义
•   1.2 国内外研究现状
•   1.3 论文研究内容
•   1.4 论文组织结构
• 第二章 复杂网络及社团划分的基本概念
•   2.1 基本概念
•   2.2 网络的基本拓扑性质
•   2.3 社团划分的评价指标
•   2.4 本章小结
• 第三章 社团划分的经典算法
•   3.1 Fast-Newman算法
•   3.2 Louvain算法
•   3.3 Infomap算法
•   3.4 标签传播算法
•   3.5 本章小结
• 第四章 一种新的基于密度峰值聚类改进的社团划分算法
•   4.1 密度峰值聚类
•   4.2 改进的密度峰值聚类
•     4.2.1 网络中节点密度的定义
•     4.2.2 聚类中心的选取
•     4.2.3 非聚类中心节点的划分
•   4.3 实验与结果分析
•     4.3.1 真实的网络数据集
•     4.3.2 人工生成的网络数据集
•   4.4 本章小结
• 第五章 总结与展望
•   5.1 总结
•   5.2 展望
• 参考文献
• 致谢
• 作者简介
• 学位论文评阅及答辩情况表

文章来源

类型: 硕士论文

作者: 张鹏

导师: 亓兴勤

关键词: 复杂网络,社团划分,密度峰值聚类

来源: 山东大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 山东大学

分类号: O157.5

总页数: 55

文件大小: 3758K

下载量: 122