复杂网络引论

章节摘录

版权页：   插图：   4.2.7 Router-Level Internet Topology A common tool to represent the router-level Internet topology by a graph is the traceroute （Unix traceroute or Windows NT tracert.exe）, or its IPv6 version, traceroute6 （35）. The traceroute uses hop-limited probe, which consists of a hop-limited IP （Internet Protocol） packet and the corresponding ICMP （Internet Control Message Protocol） response, to probe every possible IP address and record every reached router and the corresponding edges. An earlier attempt in 1995 （36） was to use traceroute to trace 5,000 hosts, selected from a network accounting database. After the 5,000 destinations were selected, 11 of them were used as the new sources of routes to trace the remaining destinations. This eventually produced a graph of 3,888 nodes and 4,857 edges, excluding those routers that could not be traced due to transient routing or other technical problems. The analytical results show that more than 70% of the nodes have degree 1 or 2, and they do not belong to the core. The major limitation of this method is that it heavily depends on the choice of the destinations, namely, it needs to choose a certain number of destinations representing a subset of the Internet structure, to obtain the routing information before probing. An intelligent heuristic technique was then introduced （37） to overcome this drawback, by using heuristic to decide whether the network includes a single node. This technique does not require an initial database of targets for exploring the network topology. Based on some careful analysis of the collected data, consisting of nearly 150,000 nodes （routers and interfaces） and almost 200,000 edges, it was found （38） that the degree distribution of nodes with degree less than 30 follows a power-law form. However, the distribution of nodes with degree larger than 30 turns out to be significantly different: it has a faster cut-off other than a power-law distribution, indicating that there may be another law governing the distribution of higher-degree nodes in the network. Moreover, it was found that the distribution of the numbers of node-pairs within a certain number of hops in the network follows neither exponential （39） nor power-law form. Some analysis on the real data collected during October and November f 1999 shows that the hierarchical characteristic basically does not exist in the router-level of the Internet topology （40）, where the node-degree distribution has a power-law behavior which however is smoothed out by a clear exponential cut-off. Therefore, the Weibull distribution, instead of the power-law distribution, can fit the collected data better, agreeing with the result reported in （38）. However, this approach could not give a complete map of the Internet topology since it fails to represent the details of the Stub subnets although it can capture the topology of the Transit portion of the Internet. It is therefore suggested that probing from a large number of sources may be able to improve the performance regarding the completeness of the traceroute-style probes （41）. Recently, Border Gateway Protocol （BGP） routing tables were examined to determine the destinations of a traceroute （42）. A directed probing technique was used to interpret BGP tables thereby identifying relevant traceroutes and pruning the remainders （42）. A path reduction technique can also be used to identify redundant traceroutes, so as to generate a router-level Internet topology. An advantage of using these two techniques is that it can significantly reduce the number of required traces without sacrificing the accuracy. Actually, compared to the brute-force all-to-all approach, this method of combining the directed probing and the path-reduction techniques can reduce the number of required traces significantly by three orders in magnitude. Some analytical results on the real data collected during December 2001 to January 2002 show that the Weibull distribution can better fit the complementary cumulative distribution function of router out-degree than the Pareto （power-law） distribution （42）. In general, however, because most Internet Service Providers regard their routerlevel topologies as confidential, and there exist some technical problems such as multiple interfaces and hence multiple IP addresses for a single router, it is still a challenging task to build a relatively complete router-level Internet topology today. 4.2.8 Geographic Layout of the Internet Due to the lack of topological information about the Internet with geographic layout of AS and routers, very little work has been done to explore the geometry of the Internet infrastructure to date. One earlier work on this issue （43） used the NetGeo tool, developed by CAIDA （44）, to identify the geographic coordinates of 228,265 routers of the Mercator map, aiming at investigating the fundamental driving forces that shape the Internet's evolution. The obtained Internet topology, embedded with geographic information of routers, allows one to analyze the physical layout of the Internet infrastructure. It is found that routers form a fractal set with fractal dimension Df = 1.5 ± 0.1, and that they strongly correlate with the population density around the world, as illustrated by Fig. 4.22, where （a） is the router distribution density of the geographic locations of 228,265 routers of the Mercator map, and （b） is the population density distribution calculated based on the CIESIN population data （45）.

内容概要

