复杂网络理论及其实证研究

VIP免费

3.0 牛悦 2024-11-19 4 4 711.69KB 39 页 15积分

侵权投诉

摘要

复杂网络作为复杂系统研究领域的一个分支，近年来得到科学界前所未有的关

注，网络研究的新成果不断发表于国际一流的权威期刊上。复杂网络的研究方向

主要包括了现实世界网络拓扑结构的实证研究，网络的演化、模拟和理论分析，

以及网络中的动力学过程研究等等。

所谓实证研究，也就是通过实际计算网络的统计属性参数，如平均度、度分

布、平均最短路径长度等，来研究网络的拓扑结构。本文研究了 07 年的中国教育

网，通过编写网络机器人对.edu.cn 下的网页进行了搜索，并建立了一个有 2354934

个节点，26816209 条边网络。

当网络的规模很大时，无论是从数据的存储还是计算的时间上都使得传统的

处理方法难以胜任。在对于平均最短路径长度的计算上，本文提出了一种新的近

似计算方法，使得我们在现有的计算机资源下，在能够在可以接受的时间内完成

对中国教育网平均最短路径长度的计算，这对以后的研究有着积极的意义。

本文同时对社团结构进行了一些研究，提出了一些新的算法。

本文所做的工作主要可分为四个部分：

一、编写网络机器人，对中国教育网的链接进行跟踪，并保存数据。

二、中国教育网 07 年网络拓扑结构研究。

三、对于大规模网络最短路径的计算提出了一种新的算法。

四、对社团结构进行了一些研究，并提出了新的算法。

关键词：中国教育网复杂网络最短路径幂律分布小世界效应社团

结构大规模网络

ABSTRACT

The complex network, as a branch of the complex system research field, has

received unprecedented concern of scientists in recent years. New achievements has

been constantly published in the world first-class authoritative periodicals. The research

of the complex network includes the demonstration research of the topological structure

of real-world network, the evolution, simulation and theory of complex network, and

the dynamic of the network etc.

The demonstration research means to study the characteristic of complex network

by analyzing real networks which includes calculating the average degree, degree

distribution, average shortest path length, etc. This paper describe a work on the China

Education Network of 2007. By programming a net bot to search the web pages under

the domain of ‘.edu.cn’, we are able to build a network which contains 2354934 nodes

and 26816209 edges.

When the network becomes large, the traditional methods are unable to do their

work both in time efficient and storage efficient due to the limit of computer resources.

This paper brings forward a new algorithm which makes it possible to calculate a

similar value of this large network which we has built by using the current computer

resources, which is believed to have positive effect to the future research.

This paper also describes some research on community structure and its relative

algorithms.

The work of this paper mainly contains 4 parts:

1. Program to make a net bot to trace the link under “.edu.cn”, and save the data.

2. study the topology of China Education Network of 2007.

3. bring forward a new similar algorithm to calculate the average path length of

large scale network.

4. study community structure.

Key Word: CERNET, Complex network, Shortest path length,

Power-law distribution, Small world, Community structure,

Large-scale network

中文摘要

ABSTRACT

摘要 ...................................................................................................................................................... 4

ABSTRACT ........................................................................................................................................... 5

绪论 ........................................................................................................................................................ 1

§1 选题背景 ................................................................................................................................ 1

§2 国内外的研究情况 ................................................................................................................2

§2.1 国外研究情况 ............................................................................................................2

§2.2 国内研究情况 ............................................................................................................2

§3 本文所做工作及意义 ............................................................................................................2

§4 论文框架 ................................................................................................................................ 3

复杂网络简介 ........................................................................................................................................ 4

§2.1 复杂网络理论概述 ............................................................................................................4

§2.2 数学模型 ............................................................................................................................ 5

§2.2.1 ER 随机图模型 .......................................................................................................5

§2.2.2 小世界网络模型 ........................................................................................................5

§2.2.3 无标度网络模型 ....................................................................................................6

§2.3 复杂网络的数字特征 ........................................................................................................7

