知识库

1. 小世界网络、偏好依附机制、跨学科研究——网络科学20年

Erdos-Renyi model

• 生成随机网络
• 网络中任意两个节点之间的平均路径长度（两个节点相连所需要的最小连边数量），与节点总数满足对数关系
• 缺点：
  • failed to replicate the clustering, triadic closure, and hubs seen in real-world networks.
  • 对网络中节点之间连边生成规则缺乏认识，并且还假设一对节点之间连接的概率可以随机给定
  • 不能捕捉到真实世界中网络节点的局部聚集性(Cliquishness）
    • 聚集性由聚集系数来度量，聚集系数定义为“某个节点的邻居节点之间的连边数量，与邻居节点之间可能连边数最大值之比”，用来定量描述节点的聚集程度

泊松分布

• 泊松分布适合于描述单位时间（或空间）内随机事件发生的次数。
• 如某一服务设施在一定时间内到达的人数，电话交换机接到呼叫的次数，汽车站台的候客人数，机器出现的故障数，自然灾害发生的次数，一块产品上的缺陷数，显微镜下单位分区内的细菌分布数等等。

Watts-Strogatz model

• 引入随机性（Stochasticity）
• generate random-graphs with small-world properties
• Small-world networks tend to contain cliques, and near-cliques, meaning sub-networks which have connections between almost any two nodes within them
  • 真实世界的网络中，节点聚集的典型例子是“我朋友的朋友也是我的朋友”：三个人在社交网络中彼此成为朋友的概率，远远高于用简单随机过程构建的模型网络所做的预测。

1988年，Watts 和 Strogatz 提出了一个用于解释实际网络结构的模型。a，图中的三角晶格中，每个节点和其他六个节点相连，Watts就是从这种规则的网络开始构建模型；b，他们让节点之间以固定的概率随机重连。随着这个概率值的增加，越来越多的近路(红线)把网络中相距较远的节点连接起来。这就能产生小世界效应:只需通过少许几条节点之间连边，任何两个节点都能相连，但是相邻的节点又相互连接，形成了集聚集团。

随机性可以解释被统称为“六度分隔”的小世界现象

Barabasi-Albert model

• generate scale-free networks through preferential attachment mechanism（偏好依附机制）
• 该模型强调了真实网络中节点之间连边的概率经常有“重尾分布（heavy-tailed）”的特点，而不是由随机网络推出的泊松分布

scale free behaviour

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically(近似的). That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as

幂律分布（the Power Law distribution）

In statistics, a power law is a functional relationship) between two quantities, where a relative change in one quantity results in a proportional relative change in the other quantity, independent of the initial size of those quantities: one quantity varies as a power of another.

Why power has two meanings on the internet

A very small number of websites have colossal numbers of links, while millions of others have to make do with only a few.

争议

理论危机 | 无标度网络遭到史上最严重质疑

Zipf’s law and the Internet

3 assumptions:

1. Proportional growth or preferential attachment
2. The sites established early would have grown to greater sizes than recently founded ones.
   1. However, studies have found only weak correlation between the size of a site and its age
3. Sites can grow at different rates, depending on the type of content and interest that they generate.

In summary, a very simple assumption of stochastic multiplicative growth, combined with the fact that sites appear at different times and/or grow at different rates, leads to an explanation for the scale free behavior so prevalent on the Web

• connnection to the of Barabasi-Albert network——偏好依附机制

It can b expressed in mathematical fashion as a power law, meaning that the probability of attaining a certain size x is proportional to x^r, where r is greater than or equal to 1.