复杂网络的搜索策略与动力学行为模型

第1章 引 论 1.1 引 言 现实生活中的生物网络、食物链网络、互联网、交通网、电力网络、社会网络等均拥有相对复杂的拓扑结构，其动力行为具有动态性和多样性。Watts和Strogatz创造性地构建了小世界网络（small-world networks）模型[1]以及Barabási和Albert构建了BA网络演化模型[2]，由此掀起了复杂网络的研究热潮。 随着工业和科技的快速发展，复杂网络的形式和模型也在发生着变化。在这些不断变化的不确定系统中，很多问题的解决方法和处理手段都有着共性。这些问题本质上都可以被看成是一个搜索问题[3]，我们可以把这些搜索问题归结为复杂网络中的搜索问题。传统的网络搜索[4]往往将固定系统作为研究对象，导致其无法满足现有复杂网络的实际应用需求。 复杂网络中的节点属性呈动态变化，因此，分析网络的全局行为是非常困难的，对其进行研究具有很高的应用价值，科研人员也在不断地寻求着高性能的搜索策略。目前的研究重点是怎样使网络搜索更加有效、准确与迅速。研究人员已经找到了社会网络和随机网络（random networks）、规则网络（regular networks）不一样的拓扑性质。Watts和Strogatz设计了小世界网络模型，使“六度分离”特性得到深入解读，而实际网络内的无标度特征被Albert发现。对复杂网络进行搜索的算法有广度优先搜索算法与深度优先搜索算法，这两种搜索算法的搜索效率都不太理想，主要是很容易产生大量的查询消息流量，造成网络流量的急剧增加，从而导致网络拥塞[5]或者是不符合用户的需求。宽度优先搜索（breadth-first-search）是网络中常见的搜索算法之一[6]，与随机游走（random walk）算法属于同一种深度优先搜索算法[7]，这两种算法中，根据单个节点无法知道整个网络的拓扑结构，甚至不知道目标文件存在的节点位置。*大度搜索（high degree searching，HDS）[8]是基于幂律的搜索算法。在每个节点都认识自己的邻居并知道每个邻居的度的条件下，应用*大度搜索策略在网络中的节点上可以寻找指定的文件或者数据。 通过对复杂网络搜索策略的研究，可以将相关的研究成果应用于解决现实中存在的很多问题（尤其是很多优化问题），这也是科研人员追求的目标。这有利于人们重新认识这个纷繁复杂的世界，并且更加清楚地了解和认识复杂网络的特殊行为，使复杂网络的理论和技术朝着有利于人类进步的方向不断发展。 1.2 复杂网络研究简史 复杂网络是近年来国内外学者研究的一个热点问题。对网络的研究*早可以追溯到18世纪伟大数学家欧拉提出的著名的“Konigsberg七桥问题”。随后两百多年中，各国的数学家一直致力于对简单的规则网络和随机网络进行抽象的数学研究。规则网络因过于理想化而无法表示现实中网络的复杂性，20世纪60年代，Erdos和Rényi提出了随机网络[6]。进入20世纪90年代，人们发现现实世界中绝大多数的网络既不是完全规则的，也不是完全随机的，于是提出了一些更符合实际的网络模型。此时，国际上有两项开创性工作掀起了一股研究复杂网络的热潮：一是Watts和Strogatz在Nature上发表了一篇文章，提出了小世界网络模型，也称WS（Watts-Strogatz）模型。该模型既具有规则网络的高聚类性，又具有类似随机网络的小的平均路径长度。二是Barabási和Albert在Science上发表了一篇文章，提出了BA（Barabási-Albert）网络演化模型。他们认为，现实世界中大多数的复杂系统是动态演化的，是开放自组织的，实际网络中的无标度现象来源于两个重要因素，即增长机制和优先连接机制。 近年来，复杂网络的研究已经成为很多领域，尤其是交叉学科领域的研究热点之一。信息搜索是帮助人们快速、准确地获取所需信息的技术。地理信息搜索是指在互联网、数据库或数字图书馆等数字资源中检索跟地理位置有关的信息，并对搜索结果按某种方式进行排序，从而找到有用的信息。这些紧密相关的数据和信息可以用复杂网络来描述，网络中的节点往往只能通过相邻节点的相关信息或者近邻节点的局部信息进行搜索，而现实中的网络通常是相当复杂的，加之人们对复杂网络的拓扑结构和演化机制的认识还存在局限，很难像交通网中的一张地图那样准确标出各个节点之间的连接关系。因此，在复杂网络搜索算法研究中，如何在提高网络搜索速度的同时，增加搜索过程中所产生的有效信息，进而设计出更为行之有效的搜索策略，就成为科研人员不断探讨和深入研究的内容。 1.3 基本结构参量 随着对复杂网络的深入研究，人们提出了许多关于复杂网络的概念和度量方法，用于表示复杂网络的结构特性，现在普遍通过研究网络的静态统计量特征，来确定网络的性质和实际意义。目前，用来刻画现实网络宏观结构统计特征的静态统计量主要有平均路径长度、集聚系数、网络的度与度分布、介数以及网络弹性等。力求更加详细和全面地描述复杂的现实网络，寻找网络的各种宏观统计性质的微观生成机制是网络研究中极具意义和挑战性的事情。 1.3.1 度分布 度分布是图论和复杂网络理论中的基本概念。一个图（或网络）由一些顶点（节点）和连接它们的边（联结）构成。每个顶点（节点）连出的所有边（联结）的数量就是这个顶点（节点）的度。度分布是对一个图（网络）中顶点（节点）度数的总体描述。对于随机图，度分布指的是图中顶点度数的概率分布。 网络的度分布是描述网络性质的一个重要的静态特征统计量。度分布是网络的一个重要统计特征，是用来描述网络局部特性的基本参数，用 表示。网络中一个节点的度是指连接到这个节点的其他节点的数目[9]。节点 的度是与一个节点相关联的边的个数，对于有向网络，节点的度又可分为节点的入度和节点的出度，其中入度是指向给定节点的弧的数量，出度是从给定节点出发的弧的数量。例如，在科技引文网络中，节点的入度是指该文献被引用的次数，节点的出度是指该文献引用其他文献的数量。网络的度在不同的网络中所代表的含义也不同，一个节点的度越大，则意味着这个节点在某种意义上就越重要。例如，在社会网络中，网络的度可以表示个体的影响力和重要程度，度越大，个体的影响力也就越大，在整个组织中的作用也就越大。 复杂网络研究的一个重要内容就是要揭示所有节点的度所满足的统计规律性。图论中节点 的度为 ，用来表示节点 连接的边的数目，所有节点 的度 的平均值被称为网络平均度，用 来表示[10]，公式为 （1.1） 其中， 和 分别表示网络的边数和节点数。 网络中节点的度的分布情况可以用一个分布函数 来表示， 为一个随机选择的节点的度恰好有k条边的概率，也等于网络中度数为k的节点的个数占网络节点总个数的比值。网络节点度的分布函数反映了网络的宏观统计性质，理论上可以用度分布计算出其他表征全局特性的量化数值。 1.3.2 平均路径长度 网络中的两个节点 和 之间的路径长度 的定义为连接这两个节点的*短路径上的边数[10]。在复杂网络研究中，一般定义两个节点之间的距离为连接两者*短路径边的数目，网络的直径为任意两个节点间的*大距离，而网络的平均路径长度是指所有节点对之间距离的平均值，它描述了网络中节点间的平均分离程度，而且能够较好地衡量复杂网络的疏密程度，描述了网络的随机性和动态性。复杂网络研究的一个重要发现是绝大多数大规模现实网络的平均路径长度比想象的要小得多，这被称为小世界效应[11]。如果相对于随机网络来说平均路径长度的值越大，则该网络的动态性就越小，其随机性也就越大。网络中的任意两个节点之间路径的*大值被称为网络的直径，即 。网络的平均路径长度 的定义为任意两个节点之间距离的平均值，即 （1.2） 其中， 表示节点间距离， 表示网络中的节点数。 1.3.3 集聚系数 集聚系数 也叫作簇系数，被用来描述网络中节点周围的连接情况，是网络中的另一个重要参数。它衡量的是网络中任意一个节点的邻居节点之间相连接的平均可能性，即网络的疏密程度。例如，在社会网络中，你朋友的朋友可能也是你的朋友，或者你的两个朋友可能彼此也是朋友。 集聚系数的计算方法[12]是，假设节点 通过 条边与其他 个节点相连接，如果这 个节点都相互连接，那么它们之间存在 条边，而这 个节点之间实际存在的边数只有 的话，则它与 之比就是节点 的集聚系数，网络的集聚系数就是整个网络中所有节点集聚系数的平均值 （1.3） 这些现实的复杂网络并不是完全随机的，而是在某种程度上具有社会关系网络中的物以类聚、人以群分的一些特性。 1.3.4 介数 在社会网络中，有的节点的度虽然很小，但是该节点很可能是某两个社团的中间联系人，如果删除该节点，就会导致两个社团的联系被迫中断，因此该节点在网络中起到非常重要的作用。对于这样的关键节点，我们就需要定义新的衡量指标，由此引出了网络的重要全局几何量，也就是介数。 网络的介数和度都是描述网络拓扑结构的重要参数，不同之处在于节点的度描述的是单个节点或边对网络的影响。介数分为节点介数和边介数[13]，节点介数为网络中的所有*短路径经过该节点的次数；边介数的含义与节点介数的含义类似，是网络中的所有*短路径必须经过此边的次数。介数反映了相应的节点或者边在整个网络中的作用和影响力，这对于在现实网络中发现和保护关键资源具有重要意义。另外，网络拓扑还有其他重要的特征，如大型连通分支的规模[14]是指图中节点间相互连接的*大子图的节点数，节点对之间的连接跳数[15]是指两个节点之间的某条路径中含有的中间节点数。 参 考 文 献 [1] Watts D J， Strogatz S H. Collective dynamics of ‘small-world’ networks. Nature， 1998， 393(6684): 440-442. [2] Barabási A L， Albert R. Emergence of scaling in random networks. Science， 1999， 286(5439): 509-512. [3] Lv Q， Cao P， Cohen E， et al. Search and replication in unstructured peer-to-peer networks. ACM Sigmetrics Performance Evaluation Review， 2002， 30(1): 258-259. [4] Adamic L A， Lukose R M， Huberman B A. Local Search in Unstructured Networks. Handbook of Graphs and Networks. New York: ACM Press， 2003: 295-317. [5] Dijkstra E W. A note on two problems in connection with graphs. Numerische Mathematik， 1959， 1(1): 269-271. [6] Floyd R W. Algorithm 97: Shortest path. Communications of the ACM， 1962， 5(6): 345. [7] Cherkassky B V， Goldberg A V， Radzik T. Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming， 19