§2.3.1 网络拓扑结构 ............................................................................................................7

§2.3.2 顶点度分布 ................................................................................................................7

§2.3.3 平均路径长度 ............................................................................................................8

网络搜索 .............................................................................................................................................. 10

§3.1 任务分析 .......................................................................................................................... 10

§3.1.1 需求分析 ..................................................................................................................10

§3.1.2 功能定义 ..............................................................................................................10

§3.1.3 其它要求 ..................................................................................................................10

§3.2 Java 简介 ......................................................................................................................... 11

§3.3 网络机器人编写思路 ......................................................................................................12

§3.4 CERNETBot 类介绍 ...........................................................................................................13

§3.5 URLCollector 类介绍.....................................................................................................14

§3.5.1 类介绍 ......................................................................................................................14

§3.5.2 算法流程 ..................................................................................................................15

§3.6 util 包介绍 .....................................................................................................................16

§3.7 exception 包介绍 ...........................................................................................................16

§3.8 程序运行过程中碰到的新问题 ......................................................................................16

§3.8.1 链接黑洞 ..............................................................................................................16

§3.8.2 变种的动态网址 ..................................................................................................17

拓扑结构研究 ...................................................................................................................................... 18

§4.1 数据抓取 .......................................................................................................................... 18

§4.2 数据库的建立 ..................................................................................................................18

§4.3 数据的填充 ......................................................................................................................19

§4.3.1 java 数据导入到数据库中 ....................................................................................... 19

§4.3.2 更新 edgeInfo 的linkInPageIndex ..........................................................................20

§4.3.3 更新 pageInfo 的pageOutDegree ........................................................................... 20

§4.3.4 更新 schoolInfo 的schoolPagesInDegree ...............................................................21

§4.4 度分析 .............................................................................................................................. 22

§4.4.1 平均度 ......................................................................................................................22

§4.4.2 度分布 ......................................................................................................................22

§4.5 平均最短路径长度 ..........................................................................................................24

§4.5.1 普通方法 ..................................................................................................................24

§4.5.2 一种新的近似算法 ..................................................................................................25

§4.5.3 具体实现 ..................................................................................................................26

§4.5.4 计算教育网平均最短路径长度 ..............................................................................27

§4.5.5 结果 ..........................................................................................................................27

§4.5.6 分析和一些新的尝试 ..............................................................................................27

§4.6 其它讨论 .......................................................................................................................... 28

社团结构研究 ...................................................................................................................................... 29

§5.1 社团结构定义 ..................................................................................................................29

§5.2 算法思想 .......................................................................................................................... 29

§5.3 算法实现 .......................................................................................................................... 29

结束语 .................................................................................................................................................. 31

研究总结 ...................................................................................................................................... 31

研究展望 ...................................................................................................................................... 31

附录：搜索算法流程图 ......................................................................................................................33

参考文献 .............................................................................................................................................. 34

在读期间公开发表的论文和承担科研项目及取得成果 ................................................................. 36

致谢 .................................................................................................................................................... 37

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要复杂网络作为复杂系统研究领域的一个分支，近年来得到科学界前所未有的关注，网络研究的新成果不断发表于国际一流的权威期刊上。复杂网络的研究方向主要包括了现实世界网络拓扑结构的实证研究，网络的演化、模拟和理论分析，以及网络中的动力学过程研究等等。所谓实证研究，也就是通过实际计算网络的统计属性参数，如平均度、度分布、平均最短路径长度等，来研究网络的拓扑结构。本文研究了07年的中国教育网，通过编写网络机器人对.edu.cn下的网页进行了搜索，并建立了一个有2354934个节点，26816209条边网络。当网络的规模很大时，无论是从数据的存储还是计算的时间上都使得传统的处理方法难以胜任。在对于平均最短...

展开>> 收起<<

复杂网络理论及其实证研究.pdf

共39页,预览4页

还剩页未读，继续阅读

复杂网络理论及其实证研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: