NW小世界网络公式推导

这篇具有很好参考价值的文章主要介绍了NW小世界网络公式推导。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

假设网络中度数为 k k k 的节点有 N k N_k Nk 个,总共有 N N N 个节点,则度数为 k k k 的节点出现的概率可以表示为:

P ( k ) = N k N P(k) = \frac{N_k}{N} P(k)=NNk

在NW小世界网络中,每个节点有 k k k 条边,其中 k k k 是一个偶数, k / 2 k/2 k/2 条边与相邻节点相连,另外 k / 2 k/2 k/2 条边与远离节点相连。因此,一个节点的所有邻居节点可以分为两类:相邻节点和远离节点。

现在考虑相邻节点之间的连接情况。相邻节点之间的连接有两种情况:一种是它们之间已经有一条边了,另一种是它们之间没有边,但可以添加一条边以形成一个三角形。假设每个节点的相邻节点有 k n n k_{nn} knn 个,由于每个节点有 k k k 条边,因此有 k / 2 − k n n k/2-k_{nn} k/2knn 条边与远离节点相连。由于NW小世界网络是随机网络,因此相邻节点之间的连接概率与它们之间的距离无关,即两个相邻节点之间添加一条边的概率为 p p p

添加一条边后,可以得到一个三角形,三角形的个数为:

N t r i = 1 3 ⋅ ∑ i = 1 N C k i 2 = 1 6 ⋅ ∑ i = 1 N k i ( k i − 1 ) N_{tri} = \frac{1}{3} \cdot \sum_{i=1}^{N} C_{k_i}^{2} = \frac{1}{6} \cdot \sum_{i=1}^{N} k_i(k_i-1) Ntri=31i=1NCki2=61i=1Nki(ki1)

其中 C n m C_n^m Cnm 表示从 n n n 个元素中选取 m m m 个元素的组合数。由于每个三角形会被三个节点所包含,因此三角形的总数为 N t r i / 3 N_{tri}/3 Ntri/3

接下来需要求解度分布的标准差 σ \sigma σ,由于NW小世界网络是随机网络,因此节点度数的方差可以表示为:

σ 2 = ⟨ k 2 ⟩ − ⟨ k ⟩ 2 \sigma^2 = \langle k^2 \rangle - \langle k \rangle^2 σ2=k2k2

其中 ⟨ k 2 ⟩ \langle k^2 \rangle k2 ⟨ k ⟩ \langle k \rangle k 分别表示节点度数的平方和平均值。由于每个节点有 k k k 条边,因此:

⟨ k ⟩ = k \langle k \rangle = k k=k

接下来需要求解 ⟨ k 2 ⟩ \langle k^2 \rangle k2。每个节点的度数为 k k k,因此:

⟨ k 2 ⟩ = 1 N ⋅ ∑ i = 1 N k i 2 \langle k^2 \rangle = \frac{1}{N} \cdot \sum_{i=1}^{N} k_i^2 k2=N1i=1Nki2

由于每个节点有 k k k 条边,因此有 k ( k − 1 ) / 2 k(k-1)/2 k(k1)/2 条边连接到其他节点的概率为:

p = k / 2 − k n n N − 1 p = \frac{k/2-k_{nn}}{N-1} p=N1k/2knn

其中 N − 1 N-1 N1 表示除了自己以外的所有节点数。

对于一个度数为 k k k 的节点,它与相邻节点之间添加一条边形成一个三角形的概率为 p p p,因此它被包含在一个三角形中的概率为 p ⋅ k n n p\cdot k_{nn} pknn。另外,它与远离节点之间添加一条边的概率为 ( k / 2 − k n n ) / ( N − 1 ) (k/2-k_{nn})/(N-1) (k/2knn)/(N1),因此它的度数可以增加 1 1 1 的概率为 ( k / 2 − k n n ) / ( N − 1 ) (k/2-k_{nn})/(N-1) (k/2knn)/(N1)。因此,一个度数为 k k k 的节点可以通过与相邻节点连接形成一个三角形或通过与远离节点连接增加度数 1 1 1,从而获得度数为 k + 1 k+1 k+1 的节点。因此,度数为 k k k 的节点数 N k N_k Nk 可以表示为:

N k = k n n ⋅ p ⋅ N + ( k / 2 − k n n ) ⋅ k − 1 N − 1 ⋅ N N_k = k_{nn} \cdot p \cdot N + (k/2-k_{nn}) \cdot \frac{k-1}{N-1} \cdot N Nk=knnpN+(k/2knn)N1k1N

p p p 的值带入上式并化简,可以得到:

N k = k n n ⋅ k N − 1 ⋅ N + k ( k − 1 ) 2 ( N − 1 ) ⋅ N N_k = k_{nn} \cdot \frac{k}{N-1} \cdot N + \frac{k(k-1)}{2(N-1)} \cdot N Nk=knnN1kN+2(N1)k(k1)N

将上式化简后,可以得到NW小世界网络的度分布公式为:

P ( k ) = k n n ⋅ k N − 1 + k ( k − 1 ) 2 ( N − 1 ) P(k) = \frac{k_{nn} \cdot k}{N-1} + \frac{k(k-1)}{2(N-1)} P(k)=N1knnk+2(N1)k(k1)

