1、I目录复杂系统：网络思维 .11 引言 .12 复杂系统 .23 网络 .23.1 网络实例与关于网络的问题 .33.2 网络模型 .34 网络特性的应用 .74.1 在网络中的搜索 .84.2 在网络中寻找社区的结构 .95 元胞自动机计算 .106 自然复杂系统中自适应信息的处理 .146.1 在免疫系统中通过亲和力成熟和扩散反馈进行自适应信息处理 .146.2 蚁群中的觅食和任务分配 .166.3 生物细胞的新陈代谢 .177 非集中式系统中自适应信息处理的四条原则 .177.1 全局信息被解释成涵盖整个系统成分的统计学模式和动力学模式 .187.2 随机性和或然性是本质的 .187.3
2、 系统采用一种细粒度的、并行的、可能性搜索 .187.4 系统展现出连续的自底向上和自顶向下处理的相互作用 .198 结论：人工智能相关方面 .20致谢 .201复杂系统：网络思维Melanie Mitchell波特兰州立大学和圣菲研究院（发表于 人工智能 ）我确信能够掌握复杂性新科学的国家及人们将成为下个世纪经济、文化、政治上的超级大国。Heinz Pagels50当我听到“复杂性”这个词的时候，我顿时感到很困惑，但是我怀疑是我的眼界狭窄。它有着魔咒般危险的诱惑，预示着将会获得如同生物学中“适者生存”一样令人愉悦的解释。Philip Ball1 引言如同早期的人工智能，在最近的二十年中，复杂
3、系统领域受到诸多压力，有肯定的、也有否定的、有轻描淡写夸大的、也有不公平的恶意中伤的。与早期人工智能一样，复杂系统科学家们经常承诺并且提出对任何年轻的科学都难以实现的期望。 “复杂性规律自然地造成自然界的无序28” ，这是真的么？简单的程序可以产生非常复杂的行为真的是 “在整个理论科学史上的一个非常重要的发现”66？另一方面，一个知名的科学杂志，在它封面上提出复杂性科学是否是一个“骗局” ，而这又是公平的吗？尽管有着夸大和诽谤，但是在过去的几年中，还是发现复杂系统中一些很有趣的、有价值的工作被完成，这些工作不仅体现在许多书籍、杂志、会议甚至整个学院都致力于该领域的研究，同时它体现在那些正在研究
4、科学、医药、经济、商业、甚至于自然界和人工系统智能中的人们所看到的真实变化。作为一个有效的科学行为，复杂系统的计算机建模被广泛的采用。在复杂系统思想中重要的“系统生物学” ，已经成为人类基因图谱计划时代的一个关键词语。现在，寻找控制复杂网络的一般规律成为从探索工具到社会学范围内各领域的一个中心事项。在本文中，我讨论了几个网络话题上的复杂系统的最新观点，这些观点都是源于最近三本复杂系统的书籍，它们似乎与从事 AI 研究的人们有显著的关系。网络的一般性科学是Albert-Barabasi 的连接2和 Duncan Watts 的六度分离63的主题。复杂生物网络（如免疫系统、群居昆虫、和细胞新陈代谢
5、）的共性以及它们与计算机系统的智能关系问题，在关于“分布式自治系统”的跨学科会议上研究过。第三本书中的观点使我提出在分布式系统中自适应信息处理的四个通用规则。这些规则和与 AI 的“ 网络思维”的相关性（反之亦然） ，是本文后两节的主要内容。22 复杂系统在自然界和社会中，复杂系统的经常引用的例子包括人脑、免疫系统、生物细胞、新陈代谢网络、蚁群、因特网与万维网、经济市场和人际社会网络。“复杂系统”没有一个公认的标准定义。非正式的认为，复杂系统是由相对简单成分组成的一个巨大的网络，它没有控制中心，可以涌现各种复杂的行为。当然，定义中的术语也不是被严格定义的。 “相关的简单成分”是指个体成分，或者
6、至少是那些在系统集体行为中所起到的作用相对与集体行为来说是简单的成分。例如，一个单独的神经元或者一只单独的蚂蚁本身是一个复杂的实体，然而，与整个系统的行为相比较，这些单独实体的功能在整个大脑或整个蚁群中的功能性作用又是相对简单的。“涌现复杂行为”就更加难以定义。大致上，涌现的概念指：系统的整体行为不仅是复杂的，也是从简单成分的集体行为中产生的，并且这种从个体行为到集体行为的映射并不是微不足道的。在这里非线性的概念是很重要的：整体大于局部之和。一般来讲，系统整体行为的复杂性是以下三个方面为特征的：组成模式、所完成的信息处理、模式结构和信息处理对系统的适应度，即在一些进化或竞争的情况下，提高其成功
7、的能力。为了特征化表示这些行为，复杂系统科学家使用了不同学科的工具，包括非线性动力学、信息论、计算理论、行为心理学和进化生物学，等等。复杂系统领域探求解释和揭开在交叉学科的复杂系统中涌现和自组织行为的一般规律。许多科学家也相信此通用法则的发现对于创造人工生命和人工智能也是必不可少的。顾名思义，复杂系统一般是难以理解的。传统上，越是面向数学的科学，例如物理、化学以及数学生物学，越能集中出更简单的模型系统，这种系统可以通过数学的手段更易于处理。对理解复杂系统的通用特性方面的关注，随着计算机技术的发展而提高，因为计算机在人类历史上第一次使为自然界中的复杂系统建立精确模型变为可能。3 网络近年来，很多
8、学科中都涌起一股研究网络的热潮，这些学科涉及从计算机科学和通信到社会学和流行病学。网络的数学研究起源于图论，它是一门非常早的学科，可以追溯到十八世纪欧拉对著名的“哥尼斯堡七桥”问题。在上世纪五十年代，Erodos 和 Renyi 在随机图论上做了许多有影响力的工作。然而，直到近期，数学图论也没有对真实世界网络研究中产生巨大的影响，因为后者的特性与随机图的特性相差甚远。相当一部分社会学家也研究了社会网络很长时间。在最近十年左右，一些应用数学家和物理学家也加入其中，开发网络的基本理论。最近两本描写这方面工作的书有：Duncan Watts 的六度分离：一个连接时代的科学 63，Albert-Laz
9、lo Barabasi 的连接：网络的新科学2 。这两本书都适合于“非专业性的读者” 。与此同时，Mark Newman，Watts 和 Barabasi 一起编辑了一本网络理论方面：3网络的结构和动力学方面近期论文的更为专业性的收集46。本节和下面的两部分中，我描述了许多近期在网络上的发现，这些可能对从事 AI 的研究者来说很感兴趣。3.1 网络实例与关于网络的问题一个网络（或图）是节点（顶点）和节点之间连接（边）的简单集合。连接可以是有向的或者无向的，加权的或不加权的。许多可能是大部分自然现象可以用网络术语进行有效描述。大脑是一个由神经键连接的巨大的神经元网络。在一个细胞中，基因行为的控制
10、是由调节蛋白连接的基因复杂网络控制。社会团体，是节点人为节点的（或由人组成的组织）的网络，它们之间有许多可能不同关系类型。因特网和万维网理所当然是当今社会两个非常显著的网络。在国家安全的领域内，已经投入非常大的精力来鉴别和分析所有可能存在的“恐怖分子网络” 。所有的这些课题都被研究过一段时间，但是直到近期，网络研究才普遍的成为复杂系统研究的一个主要课题。原因之一在于高速计算机，从经验上使研究真实网络变为可能， ，同时对这个领域关注的增加也得益于为了应用其强大的分析技术而注意其它领域的物理学家们。正如 Watts 指出：“受到这个新问题的激励，如饥似渴的物理学家是如此狂热而又数量众多，这是其他领
11、域的科学家所无法比拟的” 63。 下面是网络科学家们致力于解决的一些问题： 哪种拓扑度量可以被用来特征化网络的特性？ 哪些特性是真实世界网络中不同的集合之间共享的？为什么？这些特性如何产生的呢？ 如何设计有效的算法来确定这些特性？ 这些特性是如何影响信息（或者疾病、或者其他的通信）在网络上的传播动态，以及网络抗噪音、成分故障或蓄意攻击的能力？ 给定一个具有某些特性的网络，寻找网络特殊节点的最优方法是什么？回答这些问题不仅对我们理解许多自然界和社会系统方面问题影响重大，对我们设计和有效使用复杂网络，包括从优化网络搜索、因特网路由选择，到控制疾病扩散，打击有组织性质的犯罪，阻止人类行为导致生态破坏
12、都有十分深远的影响。3.2 网络模型Watts 和 Barabasi 的书中描述了三个一般网络模型：随机图，小世界网络和无尺度网络。这些模型每个都由网络创建的方式、结果统计量的方式特征化描述，例如度分布、节点对间的平均距离、和聚类度。在下面描述的模型中，假定一个给定的由 n 个节点组成的网络。为了更简化一些，假定连接是无向的、不加权的。两个节点被称为相邻节点当且仅当两节点之间只有一个连边。4节点的度即节点的相邻节点的数目。一个网络的度分布是网络中所有不同度的频率的分布。例如，在图 1 中，标记为 的节点度为 3，网络的度分布图在网络图的旁边。所有1n8 个节点的平均度是 2。图 1.(a)一个
13、网络示例。节点 的度为 3（即与其它节点有 3 个连接） (b)网络的度1n分布随机网络随机网络是通过指定每对节点都以统一的概率 p 连接。Erodos 和 Renyi 是从纯数学的角度去研究这种网络的。在 n 无穷大的时候，随机网络的全体平均特性都能通过分析来表达，这使得随机网络成为一流的数学对象。然而，Erodos-Renyi 的随机图网络的某些关键特性却与大多数真实世界网络所呈现出来的特性很不相同。首先，随机图网络不存在真实世界中节点的强聚类（即密集的相互连接节点的子网） 。相对于一个随机的人，你更可能成为你朋友的朋友的一个朋友，这就产生了聚类。网络的聚类系数是一个给定节点的两个相邻节点
14、同时也互为相邻节点的平均概率。一个随机网络的聚类系数确定为 p。但是，真实世界网络的经验化研究显示真实网络的聚类系数的数量级比具有相同节点和连接的随机图的聚类系数的数量级要高。第二，图中可以显示：随机图网络的度分布近似于高斯分布（当 n 无穷大时，真正为泊松分布） ，这和通常在真实世界网络中观察到的的幂率分布不同。幂率度分布表示为， 是一个节点的度为 的节点的概率， 是一个大于 0 的实数。图 2（左）kP)()(k为 （万维网的近似经验度分布）的理想幂率分布。幂率分布的右侧倾斜：它有一个1.2长的没有转折点（即 达到 0）的右尾巴。作为对比，图 2（右）显示了一个有短尾巴)(kP和明显的转折
15、点的高斯分布。5图 2 左：理想幂率分布 ，在半对数坐标中， 是一个节点的度， 是1.2)(kPk)(kP度为 k 的节点的概率。右：理想高斯分布小世界网络1998 年，Watts 和 Strogatz 提出了他们的小世界模型。为了构建一个小世界网络，从一个类似与“环”格子的细胞原胞自动机开始，其中每个节点与最近的 个邻居节点连接。k对于每个连接，以最小概率 重新和网络中随机选择的节点连接。对于 ，是一个完p 0p全规则网络，对于 ，是一个完全随机网络。对于小但非零的数 ，会产生一个有很1多局部连接和许多“长距离”连接的网络。这种网络具有所谓的“小世界特性”：即使没有远距离连接存在，两个节点之
16、间的最短路径（连接距离的数目）以对数形式表示或者对于固定平均度随着网络大小的改变 n 而变慢。这意味着即使在有许多节点的小世界网络中，两个个体节点之间的最短路径也可能比较小，因此被称为“小世界” 。相反，在一个规则连接网络中，路径长度与网络的大小呈线性关系。Watts 和 Strogatz 发现即使再连接概率 p非常小，小世界特性也会出现。具有非常小但非零概率 的小世界网络同样具有很大的聚类系数。相反，随机网络有p较短的平均路径长度和低的聚类系数。然而，Watts 和 Strogatz 的模型的典型度分布结果却和大多数研究过的真实世界的度分布情况不符。无尺度网络在 Watts 和 Stroga
17、tz 提出他们的小世界网络的同时， Barabasi 和 Albert 也提出了一个可供选择的网络模型，即通过“偏好连接”而产生所谓的无尺度网络。无尺度网络简单的来说是一个具有幂率分布的网络，如图 2（左）所示。注意，图 2（右）所示的高斯分布具有分布趋向 0 的“转折”值。这就给定了一个固有的刻度的分布例如，如果要以成年人的身高和人群中这种身高的频率为横纵坐标进行绘图，可以说，没有人会低于 1 英尺或高于 15 英尺。相反，一个无尺度分布没有转折值；所有标度都有对应实例，因此被称为“无尺度” 。在一个具有高斯度分布的网络中，绝大部分节点有近似相同的连边数目，很少能发现6连边数目与平均值偏离很
18、大的节点。而在无尺度网络中，每个节点的连边数目却有很大的差异。少数节点（“中心节点” ）具有很多连边，而大部分节点只有很少的连边。许多也许是大部分被研究的真实世界网络看起来像是无尺度的；也就是说它们呈幂率分布而不是高斯分布的。这与我们的生活类似：你可能了解，只有很少的一些人有一大群朋友（或合作者，或者是粉丝） ，而更多的人的生活圈子相对小得多。1999 年，Barabasi 和 Albert 提出“偏好依附增长”的机制对无尺度网络经验化的事实进行解释3。那时他们并不知道，他们再次发现了 Simon 和 Price 早期的提议44。简单的说就是“富者越富” 。网络的增长方式与此类似，即度高的节点
19、比度低的节点更可能接收新的连接。直观上讲这个是显而易见的，相比朋友少的人来说，朋友多的人会遇到更多的人，因此会结交更多的朋友。比连接少的网页来说，连接多的网页更容易被找到，所以更多的新网页会被连接到度高的网页上面。Barabasi 和 Albert 提出的网络增长模型如下：网络从少量的初始节点开始，在每一时间阶段，都有一个新的节点被添加，并被连接到 m 个现存的节点上，这里 m 是任意的，在这个过程中，连接到节点 i 上的概率与节点 i 的度成比例。通过对各种真实世界网络研究，包括万维网，因特网，电力网，飞机航班网，科研合作网，生物有机体中的新陈代谢网络，酵母中的蛋白质网络等等，Barabas
20、i、Albert 和其他人发现经验化的度分布可以用幂率分布 很好的表示，其中， 在 2 和 3 之间kP)( （依赖特定的网络） 。Barabasi 和 Albert（效仿 Price 和其它人的早期工作）得到结论： “偏好依附增长”机制是是真实世界网络进化推动者。Barabasi 指出在真实世界中， “能力上的细微差异，甚至是纯粹的随机波动，随着时间推移都可能产生和导致极大的不平衡” 。2上述分析同样显示，无尺度网络也具有小世界特性。因而，一些（不是全部）小世界网络也是无尺度的。表 1 给出上面描述的不同网络模型的网络不同特性的一个定性的总结。表 1 不同网络模型和真实世界网络的经验化结果的
21、定性对比网络模型 度分布 聚类系数 平均路径长度规则网络 常数 高 高随机网络 泊松 低 低Watts-Strogatz 小世界网络（小，非零p）取决于 p 高 低Barabasi-Albert无尺度网络幂率 高 低真实世界网络的经 幂率 高 低7验化结果上面的讨论中隐含着绝大多数网络研究者共同的简化假设。迄今为止，被讨论的模型不考虑在现存的节点中新增和删除的连接。同样，假定连接边上的“权”和使用的连边的类型都没有变化，也没有表示连边强度差异或关联维度，创建连边也没有与代价相关联。此外，假定创建节点连边的概率与其节点的度严格成比例，这也是不切实际的；在真实世界中，所有节点不都相同，内在特性例如
22、“质量”也会变化（例如，也许一些网页被连接是因为它们的高质量，而不只是因为它们已经有了很多的连接） 。但是，如果修改了创建连边与节点的度成正比的这个假定，网络的度分布可能就不再是一个幂率分布了。目前有很多的研究正在探讨如何放宽这类假定，但是令人惊讶的事实却是：即使所有的假设都存在，这些简单的模型似乎已经抓住真实世界网络的某些本质的方面。4 网络特性的应用Watts 和 Barabasi 的书都强调“网络思维”在处理真实世界复杂系统中的重要性。根据度的分布、聚类系数、平均路径长度和相似性将网络特征化描述的目的是为了从科学的角度更好的理解网络并且开发更好的工具来按照预想的那样设计和管理网络。例如：
23、开发更好的方法来设计和注射疫苗与其它药品；能够更好的管理控制流行病；为网络搜索、对等网络、因特网通讯、计算机安全等方面设计高级的网络搜索算法；减轻电力系统故障的影响；帮助发现高度连接的个体子网络，不论是对书有共同爱好的顾客网络还是可能的犯罪组织网络都应该被紧密的监视。Cohen，Havlin 与 ben-Avraham8利用“网络的思维”提出了一个有趣的公众健康策略，即在资源有限的情况下接种疫苗策略：该策略不是随机的给人们接种疫苗，而是首先询问很多人，让每个人说出他一个朋友的名字，然后给那个朋友接种疫苗。在一个有幂率分布和高聚类系数的社会网络里，搜集每个人朋友的名字比随机选择个体接种疫苗，更可
24、能产生网络的中心站（有很多朋友的人） ，给中心站的人接种疫苗比给随机选择的人接种疫苗更可能减少疾病的传播。类似的，药品设计者也许更关注在一个病毒基因排列网络的中心站，把这些中心站作为新药的潜在目标。网络搜索引擎可以通过关注“权威” （被许多其他网页指向的网页）和“中心站” （与许多网页连接的网页）30对网页进行等级分类。更一般的，在预测什么条件下网络对节点或连边的丢失或损坏存在恢复力和确定网络脆弱性时，就需要网络描述。例如，众所周知，当节点或连接随机失效时，无尺度网络远远比随机网络更强壮，因为前者保持了表 1 中归结的基本结构和通信特性，这也是为什么即使某个路由器始终是坏的，因特网也具有鲁棒性
25、的原因。然而，无尺度网络对它们中心站的故障是没有恢复力的，所以当面临某些偶然的故障或蓄意攻击时候，它也非常脆弱。例如，一个中心机场出现坏天气或其它问题，可能造成全国飞机的长时间延迟。而中心站8的存在是无尺度网络具有短路径的原因之一，这也是以易于被攻击为代价的。在效率和鲁棒性存在一个明显的折中。4.1 在网络中的搜索网络思维的一个主要的潜在应用就是提高搜索网络中具有某些特定特性节点的搜索算法。一般来说，这是一个很困难的问题。在一个巨大网络中，仅仅因为存在从一个节点到另一个节点之间的短路径，并不意味着这条路径容易被发现。1957 年 Stanley Milgram 做的一系列经典的社会学试验37，
26、表明社会网络的小世界特性和发现人们之间的短路径是很困难的。Milgram 的最初试验包括住在 Kansas 和 Nebraska的志愿者。他给每人都发了一封信，要求这封信到达一个住在 Boston 的特定目标人手中，但任何一个 Midwestern 志愿者都不认识这个目标人。每个志愿者只知道目标人的姓名和职业，通知他们根据目标人的名字把这封信送给他们认识的一个人，这个人他们认为比自己更有可能认识目标人。这条链中每个收到信人都给于同样指令。每封信上都有它所经过路径上的人的名字。经过使用不同协议的几个实验，Milgram 发现大约有 540%的信可以到达了目标人手中。他发现这些成功到达的信的平均路
27、径长度（传递一封信的人数）是 6。这就是人们所熟知的“六度分离”概念的起源。Milgram 的分析同样显示网络中中心节点的存在：一封成功的信都经过了一小部分联系广泛的人。在他的书中，Watts 深入描述了这个试验，指出原始实验中 Milgram 的报告存在疑问几个方面。他还指出由于平均成功路径较短，只有相对小数量的信件能成功到达，这证明了人们在只有局部网络知识时，搜索短路径的难度。之后，计算机科学家 Jon Kleinberg 证明在网络中，根据 Watts-Strogatz 模型用统一的概率随机选择节点并添加连接，对这样的网络没有有效的查找短路径的分散搜索算法31。在其它方面，这表明 Mil
28、gram 的社会网络与 Watts-Strogatz 的模型在某些方面是不同的，至少在最短路径的发现方面。Kleinberg 提出一个允许高效分布搜索的 Watts-Strogatz 模型的变量。这个模型从节点的集合开始，集合中两个节点的空间距离以 d 维定义。通过与其距离 d 次幂递减的概率在两节点之间重复的添加连接来构建网络。这个模型产生的一个网络，其中每个节点在所有的距离尺度上都可能有相同数目的连接。正如 Watts 所说：“你应该期待有同样多的朋友，和你住在邻居的朋友一样，分布在城市、州、国家、直至世界的其它地方的其他地方”Kleinberg 表示这种在所有范围上的相等连通的情况确保短
29、平均路径长度，并且允许个体节点 i 能有效的找到到节点 j 的一条短路径。节点 i 简单的给与它连接的节点发送一条信息，并且它判断这是到达目标节点最近的节点。Watts 指出， “为了使社会连接更有效也就是有意的发现一些事务它们必须对基础的社会结构信息编码但是 Kleinberg 模型没有解释世界是如何完成的。 ”当然，在真实世界中，两个个体之间的“距离”有许多维：物理空间，共同的兴趣，9年龄，社会级别，性别等等。Watts 给出证据显示清楚的区分这些不同维使得点对点网络更易于搜索，甚至在 Kleinberg 的距离尺度平等连通性条件不满足的情况下。4.2 在网络中寻找社区的结构网络分析的另外
30、一个重要应用是在一个给定的网络中发现聚类或社区结构。这是一个发现子网络（“社区” ）的问题，该子网络中包含密集连接，即一个给定的社区，社区内部节点之间比其与网络其它部分节点更容易相连。寻找这样的社区与计算机科学中的图分割问题也与社会学中的等级聚类问题有关。Newman 和 Girvan47、Newman45和 Guimera 与 Amaral18 曾对此问题一些有影响力的方法提出。尤其是 Guimera 与 Amaral 的工作非常有趣，因为他们的算法发现了鲜为人知的新陈代谢网络中的社区结构。在这样一个网络中，节点表示代谢物（小的基层molecules 和生物体内新陈代谢处理的产物） 。如果存
31、在一个化学反应，其中 i 是substrate，j 是产物，则两个节点 i 和 j 之间相连，反之亦然。 Guimera 和 Amaral 使用现存的一个新陈代谢网络数据库在 12 种不同生物体网络中搜索社区结构。他们用模拟退火法搜索最大化网络模块的社区结构，象 Newman 和 Girvan 定义的那样。在被发现的结构中，Guimera 和 Amaral 统一了节点扮演的几种不同类型的“角色” ，包括： 模块 hub（在它们的社区或“模块”内有很多连接的节点） 紧外围节点（所有连接都在节点模块内部） 外围节点（绝大部分连接都在节点模块内部） 非 hub 连接型节点（和其它模块有很多连接的节点
32、） 非 hub 无偏向连接型节点（均匀分布在所有模块的连接节点）他们还发现 hub 的三种子角色：地方型（节点连接的大部分主要的都是在节点模块的内部） ，连接型（节点是一个中心站同时与其它部分模块也有许多连接） ，无偏向型（节点的连接均匀分布在所有模块中） 。Guimera 和 Amaeral 假定在不同有机体中节点扮演的角色在其各自的有机体内有着相似的新陈代谢功能，结构上相关的节点（例如代谢物）在物种交叉中被保留下来。为了研究这些，作者评定了数据中不同有机体在 across 时被保留下来的不同角色的度。他们发现过外围节点节点被保留的最少、连接中心节点被保留的最多，这也是理所当然的。然而，他们还发现一个令人难以理解的结果：非中心连接器节点比地方性中心站节点保存的更多，即使一个中心站节点的度远远高于非中心连接器的度。作者的解释是连接器节点负责与其它连接匮乏的模块之间通讯。这些模型本身又扮演了功能的角色，这种功能可以由不同代谢物来实现，所以执行功能的特定代谢物的集合不需要在物种交叉中保留下来。而连接器扮演了一个结构的角色，因此必须被保留。用他们的话说：“在网络中节点的全局角色比起节点的度来说，将是一个更好的指示器” 。
