族谱网 头条 人物百科

随机图

2020-10-16
出处:族谱网
作者:阿族小谱
浏览:628
转发:0
评论:0
定义与模型随机图的“随机”二字体现在边的分布上。一个随机图实际上是将给定的顶点之间随机地连上边。假设将一些纽扣散落在地上,并且不断随机地将两个纽扣之间系上一条线,这样就得到一个随机图的例子。边的产生可以依赖于不同的随机方式,这样就产生了不同的随机图模型。一个典型的模型是埃尔德什和雷尼共同研究的ER模型。ER模型是指在给定n个顶点后,规定每两个顶点之间都有p的概率连起来(0⩽⩽-->p⩽⩽-->1{\displaystyle0\leqslantp\leqslant1}),而且这些判定之间两两无关。这样得到的随机图一般记作Gnp{\displaystyleG_{n}^{p}}或ERn(p){\displaystyleER_{n}(p)}。另一种随机图模型叫做内积模型。内积模型的机制是对每一个顶点指定一个实系数的向量,而两个顶点之间是否连接的概率则是它们的向量的内积的函数。一般来说,可以定义任意...

定义与模型

随机图的“随机”二字体现在边的分布上。一个随机图实际上是将给定的顶点之间随机地连上边。假设将一些纽扣散落在地上,并且不断随机地将两个纽扣之间系上一条线,这样就得到一个随机图的例子 。边的产生可以依赖于不同的随机方式,这样就产生了不同的随机图模型。一个典型的模型是埃尔德什和雷尼共同研究的 ER模型 。ER模型是指在给定 n 个顶点后,规定每两个顶点之间都有 p 的概率连起来( 0 ⩽ ⩽ --> p ⩽ ⩽ --> 1 {\displaystyle 0\leqslant p\leqslant 1} ),而且这些判定之间两两无关。这样得到的随机图一般记作 G n p {\displaystyle G_{n}^{p}} 或 E R n ( p ) {\displaystyle ER_{n}(p)} 。

另一种随机图模型叫做 内积模型 。内积模型的机制是对每一个顶点指定一个实系数的向量,而两个顶点之间是否连接的概率则是它们的向量的内积的函数。

一般来说,可以定义任意两个顶点之间相连的概率,这个概率也被称为 边概率 。定义更广泛的随机图模型的方法是定义所谓的网络概率矩阵。这个矩阵的系数就是边概率,因此详细刻画了随机图的模型。

随机规则图是随机图中特殊的一类,它的性质可能会与一般的随机图不同。

性质

随着边概率的不同,随机图可能会呈现不同的属性。对于最典型的ER模型,埃尔德什与雷尼研究了当顶点数目 n 趋向于正无穷大时,ER随机图的性质与概率 p 之间的关系。他们发现,当 p 的值越过某些门槛时,ER随机图的性质会发生突然的改变 。ER随机图的许多性质都是突然涌现的,比如说,当 p 的值小于某个特殊值之前,随机图具有某个性质的可能性等于0,但当 p 的值大于这个特殊值以后,随机图具有这个性质的可能性会突然变成1。

举例来说,当概率 p 大于某个临界值 p c ( n ) 后,生成的随机图几乎必然是连通的(概率等于1)。也就是说,对于散落在地上的 n 个纽扣,如果你以这样的概率 p 将两个纽扣之间系上线,那么你拿起一颗纽扣时就几乎能带起所有的纽扣了 。

随机树

随机树是随机图的一类。如同随机图一样,随机树是一个经由随机过程建立的树。随机树的一种生成方法是利用随机置换。首先生成一个 n 2 ( n − − --> 1 ) {\displaystyle \scriptstyle {\frac {n}{2}}(n-1)} 阶随机置换函数,将 n 2 ( n − − --> 1 ) {\displaystyle \scriptstyle {\frac {n}{2}}(n-1)} 个可能连起来的边标上 1 至 n 2 ( n − − --> 1 ) {\displaystyle \scriptstyle {\frac {n}{2}}(n-1)} 的序号。然后按照从小到大的序号排列为原本没有边的图一一添加边。添加第 k {\displaystyle \scriptstyle k} 条边时,如果发现添加后会导致图现一个圈,那么就放弃添加这条边,而开始添加第 k + 1 {\displaystyle \scriptstyle k+1} 条边。最后得到的就是一个随机树 。

