复杂网络节点中心性多元评估与社团探测新算法研究

发布时间：2017-04-11 20:03

  本文关键词：复杂网络节点中心性多元评估与社团探测新算法研究，由笔耕文化传播整理发布。

【摘要】：对复杂网络的定性和定量特征进行研究,有助于揭示复杂网络的普遍规律和未知信息,在计算机科学、物理科学、生物科学、社会科学、数学等诸多学科中具有重要意义。复杂网络节点中心性评估及其对社团探测影响等问题一直是复杂网络研究的热点,系统研究这些问题有利于解释网络成因,理解网络结构,指导网络行为和提高人类对复杂网络的认知。本论文主要研究复杂网络节点中心性多元评估与基于节点中心性的社团探测算法,主要工作与创新点如下：针对复杂网络节点中心性单指标评估的片面性和不稳定性等问题,以及多指标评估算法计算时间复杂度高和不精确等问题。对特征向量中心性、中介中心性、紧密中心性、点度中心性、互信息中心性等指标向量进行深入研究,同时,对主流数据降维算法进行对比分析,提出了一种节点中心性多元评估算法(MI-LDA)。该算法将高维模式样本投影到最佳鉴别矢量空间,将特征空间维数进行压缩。仿真结果表明,该算法能够更高效地找到网络的中心节点,相比其他的主流数据降维算法,MI-LDA时间复杂度更低。为进一步提高节点中心性评估的精确度,提出另外一种节点中心性多元评估算法(MI-LLE)。该算法将各项指标值作为初始数据输入,在保留邻居节点的情况下,最小化代价函数,将数据降维转化为特征分解的问题,然后将高维样本投影到低维样本空间实现数据维数的压缩,从而识别出中心节点。实验结果表明,相比其他主流数据降维算法,此算法计算精确度更高。由于大部分网络的中心节点即为社团的中心,提出一种基于节点中心性的社团探测算法Infomap-SA,该算法首先利用LDA算法识别出中心节点,并按降序排列。随后利用基于随机行走编码的Infomap算法,同时引入模拟退火思想优化模块度函数。仿真结果表明Infomap-SA算法能够对社团进行准确检测、高效划分,比Infomap算法具有更高的模块度和连接密度,更低的时间复杂度,并且更适用于大规模网络的社团探测。充分利用CNM算法全局性层次聚类的优点,同时结合节点中心性的思想,提出一种新型的基于节点中心性的社团探测算法CNM-Centrality,该算法基于快速贪婪聚类算法CNM,应用PageRank算法进行中心节点识别,然后对中心节点与其临近节点进行优化划分。实验结果表明CNM-Centrality算法能够对社团进行准确探测、高效划分,比CNM、Infomap、Walktrap等算法具有更高的模块度值和归一化互信息(NMI)值。本论文研究并实现了节点中心性多元评估算法MI-LDA和MI-LLE,以及基于节点中心性的社团探测算法Infomap-SA和CNM-Centrali ty.将这些算法在真实世界网络和基于LFR准则生成的网络中进行仿真实验,并与主流多元评估算法和主流社团探测算法进行了详细的对比分析,实验结果均表明新算法有更高的精确性和有效性,具有较好的研究意义和实用价值。
【关键词】：复杂网络 节点中心性 多元评估 社团探测 Infomap-SA算法 CNM-Centrality算法
【学位授予单位】：华中师范大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要5-7
• Abstract7-12
• 第一章 前言12-26
• 1.1 研究背景与意义12-15
• 1.1.1 研究背景12-13
• 1.1.2 研究意义13-15
• 1.2 国内外研究现状15-21
• 1.2.1 复杂网络节点中心性评估研究现状15-17
• 1.2.2 复杂网络社团结构探测研究现状17-21
• 1.3 研究目标与研究内容21-24
• 1.3.1 研究目标21-22
• 1.3.2 研究内容22-24
• 1.4 论文章节安排24-26
• 第二章 相关理论与指标参数26-41
• 2.1 复杂网络的基本特性26-27
• 2.2 多元统计分析与数据降维理论27-30
• 2.2.1 多元统计分析和数据降维27-28
• 2.2.2 线性数据降维与非线性数据降维28
• 2.2.3 数据降维算法介绍28-30
• 2.3 复杂网络节点中心性评估30-34
• 2.3.1 复杂网络节点中心性意义31
• 2.3.2 复杂网络节点中心性定义31
• 2.3.3 复杂网络节点中心性评估指标31-34
• 2.4 社团结构探测34-38
• 2.4.1 社团结构探测意义34-35
• 2.4.2 社团结构探测指标及参数35-37
• 2.4.3 社团探测相关算法介绍37-38
• 2.5 仿真网络38-40
• 2.6 本章小结40-41
• 第三章 节点中心性多元评估算法(MI-LDA)实现41-53
• 3.1 MI-LDA算法思想描述41
• 3.2 MI-LDA算法实现与复杂性分析41-43
• 3.3 ARPA网络仿真与评估43-52
• 3.4 本章小结52-53
• 第四章 节点中心性多元评估算法(MI-LLE)实现53-68
• 4.1 MI-LLE算法思想描述53
• 4.2 MI-LLE算法实现与复杂性分析53-55
• 4.3 真实世界网络仿真与评估55-67
• 4.3.1 Zachary空手道俱乐部网络仿真55-58
• 4.3.2 宽吻海豚网络评估58-62
• 4.3.3 悲惨世界网络仿真62-64
• 4.3.4 E-mail网络仿真64-67
• 4.4 本章小结67-68
• 第五章 基于节点中心性的社团探测算法(Infomap-SA)实现68-82
• 5.1 Infomap-SA算法思想描述68
• 5.2 Infomap-SA算法实现与复杂性分析68-72
• 5.3 真实世界网络的仿真与评估72-76
• 5.3.1 Zachary空手道俱乐部网络仿真72-73
• 5.3.2 宽吻海豚网络仿真73-74
• 5.3.3 悲惨世界人物关系网络仿真74
• 5.3.4 真实世界网络评估分析74-76
• 5.4 基于LFR准则生成的网络仿真与评估76-80
• 5.4.1 基于LFR准则生成网络仿真76-77
• 5.4.2 基于LFR准则生成网络评估分析77-80
• 5.5 本章小结80-82
• 第六章 基于节点中心性的社团探测算法(CNM-Centrality)实现82-97
• 6.1 CNM-Centrality算法思想描述82
• 6.2 CNM-Centrality算法实现与复杂性分析82-86
• 6.3 真实世界网络的仿真与评估86-91
• 6.3.1 Zachary空手道俱乐部网络仿真87
• 6.3.2 宽吻海豚网络仿真87-88
• 6.3.3 悲惨世界人物关系网络仿真88-89
• 6.3.4 美国国家西部电力网络仿真89
• 6.3.5 真实世界网络评估分析89-91
• 6.4 基于LFR准则生成网络的仿真与评估91-96
• 6.4.1 基于LFR准则生成网络1仿真91-92
• 6.4.2 基于LFR准则生成网络2仿真92
• 6.4.3 基于LFR准则生成网络3仿真92-94
• 6.4.4 基于LFR准则生成网络评估分析94-96
• 6.5 本章小结96-97
• 第七章 结论与展望97-100
• 7.1 全文总结97-98
• 7.2 研究展望98-100
• 附录-名词解释100-102
• 参考文献102-109
• 在校期间发表的论文109-110
• 致谢110-111

