Evaluation in Network

网络是在变化之中的，每一天的网络都会呈现出不同的形态，如果说我们之前的研究是关于网络在一个静态的具体的性质，那么现在我们就要看看网络在动态的变化的过程之中会有什么样的表现。

比如说上图就是苹果这些年来的供应商的网络变化图。

那么对于网络的变化我们可以从三个不同的层次对于其进行审视，分别是Marco,Meso,Mirco的层次，其中Marco也就是宏观的层次，比如说网络的形状的变化以及他们的Densification的变化，所谓的Densification也就是网络的连接的强弱。Meso的层次就是网络之中的Motifs以及Communities的变化的情况，而 Mirco就更加低Level了，也就是说网络之中的节点的数量，或者是说link的性质比如说那些(Degree ,Network Centrality)的这类的性质。

那么我们就从三个不同的层次来分别的看

Marco Evolution of Network

如果将$N(t)$表示为在时间$t$的节点的数量，而以$E(t)$表示边的数量。有一个问题就是如果节点的数量翻倍的话，边的数量会怎么变化的呢？

事实上的边的数量和节点的数量是服从一个指数的分布的，即

$$E(t) \propto N(t)^{\alpha}$$

或者说

$$\frac{\log (E(t))}{\log N(t)} = C$$

也就是说平均的Degree是增加的，这也就意味着边的数量会远远快于节点的增加的数量。

如果将网络之中的Diameter也就是最长的最短路径作为衡量网络之中的节点的连接的紧密的程度的标准的话，可以发现其有如下的性质

也就是减小的趋势，为什么会有这样的一个趋势呢？难道一个随机的图都会产生这样的结果吗？通过Simulation的结果可以看出来其实并不是这样的

根据我们的Simulation的结果，可以发现，其中的Diameter是随着网络的增加而不断的增加的，这就与我们的真实的情况并不符合了，那么我们就需要考虑在这里是不是出现了其他的干扰因素，所以我们假设随机的生成的图的Degree的分布和真实的分布是一样的，所以按照相同的Degree Distribution所生成的图的Diameter的分布

就可以拟合成功了。那么可以看出来所有的问题的关键都是在这个Degree的上面，假设Degree是按照$\gamma$指数级别增长，那么上面的$\alpha = 2/\gamma$.

或者$\gamma_{t}$随着Graph的size的大小$n$增加

令
$$\gamma_{t} = \frac{4 n_{t}^{x-1} -1 }{2 n_{t}^{x-1} -1 }$$

其中的$x = a$ . 可以发现随着网络无限的增加，$\gamma$也趋向于2，也就是说网络会倾向于Full Conneted

也可以拟合真实的数据的趋势。

那么我们该如何模拟网络增加的过程呢？之前的随机图的生成的过程非常的限制，因为他需要知道Degree的分布或者是已经有一个图，但是很多时候对于我们来说，这个东西是缺乏的，所以使用一个新的算法，也被称作是Forest Fire Model.

其基本的思想是在Party上面交友的过程，一个新人来到一个新的Party上面，他如果要更好的融入之中，则需要有人给他引荐其他的人。他遇见了新的朋友，新的朋友又介绍给新的朋友，就像是森林大火的燃烧的过程。

介绍的过程符合几何分布，这里有两个几何分布，分别记作是Forward Burning 以及Backward Burning.每有一个新的节点加入的话，通过从这两个分布之中进行采样，得到了两个值$x,y$，他的介绍人记作是$w$，从$w$的Out Edge之中选择$x$个，而从$w$的In Edge之中选择$y$个，这些都是要即将被点燃的。

Micro Evolution of Networks

Temporal Network

Temporal Network指的是一序列的静态的基于固定节点的有向图。而Temporal Edge与普通的Edge相比，多出了一个Time Stamp，也就是指明这个Edge是在什么时间点被成功的连接的。

可以发现在每一个条边上都有一个时间戳，代表着这个边在哪些时间点上是存在的。

Micro Evolution

现在可以看看网络在微观层面的变化了，首先给一个概念叫做Temporal Path，这个概念非常的……非常的抽象，自己理解也花费了一段时间，

