论文部分内容阅读
网络世界已经成为信息时代生活中不可缺少的一部分。然而，近年来国内外发生的一系列重大网络事件，比如，2000年5月4日，“爱虫”病毒在互联网上大肆传播，一天之内造成全球经济损失十多亿美元，而且现在还在肆虐。还有2003年8月18日北美突然大停电，就是复杂电力网络的一系列级联反应，导致整个电力系统土崩瓦解。国内外电力网络的数据分析表明,这种灾变与网络的性质有关，涉及到网络本身结构和功能缺陷等内在因素，但是最终原因尚无定论，各种复杂网络的一系列谜团急待解开。
科学家为了寻找应对新挑战的办法，积极探索如何利用高科技的成果进一步推动复杂网络的基础研究，试图解开复杂系统的“庐山真面目”。1998年以来，科学家终于冲破了从20世纪60年代开始占据了40年之久的随机网络理论的禁锢，取得了突破性进展，复杂网络的一个个谜团开始露出端倪。尤其引人关注的是三项重要的发现：小世界效应、无标度特性和超家族特性，由此揭开了一门新学科——“网络科学”的诞生。
“海内存知己，天涯若比邻”
——小世界效应
复杂网络的重要发现之一是小世界效应或称小世界现象。历史上，这个现象源于1967年美国社会学家米尔格朗提出一个大胆的假设：“六度分离概念”。迄今这个理论尚未被严格证明。1998年瓦茨和斯托盖兹在复杂网络研究中重新发现并拓广了小世界效应，其论文发表在英国《自然》杂志上，这才引起了全世界的广泛兴趣和关注。实际上，小世界现象到处可见，大家都有这样的体会，与一些新朋友交谈时，很快就能发现：他认识你的朋友，你认识他的朋友的朋友。于是大家不约而同地脱口而出：这个世界真小啊！这里包含了“六度分离概念”的基本思想，它原意是指在美国大多数人中，任意两个人平均最多通过6个人就能够彼此认识。2003年瓦茨领导的研究小组在《科学》杂志发表题为“六封电邮环游地球”的报告，他们利用互联网在全世界范围内初步检验了上述惊人的假说，这是利用互联网初步验证了小世界现象。但是参与这个试验的人数还不够多，他们准备做上亿人参加的互联网进一步试验。试想，这个小世界现象与我国名诗“海内存知己，天涯若比邻”，何其相似。
那么，从新兴的网络科学如何来表征小世界效应呢？首先，这里介绍两个主要概念。一是网络的平均距离L，通常网络中的两个结点可以通过一些首尾相连的边连接起来，把连接它们所需要的最少的边的数目称为它们之间的距离。不难知道，这两个点之间的距离总是比网络拥有的结点总数要小。对所有节点对的距离的平均值，就是网络的平均距离；二是网络的群聚（团簇）系数C，用来衡量结点集聚成团的程度。对于某个结点，它的群聚系数C定义为:它所有相邻结点之间连边的数目与可能的最大连边数目之比。类似地，网络的群聚系数则是所有结点群聚系数的平均值。研究表明，规则网络具有大C和大L，随机网络则具有小C和小L。1998年，物理学家瓦茨和斯托盖兹提出小世界模型，通过以某个很小的概率切断规则网络中原始的边，并随机选择新的端点重新连接，构造出了一种介于规则网络和随机网络之间的网络，它同时具有大C和小L，称为具有小世界效应的小世界网络。
小世界效应的特点除了是具有小的平均距离外，还有另一种表现是，实际网络通常具有大的群聚系数，意思是说，一个人有很大的可能性认识他的朋友的朋友。小世界效应在许多真实网络中得到了实证，例如在计算机互联网、万维网、食物链网络、电力网络、好莱坞的演员关系网、科学家合作网络等等都有表现。
“江流天地外，山色有无中”
——无标度特性
复杂网络的重要发现之二是，无标度特性。1999年巴罗巴斯和阿尔伯特在《科学》上发表文章指出，许多实际的复杂网络的结点度分布具有幂律函数形式,由于幂律分布没有明显的特征长度，故称这种结点度的幂律分布为无标度特性，称该类网络为无标度网络。无标度网络生成主要依靠两个规则：一是网络大小随时间一步步不断生长，即结点不断增加，规模不断扩大；二是对网络中凡是结点度高的结点具有优先连接倾向。
在无标度网络中，有些集散结点甚至具有数不清的连结，而且不存在代表性的结点。这种网络具有可预期的行为特性。例如，对意外故障具有惊人的承受力，但面对协同式攻击时则很脆弱。这些发现大大地提高了人们对复杂外部世界的认识。集散结点的存在使我们认识到前未涉及的一些重要问题和启示：各种复杂系统可能存在某些相同的基本的法则，并可能适用于不同网络，包括细胞、计算机、语言和社会等完全不同的领域。显然，深入认识和运用这些法则，必将有助于解决复杂网络提出的一系列问题，具有应用潜力，如可以利用来开发更好的药物，防止黑客侵入互联网、消除电力网灾变和阻止致命流行病的传播等等。因此，上述研究具有现实意义。
“山外青山楼外楼”
——超家族特性
复杂网络第三个值得关注的有趣特征是超家族特性。2004年西弗等人在《科学》上发表文章，比较了许多已有网络的局部结构和拓扑特性,分析观察到了有一些不同类型的网络的特性在一定条件下具有相似性并提出了一种方法研究了不同网络局部结构的相似性。他们观察到属于完全无关的网络却具有类似的“重大轮廓外形”特征，例如3种不同万维网、3种不同社会网和5种不同语言网络都具有相似的三角“重大轮廓外形”。这种现象被他们称为超家族特性。顾名思义，不同网络之间存在“血缘”联系，出现某些网络家族的相似特性，来源于它们的相同或相似的网络“基因”，问题是网络“基因”是不是找准了？是否存在网络“基因”排序等更深层次的问题？国际上对此方法和研究结果持比较谨慎的态度，也存在一定的异义。有人认为西弗等人讨论的超家族及基本方法在识别网络演化设计原理中受到限制，例如在神经网络，复杂生态食物链网络等中就不能使用。因此需要更多的不同网络的实证研究和严格的理论证明。
世界的复杂性，自然形成了网络的多样性，既有天然的网络，又有人造的网络，既有物理网络，又有技术网络，还有固定规则网络，时空演化增长网络，无向网络，有向网络等等。形形色色的网络模型和实证研究应运而生，以完善和发展现有的复杂网络研究，更真实地刻画实际网络特性，包括产生小世界效应和无标度特性等不同拓扑特性的许多模型。迄今复杂网络的发现只是揭示了冰山一角。网络科学面临许多挑战性课题。正如20世纪美国最有影响的五十人物之一E.O.威尔逊指出：“今天最大的挑战性，不仅是细胞生物学和生态学，而是科学的所有方面，特别是如何精确地和完全地描述复杂系统。科学家已经认识了许多类型的复杂系统。他们已经知道系统中大多数元素和受力情况，下一步的任务就是怎么组装起来。”
【责任编辑】庞云
科学家为了寻找应对新挑战的办法，积极探索如何利用高科技的成果进一步推动复杂网络的基础研究，试图解开复杂系统的“庐山真面目”。1998年以来，科学家终于冲破了从20世纪60年代开始占据了40年之久的随机网络理论的禁锢，取得了突破性进展，复杂网络的一个个谜团开始露出端倪。尤其引人关注的是三项重要的发现：小世界效应、无标度特性和超家族特性，由此揭开了一门新学科——“网络科学”的诞生。
“海内存知己，天涯若比邻”
——小世界效应
复杂网络的重要发现之一是小世界效应或称小世界现象。历史上，这个现象源于1967年美国社会学家米尔格朗提出一个大胆的假设：“六度分离概念”。迄今这个理论尚未被严格证明。1998年瓦茨和斯托盖兹在复杂网络研究中重新发现并拓广了小世界效应，其论文发表在英国《自然》杂志上，这才引起了全世界的广泛兴趣和关注。实际上，小世界现象到处可见，大家都有这样的体会，与一些新朋友交谈时，很快就能发现：他认识你的朋友，你认识他的朋友的朋友。于是大家不约而同地脱口而出：这个世界真小啊！这里包含了“六度分离概念”的基本思想，它原意是指在美国大多数人中，任意两个人平均最多通过6个人就能够彼此认识。2003年瓦茨领导的研究小组在《科学》杂志发表题为“六封电邮环游地球”的报告，他们利用互联网在全世界范围内初步检验了上述惊人的假说，这是利用互联网初步验证了小世界现象。但是参与这个试验的人数还不够多，他们准备做上亿人参加的互联网进一步试验。试想，这个小世界现象与我国名诗“海内存知己，天涯若比邻”，何其相似。
那么，从新兴的网络科学如何来表征小世界效应呢？首先，这里介绍两个主要概念。一是网络的平均距离L，通常网络中的两个结点可以通过一些首尾相连的边连接起来，把连接它们所需要的最少的边的数目称为它们之间的距离。不难知道，这两个点之间的距离总是比网络拥有的结点总数要小。对所有节点对的距离的平均值，就是网络的平均距离；二是网络的群聚（团簇）系数C，用来衡量结点集聚成团的程度。对于某个结点，它的群聚系数C定义为:它所有相邻结点之间连边的数目与可能的最大连边数目之比。类似地，网络的群聚系数则是所有结点群聚系数的平均值。研究表明，规则网络具有大C和大L，随机网络则具有小C和小L。1998年，物理学家瓦茨和斯托盖兹提出小世界模型，通过以某个很小的概率切断规则网络中原始的边，并随机选择新的端点重新连接，构造出了一种介于规则网络和随机网络之间的网络，它同时具有大C和小L，称为具有小世界效应的小世界网络。
小世界效应的特点除了是具有小的平均距离外，还有另一种表现是，实际网络通常具有大的群聚系数，意思是说，一个人有很大的可能性认识他的朋友的朋友。小世界效应在许多真实网络中得到了实证，例如在计算机互联网、万维网、食物链网络、电力网络、好莱坞的演员关系网、科学家合作网络等等都有表现。
“江流天地外，山色有无中”
——无标度特性
复杂网络的重要发现之二是，无标度特性。1999年巴罗巴斯和阿尔伯特在《科学》上发表文章指出，许多实际的复杂网络的结点度分布具有幂律函数形式,由于幂律分布没有明显的特征长度，故称这种结点度的幂律分布为无标度特性，称该类网络为无标度网络。无标度网络生成主要依靠两个规则：一是网络大小随时间一步步不断生长，即结点不断增加，规模不断扩大；二是对网络中凡是结点度高的结点具有优先连接倾向。
在无标度网络中，有些集散结点甚至具有数不清的连结，而且不存在代表性的结点。这种网络具有可预期的行为特性。例如，对意外故障具有惊人的承受力，但面对协同式攻击时则很脆弱。这些发现大大地提高了人们对复杂外部世界的认识。集散结点的存在使我们认识到前未涉及的一些重要问题和启示：各种复杂系统可能存在某些相同的基本的法则，并可能适用于不同网络，包括细胞、计算机、语言和社会等完全不同的领域。显然，深入认识和运用这些法则，必将有助于解决复杂网络提出的一系列问题，具有应用潜力，如可以利用来开发更好的药物，防止黑客侵入互联网、消除电力网灾变和阻止致命流行病的传播等等。因此，上述研究具有现实意义。
“山外青山楼外楼”
——超家族特性
复杂网络第三个值得关注的有趣特征是超家族特性。2004年西弗等人在《科学》上发表文章，比较了许多已有网络的局部结构和拓扑特性,分析观察到了有一些不同类型的网络的特性在一定条件下具有相似性并提出了一种方法研究了不同网络局部结构的相似性。他们观察到属于完全无关的网络却具有类似的“重大轮廓外形”特征，例如3种不同万维网、3种不同社会网和5种不同语言网络都具有相似的三角“重大轮廓外形”。这种现象被他们称为超家族特性。顾名思义，不同网络之间存在“血缘”联系，出现某些网络家族的相似特性，来源于它们的相同或相似的网络“基因”，问题是网络“基因”是不是找准了？是否存在网络“基因”排序等更深层次的问题？国际上对此方法和研究结果持比较谨慎的态度，也存在一定的异义。有人认为西弗等人讨论的超家族及基本方法在识别网络演化设计原理中受到限制，例如在神经网络，复杂生态食物链网络等中就不能使用。因此需要更多的不同网络的实证研究和严格的理论证明。
世界的复杂性，自然形成了网络的多样性，既有天然的网络，又有人造的网络，既有物理网络，又有技术网络，还有固定规则网络，时空演化增长网络，无向网络，有向网络等等。形形色色的网络模型和实证研究应运而生，以完善和发展现有的复杂网络研究，更真实地刻画实际网络特性，包括产生小世界效应和无标度特性等不同拓扑特性的许多模型。迄今复杂网络的发现只是揭示了冰山一角。网络科学面临许多挑战性课题。正如20世纪美国最有影响的五十人物之一E.O.威尔逊指出：“今天最大的挑战性，不仅是细胞生物学和生态学，而是科学的所有方面，特别是如何精确地和完全地描述复杂系统。科学家已经认识了许多类型的复杂系统。他们已经知道系统中大多数元素和受力情况，下一步的任务就是怎么组装起来。”
【责任编辑】庞云