763
个编辑
更改
跳到导航
跳到搜索
第2行：
第2行： − + − + − <math>p^M (1-p)^{{n \choose 2}-M}</math>。 − 此模型中的参数''p''可以看成是加权函数；随着''p''从0增加到1，模型更倾向于包含拥有更多连边的图，而包含拥有较少连边的图的概率则降低。特别地，与''p''=0.5相对应的情况是，在拥有''n''个节点的<math>2^\binom{n}{2}</math>个图中，每个图被选择的概率相等。<br /> − + + + + + + +
→定义
==定义==
==定义==
ER随机图模型有两个密切相关的版本。
ER随机图模型有两个密切相关的版本。
*在模型''G''(''n'', ''M'')中，从''n''个节点、''M''个连边构成的所有图的集合里随机选择一个图。例如，在''G''(3, 2)模型中，3个节点和2个连边能构成三种可能的图，每种图的概率为1/3。
*在模型<math>G(n,M)</math>中，从<math>n</math>个节点、<math>M</math>个连边构成的所有图的集合里随机选择一个图。例如，在<math>G(3, 2)</math>模型中，3个节点和2个连边能构成三种可能的图，每种图的概率为1/3。
*在模型''G''(''n'', ''p'')中，随机连接节点构成一个图。图中每个连边彼此独立，连接的概率为''p''。等价地，拥有''n''个节点、''M''个连边的所有图具有相同的概率
*在模型<math>G(n,p)</math>中，随机连接节点构成一个图。图中每个连边彼此独立，连接的概率为<math>p</math>。等价地，拥有<math>n</math>个节点、<math>M</math>个连边的所有图具有相同的概率：
我们通常研究节点数''n''趋于无穷时随机图的表现。尽管在这种情况下，''p''和''M''可以固定，但是，它们也可以是关于''n''的函数。例如，命题“''G''(''n'', 2ln(''n'')/''n'')中几乎每个图都是连通的”的意思是，当''n''趋于无穷时，拥有''n''个节点、连边概率为2ln(''n'')/''n''的图连通的概率趋于1。
:<math>p^M (1-p)^{{n \choose 2}-M}</math>
此模型中的参数<math>p</math>可以看成是加权函数；随着<math>p</math>从0增加到1，模型更倾向于包含拥有更多连边的图，而包含拥有较少连边的图的概率则降低。特别地，与<math>p=0.5</math>相对应的情况是，在拥有<math>n</math>个节点的<math>2^\binom{n}{2}</math>个图中，每个图被选择的概率相等。<br />
我们通常研究节点数<math>n</math>趋于无穷时随机图的表现。尽管在这种情况下，<math>p</math>和<math>M</math>可以固定，但是，它们也可以是关于<math>n</math>的函数。例如，命题“<math>G(n, 2ln(n)/n)</math>中几乎每个图都是连通的”的意思是，当<math>n</math>趋于无穷时，拥有<math>n</math>个节点、连边概率为<math>2ln'n)/n</math>的图连通的概率趋于1。
==两种模型的比较==
==两种模型的比较==