5 Evolving Networks.Rmd

# 演化网络
    演化网络 （Evolving networks）是一种随着时间的变化而产生变化的网络，即演化网络是作为时间的函数而变化的网络。演化网络是网络科学的自然延申，因为几乎所有现实世界的网络都是在随着时间变化而演化的，这种演化是通过随着时间的推移，网络的节点以及节点之间的连接进行增加和删除来实现的。通常情况下，网络演化中的这些过程都是同时在发生的，同时进行的，并不存在先后关系。就拿我们都十分熟悉的社交网络来说：我们每个个体都是社交网络中的一个节点，而我们之间的关系就是社交网络中的边，无数的点和边共同构成了这个巨大的社交网络。我们都知道，每时每刻都有人结交了新朋友，或与原有的朋友疏离，每时每刻都有新的关系建立或遭到破坏，这个世界也每天都见证着新生命的诞生和消亡。这个社交网络一直在发生着改变，从未停止。演化网络的概念越来越受到欢迎，这个建立在既定的网络理论之上的概念，正在被引入到许多不同领域的网络研究中去。

## 网络理论背景
    网络研究源于图论 graph theory的发展，莱昂哈德·欧拉 Leonhard Euler于1736年首先分析了图论，当时他撰写了著名的柯尼斯堡七桥问题 Seven Bridges of Königsberg论文。随后在八篇由保罗·埃尔德什 Paul Erdős和阿尔弗雷德·雷尼 Alfréd Rényi撰写的研究随机图 random graphs的著名论文的帮助下，概率网络理论得以发展。埃尔德什-雷尼模型 Erdős–Rényi model(即ER模型)假定一个图由n个有标记的节点组成，其中每一对节点通过一个预设的概率p连接。
    然而，尽管ER模型的简单性使其能够被应用于许多情况，但它并不能准确地描述许多真实世界中的网络。ER模型无法像在现实世界的网络中那样地频繁地生成三元闭包和局部聚类。因此，瓦茨-斯托加茨模型 Watts-Strogatz model 出现了，它将网络构造成了规则的环网格，并根据一定的概率β来重新连接节点。如此创建的网络就可以代表在许多现实世界网络中观察到的小世界现象了。
    尽管如此，不管是ER模型还是瓦茨-斯托加茨模型都不能解释在许多现实世界网络中观察到的中心节点的形成。

## 无标度网络——第一个演化网络模型
    巴拉巴西-阿尔伯特模型 Barabási–Albert model（BA模型）是第一个被广泛接受的产生无标度网络的模型。随着时间的不断向前推移，更多的节点被陆续添加到网络中，并且更有可能连接到其他度比较大的节点，这是通过偏好依附和增长来进行实现的。BA模型应用与互联网上，我们就能清楚地看到，随着时间的不断推移，会不断有新的网页出现，并且，每个新出现的网页都有更大的可能去链接到诸如谷歌等具有非常高的度分布的中心节点，而非那些链接数量少之又少的节点。


## 描述演化网络的其他方法
    除了以上不断生长的网络模型之外，在有些时候其他的一些方法对于演化网络某些性质的描述更加有用和方便。
### 一：将演化网络视为连续的静态网络快照
    观察不断演化的网络中十分常用的方法就是将它们看作连续的静态网络。就像是电影一样，电影就是由一个个静态图像所组成的。而描述一个静态网络可比描述一个动态网络要简单和方便的多，有许多简单的如节点数，边，路径长度等参数可以用于描述，或者是描述静态图中的某个特定节点，比如其链接数和集聚系数（集聚系数是图论中用来描述一个图中的顶点之间集结成团的程度的系数）。之后便可将这些属性单独作为时间序列来进行研究。例如，通过查看网络的连续快照中每张快照中的链接数量，通过这种方式来跟踪查看一段时间内建立到服务器的链接的数量。然而，这种方法的缺点也十分突出，即难以选择合适的时间尺度。过短的时间间隔虽然可以让我们对网络的演化有更细致的观察和了解，但这也可能掩盖了需要在较长时间间隔下才能被发现的大趋势。相反，如果快照的时间间隔过长，连续两张快照就会有巨大的差别，我们无法分辨出快照中时间的发生顺序。因此，时间尺度的找寻是该方法的一大痛点。
### 二：定义动力学性质
    有些网络演化中的特性对我们的研究是十分重要的，具有重大意义，但是这些性质又不能直接利用方法一观察。这时候定义动力学性质这种方法就十分有用了。我们可以通过定义这些属性，然后通过网络的演化来跟踪这些属性，直接通过可视化来进行观察和研究。

## 应用举例
    在我们生活的现实世界中的网络几乎都是处于不断演化状态中的网络，随着时间的推移而不断改变和演化。比如文章开头提到的社交网络，还有通信网络，互联网，交通网络等许多现实世界中的网络都在演化网络的研究范围内。社会不断进步发展，各种交通运输手段不断出现和改善，整个社会的交通网络都在不断地趋向完整和复杂。
    拿公共交通的演化网络模型来看。公交停靠站点和公交线路是构成公共交通网络的两个基本要素。运用Space P 网络拓扑方法，将公交站点视作节点，任意两个站点之间只有有直达公交线路，则两个节点间就有连接的边。
    在拓扑中遵从以下假设：
    (1)仅考虑公交线路，不考虑轨道交通线路；
    (2)网络抽象为无向网络；
    (3)对于个别线路因为交通管制等原因造成上下站点有差异的，以上行方向的线路为准；
    (4)不考虑发车频率的不同，将网络抽象为非加权网络；
    (5)相同名称站点看作一个停靠站点，忽略个别站点名称相同但位置不同造成的差异。
    公共交通网络的局域世界演化模型的建立和演化过程是：
    (1)初始网络：以最重要节点为七点，通过增加节点重要降序排列的节点与最重要节点之间的最短路径上的节点，一直增加到m0（m0>=m）个节点为止。按照现有的公交网络的拓扑结构，设置着m0个节点之间的连边，构成初始网络。
    (2)增长：随机选取未被加入并与已有站点在路网上相邻的节点作为网络新增节点Ni。
    (3)连接：根据单条公交线路最大，最小出行距离以及新增节点Ni距离公交起终点的最大，最小距离，确定新增节点Ni可能到达的所有公交站点，构成新增节点的局域世界LW。新增节点在其局域世界LW中根据有限连接概率来选择节点Nj。新增节点Ni与Nj之间的最短路上任意两节点无边连接，则用边连接，并计为随新增节点增加的边。在LW中选择多个节点，直至增加了m条边或者局域世界LW中所有节点已经全部都被连接为止。
    由以上建立过程可以看出，公共交通网络是在不断地改变，不断地进行演化的。
    单单一个仅仅由公交车组成的小型交通系统便是十分庞大，不断在变化。而囊括所有交通方式的交通网络的庞杂程度更是难以想象的。这一个网络，即是在不断地演化和改变的。通信网络，互联网等网络也是不断在演化地。

    网络的演化与我们每个人息息相关，我们的身边每时每刻都存在着网络的演化，甚至可以说我们每个人都是网络演化的诱因的推动力。网络的演化繁杂且奇妙，我们对与演化网络的研究还要一直地持续下去。

## 参考文献
刘锐,严宝杰,黄志鹏.公共交通的局域世界演化网络模型[J]. 公路交通科技, 2010(03):112-117.