其中 k n n k_{nn} knn 表示每个节点的相邻节点个数, N N N 表示节点总数。文章来源地址https://www.toymoban.com/news/detail-449479.html

到了这里,关于NW小世界网络公式推导的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • PnP算法详解(超详细公式推导)

    博主缺粉丝希望大家能给个关注!!! PnP(Perspective-n-Point)是求解3D到2D点的对应方法。它描述了当知道n个3D空间点及其位置,如何估计相机的位姿。如果两张图像中的一张特征点3D位置已知,那么至少需要3个点对(以及至少一个额外验证点验证结果)就可以计算相机的运动。 P

    2024年02月03日
    浏览(37)
  • 对数换底公式及推导证明

    在数学中,对数是对求幂的逆运算,正如除法是乘法的逆运算,反之亦然。如果 a 的 x 次方等于 N (a0,且a≠1),那么数 x 叫做以 a 为底 N 的对数(logarithm),记作 x = l o g a N x=log_a N x = l o g a ​ N 。其中, a 叫做对数的底数, N 叫做真数。 x = l o g a N x=log_a N x = l o g a ​ N 等

    2024年02月11日
    浏览(61)
  • 贝叶斯分类器(公式推导+举例应用)

    引言 在机器学习的世界中,有一类强大而受欢迎的算法——贝叶斯分类器,它倚仗着贝叶斯定理和朴素的独立性假设,成为解决分类问题的得力工具。这种算法的独特之处在于其对概率的建模,使得它在面对不确定性和大规模特征空间时表现卓越。 本文将深入探讨贝叶斯分

    2024年01月21日
    浏览(46)
  • 【论文精读】NeRF中的数学公式推导

    这篇文章用于记录NeRF论文中数学公式的推导过程。 论文里的第一个公式就很硬核,展示了相机射线的期望颜色的计算方法。 5D 神经辐射场将场景表示为空间中任意点的体积密度和定向发射的辐射。文章使用经典体积渲染的原理,来渲染任何穿过场景的光线的颜色。体积密度

    2024年02月10日
    浏览(43)
  • 线性回归python实现详解(附公式推导)

    1.1简单线性回归 在简单线性回归中,输入x只有一个特征,通过调整a和b的参数值,来拟合从x到y的线性关系。下图为进行拟合所需要优化的目标,也即是MES(Mean Squared Error),只不过省略了平均的部分(除以m)。 对于简单线性回归,只有两个参数a和b,通过对MSE优化目标求导

    2023年04月11日
    浏览(33)
  • Minimum Snap闭式求解相关公式推导

    可以看看我的这几篇Blog1,Blog2,Blog3。 闭式法中的 Q Q Q 矩阵计算和之前 M i n i m u m Minimum M inim u m S n a p Snap S na p 当中的一样,但约束的形式与之前略为不同,在之前的方法中, 等式约束只要构造成 [ … ] p = b [ldots] p=b [ … ] p = b 的形式就可以了,而闭式法中,每段轨迹都构

    2024年02月15日
    浏览(34)
  • 【数据结构-矩阵】矩阵的相关公式推导

    设数组元素长度为 L。 1.1 一维数组 数组下标从 0 开始( A[0]–A[n] ,一共 n+1 个),假设当前下标为 A[i] : 第几个 = i + 1 存储地址 = 首地址 + (第几个-1) * L = A[0] 地址 + i * L 数组下标从 1 开始( A[1]–A[n] ,一共 n 个),假设当前下标为 A[i] : 第几个 = i 存储地址 = 首地址 + (第

    2023年04月22日
    浏览(46)
  • 【应试技巧】格林公式记忆方法及简单推导

    视频讲解:格林公式记忆方法及简单推导 大家在学格林公式的时候会发现其实书本上给的形式并不容易记忆。 大家可能会产生下述的问题 忘记了逆时针和顺时针哪个是正方向? 忘记了P,Q该对谁求偏导? 忘记了求偏导以后是谁减谁? 本文分为两个部分,第一部分是将格林

    2024年02月05日
    浏览(38)
  • 分块矩阵求逆推导 + 矩阵反演公式由来

    引自知乎:https://www.zhihu.com/question/47760591 David Sun 大佬的回答 其实也可以正面刚,下面从正面刚一下: 其实正面刚比上一种解法更简单! PS:啥时候Markdown 编辑公式能像Mathtype 那么方便就好了,这样笔者也不用先在word中编辑一遍再贴个图过来了。 注意到第一种分块矩阵求逆

    2024年02月07日
    浏览(39)
  • 变分自编码器(VAE)公式推导

    论文原文:Auto-Encoding Variational Bayes [OpenReview (ICLR 2014) | arXiv] 本文记录了我在学习 VAE 过程中的一些公式推导和思考。如果你希望从头开始学习 VAE,建议先看一下苏剑林的博客(本文末尾有链接)。 VAE 认为,随机变量 (boldsymbol{x} sim p(boldsymbol{x})) 由两个随机过程得到: 根

    2024年02月11日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包