陈关荣，1981年获中山大学计算数学硕士学位，1987年获美国德克萨斯A&M大学应用数学博士学位。于休斯顿大学任教至2000年，现任香港城市大学电子工程系讲座教授。1996年当选为IEEEFellow。获2008年国家自然科学二等奖、2010年何梁何利奖、2011年俄罗斯欧拉奖并获俄罗斯圣彼得堡国立大学荣誉博士学位，获4项IEEE等最佳学术杂志论文奖，是国内外30多所大学的荣誉或客座教授。现任International Journal of Bifurcation and Chaos主编，SCI他引一万六千多次，h指数62，被ISI评定为工程学高引用率研究人员。 汪小帆，1996年获东南大学工学博士学位。现为上海交通大学电子信息与电气工程学院教授、致远学院常务副院长。2008年受聘为教育部长江学者特聘教授。近年一直从事复杂网络系统分析与控制研究。获2002年国家杰出青年科学基金、2005年IEEE电路与系统汇刊最佳论文奖、2008年上海市自然科学一等奖和20108：上海市自然科学牡丹奖。 李翔，2002年获南开大学工学博士学位。现为复旦大学信息科学与工程学院教授、电子工程系主任。近年一直从事复杂网络系统控制的理论与应用研究。获2005年IEEE电路与系统汇刊最佳论文奖、2008年上海市自然科学一等奖、2010年上海市青年科技英才奖和2011年霍英东教育基金会高等院校青年教师奖，2009年入选教育部新世纪优秀人才计划。

书籍目录

