网络模型
网络模型
结构
网络由节点以及连接节点(node)的边(edge)组成。由边连接起来的节点互为邻居。
网络中的边可以是定向的，也可以是非定向的。在非定向网络中，一个节点的度(degree)等于连接到它的边的数量。
网络以一组网络统计数据为特征。对于每个统计量，我们可以计算网络平均值和所有节点的分布。度分布(degree distribution)告诉我们某些节点是否比其他节点连接得更多。
路径长度(length)，指两个节点之间的最小距离，与度成反比。当增加边时，就缩短了节点之间的平均距离。
最短路径上的节点在网络中起着关键作用。如果信息是通过最短路径传递的，那么就必定会经过最短路径上的节点。
节点的介数得分(betweenness score)等于通过该节点的最小路径的百分比。在社交网络中，介数得分高的人掌握更多信息并且拥有更多权力。
聚类系数，它等于节点的邻居节点对当中，同时彼此也互为邻居节点对所占的比例。整个网络的聚类系数等于各个节点聚类系数的平均值。
网络统计量
- 度：节点的邻居数（即边数）
- 路径长度：从一个节点到另一个节点必须遍历的最小边数
- 介数：经过某个节点连接两个其他节点的最短路径数量
- 聚类系数：一个节点的邻居对当中，同样也由一条边连接的邻居对所占的百分比。
刻画网络的聚集程度的另一种方法是将节点划分为不同的社区(community)。
- 可以用来确定社区的方法有很多，其中一种方法是依次移除具有最高介数的边，因为介数高的边更有可能将不同的聚类连接起来。
- 还有一种方法是将社区的数量视为给定的，并在特定的目标函数下寻找最佳划分方法，例如最小化社区之间边的数量或最大化社区内部边的比例。
社区检测算法(community detection algorithm)
常见的网络结构
随机网络
我们可以将这个网络的统计数据与具有相同数量的节点和边的随机网络进行比较，以检验这个网络是不是随机的。在第一种常见的随机网络中，聚类系数等于一条随机的边的概率，因为一个节点的两个邻居并不比任何其他随机选择的节点更可能包含一条边。蒙特·卡罗方法
为了检验一个具有N个节点和E条边的网络是不是随机网络，可以创建大量具有N个节点和E条边的随机网络，并计算出度、路径长度、聚类系数和介数的分布。然后，执行标准的统计检验，以确定接受还是拒绝那个网络的统计数据可能抽取自该模拟分布的假设。地理网络
大多数常见的地理网络都具有较低的度，即节点仅连接到本地邻居，并且具有相对较大的平均路径长度。在地理网络上，介数和聚类系数不会有变化。幂律网络
这种网络的度分布是幂律的。少数节点有许多连接，同时大多数节点的连接则非常少。小世界网络
它结合了地理网络和随机网络的特征。要想构建一个小世界网络，可以从一个地理网络开始，然后进行“重新布线”，方法是随机地选择一条边并把这条边所连接的其中一个节点替换为一个随机的节点。如果“重新布线”的概率等于零，所拥有的就是一个地理网络；如果“重新布线”的概率等于1，那么就有了一个随机网络；而当概率介于这两者之间时，就会得到一个小世界网络，以小集群区别于通过随机链接连接到其他集群的地理网络。社交网络看起来类似于小世界，每个人都有一群朋友，以及若干随机的朋友。
逻辑
我们遇到的大多数网络结构都是从个体行为者做出的关于建立连接的选择中涌现出来的。不过，也有一些网络，例如供应链网络，确实是计划的产物。我们希望按计划构造的网络对节点的故障具有鲁棒性。
⚠️：自发涌现的网络结构都具有鲁棒性这个事实是一个谜。
上述已经讨论了如何创建随机网络和小世界网络。只需要随机创建一组节点，然后绘制连接随机节点对的边，就可以创建随机网络。通过构建一个规则的地理网络（常用的方法是在一个圆周上排列节点并在每个方向上连接k个邻居），然后随机“重新布线”一部分边，就可以创建一个小世界网络。
要创建一个具有长尾分布的网络，可以利用优先连接模型的一个变体。先随机创建一些节点，然后画出从新节点到现有节点的边。如果我们令连接到节点的概率与节点的度成正比，就可以产生幂律的度分布。在这个模型中，越早“到达”的节点的度越大。但是这个模型有一个缺点，那就是，它不允许节点质量有任何差异。更高质量的节点本应具有更高的度。不过，质量和度的网络形成模型(quality and degree network formation model)纠正了这种缺憾，并且产成了长尾分布。
⚠️：质量和度的网络形成模型
创建d个互不连接的节点。在每周期t中创建一个质量为Qt的、从分布F中抽取出来的新节点。根据其他d个节点的度将这个新节点连接到那些节点上。
$$
用D_{it}表示在时间t时节点i的度，那么给定N个节点时选择节点i的概率等于：
$$
$$
\frac{D_{it}+Q_{it}}{\sum_{j=1}^{N}(D_{jt}+Q_{jt})}
$$
如果新节点质量的均值和方差都足够低，那么这个模型就类似于标准的优先连接模型。如果质量分布有一条长尾，那么质量很高的新节点的度可以增长到非常大的程度。
功能
友谊悖论：如果网络中任何两个节点的度不同，那么平均而言，节点的度会低于其相邻节点。
事实上，在任何网络上，平均来说，人们确实不可能比他们的朋友拥有更多的朋友。友谊悖论适用于任何网络：电子邮件网络、学术引文网络、银行网络和国际贸易网络等。
平均而言，一篇学术论文引用的参考文献被引用的次数比这篇文章本身更多；与一个国家的贸易伙伴进行贸易的国家数量，要比与这个国家进行贸易的国家更多；食物网络中与单一物种相连接的多个物种的连接比该物种自身更多。在具有更加分散的度分布的网络上，朋友的数量与朋友的朋友的数量之间的差异会变得更加明显。
我们的弱关系，也就是网络中的随机朋友，由于连接了具有不同兴趣和信息的社区，从而发挥了重要的信息作用。因此，社会学家很强调弱关系的力量。
鲁棒性：
网络最重要的性质是，它在受到冲击时是不是仍然能保持连接。我们可以使用模型来计算网络保持连接的概率——作为移除节点数量的函数。还可以考察当移除某些节点时平均路径长度会发生什么变化。
⚠️：缺乏局部聚类的稀疏网络更容易出现故障。远距离跳跃有助于提高网络的鲁棒性。
具有长尾度分布的互联网对随机节点故障具有很强的鲁棒性。互联网的度分布意味着，绝大多数节点的连接很少，因此即便它们发生了故障，网络也能保持连接。但是，如果考虑移除战略性节点，例如战略性地移除度最高的节点，就会破坏整个网络。
迈尔森值和结构洞 (structural holes)
填补结构洞的人能够将网络中的不同社区联系起来，从而具有更大的影响力。网络的各种统计数据，例如介数，都与能不能占据结构洞相关。对于一个人在网络中的影响力的另一个衡量指标是迈尔森值，它依赖于夏普利值的原理。
中心性测度（例如介数）只以网络为基础，而迈尔森值则取决于价值函数。