复杂网络基础

觉得最近应该把复杂网络的基础知识捡一捡，去年上课虽然学过，不过基本都忘了，什么betweeness，都不知道是什么了。最近要做复杂网络方面的研究，这些知识是必需的。打算看一下Newman的书”Networks an Introduction”。

为什么我们对复杂网络感兴趣？

很多系统都是由网络组成的。因特网，人类社会都是。有人研究个体组成，即顶点的性质，有人研究关系，即连接，还有人研究这些系统，也就是components和connections之间的pattern。

特殊的模式会在系统中产生很大影响。除非我们知道网络结构，否则很难完全理解整个系统如何工作。

网络是对一个系统的简单表示，只有基本的连接模式和其他的一点东西。顶点和边可以标记上额外的信息，来详细描述这个系统，但是在表示网络的时候通常会丢失信息。这就是它的缺点，但是也有优点。

这些年来，科学家们使用数学、计算机、统计学方法对复杂网络进行分析、建模、理解。很多工具从一个简单的网络表示开始，一组顶点和边，在适当的计算后会得到一些有用的信息：比如哪个是最好的顶点，或是一个顶点到另一个顶点的路径长度。其他工具使用可以做预测的网络的形式，比如互联网流量或传染病在社区内扩散的途径。因为这些工具是在抽象形式下工作，所以理论上可以应用到任何可以表示成网络的系统上。因此如果你感兴趣的系统可以表示成网络，那就有很多工具可以使用。当然不是所有的工具都能给出有效的结果，有些方法是用在特定问题上的。但是如果你有一个关于网络的well-posed question，大多数型框架，还是有一个可以解决这个问题的工具的。

一些网络的例子

最出名的且广泛研究的网络之一就是好论文。计算机组成的网络，计算机是顶点，物理数据连接是边，如光纤或电话线。图1.1展示了互联网的结构，2003年的一个snapshot，通过数据包的流通构建的网络。尽管互联网是人工制造的，而且是很细致的工程，但是我们并不知道它的结构是什么，因为它是由很多不同的人群构建出来的，大家并不了解其他人的行动，很少有中央控制。

有很多令人激动的实用原因让我们想研究因特网的结构。因特网的功能是在不同地方的计算机之间传播数据，他们会将数据分成片或包，然后再网络中的顶点间传送，直到这些包到达他们的目的地。网络的结构会影响他们完成这些任务的效率，而且如果我们直到网络的结构，我们可以解决很多实际问题。我们应该选择哪个路由来传输数据？最短路径总是最快的吗？如果不是，怎么才能找到最快的？我们怎么避免bottleneck使流量阻塞？当一个顶点或一条边挂掉时会发生什么？等等问题。

因特网结构的知识在研发新的通讯标准中是至关重要的。新的标准和协议还是为因特网所设计，老的会被翻新。协议的参数会为了网络的结构而优化。在网络的早些时候，不是网络结构的主要模型在调整过程中使用，而是那些更好的结构数据变得可获得后，我们可以更好的理解这些数据并且提升模型的性能。