中国教育网属性与算法研究

VIP免费
3.0 陈辉 2024-11-20 23 4 1.81MB 74 页 15积分
侵权投诉
第一章 绪论
1
第一章 绪论
§1.1 引言
近年来，有关与网络刻画与理解的研究工作非常活跃。现实世界中，许多自
然的和人造的系统中都存在着大量的大规模网络。如生态系统中，物种之间的相
互关联可以描述为复杂的食物链网络。社会系统可以抽象成描述个体间多种相互
作用的图来代表。在科技领域中，互连网和万维网是自组织的原型代表。现代社
会中许多庞大的基础系统如能源和航空运输网，都是不可缺少的网络系统。具有
活力的细胞也不例外，基因、蛋白质和其他分子之间的相互作用形成了一个复杂
的网络，从而产生了细胞的组织和功能。
近来网络研究方法也出现了一个重要的新变迁，即从对含节点数较少的图中
个别节点或边的属性分析转变为对含大量节点数的图的统计属性进行研究。这一
新研究方法很大程度上得益于计算机和通讯网络的出现，使得人们能够收集和分
析远大于以前规模的数据。过去，研究对象可能是只有数十个节点的网络，极端
情况下也不过数百个节点。如今，包含几十万个甚至上百万个节点的网络也是屡
见不鲜,如2004 年2月，由 Debora Donato[1]等人研究的 Web 网络就包含了 2亿
个节点，
1.4 亿条边。网络规模的变化迫使我们相应地改变我们的分析方法。许多
过去在小型网络研究中可能被问及的问题已经不能够简单地在很多大型网络中适
用了。以前分析网络时可能会提出这样的问题：“网络中哪个节点在被删除的情况
下对网络的连通性最为关键？”但此类问题，对于多数包含有数百万个节点的网
络来说，已几乎没有意义，在这种网络中删除单个节点根本不会产生很大的影响。
对于大型网络而言，提出下面的问题是合理的，即“假定要对网络连通性产生实
质影响，需要删除百分之多少的节点？”，由于网络规模较大，研究此类的问题，
需要借助于计算机的分析才能予以回答。
§1.2 开展实证研究的意义
以下几个方面促进了实证的研究的蓬勃发展：
A) 在各个领域中，计算机化的数据采集使各种现实网络的大型数据库得以产生。
B) 逐渐增长的计算能力使我们可以研究含有数百万个节点的网络，探索以前不
可能阐明的问题。
C) 科学界限的逐步地打破，为研究人员使用各种数据库提供了便利条件，使他
中国教育网属性与算法研究
2
们能够揭示复杂网络的一般特性。
D) 对于只有数十个或数百个节点的网络而言，用实际的点和线就可以相对直接
地画出网络图，并通过观察图来回答有关网络结构的特定问题，然而对于大
规模网络，观察无法全面地用来分析网络。
对网络直接进行观察是自网络研究领域开创以来，分析家们首要采用的方法
之一。人眼是一种非常强大的分析工具，用目光对网络进行观察是一种了解其结
构的极好方式。然而，这一方法对于拥有几十万个，上百万个节点的网络来说却
不起作用。仅凭一人之力不能够做到既描绘出这一大型网络，同时又能够使其有
意义，即使动用现代的 3D 计算机绘图工具也做不到这点，从而要想通过眼睛观
察进行直接地分析也是不可能的。因此采用实证的研究方法去理解现实世界的网
络成了当今一些学者研究热点兴趣。如何在不能够对网络作出实际观察的情况下
得知这一网络的形象？这是采用计算机进行实证研究的主要目的。
§1.3 国内外的研究情况
§1.3.1 国外研究情况
在实证研究领域，国外已经对许多的数据库进行了研究，Barabási[2] 和
Albert(1999)对以国际互联网电影数据库中演员为节点，若两个演员在同一部电影
中合作过则定义一条边而构成的一个包含 212250 个节点的网络进行了研究，发现
演员网中各个节点的度分布满足幂律分布，指数
1.03.2 r
，演员的度与演员的
出名程度成正相关。而网络中演员之间的平均最短路径长度为 3.65，相当于相同
规模和平均度的随机网络，这说明演员网是一个小世界网络。但是演员网络的群
聚系数却比随机图要高出 100 倍，表现出很高的群聚特性；Faloutsos[2](1998)等人
已在两个层次研究了国际互联网，得出度分布遵循幂函数规律的结论。国际互联
网作为一个网络的确显示了群聚特性和最短路径长度小的特性，并且其群聚系数
在0.18 至0.3 之间，比随机网络要大得多。此外，国外已研究的网络还包括 Web
网，科研合作网，人类性接触网络，细胞网络，生态网络，电话网，引文网，语
言学网，电力网与神经网络，蛋白质网络等等。
在Web 网络方面，国外有一些文章已有相关研究，除了研究了相应的 Web
网络之外，有的也研究了相应的算法，主要有：
Ravi Kumar[3]等人对 Web 网络的演化模型进行的研究，主要研究了线性增长
模型(linear growth)、指数增长模型(exponential growth)、演化一致模型(evolving
uniform model)。A.Broder[4]等人研究了 Web 网络的内部结构，首次提出了 Web
第一章 绪论
3
网络的 bow-tie 结构。Taher H.Haveliwala[5]等人研究了计算 Web 网络中各网页
PageRank 的算法，主要介绍了搜索引擎在网络上搜索信息的原理和算法。Lada[6]
等人研究了 web 网络中的小世界现象，并且阐述了网络中强连通分量对搜索引擎
在web 网中搜索信息的运用。William Aiello[7]等人研究了满足幂律分布网络的网
络生成模型，系统地总结了已有的网络生成模型，提出了更为一般化的四种网络
演化模型，包括了有向网络和无向网络，并对它们的度分布进行了证明。
§1.3.2 国内研究情况
国内对网络进行实证研究的并不多见，何大韧[8]等人对中药方剂，淮扬菜系，
中国火车车次，北京和扬州的公交线路、中国电力系统，中国铁轨线、长江流域
港口之间的贸易系统进行了实证研究。由杨波[9]等人将复杂网络理论和基于博弈
的经济网络理论相结合，探讨小世界网络的结构演化问题。另外由周涛[10]等人进
行了复杂网络上计算机病毒传播和 SARS 传播研究。国内有关 Web 网络的研究目
前还未发现，以上几个有关的实证研究有一个共同点：即从其研究的规模来看，
还是属于小规模的网络，其中最大的只有 1500 个节点左右，这可能受限于两种情
况：一是数据收集较难，对所研究的网络进行较大的抽象，从而人为地减小了网
络的规模；二是由于网络规模对计算机处理能力起着至关重要的作用，对于大规
模的网络进行研究需要较强的计算机处理能力。显然目前国内在这方面的研究还
不多，能够直接用来对网络进行研究的计算工具还非常少。
§1.4 本文所做的工作
通过网络“爬行”，收集了全国所有网站内的以“edu.cn”为后缀名了网页，
以网页为节点，以网页间的超链接为边，构建了一个包含 366422 个节点，540755
条边的虚拟网络—中国教育网。基于 VC 平台开发了计算网络各种属性的算法并
研究了中国教育网的结构属性，如网络的度分布，平均最短路径长度，网络的连
通分量，强连通分量，点（边）介数，内部 bow-tie 结构，Bipartite clique 结构分
布等等。以此来揭示中国教育网的连接规律，反映它的内部结构特征。当然，在
研究中国教育网的过程中，碰到一些瓶颈问题，比如对于平均最短路径长度的计
算，即便在一台较高配置 PC 的计算机中完成计算也是相当耗时的(少则几天，多
则上月的计算时间)，为了解决这一大规模的计算问题，对算法进行了并行化处理，
使其能够很容易地应用到局域内中多台电脑一起计算。本文所开发的研究算法不
仅仅能够研究中国教育网，同时也能够用来解决其它同样大规模的网络研究问题。
中国教育网属性与算法研究
4
本文所做的主要工作可以总结如下：
收集了全国所有以 edu.cn 为后缀域名的教育类网页，并根据各网页中的
超级链接建立了一个包含 366422 个节点 54075 条边的虚拟网络，称之为
“中国教育网”。
研究了中国教育网的拓扑结构，主要是计算网络的一些属性参数，其中
包括网络的度分布，平均最短路径长度，点(边)介数，群聚系数，网络
的连通分量，强连通分量，以及网络的内部 bow-tie 结构，Bipartite clique
结构。
介绍了当今国内外有关 Web 网络的研究进展，分析 Web 网络的演化规
律，并结合国外已有的 Web 网的网络生成模型，提出了自己的网络生成
模型。
开发了一套相应的算法，并对其各个功能模块进行了集成，使之能够方
便地运用到其它类似的研究当中去，在第五章对算法的详细设计与性能
分析有详细的说明。
§1.5 论文框架
文章共分为六章，每一章的主要内容为：
第一章 绪论：主要回顾传统的网络研究方法，介绍了国内外有关复杂网络实证研
究方面所做的一些工作和取得的一些成就。介绍了本文所做的主要工作以
及本文的总体框架。
第二章 Web 网络的属性与结构：这一章主要是介绍了有关 Web 网络的属性的定
义，如度分布，网络直径等。同时还介绍了国外有关 Web 网络结构研究
的一些成果，目前国内对于 Web 网络结构的研究还很少见。
第三章 中国教育网的属性与结构：这一章主要是在第二章的基础上分别研究了中
国教育网的网络属性和它的结构特征。
第四章 生成模型：这一章主要介绍了有关无标度网络的网络生成模型，包括最早
的由 Price 等人提出的具有“累积效应”的 Price 模型；以“偏好连接”
为显著特征的 B-A 模型。其中 Price 模型主要是模拟生成科技引文网络的，
而B-A 模型是最简单的无向网络生成模型。这两个模型都不是针对 Web
网络而设计的，随后介绍了几个模拟 Web 网络的网络生成模型，如由
Kumar 等人提出的节点拷贝模型，
),(
模型，由 William Aiello 等人提
出的 3种有向网络生成模型。最后 bow-tie 设计了符合中国教育网网络特
第一章 绪论
5
点的网络生成模型。
第五章 算法研究：这一章主要介绍了与算法有关的一些实现细节，如数据结构设
计，各算法的实现细节以及空间，时间性能分析等。
第六章 附录：主要提供了软件的功能结构图、类结构图以及有关的源程序代码。
§1.6 小结与展望
对大规模网络的实证研究已越来越引起人们的兴趣，随着信息时代的到来以
及现代计算机数据收集能力的飞速发展，使得人们可以很容易收集到某一个行业
或领域内大规模的数据信息，并建立相应的数据库。为了挖掘大量隐含在简单数
据背后的重要信息，揭示复杂系统的本质规律，需要对这些大量的数据进行数据
挖掘。为此开发一些高效的算法来处理这些数据就显得非常重要。本文主要针对
中国教育网的网络拓扑结构属性进行研究，并开发了相应的高效算法。所开发的
算法不仅能够研究中国教育网，也可以用来研究其它类似的大规模网络。基于本
文所做的工作，其中有一些方面可以做进一步深入研究，主要有：
虽然从度分布，最短路径长度分布，群聚系数，bow-tie 结构等方面对中国教
育网进行了研究，对网络的宏观、微观结构有了较为清晰的认识，但是有关
于这一网络还可研究的内容非常多，如网络的弹性研究，网络上的病毒传播
模型研究等。
本文结合 bow-tie 结构给出了中国教育网的网络生成模型，依据这一结构特点
生成的 Web 网络势必也具有 bow-tie 结构，但是相对于 Web 网络复杂的演变
机理来说，该模型还是很粗糙的，可以深入研究的地方还有很多，本文在这
一方面所做的工作还很有限，建立一个更为一般化的网络生成模型更好地模
拟网络的发展，这是一个很有吸引力的研究方向。
本文所开发的算法所能够计算的网络属性还很有限，只能够对网络进行较为
有限的研究，但是通过对软件设计思想的了解，熟悉软件设计的类层次结构
与功能结构图，就很容易对软件的算法进行扩展，达到研究特定网络的目的。
中国教育网属性与算法研究
6
第二章 Web 网络的属性与结构
§2.1 引言
Web 网是一种有向图，具备有向图的所有属性，如网络的直径，最短路径长度
等。作为一种大规模网络，仅仅要根据这些属性来刻画网络还不够全面。比如对
于网络的弹性研究，图论所考虑的一般是具体到删除网络中某个节点的对网络连
通性的影响，这对于含有几十万个节点的大规模网络来说没有什么意义，更多是
考虑删除百分之多少的节点会对网络产生什么样的影响。因此有必要从统计学的
角度来研究网络。建立新的网络参数来更全面地描述 web 网络，如节点的度分布，
度相关性，网络的集群系数，节点介数分布等。所以在研究中国教育网的网络结
构以前，先来介绍一下 Web 网的一些网络属性以及结构特征。
§2.2 Web 网的网络属性
§2.2.1 节点度分布
节点度是指与该节点相关联的边的条数，我们定义
)(kP
为网络中度数为
k
的
节点个数占总节点数的比例。
)(kP
也等于在随机一致的原则下挑选出的节点其度
数为
k
的概率。以横坐标表示节点的度
k
，纵坐标表示
)(kP
，这样刻画出来的曲
线就是网络节点的度分布图。
A. 泊松分布
在含有
N
个节点的 ER 随机图
),( ENG
中，每条边存在或不存在的概率均为
P
，
对于网络中任意一个节点
V
，其度为
k
的概率可以这样计算：从网络中其它的
个节点选出
k
个节点，一共有
k
N
C1
种选法，选出的
k
个节点全部与
V
相连的
概率为
k
P
，而剩下的
kN 1
个节点均不与之相连的概率为
kN
P
1
)1(
,因此节点
V
的度为
k
概率：
kNkk
NppCkP
1
1)1()(
(2.1)
在
n
时，(2.1)式近似满足 Poisson 分布：
第二章 Web 网络的属性与结构
7
!
)( k
z
ekP
k
z
(2.2)
其中
pnz
,为泊松分布的期望值，即为网络的平均度数
k
。其分布图像：
图2.1 ER 随机图的节点度分布图
对于随机图来讲，尽管边的位置是随机的，但是典型的随机图是相当均质的，
大多数节点都几乎含有同样多的度数。
B. 幂律分布
在多数情况下可以发现，现实世界网络的节点度分布与 ER 随机网络截然不同。
它们度分布的一个明显特征就是大多数节点都只有很小的度，而极少数节点却具
有很大的度，而且随着网络不断地发展，度数较大的节点相对于度数较小的节点
而言有更高的概率获得更多的边连接，也就是说网络的节点之间的度差异会随着
网络的增大而增大，这就是所谓的“马太效应”，或者称之为“富者愈富”现象。
对这种网络进行度统计时，发现其度服从幂律分布，即存在某一常数
r
，
b
，使
得节点
V
度数为
k
的概率
)(kP
满足：
r
k
b
kP )(
(2.3)
对式 (2.3)两 边取 对数 得:
)ln()ln())(ln( krbkP
，其图像为一条经过点
(1,ln(b))，斜率为
r
的直线。
中国教育网属性与算法研究
8
图2.2 幂律分布的双对数坐标图
对于有向图而言，每一个节点都有一个入度和出度，其联合度分布可以写成
ij
p
，代表入度为
i
而出度为
j
的节点占总节点个数的比例，对
ij
p
基于指标
i
或指
标
j
进行求和就得到有向图的出度分布
out
j
p
和入度分布
in
i
p
，统计表明，大量现实
世界的网络其出度和入度分布都满足幂律分布。
§2.2.2 节点度相关性
在 ER 随机图中，由于各条边连接或不连接的概率是相同且独立的，因此各节
点度之间几乎没有什么相关性。然而对于现实世界的网络而言，情况却并非如此
简单，在很多实际网络中存在这样的特性：度数高的节点是偏向于和其它度数高
的节点相连接，还是偏向于和其它度数低的节点相连接？实际表明在很多网络当
中，这两者情形都存在。对于第一种情形，称之为“同类性”混合，第二种称之
为“非同类性”混合，以节点的度
k
为自变量，以该节点的邻近节点的平均度数
adj
k
为因变量建立函数关系时，可以描绘节点间的度度相关性，计算两个随机变量
k
与
adj
k
的相关系数可以发现，对于“同类性”混合网络，其度与度相关系数大于 0，
“非同类性”混合网络，相关系数则小于 0。
考虑到中国教育网为有向网络，分析其度与度相关性时，有几组数据的相关
性可以分析，比如：节点的出度与其父节点的平均出度相关性，节点的入度与子
节点的平均出度相关性等，一共有八组相关性。
§2.2.3 平均最短路径长度
平均最短路径长度可以对网络的连通性进行较好地描述，有时也用平均最短
路径长度
d
来定义网络直径。R.Albert[11-12]等人在对 web 网络研究时发现，得
摘要：

第一章绪论1第一章绪论§1.1引言近年来，有关与网络刻画与理解的研究工作非常活跃。现实世界中，许多自然的和人造的系统中都存在着大量的大规模网络。如生态系统中，物种之间的相互关联可以描述为复杂的食物链网络。社会系统可以抽象成描述个体间多种相互作用的图来代表。在科技领域中，互连网和万维网是自组织的原型代表。现代社会中许多庞大的基础系统如能源和航空运输网，都是不可缺少的网络系统。具有活力的细胞也不例外，基因、蛋白质和其他分子之间的相互作用形成了一个复杂的网络，从而产生了细胞的组织和功能。近来网络研究方法也出现了一个重要的新变迁，即从对含节点数较少的图中个别节点或边的属性分析转变为对含大量节点数的图的...

展开>> 收起<<
中国教育网属性与算法研究.pdf

共74页,预览8页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：陈辉 分类：高等教育资料 价格：15积分 属性：74 页 大小：1.81MB 格式：PDF 时间：2024-11-20

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 74
评分 收藏
分享
立即下载 VIP免费下载
客服
关注