随机图材料归纳

本文由用户“yohooXZ”分享发布更新时间：2021-04-20 09:48:10 举报文档

以下为《随机图材料归纳》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

随机图

书

连通：如果在

个不同对的顶点中的每一对都存在一条路径，那么我们说此图是连通的。

随机图：??=

1‘，2，…，??

，??=

??，??

，??=1，2，…，??

，此处??

是独立随机变量，使得??

=??

，??=1，2，…，??，换句话说，我们从每个顶点??随机的在??个顶点中选取一个（包括顶点自己）并在顶点??与选取的顶点间连一个弧，这种图通常称为随机图。

问：如何确定这样得的随机图是连通的概率？

答：??

图是连通的

≈

2(???1)

问：连通分量个数的分布

答：有i个分量的概率

??=1

?????+1

???1

?????

???1

问：连通分量个数的期望

答：??

??=1

???1

！

文献

一、基础准备

1、简明定义：所谓随机图，就是一些由顶点组成的集合，各顶点之间随机地用线连接

2、研究的问题：判断现实生活中的系统在化为“图”的形式之后，是不是随机图，是服从哪种分布的随机图，就成为一项重要的工作

3、结构：网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构

4、发展：

最初，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示；

二十世纪五十年代末，数学家们想出了一种新的构造网络的方法，在这种方法下，两个节点之间连边与否不再是确定的事情，而是根据一个概率决定。数学家把这样生成的网络叫做随机图

二、随机图的基本框架

1、基本简介

Newman定义了随机图的一些基本概念：

点：图中的每一个顶点定义为点(vertex)

边：点之间的联系定义为边(edge)

度数：任一个点与之相连的边的个数定义为这个点的度数(degree)

一级邻居：如果一个点A与另外的某个点B中间有一条边直接联系，那么定义点A和点B 互为一级邻居(the first nearest neighbor)

二级邻居：如果点A与点B之间需要两个边才能连接上，即点A与点B之间存在点C与它们同时相连且点A与点B不直接相连, 那么我们称点A与点B互为二级邻居(the second nearest neighbor),以此类推, 还定义了 n 级邻居(then nearest neighbor)

Newman首先就将研究的重点放在了去区分不同的随机图的点的分布的方法上

母函数：

应用母函数的方法来研究度数分布，对任意一个分布产生的随机图，我们定义它的母函数为

??=0

∞

，其中

为点的维数为??的概率，且

≤1，并得到一些基本结果，如导数，n阶矩均值，2级邻居的度数期望。

构成度：

一个点的构成度代表了这个点所能通过边到达的点的个数，构成度的母函数定义为

，而母函数

代表了任意选取一个边它所具有的构成度以及它所衍生出的边的构成度，其均值为

=1+

1???

‘

5、随机图顶点的分布

Poisson 分布：

最简单

点足够多，等概率连接，每个点度数服从Poisson 分布

指数分布：点的度数服从

内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 linear)模型、超线性(superline)模型三种

2、重新定向型增长的随机图（GNR）：指在每个时间点，一个新的点被加入到图中，一个之前的点被选中作为目标，此时按一个概率1-r 将这两个点连接起来，这等同于GN模型，否则就以概率r将新加入的点指向目标所指向的点。

3、考虑年龄的增长型随机图：所谓点的年龄就是点被加入到图中的时间，有些模型的点倾向与较早加入的点连接，有些则倾向于与刚刚加入的点连接。所以，在某些模型上，既要考虑度数的因素，也要考虑年龄的因素

4、带权系数的增长型随机图模型：分为带权重的增长型随机图、双权系数的模型、不同步链接的增长型随机图模型、增长的随机图的构成度

[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。

以上为《随机图材料归纳》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

随机图材料归纳

图片预览

热门关注

相关下载