参见

玻色-爱因斯坦凝聚

腔体法

复杂网络

小世界网络

无尺度网络


免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。

——— 没有了 ———
编辑:阿族小谱
发表评论
写好了,提交
{{item.label}}
{{commentTotal}}条评论
{{item.userName}}
发布时间:{{item.time}}
{{item.content}}
回复
举报
点击加载更多
打赏作者
“感谢您的打赏,我会更努力的创作”
— 请选择您要打赏的金额 —
{{item.label}}
{{item.label}}
打赏成功!
“感谢您的打赏,我会更努力的创作”
返回

更多文章

更多精彩文章
打赏
私信

推荐阅读

· 随机博弈
定义这类博弈由一系列阶段组成。在博弈中每一阶段的起始,博弈处于某种特定状态。每一参与者选择某种行动,然后会获得取决于当前状态和所选择行动的收益。之后,博弈发展到下一阶段,处于一个新的随机状态,这一随机状态的分布取决于先前状态和各位参与者选择的行动。在新状态中重复上述过程,然后博弈继续进行有限或无限个数的阶段。一个参与者得到的总收益常用各阶段收益的贴现和,或是各阶段收益平均值的下极限来计算。数学描述随机博弈的组成部分有:有限参与者集I{\displaystyleI};状态空间M{\displaystyleM}(可以是有限集,也可以是可测空间(M,A){\displaystyle(M,{\mathcal{A}})});对于每一参与者i∈∈-->I{\displaystylei\inI},存在行动集Si{\displaystyleS^{i}\,}(可以是有限集,也可以是可测空间(Si,Si){\...
· 随机过程
定义设(ΩΩ-->,F,P){\displaystyle(\Omega,{\mathcal{F}},P)}为一概率空间,另设集合T为一指标集合。如果对于所有t∈∈-->T{\displaystylet\inT},均有一随机变量ξξ-->t(ωω-->){\displaystyle\xi_{t}(\omega)}定义于概率空间(ΩΩ-->,F,P){\displaystyle(\Omega,{\mathcal{F}},P)},则集合{ξξ-->t(ωω-->)|t∈∈-->T}{\displaystyle\{\xi_{t}(\omega)|t\inT\}}为一随机过程。通常,指标集合T代表时间,以实数或整数表示。以实数形式表示时,随机过程称为连续随机过程;以整数表示时,则为离散随机过程。随机过程中的参数ωω-->{\displaystyl...
· 随机试验
例子查论编
· 随机数
密码学范畴的随机数根据密码学原理,随机数的随机性检验可以分为三个标准:统计学伪随机性。统计学伪随机性指的是在给定的随机比特流样本中,1的数量大致等于0的数量,同理,“10”“01”“00”“11”四者数量大致相等。类似的标准被称为统计学随机性。满足这类要求的数字在人类“一眼看上去”是随机的。密码学安全伪随机性。其定义为,给定随机样本的一部分和随机算法,不能有效的演算出随机样本的剩余部分。真随机性。其定义为随机样本不可重现。实际上衹要给定边界条件,真随机数并不存在,可是如果产生一个真随机数样本的边界条件十分复杂且难以捕捉(比如计算机当地的本底辐射波动值),可以认为用这个方法演算出来了真随机数。相应的,随机数也分为三类:伪随机数:满足第一个条件的随机数。密码学安全的伪随机数:同时满足前两个条件的随机数。可以通过密码学安全伪随机数生成器计算得出。真随机数:同时满足三个条件的随机数。随机数在密码学...
· 随机分析
参看彭实戈伊藤清确定性模型伯努利过程随机过程布朗运动马可夫过程莱维过程

关于我们

关注族谱网 微信公众号,每日及时查看相关推荐,订阅互动等。

APP下载

下载族谱APP 微信公众号,每日及时查看
扫一扫添加客服微信