复杂网络综述1——简介
本文基于Mark Newman2003发表的论文—— 《The Structure and Function of Complex Networks》
网络在现实生活中无处不在,例如因特网,社交网络和生物网络。多年来,研究者们不断努力,研究出了一些技术和模型来帮助我们理解和预测这类复杂系统中的行为模式,像小世界效应、度分布、聚类、网络相关性、随机图模型、网络的生长和偏好连接模型,当然还有更重要的网络动力学模型。
网络,是由一些节点和节点之间的连边组成的。数学上,网络也被叫做“图”,图论是离散数学中最重要的支柱。大数学家欧拉在1735年对哥尼斯堡七桥问题的证明被认为是图论研究的起源,在二十世纪,图论已经发展成了一门重要的学科。网络在社会科学中也被广泛研究,早在二十世纪三十年代,社会学家就已经认识到人们之间连接模式对理解人类社会功能的重要性。典型的社会网络研究包括通过调查问卷的方式了解受访者与他人的联系,这样就可以通过反馈来构建一个网络,网络的节点代表个体,连边代表个体之间的联系。这类研究强调中心性(某些个体有着很强的影响力)和连接性(个体是如何通过网络相连的)。接下来的几十年中,大量的研究从分析单个的小规模网络和网络中节点和连边的特点转移到分析大规模网络
的统计特性。计算机和通信网络的普及促进了新方法的形成,使得在比以往更大规模的网络上收集和分析数据成为可能。这种规模上的改变导致了在分析方法上相应的改变,许多问题在大规模的网络上不再适用。例如,在一个社交网络分析中,你也许会问:“对于网络的连通性,网络中的哪个节点会是最关键的?如果它被移除之后,网络变得不再连通”,但是这个问题在拥有几百万个节点的网络中变得不再有意义,因为在这样的网络中,没有哪个节点会有这样的影响力。另一方面,你也可能会问,“在某种条件下,需要移除多大比例的节点会影响到网络的连通性?”,这类问题在大规模网络中有真正的意义。
然而,近年来有关研究方法的改变还有一个十分重要的原因,尽管它的重要性经常被低估。对于一个只有几十个或者几百个节点的网络,最直接的方法就是将点和边画成一张图,通过这张图来分析网络结构和一些特性。在之前,这是网络分析的主要方法,因为人的眼睛本身就是一个强大的分析工具。但是,当网络中的节点有百万个甚至上亿个时,人的眼睛就无法直接从图中直接分析出网络结构了。最近形成的量化大规模网络的统计方法是找到一种可以在网络分析中代替人的眼睛的工具,就像二十世纪时那样。这种统计方法回答了在无法真正看到网络时,如何描述这个网络看起来像什么”的问题。它试图解决三件事:第一,找出可以刻画网络系统中结构和行为的统计特性,例如路径长度和度分布,并且给出衡量这些统计特性正确的方法;第二,构建网络模型以便帮助我们理解这些统计特性背后的真正意义——它们是如何形成现在的样子的以及它们之间是交互的;第三,基于这些统计特性,预测网络系统将要表现出的行为和个体的局部规则,例如,网络结构是如何影响因特网上的流量、搜索引擎的性能,或者是如何影响社会或生物网络上的动力学演变的。学术界从大量的学科中汲取精华,在前两个目标(刻画网络结构并对其建模)中已经取得巨大的进展,但是在研究网络结构的影响方面才刚刚开始。
由一些点和它们之间的连边组成的网络是一种最简单的网络,然而还有一些网络要比这复杂一些。例如,在网络中存在不止一种类型的节点,或者多种类型的连边,并且节点和连边有着各自的特性。以社交网络为例,节点可能代表男性,也可能代表女性,又或者是不同国家、不同地域、不同年龄、不同收入的人。连边可能代表朋友关系,也可能是敌对关系,或者仅仅是地理位置离得近。连边上可以有权重,表示两个人的熟悉程度。连边也可以是有向的,从一个点指向另一个点,由有向边组成的图称为有向图,通信网络可以看成是一个有向图,因为信息只能单向流动。有向图可以是循环的,意味着图中包含一个闭圈。
网络中也可以包含超边——一条边可以连接任意数量的顶点。由超边组成的图称为超图。例如,超边可以用来表示社会网络中的家庭关系纽带。图也可以用多种方式来划分,例如二分图,它包括两种类型的节点,只在这两种不同类型的节点间才存在连边。最简单的例子就是天猫上的用户可以看成一类节点,商品看成另一类节点,那么用户购买商品的网络就是一个二分图。