复杂网络中目标节点分析技术研究

摘要

正是基于现代计算机超强的计算能力，复杂网络的研究，融合了拓扑学、图论、社交网络分析、互联网宏观拓扑研究、物理学、生物学等学科的相关研究成果，形成了这个学科独有的体系和方法论。小到互联网的拓扑结构，大到浩瀚无垠的宇宙，复杂系统都可以被抽象成由节点和边组成的网络化表示的模型。而复杂网络领域的科学家们现在普遍认为:不同真实网络结构上和动力学上的相似性表明某种普遍的规则可能可以准确的描述所有这些网络的动力学。与此同时，控制论、博弈论、排队论、曲面几何等各种现有自然科学理论均能够有效地与复杂网络研究相结合，随着人们在自然界中真实存在的各种复杂系统中发现复杂网络的一般性特征和规律，复杂网络理论和其分析技术的研究在各个领域的科学家手中都找到用武之地。同时，现有的模型和计算机分析技术还不能完美的再现或解释很多真实存在的复杂网络特征和现象。
　　复杂网络中目标节点分析技术研究是通过设计新的计算机算法或可计算模型，以网络化表达的数据中，研究人员关注的部分节点为研究对象，综合运用中心性分析、社团发现、链路预测、统计分布等手段来对目标网络进行研究和分析，并基于对目标复杂网络拓扑特征和规律的理解，发现新的规律、拓展原有理论的研究。按照计算机相关领域内对复杂网络研究一般过程的分类，可以分成拓扑探测、拓扑规律发现、拓扑建模三个部分。面向多样性的复杂网络研究对象，本文共包含了四个方面的问题，(1)文本数据中词汇复杂网络的探测算法，(2)设计了网络中节点重要性程度度量方法，并通过针对互联网等真实网络的蓄意攻击实验验证了提出的节点重要性度量方法的有效性，(3)通过追踪IPv6互联网全球拓扑的在4个月的演化数据，发现了互联网拓扑演化过程中的异常现象，并研究分析了两个典型的互联网异常演化现象在宏观拓扑内部形成的原因，(4)设计了一个新的可计算模型来分析二十四史中9个典型中国王朝的建立过程。
　　具体地，本文首先设计了一种面向中文文本信息的复杂网络探测算法，通过对中文单字复杂网络结构中边频度的加权和对字拓扑结构的分析，简化的中文习语与词汇的抽象过程，在较低的时间复杂度下实现了对不同时代成文的中文文本信息中蕴含的复杂网络结构的提取，实验表明，尽管牺牲了部分词汇分割精度，探测过程具有适应不同时代各种中文文本数据的特点，算法时间复杂度很低，抽象出来的词汇复杂网络结构具有典型的小世界特征和近似的无尺度特征。
　　其次，为了能够改善现有复杂网络中节点的重要性程度的度量方法，本文基于迭代对数函数设计了基于邻居度分布的邻居向量中心性指标，实验表明，该中心化度量方法在针对真实互联网拓扑、社交网络拓扑、生物学网络拓扑等多种复杂网络的蓄意攻击实验中，对多种复杂网络拓扑结构具有最大的破坏作用，同时计算所需的时间复杂度与度中心性类似，远低于介数等中心性指标，因此该方法对网络化数据中节点在拓扑中重要性程度的度量具有很好的效果。
　　第三，通过对一个真实大规模复杂网络拓扑时序上的观测，本文发现复杂网络拓扑结构的演化过程并不是一直保持平滑的。并基于菲波那契序列的构造方式给出了拓扑异常的定义，基于这个定义，本章研究了IPv6互联网拓扑中的两种典型拓扑异常现象，发现在复杂网络度量参数异常波动的情况下，网络拓扑内部确实存在一定范围内的“突变”，随后分析并给出了这两种情况下互联网拓扑突变的内在原因以及其对互联网拓扑造成的影响。
　　最后，基于近期一篇重要文献的研究成果，本文提出了一种“资源-竞争者”双层模型。并应用该模型分析了二十四史所记载的中国历史上9个朝代的建立过程，发现对大规模复杂系统控制拥有更多影响力的个体节点，在对复杂网络整体控制权的争夺中更具优势。中华人民共和国宪法规定了多党合作和政治协商制度，从中选取一个政党，利用“资源-竞争者”模型，本文对选取政党的一次换届选举进行了分析与预测，实验表明，该模型具有一定的准确性。
　　本文主要关心的问题是如何利用计算机算法和可计算模型，为复杂网络研究目标的分析技术提供一定的新方法，讨论了几个不同角度下，如何利用文中提出的方法对网络中研究人员关心的目标节点进行分析或度量的一般方法。包括如何抽象中文文本中的节点与网络、如何计算网络中节点的重要性程度、追踪大规模网络中节点的群体在演化过程中的异常现象、设计一种新的可计算模型来分析“竞争者”节点在网络控制权的争夺过程中的优势程度，以及利用这个模型对真实的社会事件进行预测。基于计算机应用技术所提出的这些方法，均通过不同的手段和方式进行了必要的检验。以确保设计的算法和模型是简单、易用、有效的。
　　这些分析技术和方法的提出，尽可能面向广泛多样性的研究目标，通过本文的研究与验证，证明了这些内容的效能，具有较好的研究意义与应用价值。