我们在正常的图之中Walk的方式是在某一个时间点上的Path，但是在Temporal则不固定于某一个时间点，而是可以跨越时间点。什么意思呢？比如上面的这种图，如果想要从5 到3 似乎不可能，因为在任意的时间戳上，5和3都并没有直接或者是间接的联系。但是如果是在Temporal的层面上，5和3是可以产生联系的，在第一个时间步$t_1$时，5先跑到2上，而在第二个时间$t_2$上，从2再跑到3上。就达成了从5到3的目的了。这就是Temporal Path的概念，但是需要注意的是，这里不能够回到之前走过的节点，有点好马不吃回头草的意思。与普通的类似，我们这里也有一个概念叫做是Shortest Path，不过是也是在Temporal的层面的。寻找Shortest的Temporal path的算法叫做是TPSP – Dijkstra算法，大家有兴趣可以看看，这里我就不赘述了。

有了最短路径的概念，我们当然是要使用整个概念，而路径最经典的应用场景就是计算网络之中各个点之间的联系的强弱。而这里就有一个概念叫做Temporal Closeness,其所表明的的是对于点$x$而言，其与周围的$y$的联系有多紧密，记作

$$c_{clos}(x,t) = \frac{1}{\sum_{y} d(y,x|t) }$$

需要注意的是这里的Given t ，并不是指在这个某一个特定的时间点的距离，而是在从0到t这一个时间段内的最短的路径，下面给一个例子

A在时间2的Temporal Closeness，由于A与B在时间1上的最短的距离是1，所以可以是1，而A与C在时间2上的最短的距离是1，所以也可以是1，而与D而言，其最短的距离是在时间2上产生，也有两个距离，所以记作是2.同理类推。

那么求值越大，是不是说明其在网络之中就越重要呢？而想到重要，这个是一个相对的概念，所以我们是不是又要进行排序了，而对于网络之中的节点排序，有什么算法呢？当然是谷歌的最经典的PageRank算法，只不过我们现在是要把它拓展到Temporal的层面了。

所以我们给出一个Temporal Walk的概念，与Temporal Path的概念的唯一的不同点就在于其允许吃回头草。

对于上面的这张图来说。cbac是允许的，因为在2从c到b，在7从b到a，在9从a到c，也就Walk完毕，但是acba则不被允许，因为要从a到c必须等到时间9，但是c到b仅仅是时间2，在那时候已经无法从c转移到b来，这张旧船票再也登不上b的客船。

而还有一个问题就是，这个转移的成功的概率应该是会随着时间腐朽的，什么意思，可以看成是由于我们在某一个时间点等待的过久，对于这个时间点也就更加的“留恋”，不愿意走了，那么我们就加上一个“留恋系数”。我们要做的事情是，将不同的时间点的Graph都连接成为一个Time – Extended的图，怎么连接呢？就是直接连接

文中使用$A$以及$E$进行举例，对于$A$来说，在时间1上连接了$B$，时间2连接了$C$，时间3连接了$B$，所以全部用箭头连接起来。对于$E$也是同样的操作。

那么就可以得到PageRank了

$$r(u,t) = \sum_{v\in V} \sum_{k=0}^{t} (1 – \alpha)\alpha^{k} \sum_{z\in Z(v,u|t)} p[z|t]$$

其中的$Z(v,u|t)$代表从$v$到$u$的所有的可能的Temporal Walks,而$\alpha$则代表随机跳转的概率。

具体的运行的算法我贴在上面了。对于某个任意的节点，给定其Temporal Edge以及转移的概率$\beta \in (0,1]$还有开始一个随机的Walk的概率$\alpha$.首先把重要性设置为0，有效的Walk的数量也记作是0。对于在Temporal Edge之中的每一个元素，对于$r(u)$进行更近，并且最后得到真正的PageRanking.

Meso Evolution of Network

将Node的数量记做是$k$，将Edge的数量记做是$l$,将Temporal Motif的数量记作是$\delta$,

Temporal Motif不单单有结构的因素，还有时间的因素，比如先到某个点，再到某个点，比如上面的Motif B就是先从绿到红，再从绿到紫，再从紫到绿的这样的一个规律，放在原来的Temporal Graph之中就是

上面的这些都是原图的Induced Graph.通过这样的方式我们就可以找到网络之中的Motif的变动的情况，并可以得到网络之中的这些Motif的变换的情况以及规律。