机器算法验证 - 如何统计测试我的网络（图）是否是“小世界”网络？ - 吾爱随笔录

如何统计测试我的网络（图）是否是“小世界”网络？

机器算法验证假设检验图论网络

2022-03-06 20:12:31

小世界网络是一种数学图，其中大多数节点不是彼此的邻居，但大多数节点可以通过少量的跳数或步骤从彼此到达。具体来说，小世界网络被定义为一个网络，其中两个随机选择的节点之间的典型距离 L（所需的步数）与网络中节点数 N 的对数成正比增长，即

$L \approx \log (N)$ $L \approx \log(N)$

L 和 N 之间的这种关系是“经验法则”。我正在为我的研究寻找更专业的小世界图测定方法。如何测试我的图是否是小世界图？

小世界实验包括由 Stanley Milgram 和其他研究人员进行的几项实验，这些实验检查了美国人社交网络的平均路径长度。该研究具有开创性，因为它表明人类社会是一个以短路径为特征的小世界型网络。这些实验通常与“六度分离”这个词相关联，尽管米尔格拉姆本人并没有使用这个词。

先感谢您。

2个回答

TL;博士：

你不能。

通常做什么

当前确定网络是否为小世界的“最新技术”使用以下方法：

计算网络和聚类系数 $L$ $C$
生成适当的空模型网络集合，例如Erdős-Rényi 随机图或Maslov-Sneppen 随机图。
计算这个空模型网络集合的平均最短路径长度类似地计算 $L_\text{r}$ $C_\text{r}$
计算归一化最短路径。和。 $λ := L/L_\text{r}$ $γ := C/C_\text{r}$
如果和满足某些标准（例如，和），则称该网络为小世界网络。 $λ$ $γ$ $λ≈1$ $γ>1$

这背后的想法是：

小世界网络应该具有一定的空间结构，这体现在较高的聚类系数上。相比之下，随机网络没有这样的结构和低聚类系数。
小世界网络在通信和相似性方面是有效的，因此具有与随机网络相当的最短路径长度。相比之下，纯空间网络具有较高的最短路径长度。

问题出在哪里

这并没有说明平均最短路径如何随网络大小缩放。事实上，对于真实的网络，您引用的整个定义不能适用，因为不存在具有不同数量节点的同一个网络。
假设，我们对不直接基于和的值的小世界进行其他定义，例如： $λ$ $γ$

小世界网络是增加了远程连接的空间网络。

那么我们仍然无法对仅使用和（或者实际上是其他网络度量）是否满足这样的定义做出强有力的暗示。许多研究的解释假设所有网络都是Watts-Strogatz 模型对于某些重新布线概率的实现，这根本不合理：我们知道许多其他网络模型，它们的实现与 Watts-Strogatz 模型完全不同。 $λ$ $γ$
上述方法对测量误差不鲁棒。从测量建立网络时的小错误足以使格子看起来像一个小世界网络，参见例如Bialonski 等人，Chaos (2010)和Papo 等人，Front。哼。神经科学。（2016 年）。事实上，我不知道有一项研究声称某些经验网络不是小世界网络。

旁注：你会得到什么？

我不知道可以从某个网络作为一个小世界中得出任何有用的见解。某种网络模型（例如，Watts-Strogatz 模型）很好地描述了某种类型的网络的主张可能对建模研究有用，但这比仅仅声称小世界性要走得更远。

^{完全免责声明：上述论文之一来自我的直接学术附近。}

可以使用包qgraph中的函数smallworldness在“R”中计算小世界指数。

这是基于：Humphries, MD 和 Gurney, K. (2008)。网络“小世界”：确定规范网络等价的定量方法。公共科学图书馆一号，3（4），e0002051

从论文中：

“如果 S>1，网络现在被认为是一个‘小世界’——一个可以进行统计测试的断言。”

其它你可能感兴趣的问题