【复杂系统与复杂网络】增长网络中的受欢迎度与相似性

本文内容源自12年九月份nature上的一篇文章:Popularity versus similarity in growing networks.
我们都知道，在社交网络当中，朋友越多的人，越容易结识到新的朋友。换句话说，在一个无标度网络中，度越大的节点与新加入的节点相连的概率越大。这一点，巴拉巴西（Barabdási）和阿尔伯特（Albert）已经在1999年science上的一篇重量级文章中给出了证明，同时提出了BA无标度网络模型。
而所谓的度越大，越容易与新节点相连，便是受欢迎程度。这一点，可以在许多现实网络中得到印证。比如，学生最多的导师总是能够招到较多的学生，而没有学生的导师是很难招到学生的。
现如今，12年nature上的那篇文章又提出了一个新的模型。与其他一些对BA模型进行优化的模型不同的是，该模型创造性地提出了相似性这一衡量标准，从根本上弥补了BA模型的一些缺陷。堪称又一重量级文章。
所谓相似性，比如当你创建一个人人账号时，系统会根据你的个人信息，主动向你推荐一些好友。这些好友有些是你的同学，有些跟你有共同的爱好。这些人与你的相似性就比较高。
那么怎么在数学上表示受欢迎度与相似性呢。
对于受欢迎度，与以往单纯用度的大小来衡量受欢迎度不同的是，该文章引入了出生时间（birth time）的概念。也就是说，在网络增长的过程中，每一时间时刻进入一个节点，该节点是以该时刻的数值进行编号的。比如：1、2、3……
这个编号，便是出生时间。
而相似性，就是将节点随机放置在一个圆上，这个圆代表一个相似空间，点与点之间的角距离便是相似度。
因而这个模型可以简单作如下阐述：
（1）初始状态网络为空，也就是没有一个节点；
（2）当时间t>=1时，新节点t随机出现在圆上，其角位置为θt；
（3）新节点t与已存在节点s相连，s<t，而具体s到底有几个，便是由参数m来决定（这一点为了简化，我们可以把m设为1，也就是说新进入节点只与一个旧的节点相连），连接的标准便是看s与θst的乘积，如果比较小，就与之相连。
其中θst是节点t与s之间的角距离。
除此之外，该模型还有一个有趣的几何表述。
若将出生时间t用极坐标的径向坐标表示rt=lnt，那么这些点便会落在一个平面上，而不是在一个圆上。与此同时，点的坐标便是（rt，θt）。
经过一些列的运算，我们会发现，将圆盘上两点之间的距离最短作为新旧节点相连的判据与将s*θst最小值作为连接判据是等价的。
                
                
通过两个图可以看出新模型和BA模型在吸引概率和度的关系图中所表现的图像相当一致。
而在连接概率和双曲空间距离的关系图中，新的模型显然要比传统的BA（PA）表现的更好一些。
                
                
这主要是因为，新模型的群聚系数要比BA模型中大很多（所谓群聚系数，便是朋友的朋友也是朋友之类的三角关系），而真实网络当中，群聚系数往往是一个比较大的值。这样我们就有了一个更加接近真实网络的模型。
最后该文章还针对许多真实网络与模型的理论值进行了比较，结果曲线都很吻合。
                
                
参考文献：
【1】Baraba´si, A.-L.&Albert, R.Emergence of scaling in randomnetworks. Science 286,509–512 (1999).
【2】Fragkiskos Papadopoulos, Maksim Kitsak & Dmitri Krioukov. Popularity versus similarity in growing networks. Nature 489,537-540 (2012)