基于节点相似度的社团结构划分算法的研究

发布时间：2017-06-27 20:21

  本文关键词：基于节点相似度的社团结构划分算法的研究，，由笔耕文化传播整理发布。

【摘要】：复杂网络作为复杂系统的一种抽象表现形式和描述方式,广泛存在于自然界和社会中。复杂网络的研究已经涉及到各个学科,即任何一个复杂系统都能够作为复杂网络来研究,如计算机科学、社会科学、生物学、电路与系统等。随着对网络性质的深入研究,研究者们发现,这些大型的复杂系统看似杂乱无章,却存在着一些重要的特性,如社团结构。社团结构是复杂网络的一个重要特征结构,在许多方面有着广泛的应用。因此,探测复杂网络中的社团结构显得非常重要,近年来一直是众多学者的重点研究内容。复杂网络社团结构划分算法旨在揭示出复杂网络中真实存在的网络社团结构,研究者们提出了一系列有效算法来寻找复杂网络中的社团结构,以便更好地分析网络中社团结构的基本特点和共同特性。本文通过研究节点之间的相互关系,找到节点之间的相似性和相异性,并综合现有算法的优缺点,提出新的社团结构划分算法。本文的主要内容及创新性研究如下:(1)一种基于节点相似度的社团结构划分算法。算法首先根据标准化模块度矩阵的特征间隔来确定社团划分的个数;其次根据节点之间的共同邻居节点个数和节点之间的最短路径长度定义了节点相似度概念,基于节点相似度和社团结构定义,再结合分裂思想提出了新的社团结构划分算法;最后利用模块度Q值函数作为评价社团结构划分优劣的效益函数。实验结果表明,与其他一些算法相比,该算法能够利用较少的信息量得到较准确的网络社团结构,且算法比较容易实现。(2)一种改进的基于节点相异度的社团结构划分算法。算法首先根据度和平均度评估标准,筛选出核心节点作为初始核心节点集,然后基于相异度进行划分,直至社团结构划分完成。实验结果表明,与其他一些算法相比,该算法划分结果较精确且易于实现。综上所述,本文是从节点之间的关系出发,研究了节点之间的相似度和相异度。节点之间的相似度越大,则相异度越小,那么节点之间的关系越亲密,在同一个社团的可能性越大,基于此思想提出了基于节点相似度的社团划分算法。
【关键词】：复杂网络 社团结构 相似度 相异度 模块度
【学位授予单位】：兰州理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要7-8
• Abstract8-12
• 第1章 绪论12-22
• 1.1 课题研究背景及意义12-16
• 1.1.1 研究背景12-15
• 1.1.2 研究意义15-16
• 1.2 研究现状16-21
• 1.2.1 相关概念16-18
• 1.2.2 国内外研究现状18-21
• 1.3 本文主要研究内容与组织结构21-22
• 第2章 复杂网络社团结构中经典的划分算法22-29
• 2.1 GN算法22-24
• 2.1.1 GN算法的基本思想22-23
• 2.1.2 GN算法的实现23-24
• 2.2 Newman快速算法24-25
• 2.2.1 Newman快速算法的基本思想24
• 2.2.2 Newman快速算法的实现24-25
• 2.3 谱平分法25-27
• 2.3.1 谱平分法的基本思想25-26
• 2.3.2 谱平分法的实现26-27
• 2.4 Kernighan-Lin算法27-28
• 2.4.1 Kernighan-Lin算法的基本思想27-28
• 2.4.2 Kernighan-Lin算法的实现28
• 2.5 本章小结28-29
• 第3章 一种基于节点相似度的社团结构划分算法29-44
• 3.1 节点相似度29-34
• 3.1.1 相似度度量标准29-32
• 3.1.2 节点相似度定义32-34
• 3.2 标准化模块度矩阵34-36
• 3.3 算法描述36-38
• 3.4 实验与分析38-43
• 3.4.1 三社团网络38-40
• 3.4.2 美国政治图书网40-42
• 3.4.3 美国大学足球赛网络42-43
• 3.5 本章小结43-44
• 第4章 一种改进的基于节点相异度的社团结构划分算法44-53
• 4.1 节点相异度44-46
• 4.1.1 相异度度量标准44-45
• 4.1.2 改进的节点相异度45-46
• 4.2 算法介绍46-47
• 4.3 实验与分析47-52
• 4.3.1 三社团网络48-49
• 4.3.2 Zachary空手道俱乐部网络49-50
• 4.3.3 美国大学足球赛网络50-52
• 4.4 本章小结52-53
• 总结与展望53-55
• 参考文献55-60
• 致谢60-61
• 附录 攻读硕士学位期间发表的学术论文61

【参考文献】

中国期刊全文数据库 前10条

1 孙宇;;一种基于Jaccard相似度的社团发现方法[J];电子技术与软件工程;2016年03期

2 梁宗文;杨帆;李建平;;基于节点相似性度量的社团结构划分方法[J];计算机应用;2015年05期

3 孙亚红;肖淑苹;;一个基于多维特征向量的复杂网络社团结构发现算法[J];计算机与数字工程;2015年04期

4 程泽凯;张佳玉;;基于节点相似度的社团发现算法[J];计算机工程与设计;2014年05期

5 杜守印;李斌;董传杰;臧苑贞;;基于相似性复杂网络社团结构发掘算法的研究[J];软件;2014年02期

6 高洪伟;徐勇;;基于节点间的依赖程度划分网络中社团的算法[J];计算机与现代化;2014年04期

7 罗明伟;姚宏亮;李俊照;王浩;;一种基于节点相异度的社团层次划分算法[J];计算机工程;2014年01期

8 周林;晏立;沈项军;;基于边密度的复杂网络社区结构划分方法[J];计算机应用与软件;2013年12期

9 李琳;李生红;陆松年;陈秀珍;;基于PCA的社团结构谱聚类改进算法[J];计算机工程与设计;2013年10期

10 张聪;沈惠璋;;基于谱方法的复杂网络中社团结构的模块度[J];系统工程理论与实践;2013年05期

中国博士学位论文全文数据库 前1条

1 李平;复杂网络的动力学行为研究[D];电子科技大学;2009年

中国硕士学位论文全文数据库 前6条

1 李川;基于复杂网络的城市公共交通网络连通性研究[D];西南交通大学;2014年

2 尹琦;基于复杂网络理论的职教知识创新网络设计与应用[D];广东技术师范学院;2013年

3 李亚飞;复杂网络中的社团结构检测算法研究[D];北京交通大学;2011年

4 张君超;基于复杂网络的城市公交网络特性分析与演化研究[D];西南交通大学;2010年

5 赵君霞;复杂网络在中医临床知识发现中的应用研究[D];北京交通大学;2009年

6 胡柯;复杂网络上的传播动力学研究[D];湘潭大学;2006年

  本文关键词：基于节点相似度的社团结构划分算法的研究，由笔耕文化传播整理发布。

本文编号：491149