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

摘要

对复杂网络的定性和定量特征进行研究，有助于揭示复杂网络的普遍规律和未知信息，在计算机科学、物理科学、生物科学、社会科学、数学等诸多学科中具有重要意义。复杂网络节点中心性评估及其对社团探测影响等问题一直是复杂网络研究的热点，系统研究这些问题有利于解释网络成因，理解网络结构，指导网络行为和提高人类对复杂网络的认知。
　　本论文主要研究复杂网络节点中心性多元评估与基于节点中心性的社团探测算法，主要工作与创新点如下：
　　针对复杂网络节点中心性单指标评估的片面性和不稳定性等问题，以及多指标评估算法计算时间复杂度高和不精确等问题。对特征向量中心性、中介中心性、紧密中心性、点度中心性、互信息中心性等指标向量进行深入研究，同时，对主流数据降维算法进行对比分析，提出了一种节点中心性多元评估算法(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-Centrality。将这些算法在真实世界网络和基于LFR准则生成的网络中进行仿真实验，并与主流多元评估算法和主流社团探测算法进行了详细的对比分析，实验结果均表明新算法有更高的精确性和有效性，具有较好的研究意义和实用价值。

目录

声明

摘要

第一章 前言

1．1 研究背景与意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．2．1 复杂网络节点中心性评估研究现状

1．2．2 复杂网络社团结构探测研究现状

1．3 研究目标与研究内容

1．3．1 研究目标

1．3．2 研究内容

1．4 论文章节安排

第二章 相关理论与指标参数

2．1 复杂网络的基本特性

2．2 多元统计分析与数据降维理论

2．2．1 多元统计分析和数据降维

2．2．2 线性数据降维与非线性数据降维

2．2．3 数据降维算法介绍

2．3 复杂网络节点中心性评估

2．3．1 复杂网络节点中心性意义

2．3．2 复杂网络节点中心性定义

2．3．3 复杂网络节点中心性评估指标

2．4 社团结构探测

2．4．1 社团结构探测意义

2．4．2 社团结构探测指标及参数

2．4．3 社团探测相关算法介绍

2．5 仿真网络

2．6 本章小结

第三章 节点中心性多元评估算法(MI-LDA)实现

3．1 MI-LDA算法思想描述

3．2 MI-LDA算法实现与复杂性分析

3．3 ARPA网络仿真与评估

3．4 本章小结

第四章 节点中心性多元评估算法(MI-LLE)实现

4．1 MI-LLE算法思想描述

4．2 MI-LLE算法实现与复杂性分析

4．3 真实世界网络仿真与评估

4．3．1 Zachary空手道俱乐部网络仿真

4．3．2 宽吻海豚网络评估

4．3．3 悲惨世界网络仿真

4．3．4 E-mail网络仿真

4．4 本章小结

第五章 基于节点中心性的社团探测算法(Infomap-SA)实现

5．1 Infomap-SA算法思想描述

5．2 Infomap-SA算法实现与复杂性分析

5．3 真实世界网络的仿真与评估

5．3．1 Zachary空手道俱乐部网络仿真

5．3．2 宽吻海豚网络仿真

5．3．3 悲惨世界人物关系网络仿真

5．3．4 真实世界网络评估分析

5．4 基于LFR准则生成的网络仿真与评估

5．4．1 基于LFR准则生成网络仿真

5．4．2 基于LFR准则生成网络评估分析

5．5 本章小结

第六章 基于节点中心性的社团探测算法(CNM-Centrality)实现

6．1 CNM-Centrality算法思想描述

6．2 CNM-Centrality算法实现与复杂性分析

6．3 真实世界网络的仿真与评估

6．3．1 Zachary空手道俱乐部网络仿真

6．3．2 宽吻海豚网络仿真

6．3．3 悲惨世界人物关系网络仿真

6．3．4 美国国家西部电力网络仿真

6．3．5 真实世界网络评估分析

6．4 基于LFR准则生成网络的仿真与评估

6．4．1 基于LFR准则生成网络1仿真

6．4．2 基于LFR准则生成网络2仿真

6．4．3 基于LFR准则生成网络3仿真

6．4．4 基于LFR准则生成网络评估分析

6．5 本章小结

第七章 结论与展望

7．1 全文总结

7．2 研究展望

附录

参考文献

在校期间发表的论文

致谢