摘 要

复杂网络是一门新兴学科，是一门对自然界中存在的网络现象以及它的复杂性进行解释的学科。复杂网络的研究对象，顾名思义，就是网络现象本身。在自然界和人类社会中，网络无处不在，从基本粒子到河外星系，从无机界到自然界，从人类社会到人类的思维，到处都有网络的存在。而网络科学是一门交叉学科，它研究广泛存在于各个学科、各个领域具有网络特性的现象，通过建立模型达到解释这些现象的目的。

复杂网络主要研究复杂网络的特殊拓扑结构、演化和机制模型、动力学过程以及分析复杂网络的方法和应用，总的来说是研究网络结构、网络功能以及网络间的相互关系。对复杂网络中关键节点和社区结构的挖掘一直都是研究人员重点关注的研究对象，本文基于专利间相互引用的关系构建了专利引用网络，在该网络的基础上探索有针对性的关键节点与社区结构的挖掘方法，将以此为基础来探索复杂网络的特征。

关键词：复杂网络；关键节点；社区结构；专利引用网络

Abrast

Complex network is a new discipline,which can explain the network phenomenon in nuture and its complexity . As the name suggests, the research object of complex networks is the network phenomenon itself. In nature and human society, the network is everywhere, from the basic particles to the river outside the galaxy, from the inorganic community to the natural world, from human society to human thinking, everywhere there is the existence of the network. And network science is an interdisciplinary subject, It studies the phenomenon of network characteristic which exists widely in every subject and field, and establishes the model to explain these phenomena.

Complex networks mainly study the special topology of complex network, evolution and mechanism model, dynamics process and complex network analysis methods and applications of complex networks. In general, it is to study the network structure, network functions and the relationship between the network. The research on the key nodes and community structure in complex networks has always been the research object which the researchers focus on. Based on the patent reference relationship, this paper constructs a patent reference network, and explores the key mining methods of key nodes and community structure on the basis of the network. This paper will explore the characteristics of complex networks based on this.

Key words：complex network;key nodes;community structure; patent citation network

目录

摘要 I

Abrast II

1绪论 1

1.1研究背景和意义 1

1.1.1研究背景 1

1.1.2 研究意义 1

1.2 国内外研究现状 2

1.2.1 关键节点挖掘研究现状 2

1.2.2 社区结构挖掘现状 3

1.3 本文研究目标和研究内容 4

1.3.1 研究目标 4

1.3.2 研究内容 4

1.4 论文内容安排 4

2复杂网络建模 6

2.1 引言 6

2.2 复杂网络建模理论基础 6

2.2.1图表示 6

2.2.2 网络基本特征 7

2.2.3复杂网络机制模型 8

2.3 复杂网络建模 10

3基于节点度的关键节点挖掘算法 12

3.1 相关算法综述 12

3.1.1基于节点度 12

3.1.2基于子图 12

3.1.3基于近似特征向量 12

3.1.4基于节点删除法 13

3.2基于度指标的算法实现 14

3.2.1计算方法 14

3.2.2算法描述 15

3.2.3编程语言 15

3.3基于Pagerank的算法实现 15

4一种基于clique的社区结构发现算法 17

4.1 相关社区发现算法综述 17

4.1.1 Kernighan-Lin算法 17

4.1.2 GN算法 18

4.2基于clique的社区结构发现算法实现 18

4.2.2算法理论基础 18

4.2.3具体算法 19

5专利引用网络实例 21

5.1专利引用网络的构建 21

5.2 专利网络分析综述 26

5.2.1关键节点综述 26

5.2.2社区结构综述 27

5.3关键节点挖掘算法实现 28

5.3.1基于节点度的算法实现 28

5.3.2基于PageRank算法的实现 30

5.3.3 关键节点挖掘算法结论 33

5.4社区结构挖掘算法实现 33

5.4.1网络分析 33

5.4.2社区结构挖掘算法结论 38

6总结与展望 38

6.1全文总结 38

6.2未来展望 39

参考文献 40

附录 43

致谢 45

1绪论

1.1研究背景和意义

1.1.1研究背景

自然界中，系统无处不在，从基本粒子到河外星系，从人类自身到人类创造的产品，从现实到虚拟，到处都有系统的存在。而网络和系统通常是紧密联系的，如果用节点来表示系统各个组成部分，节点之间的连线则表示元素之间的相互作用^[1]，那么自然而然地网络就可以作为系统的一种新的描述方法。网络能够用来描述各种关系，如专利与专利之间的引用关系、人与人之间的社会关系甚至产品由原材料变成产品各个环节之间的关系^[2]。

随着互联网在二十一世纪末的高速发展，人们发现复杂网络广泛存在于自然界的各个角落，可以说是无处不在，比如蚁群之间的行为网络、商人之间的交易网络、人与人之间的关系网络等等都是明显的网络结构。大量的研究表明这些网络都具备复杂网络的一些特性，比如网络动态变化，同时也具有一些明显的共性，如这些网络具有小世界和无标度特性等^[3]。从此之后复杂网络因为广泛的多学科适应性逐渐成为学者们研究的热潮。