目录

声明

摘要

第一章 绪论

1．1 引言

1．2 网络科学与复杂网络的概念

1．3 网络科学的发展简史

1．4 网络科学研究内容分类与简述

1．5 计算机网络科学

1．6 复杂网络中的目标节点

1．7 本文组织结构与主要贡献

第二章 面向中文文本的复杂网络探测算法

2．1 引言

2．2 文本信息中复杂网络探测一般方法

2．3 文本信息的抽象模型

2．4 二元关系频度与加权二元关系频度

2．5 面向中文文本的复杂网络探测算法

2．6 面向不同类型中文文献的复杂网络探测试验

2．7 探测结果分析

2．7．1 度值的幂律分布

2．7．2 小世界特征判定

2．7．3 聚集系数

2．7．4 基于模块度的社团特征分析

2．8 小结

第三章 网络中目标节点重要性的度量方法研究

3．1 引言

3．2 中心性问题的描述

3．3 邻居向量中心性的定义

3．4 针对复杂网络的蓄意攻击

3．4．1 网络的连通性

3．4．2 传输效率

3．4．3 可控性和同配性

3．5 邻居向量中心性应用实例

3．5．1 复杂网络领域科研家重要性排名

3．5．2 《红楼梦》与《三国演义》中重要节点排名

3．6 小结

第四章 互联网拓扑中目标节点的异常演化

4．1 引言

4．2 互联网宏观拓扑结构的探测与研究

4．3 互联网拓扑的正常与异常演化：定义和观察

4．3．1 平均路径长度观察报告

4．3．3 平均度值观察报告

4．3．4 节点和边的观察报告

4．4 表面之下：突变的原因

4．4．1 节点和边的变化

4．4．2 度分布的转换现象

4．5 小结

第五章 基于网络可控性的目标节点分析模型

5．1 引言

5．2 标准的复杂网络控制模型

5．3 基于复杂网络控制的资源-竞争者双层模型

5．4 中国历史上9个知名朝代的建立过程分析

5．4．1 中国历史上王朝的建立

5．4．2 9个知名朝代研究目标选取与其复杂网络抽象

5．4．3 中国历史上第一次完整统一分析

5．4．4 各个朝代统一过程分析

5．4．5 三国时期的平衡状态以及最终的统一分析

5．4．6 对功臣的杀戮

5．5 中华人民共和国一个典型参政党换届选举分析与预测

5．6 小结

第六章 本文总结与网络科学研究展望

6．1 些许贡献

6．2 闪耀的群星

6．3 终极的答案

参考文献

致谢

个人简历、在学期间发表的学术论文与研究成果