【相似文献】

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

1 王晓东;解非线性0-1规划的一个算法及其在结构优化中的应用[J];数值计算与计算机应用;1988年01期

2 张晓;;基于密度聚类算法的异常检测[J];伊犁师范学院学报(自然科学版);2010年04期

3 陈沐天;找周期子字的算法[J];应用数学学报;1991年01期

4 丁才昌;方勃;鲁小平;;分布估计算法及其性能研究[J];武汉大学学报(理学版);2005年S2期

5 石明兰;杨晖;叶东毅;;面向目标的关联规则挖掘的一个FP增长算法[J];集美大学学报(自然科学版);2006年02期

6 张维群;;基于海量数据关联效应测度算法的设计[J];统计与信息论坛;2012年07期

7 罗蕾,徐洪利;构造Dn-最优确切设计的优化方法──离散算法[J];辽宁大学学报(自然科学版);1999年02期

8 贺永恒;王斌;;基于蚁群算法的候选标签子集构造方法研究[J];中国科技信息;2014年06期

9 武小悦,沙基昌;构造网络不交化最小路集的一种新算法[J];系统工程理论与实践;2000年01期

10 姜建国;刘永青;刘梦楠;王国林;李f ;;类电磁机制算法研究与改进[J];计算力学学报;2014年01期

中国重要会议论文全文数据库 前2条

1 潘志明;郑骏;钱卫宁;周傲英;;构造XML相似相关结构库的一种有效方法[A];第二十届全国数据库学术会议论文集（技术报告篇）[C];2003年

2 林景亮;董槐林;姜青山;吴书;;一种基于新增阈值的频繁模式挖掘算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

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

1 张磊;基于概念格的角色工程相关算法研究[D];哈尔滨工业大学;2015年

2 孟静;新型Krylov子空间算法及其应用研究[D];电子科技大学;2015年

3 胡芳;复杂网络节点中心性多元评估与社团探测新算法研究[D];华中师范大学;2015年

4 唐益明;（1，2，2）型异蕴涵泛三I算法及其应用研究[D];合肥工业大学;2011年

5 牛云云;求解计算困难问题的膜计算模型与算法研究[D];华中科技大学;2012年

6 李冬冬;基因组序列标注的算法与理论研究[D];国防科学技术大学;2004年

7 周琨;航空公司航班运行调度模型与算法研究[D];南京航空航天大学;2012年

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

1 闫铭;基于度量学习的不完整数据聚类方法研究[D];哈尔滨工业大学;2015年

2 张小琼;基于改进萤火虫群优化算法的BP神经网络研究[D];广西大学;2015年

3 李俊杰;基于蚁群算法的聚类区分器设计研究[D];电子科技大学;2014年

4 艾慧;天波雷达电离层污染校正与测高算法研究[D];电子科技大学;2015年

5 陈红强;大规模并行排序学习算法研究[D];西安电子科技大学;2014年

6 郭艳茹;k-中心平面聚类模型与算法研究[D];浙江工业大学;2015年

7 白鹭;基于自适应人工免疫进化的网格聚类算法研究[D];沈阳大学;2010年

8 纪彤坤;概念格Chein算法的研究与改进[D];华南理工大学;2012年

9 钱伟强;一种基于改进粒子群和K均值结合的聚类算法[D];西安电子科技大学;2011年

10 张菲;蜂群混合算法[D];西安电子科技大学;2013年

  本文关键词：复杂网络节点中心性多元评估与社团探测新算法研究，由笔耕文化传播整理发布。

，

本文编号：299841