4TheBarabási-Albertmodel

一、	简介

1999年10月15日Science杂志刊登了巴拉巴西和阿尔伯特的文章，他们提出了通过网络生长和偏好依附的模型，
可以获得无标度网络，后被称为 B-A模型。这一模型的提出，是网络科学里程碑式的工作
。在此之前，大多数网络被想当然的认为是随机的，因此连接度分布可以近似用泊松分布来表示，
而巴拉巴西与其学生阿尔伯特、郑浩雄通过对万维网的度分布测量的结果却显示万维网度分布近似服从幂律分布，存在枢纽节点（拥有大量链接的节点）。
这项研究之后，关于复杂网络的研究如雨后春笋，不断出现。
也许万维网是特别的，为了避免这种偶然性，巴拉巴西等人进而又分析了两个网络系统——IBM计算机芯片布线图与好莱坞演员数据库，结果其度分布均遵循幂律分布。
B-A模型无疑是当今使用的最著名的生成网络模型，它与Price的模型相似，但又不完全相同，它是一个无标度网络模型。

二：前提假设

增长性：随机网络模型假设节点数目N是固定的，而绝大多数现实中的网络由于新节点的加入，是不断扩大不断增长而来的，
例如互联网中新网页的诞生，社交网络中新朋友的加入，航空网络中新机场的建造等等。 
优先连接性：随机网络中节点随机地选择节点进行连接，而在真实网络中，新的节点在加入时会倾向于与有更多连接的节点相连。
例如新网页一般会有到知名的网络站点的连接，在社交中受欢迎的同学更有机会被认识，新机场会优先考虑建立与大机场之间的航线等。

三：模型构造 

其实该模型等价于Price模型的一个特例。想象一下，我们为网络中添加的每条边提供了一个方向，从刚刚添加的边连接到的先前存在的顶点。
这就是每一条边的运行。新的节点在加入时会倾向于与有更多连接的节点相连。
通过这种方式，我们将网络转化为一个有向网络，其中每个顶点的出度正好为c（因为这是顶点开始时的输出边数不再增加）。
一个顶点的总度是顶点入度和出度之和，即ki=qi+c，其中qi与前面一样表示入度。
但是，假设一条边附着到一个顶点的概率与ki成正比，那么它就是 qi+c,因此，也与qi+c成比例，这与Price模型中的相同(特定a=c下)。
因此，在这个有向网络中，入度的分布与Price的分布具有相同的模型。B-A模型产生了一个带有幂律尾的度分布,其中预测度指数始终为α=3。
B-A模型由于它的简单性而具有吸引力，它不需要考虑 Price模型的参数a，因此少了一个需要担心的参数。
这使它成为了令人满意的可编写度分布，而无需使用特殊函数。但是该模型也存在很多问题，其中最严重的应该是该模型不再能够与实际网络中观察到的指数相匹配，而仅限于单个指数值α=3。

四：实例 

电影演员网络代表了一个有充分记录的社交网络示例。每个演员都用一个节点表示，如果两个演员在同一部电影中一起出演，则两个演员是相连的。（图1A）。
万维网相较于电影演员网络节点更多且更复杂，一个网页用一个节点表示，一个网页对于另一个网页的连接就构成它们之间的边。一个网页指向某个网页的概率遵循幂律（图1B）。
还有一个典型实例是美国西部的电力网，节点代表发电机、变压器和变电站，边对应于它们之间的高压输电线。由于该网络的规模相对较小，仅包含4941个顶点，因此缩放区域不太明显，但仍然近似服从幂律分布（图1C）。
 
（A） 电影演员网络，N=212250，〈k〉=28.78的参与者集合图；
（B） 万维网，N=325729，〈k〉=5.46（6）；
（C） 电网数据，N=4941，〈k〉=2.67。
其中N为节点数，〈k〉为平均连通度。
虚线的斜率为（A）γactor=2.3，（B）γwww=2.1和（C）γpower=4。

五：基于R语言生成简单的随机图 
library(igraph)
## 
## Attaching package: 'igraph'
## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum
## The following object is masked from 'package:base':
## 
##     union
random<-erdos.renyi.game(27,0.2,type=c("gnp", "gnm"),directed=F)
#gnm<-sample_gnm(10,20,directed = F)
 #gnp<-sample_gnp(10,0.3,directed = F)
 V(random)$color<-"red" 
V(random)$size<-30
E(random)$color<-"blue" 
pa<-get.all.shortest.paths(random,1,20)$res[[1]]
 E(random,path=pa)$color<-"black"
plot(random,layout=layout.fruchterman.reingold)
 
plot(degree.distribution(random), xlab="node degree")
 
mean_distance(random)
## [1] 2.006154
transitivity(random)
## [1] 0.2301587

六、BA模型的局限

1.	该模型预测度指数为α=3，而真实网络的度指数可以有更宽松取值(一般2到5间)。
2.BA模型定义中有数学细节未指明包括初始M0个节点的连接情况;加入的节点新建的链是逐步的还是同时的，可能导致多重链接。 
3.万维网、引文网络等许多真实网络都是有向的，而BA模型生成的网络都是无向网络。 
4.网络中观测到的很多过程，例如节点间形成链接、链接消失、节点消失等，在BA模型中没有。 
5.BA模型是一个最较简化的、原理性的模型，其主要初衷是刻画无标度特性形成的基本机制，针对实际网络系统还有其他特性需要考虑，如有向性、节点的消失等。

七、参考文献

[1]Network an Introduction M.E.J.Newman
[2]Albert-Laszlo Barabasi.Network Science[M].2014