Part Ⅰ Fundamental Theory Chapter 1 Introduction 1.1 Background and Motivation 1.2 A Brief History of Complex Network Research 1.2.1 The KSnigsburg Seven-Bridge Problem 1.2.2 Random Graph Theory 1.2.3 Small-World Experiment 1.2.4 Strength of Weak Ties 1.2.5 New Era of Complex-Network Studies 1.3 Some Basic Concepts 1.3.1 Graph Representation of Networks 1.3.2 Average Path Length 1.3.3 Clustering Coefficient 1.3.4 Degree and Degree Distribution 1.3.5 Statistical Properties of Some Real-World Complex Networks Problems References Chapter 2 A Brief Introduction to Graph Theory 2.1 What is a Graph？ 2.2 Notation, Definitions and Preliminaries 2.3 Eulerian and Hamiltonian Graphs 2.3.1 Eulerian Graphs 2.3.2 Hamiltonian Graphs 2.4 The Chinese Postman Problem 2.5 The Shortest Path Length Problem 2.6 Trees 2.7 The Minimum Connector Problem 2.8 Plane Graphs and Planar Graphs 2.9 Euler Formula for Plane Graphs 2.10 Directed Graphs Problems References Chapter 3 Network Topologies: Basic Models and Properties 3.1 Introduction 3.2 Regular Networks 3.3 Random-Graph Networks 3.4 Small-World Network Models 3.4.1 The WS Small-World Network Model 3.4.2 The NW Small-World Network Model 3.4.3 Statistical Properties of Small-World Network Models 3.5 The Navigable Small-World Network Model 3.6 Scale-Free Network Models 3.6.1 The BA Scale-Free Network Model 3.6.2 Robustness versus Fragility 3.6.3 Modified BA Models 3.6.4 A Simple Model with Power-Law Degree Distribution 3.6.5 Local-World and Multi-Local-World Network Models Problems References Part Ⅱ Applications: Selected Topics Chapter 4 Internet: Topology and Modeling 4.1 Introduction 4.2 Topological Properties of the Internet 4.2.1 Power-Law Node-Degree Distributions 4.2.2 Hierarchical Structures 4.2.3 Rich-Club Structure 4.2.4 Disassortative Property 4.2.5 Coreness and Betweenness 4.2.6 Growth of the Internet 4.2.7 Router-Level Internet Topology 4.2.8 Geographic Layout of the Internet 4.3 Random-Graph Network Topology Generator 4.4 Structural Network Topology Generators 4.4.1 Tiers Topology Generator 4.4.2 Transit-Stub Topology Generator 4.5 Connectivity-Based Network Topology Generators 4.5.1 Inet 4.5.2 BRITE Model 4.5.3 GLP Model 4.5.4 PFP Model 4.5.5 TANG Model 4.6 Multi-Local World Model 4.6.1 Theoretical Considerations 4.6.2 Numerical Results with Comparison 4.6.3 Performance Comparison 4.7 HOT Model 4.8 Dynamical Behaviors of the Internet Topological Characteristics References Chapter 5 Spreading Dynamics 5.1 Introduction 5.2 Epidemic Threshold Theory 5.2.1 Epidemic Models 5.2.2 Epidemic Thresholds on Homogenous Networks 5.2.3 Statistical Data Analysis 5.2.4 Epidemic Thresholds on Scale-Free Networks 5.2.5 Epidemic Thresholds on BA Scale-Free Networks 5.2.6 Epidemic Thresholds on Finite-Sized Scale-Free Networks 5.2.7 Epidemic Thresholds on Correlated Networks 5.2.8 Epidemic Thresholds on Some Generalized Scale-Free Networks 5.2.9 SIR Model of Epidemic Spreading 5.3 Immunization on Complex Networks 5.3.1 Random Immunization 5.3.2 Targeted Immunization 5.3.3 Acquaintance Immunization 5.4 Computer Virus Spreading over the Internet 5.4.1 Random Constant Spread Model of the Code-Red Worm 5.4.2 A Compartment-Based Model of Computer Worms 5.4.3 Spreading Models of E-mail Viruses 5.4.4 Effects of Computer Virus on Network Topologies 5.5 Other Spreading Phenomena on Complex Networks 5.5.1 Rumors Spreading over Social Networks 5.5.2 Some Generalized Models of Spreading Dynamics References Chapter 6 Cascading Reactions on Networks 6.1 Introduction 6.2 Dynamic Cascading Failures: Models and Analyses 6.2.1 Models Based on Node Dynamics 6.2.2 Models Based on Edge Dynamics 6.2.3 Hybrid Models Based on Node and Edge Dynamics 6.2.4 Binary Influence Model 6.2.5 Sand-Pile Model 6.2.6 OPA Model 6.2.7 CASADE Model 6.2.8 Other Models 6.3 Cascading Failures in Coupled Map Lattices 6.3.1 Cascading Failure Model Based on CMLs 6.3.2 Cascading Failures on Typical Coupling Lattices 6.4 Cascading Failures of Interdependent Networks References Chapter 7 Human Opinion Dynamics 7.1 Introduction 7.2 Social Network Topologies and Sociodynamics 7.3 Social Opinion Formation 7.3.1 Voter Model 7.3.2 Galam Majority-Rule Model 7.3.3 Latane Social Impact Theory 7.3.4 Sznajd Model 7.3.5 Virtual Social Game on the Internet 7.3.6 Online Social Opinion Formation 7.4 Bounded Confidence Models References Chapter 8 Network Synchronization 8.1 Introduction 8.2 Complete Synchronization of Continuous-Time Networks 8.2.1 Complete Synchronization of General Continuous-Time Networks 8.2.2 Complete Synchronization of Linearly Coupled Continuous-Time Networks 8.3 Complete Synchronization of Some Typical Dynamical Networks 8.3.1 Complete Synchronization of Regular Networks 8.3.2 Synchronization of Small-World Networks 8.3.3 Synchronization of Scale-Free Networks 8.3.4 Complete Synchronization of Local-World Networks 8.4 Phase Synchronization 8.4.1 Phase Synchronization of the Kuramoto Model 8.4.2 Phase Synchronization of Small-World Networks 8.4.3 Phase Synchronization of Scale-Free Networks 8.4.4 Phase Synchronization of Non-Uniformly Coupled Networks References Chapter 9 Network Control 9.1 Introduction 9.2 Spatiotemporal Chaos Control on Regular CML 9.3 Pinning Control of Complex Networks 9.3.1 Augmented Network Approach 9.3.2 Pinning Control of Scale-Free Networks 9.4 Pinning Control of General Complex Networks 9.4.1 Stability Analysis of General Networks under Pinning Control 9.4.2 Pinning and Virtual Control of General Networks 9.4.3 Pinning and Virtual Control of Scale-Free Networks 9.5 Time-Delay Pinning Control of Complex Networks 9.6 Consensus and Flocking Control References Chapter 10 Brief Introduction to Other Topics 10.1 Network Modularity and Community Structures 10.2 Human Mobility and Behavioral Dynamics 10.3 Web PageRank, SiteRank and BrowserRank 10.4 Recommendation Systems 10.5 Network Edge Prediction 10.6 Living Organisms and Bio-Networks References Index

编辑推荐

《复杂网络引论:模型、结构与动力学(英文版)》是为自然科学、数学和工程领域的研究生以及本科高年级学生编写的一本入门教科书，可以作为一个学期教学使用的讲义，也可以作为科研参考书或自学读物。

作者简介

《复杂网络引论:模型、结构与动力学(英文版)》力求正确和准确，但并不刻意采取十分严谨的写法，以期通俗易懂，侧重于主要思想和基本方法的介绍，仅提供启发性的数学支撑，希望具有初等微积分、线性代数和常微分方程的读者能够轻松地学习书中的主要内容。《复杂网络引论:模型、结构与动力学(英文版)》分成两大部分：第一部分是基础理论，包括背景材料和信息并附有适量的练习题，旨在让读者熟悉一些最基本的建模方法和分析技巧。第二部分是应用选题，包括复杂网络在几个代表性领域巾的应用研究，这些章节彼此相对独立。最后一章是近年来比较活跃的几个前沿研究课题的简介。各章均附有详细的关键文献，希望能够帮助有兴趣的读者很快地进入这些研究领域。

---

 复杂网络引论下载

---