网络科学导论 |
您所在的位置:网站首页 › 拓扑几何图形的特点是什么 › 网络科学导论 |
主要内容
实际网络的连通性:无向网络中的巨片、有向网络的蝴蝶结结构网络小世界性质刻画:平均路径长度与聚类系数网络均匀性程度刻画:泊松度分布与幂律度分布
一、引言
传统的图论往往着眼于具有某种规则结构或者节点数较小的图,因而往往在理论分析时可以采用图示的方法直观地看出图的某些性质。然而,网络科学研究中涉及的实际网络往往包含着数十万甚至数百万以上的节点,而且具有复杂的不规则拓扑结构。 对于如此大规模的网络不可能通过图示的方法看出网络的拓扑性质,而必须借助于强大的计算能力和统计方法。 此外,网络科学不仅关注拓扑结构,而且更为关注拓扑结构的演化及其与网络上的动力学行为之间的关系等。 首先介绍实际网络的连通性和单个节点的度的概念,然后重点阐述网络科学中的三个重要的拓扑性质:平均路径长度、聚类系数以及度分布。 二、复杂网络的连通性 1. 无向网络中的巨片对于大规模网络而言,连通性是一个相当脆弱的概念,因为单个节点或者相当少部分的节点的行为都可能破坏连通性。 许多实际的大规模复杂网络都是不连通的,但是往往会存在一个特别大的连通片,它包含了整个网络中相当比例的节点,这一连通片称为巨片。一些关于网络拓扑性质的研究往往是针对巨片来进行的。 2. 有向网络中的蝴蝶结结构实际的大规模有向网络往往有一个包含了网络中相当部分节点的很大的弱连通片,称为弱连通巨片。这一弱连通巨片又往往具有一种包含4个部分的蝴蝶结结构。 无向网络中节点 网络中所有节点的度的平均值称为网络的平均度,记为 (无向)网络节点的度与网络边数 有向网络中节点的度包括出度和入度。 节点 在有向网络中,尽管单个节点的出度和入度可能并不相同,网络的平均出度和平均入度确实相同的。复杂系统中,对于每个个体而言不一定成立的性质,却会在整个系统的层面上成立。 3. 网络的稀疏性与稠密化一个包含N个节点的网络的密度 对于无向网络 对于有向网络,上式分母中的0.5去掉即可。 当N趋于无穷大时,网络密度趋于一个非零常数,就表明网络中实际存在的边数是与N的平方是同阶的,可认为该网络是稠密的。如果当N趋于无穷大时,网络密度趋于零或者网络平均度趋于一个常数,表明网络中实际存在的边数是比N的平方低阶的,可认为该网络是稀疏的。 四、平均路径长度与直径 1. 无权无向网络情形 (1)平均路径长度网络中两个节点i和j之间的最短路径是指连接这两个节点的边数最少的路径。两节点i和j之间的距离 网络的平均路径长度 尽管许多实际的复杂网络的节点数目巨大,网络的平均路径长度却小的惊人,这就是所谓的小世界现象。 两个节点之间如果存在最短路径,则最短路径为有限值;如果不存在最短路径,则最短路径为无穷大。可以利用广度优先搜索算法求得从一个节点到网络中所有节点的最短路径。 大型实际网络往往是不连通的,两个节点之间不存在连通的路径,因此可以考虑简谐平均 网络中任意两个节点之间的距离的最大值称为网络的直径,记为D 在实际的应用中,网络直径通常是指两个存在有限距离的节点之间的距离的最大值。
一般地,如果整数D满足g(D-1)=0.9,那么就称D为网络的有效直径。 许多实际网络的直径和有效直径都呈现越来越小的趋势,称为直径收缩现象。 2. 加权有向网络情形上述关于无权无向网络的讨论都可以推广到加权和有向的情形,只是需要注意在加权情形需要考虑边的权值,在有向情形需要考虑边的方向。 五、聚类系数 1. 无权无向网络情形假设网络中节点i的度为ki,则节点i的聚类系数Ci为 其中,Ei是节点i的ki个邻节点之间实际存在的边数,即节点i的ki个邻节点之间实际存在的邻居对的数目。 如果节点i只有一个邻节点或者没有邻节点(ki=0或者ki=1),那么Ei=0,Ci=0。 一个网络的聚类系数C定义为网络中所有节点的聚类系数的平均值。 在求得各节点聚类系数的基础上,我们可以得到度为k的节点的聚类系数的平均值,从而把聚类系数表示为节点度的函数。研究表明,对于许多实际网络,C(k)具有幂律形式 略 六、度分布 1. 度分布的概念把网络中节点的度按从小到大排序,从而统计得到度为k的节点占整个网络节点数的比例pk,可视为网络中随机选择的节点的度为k的概率,称为度分布。 2. 从钟形曲线到长尾分布泊松分布 其中,参数 略 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |