科普一下技术网络
周涛  |  2012-01-26  |  科学网  |  459次阅读

技术网络是指人造的网络系统,但又不同于描述人和人之间直接关系的社会网络。技术网络的形成也不是一蹴而就的过程,而是经历了相当长时间的演化发展,并且依然处于变化中。这类网络的形成过程往往既体现了明确的全局优化和设计方案,又包含了系统本身和相关环境自组织演化发展的因素——在不同的系统中,这两种力量的对比各不相同。在电力网络、航空网络、铁路公路网络这类系统中,网络的演化,包括调整和增长,无一不经过慎之又慎的全局统筹规划,与此同时,真正在背后驱动这些网络演化的力量是社会经济的需求、城市/乡镇格局的变化、人口的分布和流动模式等等,而这些恰好又不是能够完全预先统筹规划的复杂系统;在万维网这类系统中,尽管存在一些人为设计的因素,譬如某新闻门户网站要求每一个新闻网页都添加超链接指向自己门户中通过文本分析判断出最相似的五个其他新闻网页,但是总体上来说是自组织演化驱动的,统筹和决策扮演较不重要的角色;更复杂的类似互联网这样的系统,从不同的层次来看,这两种力量的对比各不相同,譬如在自主系统的层次,统筹设计占主导地位,而在接入互联网的计算机的层次,自组织演化占主导地位。

技术网络往往具有特殊的设计目的,承载特定的功能,这种功能往往又依赖于网络上的某种“流”来完成。譬如,在万维网和互联网上流动的是信息,在电力网络上流动的是电流,而在交通网络上流动的是人。下面我们简要介绍一下上述几类典型的技术网络。

WWW是目前深入研究过的规模最大的网络之一,很多新的网络性质最早是从研究WWW中发现的,或者通过对WWW的实证获得广泛认可譬如下一节会提到的无标度特性[57-59]和自相似性质[60-61]由于WWW规模巨大,且每天都在变化,所以以前的研究往往是通过“网络机器人”的自动搜索功能发现新网页[62]。这样构建的网络在理论上存在一个问题,就是超链接比较多的网页具有更大的可能性被发现,因此目前已知的WWW结构与实际结构是有偏差的[63]

Internet也是研究非常深入的技术网络之一,WWW类似,早期对Internet的研究衍生出了很多刻画网络的工具和指标,包括网络的无标度特性[64]、度度相关性[65,66]、分形性质[67]和几何性质[68]等等。与后面我们会经常打交道的演化的无标度网络相比,Internet还具有很多独特的性质,譬如它具有特别强的连接上的负相关,如果用Pearson关联来刻画这种负相关(参考下一节的度相关指数),即便是通过交叉重连这种保持度序列不变的随机化方法[69],也不能显著降低负相关的程度[70]——这很可能是因为Internet中度最大的中枢节点度特别地大。Internet在演化上也体现出不同于大多数网络的特性,比如它的节点和连边数都以指数形式增长,但是它的最大度节点的度却有不增反减的趋势[71]。这些“诡异之处”恰恰是学术界关心的问题。WWW类似,Internet的结构往往是通过跟踪信息包而间接得到的,一些利用率较低的链路很可能检测不到,从而使得目前广泛用于研究得Internet数据与真实网络存在一定的差异。关于Internet结构演化和动力学的详细研究,可以参考Pastor-SatorrasVespignani的著作[72]

电力网络的研究一方面受到控制频繁发生且影响广泛的大停电事故的重大需求的推动,一方面得益于复杂网络研究所提供的新的分析工具和分析方法[73]。由于长距离电力传输在技术和经济上的困难,输电线长度是有限的,经过一定距离会设置相应的变电站或其他电力传输、储备、转移设施,因此电力网络整体上具有规则网络的局域化特性。早期的分析认为电力网络节点度分布可以用一个幂函数刻画[74],后来针对同样数据更细致的分析显示电力网络度分布是典型的指数分布[18,75],这一结论被后来针对北美[76]和意大利[77]的电子网络分析所验证——有趣的是,尽管连接度符合指数分布,这两个网络中节点电力负载的分布却接近幂律[76,77]。目前电力网络研究的重点还是网络上的级联故障模型以及相应的防控预警措施。本章第四节我们会介绍电力网络和其他网络耦合形成的具有依存关系的多网络系统。

交通网络覆盖的对象非常广泛,其中受到广泛关注的就包括航空网络[78]、铁路网络[79]、公路网络[80]、道路网络[81]、城市地铁[82]、城市公交[83]等等。这类技术网络各自具有很不相同的特征,譬如说铁路网和公路网比较接近于规则网络,而航空网络则具有明显的无标度网络的性质。这类网络也具有一些有别于其他类型技术网络的共同特征,譬如这些网络从功能上讲就是把乘客或者货物从一个地方运往另外一个地方,因此地理上的限制是网络结构得以形成功能得以实现的重要因素[84]——这一点就完全不同于WWW,一个超链接就可以跨越太平洋;又如交通网络每个节点的吞吐量和每条边的运输量是其生命力的体现,所以交通网络天然地就需要用含权模式进行刻画[85]。交通网络的演化,实际上是一个优化的过程,但是这个优化往往是局部的,而且具有贪婪算法的特征,譬如说新机场和新航线的开辟,往往不以关闭老机场放弃老航线为代价,因为这个代价太高。这个优化是拓扑优势和几何限制两种势力竞争平衡的结果[86]:前者驱使节点建立与中枢节点的连边从而使整个系统中所有节点到自己的拓扑距离变小;后者驱使节点优先建立距离较短的连边,因为这种连边的费用也小。如果连边费用和边长相关性极强,譬如铁路和公路,后者的力量就大,网络结构局域化强,更像规则网络;反之如果连边费用和边长相关性较弱,譬如航空网络,前者力量就达,网络平均距离就短,并且会出现无标度网络的性质。当然,仅仅这一点还不够,要完全理解交通网络的结构和功能以及把握其发展趋势,就必须充分了解相应的社会经济因素[87]和城市设施发展情况[88]。多个交通网络的耦合作用[89]以及交通网络与地理经济学[90]的结合,应该是未来研究的热点,这方面的发展同时也会极大促进我们对于城市发展与规划,以及流行病传播的理解。

[57] R. Albert, H. Jeong, A.-L. Barabási, Diameter of the World-Wide Web, Nature 401 (1999) 130-131.

[58] L. A. Adamic, B. A. Huberman, Power-law Distribution of the World Wide Web, Science 287 (2000) 2115.

[59] A.-L. Barabási, R. Albert, H. Jeong, Scale-free Characteristics of Random Networks: The Topological of the World Wide Web, Physica A 281 (2000) 69-77.

[60] C. Song, S. Havlin, H. A. Makse, Self-similarity of Complex Networks, Nature 433 (2005) 392-395.

[61] S. H. Strogatz, Romanesque Networks, Nature 433 (2005) 365-366.

[62] A. Broder, R. KumarF. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener, Graph Structure in the Web, Computer Networks 33 (2000) 309-320.

[63] S. Lawrence, C. L. Giles, Accessibility of Information on the Web, Nature 400 (1999) 107-109.

[64] M. Faloutsos, P. Faloutsos, C. Faloutsos, On Power-law Relationship of the Internet Topology, Computer Communications Review 29 (1999) 251-262.

[65] R. Pastor-Satorras, A. Vázquez, A. Vespignani, Dynamical and Correlation Properties of the Internet, Phys. Rev. Lett. 87 (2001) 258701.

[66] A. Vázquez, R. Pastor-Satorras, A. Vespignani, Large-scale Topological and Dynamical Properties of the Internet, Phys. Rev. E 65 (2002) 066130.

[67] G. Caldarelli, R. Marchetti, L. Pietronero, The fractal properties of Internet, Eurphys. Lett. 52 (2000) 386-391.

[68] S. H. Yook, H. Jeong, A.-L. Barabási, Modeling the Internets Large-scale Topology, Proc. Natl. Acad. Sci. USA 99 (2002) 13382-13386.

[69] S. Maslov, K. Sneppen, Specificity and Stability in Topology of Protein Networks, Science 296 (2002) 910-913.

[70] S. Zhou, R. J. Mondragon, Structural constraintsin complex networks, New J. Phys. 9 (2007) 173.

[71] G.-Q. Zhang, G.-Q. Zhang, Q.-F. Yang, S.-Q. Cheng, T. Zhou, Evolution of the Internet and its cores, New J. Phys. 10 (2008) 123027.

[72] R. Pastor-Satorras, A. Vespignani, Evolution and structure of the Internet: a statistical physics approachCambridge University Press, 2004.

[73] 柏文洁汪秉宏周涛从复杂网络的观点看大停电事故复杂系统与复杂性科学 2(3) (2005) 29-37.

[74] A.-L. Barabási, R. Albert, Emergence of Scaling in Random Networks, Science 286 (1999) 509-512.

[75] S. H. Strogatz, Exploring Complex Networks, Nature 410 (2001) 268-276.

[76] R. Albert, I. Albert, G. L. Nakarado, Structural Vulnerability of the North American Power Grid, Phys. Rev. E 69 (2004) 025103.

[77] P. Crucitti, V. Latora, M. Marchiori, A topological analysis ofthe Italian electric power grid, Physica A 338 (2004) 92-97.

[78] 刘宏鲲周涛航空网路综述自然科学进展 18 (2008) 601-608. 

[79] P. Sen, S. Dasgupta, A. Chatterjee, P. A. Sreeram, G. Mukherjee, S. S. Manna, Small-world Properties of the Indian Railway Network, Phys. Rev. E 67 (2003) 036106.

[80] S. Lämmer, B. Gehlsen, D. Helbing, Scaling law in the spatial structure of urban road networks, Physica A 363 (2006) 89-95.

[81] B. Jiang, C. Claramunt, Topological analysis of urban street networks, Environment and Planning B 31 (2004) 151-162.

[82] V. Latora, M. Marchiori, Is the Boston Subway a Small-world Network? Physica A 314 (2002) 109-113.

[83] J. Sienkiewicz, J. A. Holyst, Statistical analysis of 22 public transport networks in Poland, Phys. Rev. E 72 (2005) 046127.

[84] M. Barthélemy, Spatial Networks, Phys. Rep. 499 (2011) 1-101.

[85] A. Barrat, M. Barthélemy, R. Pastor-Satorras, A. Vespignani, The architecture of complex weighted networks, Proc. Acad. Natl. Sci. U.S.A. 101 (2004) 3747-3752.

[86] Y.-B. Xie, T. Zhou, W.-J. Bai, G. Chen, W.-K. Xiao, B.-H. Wang, Geographical networks evolving with an optimal policy, Phys. Rev. E 75 (2007) 036106.

[87] 刘宏鲲张效莉曹莨汪秉宏周涛中国城市航空网络航线连接机制分析中国科学G 39 (2009) 935-942.

[88] J. Um, S.-W. Son, S.-I. Lee, H. Jeong, B.-J. Kim, Scaling laws between population and facility densities, Proc. Acad. Natl. Sci. U.S.A. 106 (2009) 14236-14240.

[89] C.-G. Gu, S.-R. Zou, X.-L. Xu, Y.-Q. Qu, Y.-M. Jiang, D.-R. He, H.-K. Liu, T. Zhou, Onset of cooperation between layered networks, Phys. Rev. E 84 (2011) 026101.

[90] S. Brakman, H. Garretsen, C. Van Marrewijk, The New Introduction to Geographical Economics, Cambridge University Press, 2009.




文章原载于作者的科学网文章,所述内容属作者个人观点,不代表本平台立场。
本文经过系统重新排版,阅读原内容可点击 阅读原文