摘 要

进入新世纪以来，信息技术蓬勃发展，以互联网为代表的先进科学技术不断涌现，世界正在大步迈入网络化时代。大数据、云计算的出现，对人们认识世界并改造世界提出了更高的要求。复杂网络是人们对复杂系统的抽象概括，对复杂网络中观结构的研究有助于帮助人们更好地认识复杂系统的底层结构、系统特性和系统行为。本设计从一种典型的网络中观结构——社团结构着眼，根据信息流在网络中无规则的流动行为，应用随机过程中的马尔可夫链，将网络中的节点进行哈夫曼编码，借此来对网络进行二级描述，寻找随机游走在网络上的最短平均描述长度。本设计通过应用随机游走过程来识别网络中的社团结构，将不含记忆和含记忆的随机游走在若干典型网络上做对比研究，展示了包含记忆性的随机游走在网络社团结构识别中的优越性能。

关键词：复杂网络；中观结构；记忆性；随机游走；马尔可夫链

Abstract

Since the beginning of the new century, information technology has been developing vigorously, and advanced science and technology, represented by the Internet, have been emerging continuously. The emergence of big data and cloud computing has raised higher requirements for people to understand and improve the world. Complex network is an abstract generalization of complex system. And it is helpful to understand the underlying structure, characteristics and behavior of complex systems. This design comes from a kind of typical intermediate-scale structure of complex networks, which called community structure. According to the irregular flow behavior of information flow in the network, the nodes in the network are coded by using Markov chain in stochastic process. In this way, the network can be described in two levels, and the shortest average description length of the random walk on the network can be found. Through the application of random walk process to identify the network community structure, this design compares the random walk with and without memory to study on several typical networks, showing the superior performance of the random walk with memory in the community structure detection.

Keywords: complex network；intermediate-scale structure；memory；random walk；Markov chain

目 录

第1章 绪论 1

1.1 课题研究的背景、目的和意义 1

1.2 国内外发展现状与研究水平 2

1.2.1 国内外网络科学的研究进展 2

1.2.2 总体研究概述 3

1.3 课题研究的内容 4

第2章 复杂网络基本理论 5

2.1 复杂网络的定义与描述 5

2.2 复杂网络的统计特性 5

2.3 复杂网络的拓扑模型 7

2.3.1 小世界网络模型 7

2.3.2 无标度网络模型 7

2.4 复杂网络的中观结构 9

2.5 社团识别的常用方法以及评价指标 10

2.5.1 社团识别的常用方法 10

2.5.2 社团识别的评价指标 13

第3章 复杂网络中的随机游走 14

3.1 马尔可夫链概述 14

3.2 网络上的随机游走 14

3.2.1描述网络上的路径 14

3.2.2 哈夫曼编码 15

第4章 基于不含记忆随机游走的社团识别算法 16

4.1 算法理论基础 16

4.2 算法设计分析 16

4.3 仿真结果分析 17

4.3.1 Zachary空手道俱乐部网络 17

4.3.2 Dolphins海豚网络 19

第5章 基于含记忆随机游走的社团识别算法 22

5.1 算法理论基础 22

5.2 算法设计分析 23

5.3 仿真结果分析 23

5.4.1 Zachary空手道俱乐部网络 23

5.4.2 Dolphins海豚网络 24

第6章 总结 26

参考文献 27

附 录 29

致 谢 37

第1章 绪论

1.1 课题研究的背景、目的和意义

随着人类社会的进步，科学技术飞速发展。进入新世纪以来，以互联网为代表的信息技术的高速发展使人类社会大步迈入了网络时代。现如今，贸易网络、交通网络、电力网络、社交网络，电力网络等等复杂多样的网络相继出现，人们已经生活在一个充满着各种各样的复杂网络的世界中，对于网络科学的研究应运而生^[1]。网络科学是一门跨越自然、社会和计算机科学以及工程学的现代学科^[2]。网络是复杂系统的拓扑抽象，它包含节点和连边，一条边通常连接一对节点。网络存在于各种各样的环境中。例如，Facebook是一个大型的社会网络，有超过10亿人通过虚拟交往联系在一起。另一个著名的例子是互联网，电脑、路由器和调制解调器的物理网络，通过电缆或无线信号连接，如图1.1所示。许多其他的例子来自生物学、物理学、经济学、工程学、计算机科学、生态学、市场营销、社会和政治科学等。

图1.1 互联网拓扑图

人类社会的网络化是一把双刃剑：它既给人类社会的生产和生活带来了极大的便利，提高了生产效率和生活水准，但也带来了一定的负面冲击，如局部动荡或传染病等更容易向全球扩散^[1]。 所以，人们需要不断地学习研究各种自然生成和人工制造的网络的特性和行为，才能更好地适应日渐网络化的社会环境。

网络的描述可以分为三个方面：局部描述、全局描述和从中观视角来描述。因此，网络理论的一个关键作用是识别大型网络的概要统计数据，从而建立一个分析和比较复杂结构的框架。因此，网络中观结构的识别使得发现网络在局部节点和连边或全局汇总统计级别上可能不明显的特性成为可能。