2017-07-21 20:31:12

度分布 免费编辑 添加义项名

B 添加义项
?
义项指多义词的不同概念,如李娜的义项:网球运动员、歌手等;非诚勿扰的义项:冯小刚执导电影、江苏卫视交友节目等。 查看详细规范>>
所属类别 :
其他
其他
编辑分类

图结构中与某节点相连接的边的数目为该节点的度,而图中各个的节点度的散布情况就为度分布。

基本信息

  • 意思

    图中顶点度数的概率分布

  • 表达式

    d ( i) = Σj ∈Gδij .

目录

折叠 编辑本段 概念

度分布图论网络理论中的概念。一个图(或网络)由一些顶点(节点)和连接它们的边(连结)构成。每个顶点(节点)连出的所有边(连结)的数量就是这个顶点(节点)的。度分布是对一个图(网络)中顶点(节点)度数的总体描述。对于随机图,度分布指的是图中顶点度数的概率分布

一个节点的度通常定义为该节点连接的所有连接(边) 的总和。 网络的度分布即为网络中节点的度的概率分布或频率分布(统称分布)。 一个节点的度k 通常定义为该节点连接的所有连接(边) 的总和,写成数学表达式为:

d ( i) = Σj ∈Gδij .

折叠 编辑本段 定义

度分布是图论和(复杂)网络理论中都存在的概念。首先介绍图的概念。一个图是一个由两个集合和构成的二元组。集合一般由有限个元素构成,其中的元素被称为图的顶点,集合是由个元素构成的集合。集合中的每个元素都是一个非负整数。在无向图中,图中的每个元素,由图中的两个顶点和连接有条边构成。在有向图中,图中的每个元素,由图中的顶点以及有条连向顶点的边构成。并且,如果一个图中所有的都不超过1,那么称图是简单图。

网络理论的数学框架建立在图论上。网络理论中的网络其实就是图论中的图,但在网络理论中称之为网络,图的顶点在网络理论中称为节点,边被称为连结。以下仍旧以图论中的术语定义度分布。从顶点中等概率地随机抽取一个顶点,那么这个顶点度数为k的概率就是p(k)。

折叠 编辑本段 分布

随机图是指由随机过程产生的图,即是将给定的顶点之间随机地连上边。一个随机图中,每两个顶点之间的边的数量是随机变量。因此任一顶点的度也是随机变量。这个变量的概率分布也称为随机图中的顶点的度分布:

在经典的随机图模型中,所有顶点的位置都是一致的,没有特殊的顶点。因此每个顶点的度分布都是相同的:。所以,随机抽取一个顶点,它的度数是的概率就是;越高,表示可能有更多的顶点度数是。当顶点数目很大每个顶点的度分布都是相对独立的时候,顶点的度分布近似等于图中度数是的顶点的比例。

折叠 编辑本段 例子

以下给出一些度分布的例子。右图是由十个顶点构成的无向图。其中度数是3的顶点有6个,度数是4的顶点有3个,度数是6的顶点有1个,所以度分布是:对于阶完全图,所有的顶点的度数都是,如果图是任意两顶点之间以概率连边的随机图,那么每个顶点都有相同的度分布。

这个分布是泊松分布。我们可以构造每个顶点的度数都是这样的概率分布的随机图模型。这样当顶点数很大的时候,度数是的顶点的个数占的比例大致是。这个分布的特点是当k很小或很大的时候,都近似于0,的值在一个特定的值处达到高峰,然后回落。也就是说,大多数的顶点的度数在这个特定值左右。然而在真实的复杂网络中,人们观察到,度分布并不像这种随机图模型显示的,聚集在某个特定值周围,而是随着k增大而以多项式速度递减,也就是遵从所谓的幂律分布:也就是说 的概率反比于 的某个幂次,其中是某个正实数。这种网络特性被称为无尺度特性。

阅读全文

热点资讯

我的关注