复杂网络研究概述
周涛柏文洁汪秉宏刘之景严钢
中国科学技术大学，近代物理系，安徽合肥：230026
摘要：近年来，真实网络中小世界效应和无标度特性的发现激起了物理学界对复杂网路的研究热潮。复杂网络区别于以前广泛研究的规则网络和随机网络最重要的统计特征是什么？物理学家研究复杂网络的终极问题是什么？物理过程以及相关的物理现象对拓扑结构是否敏感？物理学家进入这一研究领域的原因和意义何在？复杂网络研究领域将来可能会向着什么方向发展?本文将围绕上述问题，从整体上概述复杂网络的研究进展。
关键词：复杂网络小世界无标度拓扑性质
A short review of complex networks
Zhou Tao Bai Wen-Jie Wang Bing-Hong? Liu Zhi-Jing Yan Gang Department of Modern Physics, University of Science and Technology of China, Hefei, 230026
Abstract: In recent years, the discoveries of small-world effect and scale-free property in real-life networks have attracted a lot of interest of physicists. Which are the most important statistical characteristics for complex networks that known from regular networks and random networks? What is the ultimate goal of the study of complex networks? Are physical processes sensitive to the topological structure of networks? What are the reason and meaning that physicist come into the research field on complex networks? What are the directions for future research? In the present paper, we concentrate on those questions above and give a general review about complex networks.
Keyword: complex networks, small-world, scale-free, topological characters
1 引言
自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络[1]；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络[2]。类似的还有电力网络[1]、社会关系网络[1,3-4]、交通网络[5]等等。
数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构比较适合用来描述真实的系统呢？两百多年来，对这个问题的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看起来像是格子体恤衫上的花纹；又或者最近邻环网，它总是会让你想到一群手牵着手围着篝火跳圆圈舞的姑娘。到了二十世纪五十年代末，数学家们想出了一种新的构造网
络的方法，在这种方法下，
两个节点之间连边与否不再是确定的事情，而是根据一个概率决定。数学家把这样生成的网络叫做随机网络，它在接下来的四十年里一直被很多科学家认为是描述真实系统最适宜的网络[6-8]。直到最近几年，由于计算机数据处理和运算能力的飞速发展，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的网络。这样的一些网络被科学家们叫做复杂网络（complex networks ），对于它们的研究标志着第三阶段的到来。
遗憾的是，就目前而言，科学家们还没有给出复杂网络精确严格的定义，从这几年的研究来看，之所以称其为复杂网络，大致上包含以下几层意思：首先，它是大量真实复杂系统的拓扑抽象；其次，它至少在感觉上比规则网络和随机网络复杂，因为我们可以很容易地生成规则和随机网络，但就目前而言，还没有一种简单方法能够生成完全符合真实统计特征的网络；最后，由于复杂网络是大量复杂系统得以存在的拓扑基础，因此对它的研究被认为有助于理解“复杂系统之所以复杂”这一至关重要的问题。
2 复杂网络的统计特征
如前所述，复杂网络具有很多与规则网络和随机网络不同的统计特征，其中最重要的是小世界效应（small-world effect ）[1,9]和无标度特性（scale-free property ）[10-11]。
在网络中，两点间的距离被定义为连接两点的最短路所包含的边的数目，把所有节点对的距离求平均，就得到了网络的平均距离（average distance ）。另外一个叫做簇系数（clustering coeffici ent ）的参数，专门用来衡量网络节点聚类的情况。比如在朋友关系网中，你朋友的朋友很可能也是你的朋友；你的两个朋友很可能彼此也是朋友。簇系数就是用来度量网络的这种性质的。用数学化的语言来说，对于某个节点，它的簇系数被定义为它所有相邻节点之间连的数目占可能的最大连边数目的比例，网络的簇系数C
则是所有节点簇系数的平均值。研究表明，规则网络具有大的簇系数和大的平均距离，随机网络具有小的簇系数和小的平均距离。1998年，Watts 和Strogatz 通过以某个很小的概率p 切断规则网络中原始的边，并随机选择新的端点重新连接，构造出了一种介于规则网络和随机网络之间的网络（WS 网络），它同时具有大的簇系数和小的平均距离，因此既不能当作规则网络处理，也不能被看作是随机网络[1]。随后，Newman 和Watts 给出了一种新的网络的构造方法，在他们的网络（NW 网络）中，原有的连边并不会被破坏，平均距离的缩短源于以一个很小的概率在原来的规则网络上添加新的连边[12]。后来物理学家把大的簇系数和小的平均距离两个统计特征合在一起称为小世界效应，具有这种效应的网络就是小世界网络（small-world networks ）。
图1：小世界网络拓扑结构示意图 左边的网络是规则的，右边的网络是随机的，中间的网络是在规则网络上加上一点随机的因素而形成的小世界网络，它同时具有大的簇系数和小的平均距离。
大量的实证研究表明，真实网络几乎都具有小世界效应[1-5,13]，同时科学家还发现大量真实网络的节点度服从幂率分布[2,4,13-15]，这里某节点的度是指该节点拥有相邻节点的数目，或者说与该节点关联的边的数目。节点度服从幂律分布就是说具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示。幂函数曲线是一条下降相对缓慢的曲线，这使得度很大的节点可以在网络中存在。对于随机网络和规则网络，度分布区间非常狭窄，几乎找不到偏离节点度均值较大的点，故其平均度可以被看作其节点度的一个特征标度。在这个意义上，我们把节点度服从幂律
分布的网络叫做无标度网络（scale-free networks），并称这种节点度的幂律分布为网络的无标度特性。1999年，Barabási 和Albert给出了构造无标度网络的演化模型[10-11],他们所用的方法与Price的方法是类似的[16-17]。Barabási 和Albert把真实系统通过自组织生成无标度的网络归功于两个主要因素：生长和优先连接，而他们的网络模型（BA网络）正是模拟这两个关键机制设计的。
除了小世界效应和无标度特性外，真实网络还有很多统计上的特征，例如混合模式[18]，度相关特性[19-21]，超小世界性质[13]等等。限于篇幅，本文不再赘述，有兴趣的读者可以参考相关文献。
图2：无标度网络的拓扑结构示意图本图展示了有１３０个节点的ＢＡ网络，其节点度服从幂指数为－３的幂律分布。图中５个红色的节点是网络中度最大的５个节点。
3 复杂网络上的物理过程
对于物理学家而言，研究复杂网络的终极目标是理解网络拓扑结构对物理过程的影响。在以前的研究中，物理学家往往忽略了网络的拓扑性质，在讨论逾渗、传播、同步等物理过程时，他们自然地选择了最容易模拟和分析的规则网络或者随机网络，而没有仔细思考和研究这种选择是不是应该的，不同的选择会不会对物理过程产生不可忽略的影响。以网络上的传播动力学模型为例，由于传统的网络传播模型大都是基于规则网络的，因此，复杂网络不同统计特征的发现使科学家面临更改既有结论的危险。当然，如果理论研究和实验结果都说明复杂网络上的传播动力学行为与规则网络别无二致，那么我们至少暂时还可以心安理得地使用以前的结论。但是，不幸的是，复杂网络上的传播行为与规则网络相比确实存在根本上的不同。类似的情况还出现在其他的物理过程中，下面我们将简略地介绍网络拓扑性质对某些典型物理过程的影响。
逾渗模型与疾病传播动力学。之所以在这里把逾渗模型和网络上的疾病传播动力学问题归在一起讨论，是因为网络上的疾病传播模型可以等价于键逾渗模型[22-23]。以前的基于规则网络的研究表明，疾病在网络中的平均波及范围与疾病的传染强度正相关，而疾病的传染强度有一个阈值，只有当其值大于这个阈值时，疾病才能在网络中长期存在，否则感染人数会指数衰减[24-26]。根据这个理论，疾病若是持久存在，则必然波及大量个体。但实证研究表明，计算机病毒，麻疹等一般仅波及少数个体但能够长期存在[27-28]。这一理论与实证的矛盾在很长时间里一直困扰着科学界。近年来的研究表明在无标度网络中没有正的传播阈值[29-31]，也就是说即使疾病的传染强度接近零，只波及非常少的个体，也能在网络中长期存在。由于大部分真实网络是无标度网络，因此该结论很好地解决了上面的矛盾。
混沌同步。近十余年来，混沌动力系统在网络上的同步性能吸引了大量科学家的关注。早期的研究主要是针对以最近邻环网为代表的规则网络，研究表明对于给定的非零耦合强度，当节点数目很大时网络无法实现同步[32]。最近几年的研究却表明，尽管小世界网络只是在规则网络进行一个非常小的修正的结果[1,12]，但其实现混沌同步的能力却远远好于规则网络[33-34]。对于小世界上的广义混沌同步[35]与超混沌同步[36]的研究同样表明，小世界网络有明显好于规则网络的同步能力。物理学家还考察了无标度网络，研究表明其混沌同步的能力与星形网络几乎是一样的，这可能是因为它与星形网络都具有很不均匀的节点度分布[37]。
图3：网络中疾病平均波及范围与传染强度关系的示意图图中位于右侧的实线表示疾病在规则网络中传播的情况，位于左侧的实线表示疾病在小世界网络中传播的情况，虚线表示疾病在无标度网络中传播的情况。可以看到，疾病在无标度网络中没有正的传播阈值，而小世界网络的传播阈值明显小于规则网络。注意，图中的曲线只是为了帮助我们定性地理解，并不是通过数值模拟得到的定量的曲线。
图4：雪崩规模分布图红色和黑色的曲线分别代表在二维欧几里德格网和无标度网络上雪崩规模的分布，其中Ｐ（Ｓ）表示在１００万次微扰中规模为Ｓ的雪崩出现的次数。试验中，欧几里德格网和无标度网络的节点数均为４９００，平均度均为４。在无标度网络中，最大的雪崩规模为８８２９，而在欧几里德格网中相应的值仅为１７９９。
沙堆模型与自组织临界性。网络拓扑结构是否会影响沙堆模型中的自组织临界现象，一直以来就是该领域争论的焦点[38-43]。Zhou 和Wang对复杂网络上沙堆模型的研究表明，沙堆模型中的雪崩动力学性质对网络拓扑结构非常敏感，相比规则网络，无标度网络上大雪崩发生更为频繁，最大雪崩的规模也大得多[44]。
物理性质明显依赖于网络拓扑结构的物理过程还很多，例如随机游走[45-48]，玻色－爱因斯坦凝聚[49-51]，XY临界模型[52-53]等等。在此我们无法一一介绍，读者可以参阅相关文献。总的来说，物理学家已经开始学会把网络拓扑性质看作影响系统行为的一个特征量，这也很大程度上改变了我们对很多物理过程原有的认识。
４ 结语与展望
关于网络的研究，数学家早在两百多年前就开始了，他们已经发展出了成体系的理论与技术，而物理学家的进入只有五年左右的历史！到底是什么鼓动物理学家来趟这塘浑水，他们的到来有意义吗？在我们看来，研究对象特殊的尺度效应是召唤物理学家到来的根本原因。数学家经典的网络理论，要么是分析包含几十数百个顶点，可以画在一张纸上从而形成直观印象的网络；要么是讨论不含有限尺度效应，可以精确求解的网络性质。“随机移走一个顶点会对网络的性能产生什么样的影响？”这个问题对于研究有限规则网络的数学家是有意义的，但对于拥有几千万个节点，连接方式复杂多样的真实网络而言，或许“随机移走3％的顶点会对网络性能产生什么样的影响？”这个问题更有意义。这个尺度的网络，是被物理学家称作“足够大”的网络，对它们的研究，需要使用统计物理的方法。有的读者可能会问，数学家除了经典的网络理论外，还构造了一套随机图的理论，这套理论就是专门对付“足够大”的网络的，统计力学的方法到底能不能得到随机图论不能得到的新的有意义的结果呢？需要强调的是，随机图论的方法的确在复杂网络的研究中扮演了不可或缺的角色，但是，数学家的“足够大”和物理学家的“足够大”完全不是一个概念，
虽然他们都使用顶点数趋于无穷的假设。对于物理学家而言，平均场的近似，主方程的求解，在网络顶点数达到百十万甚至只需几万时，误差就已经可以接受了；而随机图的大量有意义的结果，要求节点数在连续求取三次常用对数后还要比10大[8]，在我们的宇宙中，目前还没有任何一个有物理意义的数值达到如此的量级。
从前面的介绍中我们已经看到，物理学家不仅在方法论上为网络研究注入了新的活力，而且大大地拓展了网络研究的视野。他们不仅和数学家一样关心网络自身的拓扑性质，而且关注网络上进行的各种物理过程和动力学行为，诸如传播、同步、自组织临界、玻色－爱因斯坦凝聚等等，他们发现了网络拓扑结构对各种动力学行为的影响，并给出了很多虽不严谨但很美妙的解释。这些工作很有可能会推动相关数学物理理论的发展。
图5：SCI收录的关于复杂网络的研究论文数量统计了从１９９８年到２００４年第一季度的情况，从图中可以看出，复杂网络的研究方兴未艾。
近几年来，大量关于复杂网络的文章发表在Science，Nature，PRL，PNAS等国际一流的刊物上，从一个侧面反映了复杂网络已经成为物理界的一个新兴的研究热点。香港城市大学的陈关荣教授统计了几年来被SCI收录的关于复杂网络的文章数量，从中可以看出明显的增长趋势。Evans统计了6年来在arXiv: cond-mat上提交的标题含有“network”的文章数，也同样发现了逐年递增的趋势。复杂网络的研究刚刚起步，前景看好，我国科学家应当尽快加入这个行列，争取做出原创性质的工作。
图6： arXiv: cond-mat上关于网络的研究论文数量统计了从１９９７年到２００３年ｃｏｎｄ－ｍａｔ上标题含有“ｎｅｔｗｏｒｋ”的文章数目，从图中可以看出，网络的研究在近６年来越来越受到物理学家的关注。
做为文章的结束，我们将为读者介绍一些重要的综述，希望这会有助于读者以更快的速度进入复杂网络研究的前沿阵地。
关于小世界网络的研究，Newman[54]和Hayes[55-56]给出了不算太长的三篇综述，更短的一篇由Strogatz完成[57]，发表在Nature上；Albert和Barabási给出了一篇更像是教科书的综述[58]，他们讨论的重点是演化的无标度网络,这篇文献在两年之内已经被引用了近千次；最为详尽的综述是Dorogovtsev和Mendes给出的[59]，在这篇文章中，他们用超过100页的篇幅穷举了在此之前几乎所有关于演化网络的结论，包括相当详细的实验与分析的过程；2003年Newman的综述堪称精品[60]，漂亮的组织结构，地道风趣的语言和独到的视角，使你在阅读时会忘掉是在读一篇学术文献，后面所附的四百多篇参考文献，足以填饱任何人的肚子；Wang和Chen在IEEE期刊上的一篇短综述[61]，非常适合作为入门读物，一个完全不谙此道的人都可以通过一个下午的阅读对复杂网络的研究概貌有所了解；
Wang的另一篇综述像是上一篇文章的扩展版[62]，在这篇文献中，Wang强调了复杂网络上的混沌同步，对这方面工作感兴趣的读者切不可放过该文献。最新的综述是Evans 在2004年5月完成的[63]，这篇文献中包含了很多最新研究的结果。
参考文献
[1] Watts J S, Strogatz S H. Nature, 1998, 393: 440
[2] Faloutsos M, Faloutsos P, Faloutsos C. Computer
Communications Review, 1999, 29: 251
[3] Liljeros F et al. Nature, 2001, 411: 907
[4] Ebel H, Mielsch L I, Borbholdt S. Phys. Rev. E,
2002, 66: 035103
[5] Sen P et al. Phys. Rev. E, 2003, 67: 036106
[6] Erd?s P, Rényi A. Publications of the
Mathematical Institute of the Hungarian Academy of Science, 1960, 5: 17
[7] Erd?s P, Rényi A. Acta Mathematica Scientia
Hungary, 1961, 12: 261
[8] Bollobás B. Random Graphs(London: Academic
Press Inc, 1985).
[9] Milgram S. Psychology Today, 1967, 2: 60
[10] Barabási A L, Albert R. Science, 1999, 286:509
[11] Barabási A L, Albert R, Jeong H. Physica A, 1999,
272: 173
[12] Newman M E J, Watts D J. Phys. Rev. E, 1999,
60: 7332
[13] T. Zhou et al. arXiv: cond-mat/0405258
[14] Jeong H et al. Nature, 2001, 411: 41
[15] Jeong H et al. Nature, 2000, 407: 651
[16] de Price D J S. Science, 1965, 149: 510
[17] de Price D J S. J. Amer. Soc. Inform.Sci., 1976,
27: 292
[18] Newman M E J. Phys. Rev. E, 2003, 67: 026126
[19] Pastor-Satorras R, Vázquez A, Vespignani A.
Phys. Rev. Lett., 2001, 87: 258701
[20] Vázquez A, Pastor-Satorras R Vespignani A. Phys.
Rev. E, 2002, 65: 066130
[21] Newman M E J. Phys. Rev. Lett., 2002, 89:
208701
[22] Grimmett G R. Percolation(Berlin: Springer-
Verlag, 1989) [23] Sander L M et al. Math. Biosci., 2002, 180: 293
[24] Bailey N T J. The Mathematical Theory of
Infectious Diseases and Its Applications(New
York: Hafner Press, 1975)
[25] Anderson R M, May R M. Infectious Diseases of
Humans(Oxford: Oxford University Press, 1992)
[26] Hethcote H W. SIAM Review, 2000, 42: 599
[27] Kephart J O. Sci. Am., 1997, 277: 56
[28] Kephart J O et al. IEEE Spectr., 1993, 30: 20
[29] Pastor-Satorras R, Vespignani A. Phys. Rev. E,
2001, 63: 066117
[30] Pastor-Satorras R, Vespignani A. Phys. Rev, Lett.,
2001, 86: 3200
[31] Barthelemy M et al. Phys. Rev. E, 2004, 92:
178701
[32] Wu C W, Chua L O. IEEE Trans. Circuits Syst.
I, 1995, 42: 430
[33] Gade P M, Hu C K. Phys. Rev. E, 2000, 62: 6409
[34] Wang X F, Chen G R. Int. J. Bifurcation and
Chaos, 2002, 12: 187
[35] Barahona M, Pecora L M. Phys. Rev. Lett., 2002,
89: 054101
[36] Jiang P Q et al. Int. J. Mod. Phys. B, 18 (accepted
2004)
[37] Wang X F, Chen G R. IEEE Trans. Circuits Syst.
I, 2002, 49: 54
[38] Olami Z et al. Phys. Rev. Lett., 1992, 68: 1244
[39] Klein W, Rundle J. Phys. Rev. Lett., 1993, 71:
1288
[40] Christensen K. Phys. Rev. Lett., 1993, 71: 1289
[41] Carvalho J X, Prado C P C. Phys. Rev. Lett.,
2000, 84: 4006
[42] Christensen K et al. Phys. Rev. Lett., 2001, 87:
039801
[43] Carvalho J X, Prado C P C. Phys. Rev. Lett.,
2001, 87: 039802
[44] Zhou T, Wang B H. arXiv: cond-mat/0406575
[45] Jespersen S et al. Phys. Rev. E, 2000, 62: 4405
[46] Pandit S A, Amritkar R E. Phys. Rev. E, 2001, 63:
041104
[47] Lahtinen J et al. Phys. Rev. E, 2001, 64; 057105
[48] Lahtinen J et al. Physica A, 2002, 311: 571
[49] Bianconi G et al. arXiv: cond-mat/0011224
[50] Burioni R et al. arXiv: cond-mat/0104365
[51] Burioni R et al. J. Phys. B, 2001, 34: 4697
[52] Kim B J et al. Phys. Rev. E, 2001, 64: 056135
[53] Medvedyeva K et al. Phys. Rev. E, 2003, 67:
036118
[54] Newman M E J. J. Stat. Phys., 2000, 101: 819
[55] Hayes B. American Scientist, 2000, 88: 9
[56] Hayes B. American Scientist, 2000, 88: 104
[57] Strogatz S H. Nature, 2001, 410: 268
[58] Albert R, Barabási A L. Rev. Mod. Phys., 2002,
74: 47
[59] Dorogovtsev S N, Mendes J F F. Advances in
Physics, 2002, 51: 1079
[60] Newman M E J. SIAM Review 2003, 45: 167
[61] Wang X F, Chen G R. IEEE Circuits & Systems
Magazine, 2003, 3: 6
[62] Wang X F. Int. J. Bifurcation & Chaos, 2002, 12:
885
[63] Evans T S. arXiv: cond-mat/0405123
致谢
本文的工作，受到了国家重点基础研究发展规划项目（973计划专项经费）“非线性科学中的前沿问题研究”，国家自然科学基金（70271070），中国与加拿大大学工业联合基金（CCUIPP-NSFC 70142005）以及高等教育博士点专项基金（SRFDP 20020358009）的资助，作者在此表示诚挚的谢意。
通讯联系人：bhwang@https://www.doczj.com/doc/1a6275689.html,
第二章复杂网络的基础知识 2.1 网络的概念 所谓“网络”（networks），实际上就是节点（node）和连边（edge）的集合。如果节点对（i，j）与（j，i）对应为同一条边，那么该网络为无向网络（undirected networks），否则为有向网络（directed networks）。如果给每条边都赋予相应的权值，那么该网络就为加权网络（weighted networks），否则为无权网络（unweighted networks），如图2-1所示。 图2-1 网络类型示例 (a) 无权无向网络(b) 加权网络(c) 无权有向网络 如果节点按照确定的规则连边，所得到的网络就称为“规则网络”（regular networks），如图2-2所示。如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络”（random networks）。如果节点按照某种（自）组织原则的方式连边，将演化成各种不同的网络，称为“复杂网络”（complex networks）。 图2-2 规则网络示例 (a) 一维有限规则网络(b) 二维无限规则网络
2.2 复杂网络的基本特征量 描述复杂网络的基本特征量主要有：平均路径长度（average path length ）、簇系数（clustering efficient ）、度分布（degree distribution ）、介数（betweenness ）等，下面介绍它们的定义。 2.2.1 平均路径长度（average path length ） 定义网络中任何两个节点i 和j 之间的距离l ij 为从其中一个节点出发到达另一个节点所要经过的连边的最少数目。定义网络的直径（diameter ）为网络中任意两个节点之间距离的最大值。即 }{max ,ij j i l D = （2-1） 定义网络的平均路径长度L 为网络中所有节点对之间距离的平均值。即 ∑∑-=+=-=111)1(2N i N i j ij l N N L （2-2） 其中N 为网络节点数，不考虑节点自身的距离。网络的平均路径长度L 又称为特征路径长度（characteristic path length ）。 网络的平均路径长度L 和直径D 主要用来衡量网络的传输效率。 2.2.2 簇系数（clustering efficient ） 假设网络中的一个节点i 有k i 条边将它与其它节点相连，这k i 个节点称为节点i 的邻居节点，在这k i 个邻居节点之间最多可能有k i (k i -1)/2条边。节点i 的k i 个邻居节点之间实际存在的边数N i 和最多可能有的边数k i (k i -1)/2之比就定义为节点i 的簇系数，记为C i 。即 ) 1(2-=i i i i k k N C (2-3) 整个网络的聚类系数定义为网络中所有节点i 的聚类系数C i 的平均值，记
第17卷第4期2009年10月 系统科学学报 JOURNAL OF SYSTEMS SCIENCE Vo1.17No.4 oct ，2009 复杂网络及其在国内研究进展的综述 刘建香 （华东理工大学商学院上海200237） 摘要：从复杂网络模型的演化入手，在简要介绍复杂网络统计特征的基础上，对国内关于复杂网络理论及其应用的研究现状从两方面进行综述：一是对国外复杂网络理论及应用研究的介绍，包括复杂网络理论研究进展的总体概括、复杂网络动力学行为以及基于复杂网络理论的应用研究介绍；二是国内根植于本土的复杂网络的研究，包括复杂网络的演化模型，复杂网络拓扑性质、动力学行为，以及复杂网络理论的应用研究等。并结合复杂网络的主要研究内容,对今后的研究重点进行了分析。 关键词：复杂网络；演化；拓扑；动力学行为中图分类号：N941 文献标识码：A 文章编号：1005-6408（2009）04-0031-07 收稿日期：2009-01-05 作者简介：刘建香（1974—），女，华东理工大学商学院讲师，研究方向：系统工程。E-mail ：jxliu@https://www.doczj.com/doc/1a6275689.html, 0引言 系统是由相互作用和相互依赖的若干组成部分结合的具有特定功能的有机整体[1]。而网络是由节点和连线所组成的。如果用节点表示系统的各个组成部分即系统的元素，两节点之间的连线表示系统元素之间的相互作用，那么网络就为研究系统提供了一种新 的描述方式[2、3] 。复杂网络作为大量真实复杂系统的高度抽象[4、5]，近年来成为国际学术界一个新兴的研究热 点，随着复杂网络逐渐引起国内学术界的关注，国内已有学者开始这方面的研究，其中有学者对国外的研究进展情况给出了有价值的文献综述，而方锦清[6]也从局域小世界模型、含权网络与交通流驱动的机制、混合择优模型、动力学行为的同步与控制、广义的同步等方面对国内的研究进展进行了简要概括，但是到目前为止还没有系统介绍国内关于复杂网络理论及应用研究现状的综述文献。本文从复杂网络模型的演化入手，在简要介绍复杂网络统计特征的基础上，对国内研究现状进行综述，希望对国内关于复杂网络的研究起到进一步的推动作用。 1.复杂网络模型的发展演化 网络的一种最简单的情况就是规则网络 [7] ，它 是指系统各元素之间的关系可以用一些规则的结构来表示，也就是说网络中任意两个节点之间的联系遵循既定的规则。但是对于大规模网络而言由于其复杂性并不能完全用规则网络来表示。20世纪50年代末，Erdos 和Renyi 提出了一种完全随机的网络模型———随机网络（ER 随机网络），它指在由N 个节点构成的图中以概率p 随机连接任意两个节点而成的网络，即两个节点之间连边与否不再是确定的事，而是由概率p 决定。或简单地说，在由N 个节点构成的图中，可以存在条边，从中随机连接M 条边所构成的网络就叫随机网络。如果选择M =p ，这两种构造随机网络模型的方法就可以联系起来。规则网络和随机网络是两种极端的情况，对于大量真实的网络系统而言，它们既不是规则网络也不是随机网络，而是介于两者之间。1998年，Watts 和Strogatz [8]提出了WS 网络模型，通过以概率p 切断规则网络中原始的边并选择新的端点重新连接 31--
复杂网络基础理论 第二章网络拓扑结构与静态特征
第二章网络拓扑结构与静态特征 l2.1 引言 l2.2 网络的基本静态几何特征 l2.3 无向网络的静态特征 l2.4 有向网络的静态特征 l2.5 加权网络的静态特征 l2.6 网络的其他静态特征 l2.7 复杂网络分析软件 2
2.1 引言 与图论的研究有所不同，复杂网络的研究更侧重 于从各种实际网络的现象之上抽象出一般的网络几何 量，并用这些一般性质指导更多实际网络的研究，进 而通过讨论实际网络上的具体现象发展网络模型的一 般方法，最后讨论网络本身的形成机制。 统计物理学在模型研究、演化机制与结构稳定性 方面的丰富的研究经验是统计物理学在复杂网络研究 领域得到广泛应用的原因；而图论与社会网络分析提 供的网络静态几何量及其分析方法是复杂网络研究的 基础。 3
2.1 引言 静态特征指给定网络的微观量的统计分布或宏观 统计平均值。 在本章中我们将对网络的各种静态特征做一小结 。由于有向网络与加权网络有其特有的特征量，我们 将分开讨论无向、有向与加权网络。 4 返回目录
2.2 网络的基本静态几何特征 ￠2.2.1 平均距离 ￠2.2.2 集聚系数 ￠2.2.3 度分布 ￠2.2.4 实际网络的统计特征 5
2.2.1 平均距离 1.网络的直径与平均距离 网络中的两节点v i和v j之间经历边数最少的一条简 单路径（经历的边各不相同），称为测地线。 测地线的边数d ij称为两节点v i和v j之间的距离（或 叫测地线距离）。 1／d ij称为节点v i和v j之间的效率，记为εij。通常 效率用来度量节点间的信息传递速度。当v i和v j之间没 有路径连通时，d ij＝∞，而εij＝0，所以效率更适合度 量非全通网络。 网络的直径D定义为所有距离d ij中的最大值 6
复杂网络研究概述 周涛柏文洁汪秉宏刘之景严钢 中国科学技术大学，近代物理系，安徽合肥：230026 摘要：近年来，真实网络中小世界效应和无标度特性的发现激起了物理学界对复杂网路的研究热潮。复杂网络区别于以前广泛研究的规则网络和随机网络最重要的统计特征是什么？物理学家研究复杂网络的终极问题是什么？物理过程以及相关的物理现象对拓扑结构是否敏感？物理学家进入这一研究领域的原因和意义何在？复杂网络研究领域将来可能会向着什么方向发展?本文将围绕上述问题，从整体上概述复杂网络的研究进展。 关键词：复杂网络小世界无标度拓扑性质 A short review of complex networks Zhou Tao Bai Wen-Jie Wang Bing-Hong? Liu Zhi-Jing Yan Gang Department of Modern Physics, University of Science and Technology of China, Hefei, 230026 Abstract: In recent years, the discoveries of small-world effect and scale-free property in real-life networks have attracted a lot of interest of physicists. Which are the most important statistical characteristics for complex networks that known from regular networks and random networks? What is the ultimate goal of the study of complex networks? Are physical processes sensitive to the topological structure of networks? What are the reason and meaning that physicist come into the research field on complex networks? What are the directions for future research? In the present paper, we concentrate on those questions above and give a general review about complex networks. Keyword: complex networks, small-world, scale-free, topological characters 1 引言 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络[1]；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络[2]。类似的还有电力网络[1]、社会关系网络[1,3-4]、交通网络[5]等等。 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构比较适合用来描述真实的系统呢？两百多年来，对这个问题的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看起来像是格子体恤衫上的花纹；又或者最近邻环网，它总是会让你想到一群手牵着手围着篝火跳圆圈舞的姑娘。到了二十世纪五十年代末，数学家们想出了一种新的构造网
网络基础知识 .什么是局域网： 局部区域网络( )通常简称为"局域网",缩写为。局域网是结构复杂程度最低的计算机网络。局域网仅是在同一地点上经网络连在一起的一组计算机。局域网通常挨得很近，它是目前应用最广泛的一类网络。通常将具有如下特征的网称为局域网。 ）网络所覆盖的地理范围比较小。通常不超过几十公里，甚至只在一幢建筑或一个房间内。 ）信息的传输速率比较高,其范围自到,近来已达到。而广域网运行时的传输率一般为、或者、。专用线路也只能达到。 ）网络的经营权和管理权属于某个单位。 .什么是广域网： 广域网( , )它是影响广泛的复杂网络系统。 由两个以上的构成，这些间的连接可以穿越*以上的距离。大型的可以由各大洲的许多和组成。最广为人知的就是，它由全球成千上万的和组成。 有时、和间的边界非常不明显，很难确定在何处终止、或在何处开始。但是可以通过四种网络特性通信介质、协议、拓扑以及私有网和公共网间的边界点来确定网络的类型。通信介质是指用来连接计算机和网络的电缆、光纤电缆、无线电波或微波。通常结束在通信介质改变的地方，如从基于电线的电缆转变为光纤。电线电缆的通常通过光纤电缆与其他的连接。 .什么是网桥： 网桥这种设备看上去有点像中继器。它具有单个的输入端口和输出端口。它与中继器的不同之处就在于它能够解析它收发的数据。网桥属于模型的数据链路层；数据链路层能够进行流控制、纠错处理以及地址分配。网桥能够解析它所接受的帧，并能指导如何把数据传送到目的地。特别是它能够读取目标地址信息（），并决定是否向网络的其他段转发（重发）数据包，而且，如果数据包的目标地址与源地址位于同一段，就可以把它过滤掉。当节点通过网桥传输数据时，网桥就会根据已知的地址和它们在网络中的位置建立过滤数据库（也就是人们熟知的转发表）。网桥利用过滤数据库来决定是转发数据包还是把它过滤掉. .什么是网关： 网关不能完全归为一种网络硬件。用概括性的术语来讲，它们应该是能够连接不同网络的软件和硬件的结合产品。特别地，它们可以使用不同的格式、通信协议或结构连接起两个系统。和本章前面讨论的不一样，网关实际上通过重新封装信息以使它们能被另一个系统读取。为了完成这项任务，网关必须能运行在模型的几个层上。网关必须同应用通信，建立和管理会话，传输已经编码的数据，并解析逻辑和物理地址数据。
计算机网络基础概述》述课稿 各位评委老师好：今天我要述课的内容是“计算机网络基础概述” 。下面我将从教材、学情、教学目标、教学重点难点、教法与学法、教学过程六个方面进行分析说明。 、教材分析： 本节是中职《计算机应用基础》第六章第一节的内容。在当今信息时代网络无处不在，学生每天上网，但他们对网络专业知识了解甚少。网络作为计算机专业一个重要分支，知识性、实践性都很强。本章只是让学生对网络相关知识有一个初步认识，为以后网络技术的学习奠定基础, 同时起到抛砖引玉的作用。而本节又是本章的基础篇，将从网络定义、功能、拓扑结构、网络软件、网络硬件等方面引导学生全面了解网络，以便今后在使用网络时用专业知识去解释并探究。 、学情分析： 我的教学对象是职高计算机专业二年级学生，经过一年的学习已经熟悉计算机软件、硬件资源。学生大都上过Internet 网，熟悉其常用功能，在学校机房又用过局域网，但他们对网络专业知识了解不多。 本节内容理论性强，比较抽象，而职高学生普遍存在理解能力差，学习自主性差的特点，所以在教学中必须采取有效措施，充分调动他们的学习积极性，提升教学的有效性。 基于教材以及学情分析，我确定了本节的教学目标、教学重点、难点。 三、教学目标： 1).知识目标：理解计算机网络定义及其功能掌握局域网与广域网的特点认识局域网的 三种网络拓扑结构及其优缺点了解网络硬件在网络中的作用理解协议 2).能力要求：培养学生观察分析能力、概括总结能力、小组合作能力 3).德育目标：培养学生自主学习、探究学习的意识提升学生利用网络作为工具解决生 活问题的意识 四、教学重点、难点： 重点：计算机网络定义及功能局域网与广域网的特点三种拓扑结构及其优缺点网络常用硬件设备的名称及作用
《复杂网络理论及其应用》读书笔记 1引言 二十世纪，科学研究的特点是分析的方法，还原论的方法：物理学（牛顿力学、量子力学、电子论、半导体），化学（量子分子论），生物（双螺旋结构）；建筑工程（应力应变分析），……。 二十一世纪（二十世纪末），系统成为主要的研究对象，整合成为主要方法。普列高津的耗散结构理论，哈肯的协同学，混沌和复杂系统理论，系统生物学……。 当分析为主要的研究方法时，人类关注如何将系统“分析”、“分解”，揭开系统的细部，了解是什么元素或部件组成了系统，却忽视或破坏了这些元素是如何组合成系统的。而整合的方法在于了解细部以后，研究“如何组合”的问题。这种方法导致复杂网络结构的研究。美国《Science》周刊：“如果对当前流行的、时髦的关键词进行一番分析，那么人们会发现，“系统”高居在排行榜上。” 2复杂网络的统计特征 如前所述，复杂网络具有很多与规则网络和随机网络不同的统计特征，其中最重要的是小世界效应（small -world effect）和无标度特性（scale -free property）。 在网络中，两点间的距离被定义为连接两点的最短路所包含的边的数目，把所有节点对的距离求平均，就得到了网络的平均距离（average distance ）。另外一个叫做簇系数（clustering coefficient）的参数，专门用来衡量网络节点聚类的情况。比如在朋友关系网中，
你朋友的朋友很可能也是你的朋友；你的两个朋友很可能彼此也是朋友。簇系数就是用来度量网络的这种性质的。用数学化的语言来说，对于某个节点，它的簇系数被定义为它所有相邻节点之间连的数目占可能的最大连边数目的比例，网络的簇系数C则是所有节点簇系数的平均值。研究表明，规则网络具有大的簇系数和大的平均距离，随机网络具有小的簇系数和小的平均距离。1998 年，Watts 和Strogatz 通过以某个很小的概率p 切断规则网络中原始的边，并随机选择新的端点重新连接，构造出了一种介于规则网络和随机网络之间的网络（WS 网络），它同时具有大的簇系数和小的平均距离，因此既不能当作规则网络处理，也不能被看作是随机网络。随后，Newman 和Watts 给出了一种新的网络的构造方法，在他们的网络（NW 网络）中，原有的连边并不会被破坏，平均距离的缩短源于以一个很小的概率在原来的规则网络上添加新的连边。后来物理学家把大的簇系数和小的平均距离两个统计特征合在一起称为小世界效应，具有这种效应的网络就是小世界网络（small-world networks）。 图 1 ：小世界网络拓扑结构示意图左边的网络是规则的，右边的网络是随机的，中间的网络是在规则网络上加上一点随机的因素而形成的小世界网络，它同时具有大的簇系数和小的平均距离。
第二章复杂网络的基础知识 2.1网络的概念 所谓“网络”(networks ),实际上就是节点(node)和连边(edge)的集合 如果节点对(i ,j )与(j ，i )对应为同一条边，那么该网络为无向网络(undirected networks )，否则为有向网络(directed networks )。如果给每条边都赋予相应 的权值，那么该网络就为加权网络( weighted networks )，否则为无权网络 (unweighted networks )，如图 2-1 所示。 如果节点按照确定的规则连边，所得到的网络就称为“规则网络”(regular networks )，如图2-2所示。如果节点按照完全随机的方式连边，所得到的网络 就称为“随机网络” (random networks )。如果节点按照某种(自)组织原则的 方式连边，将演化成各种不同的网络，称为“复杂网络” (complex networks ) (a) ⑹ 图2-2 规则网络示例 (a) 一维有限规则网络 (b) 二维无限规则网络 (a)无权无向网络 (b) 加权网络 (c) 无权有向网络 图2-1 网络类型示例 二二
2.2复杂网络的基本特征量 描述复杂网络的基本特征量主要有： 平均路径长度(average path length )、 簇系数 (clustering efficient )、度分布 (degree distribution )、介数 (betwee nn ess )等，下面介绍它们的定义。 2.2.1 平均路径长度 (average path len gth ) 定义网络中任何两个节点i 和j 之间的距离l j 为从其中一个节点出发到 达另一个节点所要经过的连边的最少数目。定义网络的直径( diameter )为网 络中任意两个节点之间距离的最大值。即 D = max{l i j } i, j (2-1 ) 定义网络的平均路径长度L 为网络中所有节点对之间距离的平均值。即 2 N(N -1) N -1 N ■- ■- l ij i 吕 j -i 1 (2-2) 其中N 为网络节点数，不考虑节点自身的距离。网络的平均路径长度L 又 称为特征路径长度(characteristic path length )。 网络的平均路径长度L 和直径D 主要用来衡量网络的传输效率。 2.2.2 簇系数(clustering efficient ) 假设网络中的一个节点i 有k i 条边将它与其它节点相连，这k i 个节点称为 节点i 的邻居节点，在这k i 个邻居节点之间最多可能有k i (k i-1)/2条边。节点 i 的k i 个邻居节点之间实际存在的边数 N 和最多可能有的边数k i (k i-1)/2之比 就定义为节点i 的簇系数，记为C 。即 2N j k i (k -1) (2-3) 整个网络的聚类系数定义为网络中所有节点 i 的聚类系数C 的平均值，记
《计算机网络基础概述》述课稿 各位评委老师好： 今天我要述课的内容是“计算机网络基础概述”。下面我将从教材、学情、教学目标、教学重点难点、教法与学法、教学过程六个方面进行分析说明。 一、教材分析： 本节是中职《计算机应用基础》第六章第一节的内容。在当今信息时代网络无处不在，学生每天上网，但他们对网络专业知识了解甚少。网络作为计算机专业一个重要分支，知识性、实践性都很强。本章只是让学生对网络相关知识有一个初步认识，为以后网络技术的学习奠定基础,同时起到抛砖引玉的作用。而本节又是本章的基础篇，将从网络定义、功能、拓扑结构、网络软件、网络硬件等方面引导学生全面了解网络，以便今后在使用网络时用专业知识去解释并探究。 二、学情分析： 我的教学对象是职高计算机专业二年级学生，经过一年的学习已经熟悉计算机软件、硬件资源。学生大都上过Internet网，熟悉其常用功能，在学校机房又用过局域网，但他们对网络专业知识了解不多。 本节内容理论性强，比较抽象，而职高学生普遍存在理解能力差，学习自主性差的特点，所以在教学中必须采取有效措施，充分调动他们的学习积极性，提升教学的有效性。 基于教材以及学情分析，我确定了本节的教学目标、教学重点、难点。 三、教学目标： 1）.知识目标：理解计算机网络定义及其功能 掌握局域网与广域网的特点 认识局域网的三种网络拓扑结构及其优缺点 了解网络硬件在网络中的作用 理解协议 2）.能力要求：培养学生观察分析能力、概括总结能力、小组合作能力 3）.德育目标：培养学生自主学习、探究学习的意识 提升学生利用网络作为工具解决生活问题的意识 四、教学重点、难点： 重点：计算机网络定义及功能 局域网与广域网的特点 三种拓扑结构及其优缺点 网络常用硬件设备的名称及作用
复杂网络理论及其应用研究概述 刘涛 ，陈忠，余哲 （上海交通大学安泰管理学院，上海市华山路1954号287＃信箱，200030） liuzhang@https://www.doczj.com/doc/1a6275689.html, 摘 要：本文从统计特性、结构模型和网络上的动力学行为三个层次简述复杂网络相关研究，并着重介绍了网络上的传播行为，认为它代表了复杂网络在社会经济系统中的重要应用。 关键词：复杂网络、小世界、无标度网络、疾病传播 1. 引言 结构决定功能是系统科学的基本观点[1]。如果我们将系统内部的各个元素作为节点，元素之间的关系视为连接，那么系统就构成了一个网络，例如神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络、计算机网络可以看作是计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络，类似的还有电力网络、社会关系网络、交通网络等等[2][3]。强调系统的结构并从结构角度分析系统的功能正是复杂网络的研究思路，所不同的是这些抽象出来的真实网络的拓扑结构性质不同于以前研究的网络，且节点众多，故称其为复杂网络（complex networks ）。近年来，大量关于复杂网络的文章发表在Science 、Nature 、PRL 、PNAS 等国际一流的刊物上，从一个侧面反映了复杂网络已经成为国际学术界一个新兴的研究热点。 复杂网络的研究可以简单概括为三方面密切相关却又依次深入的内容：通过实证方法度量网络的统计性质；构建相应的网络模型来理解这些统计性质何以如此；在已知网络结构特征及其形成规则的基础上，预测网络系统的行为[3]。 2. 复杂网络的统计性质 用网络的观点描述客观世界起源于1736年德国数学家Eular 解决哥尼斯堡七桥问题。复杂网络研究的不同之处在于首先从统计角度考察网络中大规模节点及其连接之间的性质，这些性质的不同意味着不同的网络内部结构，而网络内部结构的不同导致系统功能有所差异。所以，对这些统计性质的描述和理解是我们进行复杂网络相关研究的第一步，下面简述之。 2.1 平均路径长度（The average path length） 网络研究中，一般定义两节点间的距离为连接两者的最短路径的边的数目；网络的直径为任意两点间的最大距离；网络的平均路径长度则是所有节点对之间距离的平均值，它描述了网络中节点间的分离程度，即网络有多小。复杂网络研究中一个重要的发现是绝大多数大规模真实网络的平均路径长度比想象的小得多，称之为“小世界效应”l [2]。这一提法来源 资助项目：国家自然科学基金70401019，高等学校博士点科研基金2002048020。 作者简介： - 1 -
第一章 计算机网络概述 习题 1.什么叫计算机网络？ 计算机网络就是利用通信设备和通信线路将不同地理位置的具有独立功能的多台计算机连接起来用以实现资源共享和在线通信的系统。 2.计算机网络有那些功能？ 计算机网络主要的功能是通信功能和对硬件、软件和数据等资源共享。 3.计算机网络的发展分为哪些阶段？各有什么特点？ 计算机网络的发展过程包括四个阶段： 1)面向终端的计算机通信网络：特点是计算机为网络的中心和控制者，各终端分布在各处，终端通过通信线路共享主机的硬件和软件资源； 2)计算机网络互联阶段：特点是计算机与计算机直接直接通信，计算机网络分成通信子网和资源子网，分别完成数据通信和数据处理两大功能； 3)具有统一的体系结构、遵循国际化标准协议的计算机网络：特点是遵循OSI/RM，是计算机网间网互联的要求； 4)高速网络互联阶段：特点是使用TCP/IP体系，完成了网间网高速通信和资源共享。4.计算机网络按地理围可以分为哪几种？ 计算机网络根据所覆盖的地理围不同分为：局域网（几米到几公里）城域网（十公里到几十公里）广域网（百公里道几千公里） 5.计算机网络常见的拓扑结构有哪些？各有什么特点？ 网络的拓扑结构主要包括星形结构、总线形结构和环形结构： 1)星形结构的特点是：控制简单、故障诊断容易、扩展容易； 2)总线形结构的特点是：安装容易，故障隔离性好、易扩展和维护； 3)环形结构的特点是：适合于光纤高速传输，单方向数据传输，一个节点出现故障影响其它节点数据传输。 6.计算机网络系统由通信子网和资源子网组成。 7.一座大楼的一个计算机网络系统属于LAN。 8.计算机网络中可以共享的资源包括硬件、软件、数据、通信信道。 第二章 数据通信基础 习题 一、 1.将一个信道按频率划分为多个子信道，每个子信道上传输一路信号的多路复用技术称为频分多路复用。 2.调制解调器的作用是实现数字信号在模拟信道中的传输。 3.接收端发现有出差错时，设法通知发送端重发，直到正确的码字收到为止，这种差错控制方法称为自动请求重发。 4.在同一信道上的同一时刻能够进行双向数据传送的通信方式是全双工。 5.在CRC码计算中，可以将一个二进制位串与一个只含0或1两个系数的多项式建立对应的关系。与位串101110对应的多项式为x5+x3+x2+x。 6.在码元传输速率为1200波特的调制解调器中，采用4相位技术，可获得的数据传输速率为2400b/s。 7.下列编码中，属于自动编码的是曼彻斯特编码。
计算机网络技术概述 计算机网络技术的变化，可谓日新月异，相应的网络的标准、框架、实施和相应应用也飞速向前发展。现在，网格计算的应用情形也正如web服务的早期情况，又或者是XML，表面上看来是缓慢发展，但是，一旦出现统一的标准和工具，将会出现爆炸式的发展。 1）什么是网格计算，网格计算是一项逐渐形成的技术，不同的人会给出不同的定义。实际上，网格计算的定义很简单：使用网格计算技术，可以将一组服务器、存储系统和网络组合成一套大的系统，并提供高质量的服务。对终端用户或者应用，网格计算象一个巨大的虚拟计算系统。 再进一步的分析，网格技术允许组织、使用无数的计算机共享计算资源，来解决问题。被解决的问题可能会涉及到数据处理、网络或者数据存储。这个由网格技术结合在一起的系统，可能是在同一个房间，也可能是分布在世界各地，运行在不同的硬件平台，不同的操作系统，隶属于不同的组织。基本的思想是赋予某些用户执行一些特定的任务，网格技术将平衡这些巨大的IT资源，来完成任务。本质上，所有的网格用户使用一个巨大的虚拟系统工作。 这听起来，非常的美好，但问题是如何让它们成为现实，这需要标准，开放的，目标统一的协议和接口。现在标准正在制定中，并逐渐的显现出来。 反过来讲，为什么集群，连接存储设备的网络，科学的设施，网络不是网格呢？这其中的每一个都可能是网格的重要的组成部分，但他自己，却不能建立网格。 有下面几种网格类型 a）计算网格，这些机器将处理数据，及其他繁重的工作。 b）抽取网格，一般情况下是从空闲的服务器和台式机上抽取CPU时间片，用作资源密集型的任务。 c）数据网格，为某一组织的数据知识库提供统一的接口，通过接口，可以查询、管理和保护数据。 计算机网络，是指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路连接起来，在网络操作系统，网络管理软件及网络通信协议的
第1部分 计算机网络概论 〖主要内容〗计算机网络基本概念，计算机网络的发展，计算机网络的组成与功能， 计算机网络分类。 〖教学重点〗计算机网络的发展，资源子网，通信子网。 计算机网络是计算机技术(或信息技术)与通信技术结合的产物。随着计算机软件和硬件(特别是微电子技术的发展促使芯片价格越来越低)的产生和发展，在计算机应用的过程中，需要对大量复杂的信息进行收集、交换、加工、处理和传输，为了提高计算机应用效率，提供信息处理的有效手段，充分发挥计算机与信息本身的作用，从而引入了通信技术，以便通过通信线路为计算机或终端设备提供收集、交换和传输信息的手段。 1.1 计算机网络的形成与发展 计算机网络从20世纪60年代中期开始发展至今，已形成从小型的办公室局域网到全球性大型广域网的规模，对现代人类的生产、经济、生活等各个方面都产生了巨大的影响。在当今的信息社会中，人们不断地依靠计算机网络来处理个人和工作上的事务，而这种趋势正在加剧并显示出计算机和计算机网络的强大功能。 计算机网络的形成大致分为四个阶段： 1.1.1 联机终端网络阶段（第一阶段） 20世纪60年代以前，计算机主机昂贵，而通信线路和通信设备的价格相对便宜，为了使用户共享主机宝贵的资源和进行信息的采集及综合处理，网络由此产生了。 1、联机终端控制系统 A 、单点通信线路：终端用户直接共享主机资源 说明：早期计算机功能不强，又十分庞大，主要用于科学计算，为了解决用户要到机房上机的不便，因此在远离计算机的地方设置了远程终端，并在计算机上增加了通信控制功能，经线路连接输送数据进行成批处理，这 样就产生了具有通信功能的主机——单终端系统。 B 、多点通信线路：多个终端用户通过一条通信线路与主机通信 说明：主机——单终端系统减少了用户远程上机的时间，提高了计算机的应用效率。为了使更多的用户使用主机的资源，提 高通信线路的利用率，采用了多个终端通过一条通信线路或多条线路连接主机，各终端用户分时使用主机资源。 特点： (1) 通信与数据处理任务全部由主机完成 (2) 主机与终端的关系是支配与被支配的关系 (3) 在联机终端控制 系统中终端仅仅是一个I/O 设备 终端 通信 控制器 集 中器 主机 高速线路 高速线路 低速线路 终端
第一章计算机网络概述练习题 一、单项选择题 考点：计算机网络的分类 1、在哪个范围内的计算机网络可称之为局域网：（A） A、在一个楼宇 B、在一个城市 C、在一个国家 D、在全世界 2、一座大楼内的一个计算机网络系统，属于（B ） A、PAN B、LAN C、MAN D、WAN 3、广域网覆盖的地理范围从几十公里到几千公里。它的通信子网主要使用( B ) A.报文交换技术 B.分组交换技术 C.文件交换技术 D.电路交换技术 4、下列不属于广域网的是：（ A ） A、电话网 B、ISDN C、以太网 D、X.25分组交换公用数据网 5、LAN是的英文缩写。（C） A、网络 B、网络操作系统 C、局域网 D、实时操作系统 6、局域网是在小范围内组成的计算机网络，其范围一般是（D）。 A、在五十公里以内 B、在一百公里以内 C、在二十公里以内 D、在十公里以内 7、分布在一座大楼或一集中建筑群中的网络可称为 ( A ) 。 A、LAN B、广域网 C、公用网 D、专用网 8、在计算机网络中，一般局域网的数据传输速率要比广域网的数据传输速率( A) A.高 B.低 C.相同 D.不确定 考点：计算机网络的定义 9、计算机网络是分布在不同地理位置的多个独立的( D ) 的集合。 A、局域网系统 B、多协议路由器 C、操作系统 D、自治计算机 10、分布式计算机系统与计算机网络系统的重要区别是( D)。 A、硬件连接方式不同 B、系统拓扑结构不同 C、通信控制方式不同 D、计算机在不同的操作系统下，工作方式 不同 11、计算机网络的主要功能有: ( A )、数据传输和进行分布处理。 A、资源共享 B、提高计算机的可靠性 C、共享数据库 D、使用服务器上的硬盘 12、计算机网络中可以共享的资源包括（A） A、硬件、软件、数据、通信信道 B、主机、外设、软件、通信信道 C、硬件、程序、数据、通信信道 D、主机、程序、数据、通信信道 13、通信子网为网络源节点与目的节点之间提供了多条传输路径的可能性，路由
复杂网络的基本统计特征理论知识 2.1 路网拥挤核 2.1.1路网拥挤核的定义 路网的总体拥堵评估，用路网拥挤核这一指标来进行评估。路网拥挤核为路段拥挤度居全网前k%且相互连通成为一个局部网络，并且不能忽略的是，该网络对于所研究区域整体的人口，经济，政策等与人类活动的因素有着不可忽视的作用，那么这个城市道路局部网络，称为路网拥挤核。 2.1.2路网拥挤核k 值的计算 根据宁波市交通工程的实际情况，考虑到宁波市的经济社会发展水平以及交通需求水平，利用宁波市的GDP 增长率、国省道日均流量增长比以及汽车拥有量增长比这三个指标，运用以下公式： ； （2.1） 本文选择的研究对象为宁波市，所以这里K 值计算暂时只讨论宁波市的路网拥挤核；根据公式，结合你宁波近十年数据，计算可得k=17.7，而考虑到宁波市的经济总量和汽车拥有量较大，在经济总量足够大以及汽车拥有量趋于饱和后，它们的增长率和增长比的数值会有所下降，所以将k 值暂定为15，即路段拥挤度居全网前15%且相互连通成为一个局部网络，就称该局部网络为一个路网拥挤核。 2.2复杂网络的基本统计特征 对于城市道路网络演化模型构建与评估必须对于复杂网络的一些基础知识进行必要的了解。 汽车拥有量增长比增长率国省道日均流量增长比??=GDP K
2.2.1复杂网络的度与度分布 度是对于复杂网络系统里面，最常用同时也是最简单的一种概念。在一个复杂网络系统里面，具体的每个节点的度m i 是指与这个节点连接在一起的边的具体的数量，而如果给这个复杂网络系统加上方向，那么具体的度可以分为二种：出度和入度；前者指的是从选定的节点，沿着复杂网络系统的方向指向的其他节点的具体的边的数目，后者指的是从选定的节点，反着复杂网络系统的方向指向的其他节点的具体的边的数目。复杂网络系统的度m i 平均值叫做，网络的平均度用符号
计算机网络概述 1 计算机网络概述 1.1 引言 在过去的300年中，每个世纪都占据着技术主导地位。18世纪的工业革命是机器的伟大时代。19世纪是蒸汽机的时代。20世纪的重要技术是访问信息，存储，传输，处理和使用。计算机的发明这标志着信息时代的一个新的开始出现。新的信息技术产业正以强劲的势头迅猛快速发展。因此，为了提高信息社会的生产力，我们必须提供整个社会，经济，快捷的方式获取信息。这是我们通过计算机网络技术实现的。 1.2 计算机网络的组成及分类 1.2.1 计算机网络的组成 通过一系列的计算机，终端和节点的计算机网络连接的节点。一般企业来说，两台计算机的连接必须经过多个网络互连设备，通常可以使用数据存储和转发方式方法进行管理信息传输。从理论上讲，计算机网络可被认为具有由两个网络资源和通信网络及其网络结构的计算机。 ·资源子网：它由主机，终端，网络外围设备，软件和信息资源组成。 任务:完成数据进行处理，提供信息资源共享和网络技术服务。 ·通信子网：由NS，通信线路和通信设备组成。也称为分组交换网络.. ·任务：完整的网络数据传输（NS负责存储，转发和路由）。 1.2.2 计算机网络的分类 计算机网络拓扑、媒体接入方式、交换方式、数据传输速度，有很多分类标准，这些分类标准，网络的一些特点，所以只反映了网络技术的性质是不好的。实际上，网络可以区分反映网络的标准技术，这可以反映在计算机网络覆盖范围的本质上。计算机网络的类型主要是局域网（lan），城市网络（man）和广域网（wan）。网络的地理覆盖范围在管理网络分类中具有重要的度量参数。不同的企业规模具有不同的网络。为了改善就业技术，计算机可以在线分类，并且可以根据中国的网络覆盖类型进行显示。在这里，我们将简要介绍这些类型的网络。 图表1-1计算机网络的种类 1.局域网 局域网（LAN）是指连接到范围从几十米到十多公里（例如办公楼或校园）的小范围内的计算机的计算机信息网络。该局的计算机网络被广泛用于连接校园，我们的计算机和工作站。LAN与其他公司网络之间差异的主要问题体现在以下三个发展方面：·网络覆盖的物理范围。 ·网络使用的传输技术。 ·网络的拓扑结构。 经常使用在LAN共享信道。换句话说，所有的机器都连接到相同的电缆。传统的LAN具有高速数据传输（高达1U 10lbps或1uu'NbpS），低可伸缩性和低错误率。新的本地网的数据进行传输发展速度能达到实现每秒千兆位以上。 2.城域网 城域网（MAX）比局域网的规模要大得多。MAN不仅包括几个办公室不远处的建筑，同时也涵盖了城市。 3.广域网 广域网（WAN）的范围更大，它能够覆盖一整个国家。在广域网中，它包含大量资源来实现系统用户可以部署的一组计算机。据报道，这些设备就像我们通常的主机所连接的通信网络。通信子网的任务是在家庭系统之间发送消息
现代计算机网络基础知识概述(doc 7页)
第一章计算机网络概论 单播、多播、广播→单播、多播、任播 计算机网络的发展 单机系统——分时多用户系统——远程终端访问系统——计算机网络系统 计算机网络的定义和功能 定义： 计算机网络是以共享资源（硬件、软件和信息等）为目的而连接起来的，在协议的控制下，由一台或多台计算机系统和若干台终端设备、数据传输设备等组成的系统的集合。 功能： 1资源共享：硬件共享软件共享信息共享 2数据传输：邮件、文件传输等 3其他：网络计算、提高系统可靠性、网络新服务等
计算机网络的分类 1按网络覆盖范围（跨度）：局域网、广域网、城域网 2按拓扑结构：（连接网络设备的物理线缆的铺设形式） 总线型、 星型、广播式 环型、 网状 局域网：总线、星型、环型 广域网：网状、星型 3按交换方式：线路（电路）交换网、报文交换网、分组交换网 第二章网络通信基本原理 通信系统的基本组成 信源、信宿、载体（信道） 信道 有线信道：能量相对集中，具有较高的传输效率【电话线、双绞线、同轴电缆、光纤】
无线信道：信号能量相对分散，传输效率低，安全性较差。【长波、中波、短波、超短波、微波】模拟信道：【电话线、双绞线】 数字信道：数字信道具有对所有频率的信号都不衰减，或者都作同等比例衰减的特点。【光纤】 信道带宽、信道容量、差错率 信道带宽和信道容量是描述信道的重要指标，由信道的物理特性所决定。 调制解调器 调制解调器是具有调制和解调功能的通信设备。调制：用模拟信号承载数字或模拟数据 （调幅、调频、调相） 编码解码器 采样、量化、编码 编码：用数字信号承载数字或模拟数据。 通信编码 1、RS-232编码【不归零码】（外同步码） 2、曼彻斯特编码（自同步码） 3、差分曼彻斯特编码（自同步码）