当前位置：文档之家 › 复杂网络基础理论 第二章

复杂网络基础理论 第二章

  • 格式：ppt
  • 大小：1.94 MB
  • 文档页数：88

下载文档原格式

  / 88

合集下载

复杂网络理论和应用研究-PPT课件

复杂网络理论和应用研究-PPT课件

规则图的特征
平均度为3
随机图的特征

节点确定，但边以概率 p 任意连 接。 节点不确定，点边关系也不确定。
随机图——节点19，边43
平均度为2.42，集群系数为0.13。
随机图——节点42，边118
平均度为5.62，集群系数为0.133。
4. 复杂网络的演化模型
复杂网络是大量互联的节点的集合，节点 是信息的载体，比如互联网，万维网，以 及各种通信网、食物网、生物神经网、电 力网、社会经济网、科学家合作网等。 最近的研究文献揭示了复杂网络的许多重 要特性，其中最有影响的是小世界(smallworld)特性和无标度(scale-free)特性。
C
0 .1 0 7 8 0 .1 8 -0 .3 0 .7 9 0 .4 3 0 .3 2 0 .2 2 0 .2 8
C ra n d
0 .0 0 0 2 3 0 .0 0 1 0 .0 0 0 2 7 0 .0 0 0 1 8 0 .0 2 6 0 .0 6 0 .0 5
L
3 .1 3 .7 -3 .7 6 3 .6 5 5 .9 2 .9 2 .4 3 2 .6 5
b
d
e
网络(图)的基本概念

节点的度分布是指网络（图）中 ) 度为 k 的节点的概率 p ( k随节点 度 的变化规律。 k
网络(图)的基本概念


最短路径就是从指定始点到指定终点的 所有路径中总权最小的一条路经。 平均路径长度是指所有点对之间的最短 路径的算术平均值。
网络(图)的基本概念

集群系数(Clustering coefficient)反映 网络的群集程度，定义为网络的平均度 与网络规模之比。

复杂网络基础2(M.Chang)

复杂网络基础2(M.Chang)

复杂网络基础理论第二章网络拓扑结构与静态特征第二章网络拓扑结构与静态特征l2.1 引言l2.2 网络的基本静态几何特征l2.3 无向网络的静态特征l2.4 有向网络的静态特征l2.5 加权网络的静态特征l2.6 网络的其他静态特征l2.7 复杂网络分析软件22.1 引言与图论的研究有所不同，复杂网络的研究更侧重于从各种实际网络的现象之上抽象出一般的网络几何量，并用这些一般性质指导更多实际网络的研究，进而通过讨论实际网络上的具体现象发展网络模型的一般方法，最后讨论网络本身的形成机制。

统计物理学在模型研究、演化机制与结构稳定性方面的丰富的研究经验是统计物理学在复杂网络研究领域得到广泛应用的原因；而图论与社会网络分析提供的网络静态几何量及其分析方法是复杂网络研究的基础。

32.1 引言静态特征指给定网络的微观量的统计分布或宏观统计平均值。

在本章中我们将对网络的各种静态特征做一小结。

由于有向网络与加权网络有其特有的特征量，我们将分开讨论无向、有向与加权网络。

4返回目录2.2 网络的基本静态几何特征¢2.2.1 平均距离¢2.2.2 集聚系数¢2.2.3 度分布¢2.2.4 实际网络的统计特征52.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中的最大值62.2.1 平均距离平均距离（特征路径长度）L定义为所有节点对之间距离的平均值，它描述了网络中节点间的平均分离程度，即网络有多小，计算公式为对于无向简单图来说，d ij＝d ji且d ii＝0，则上式可简化为很多实际网络虽然节点数巨大，但平均距离却小得惊人，这就是所谓的小世界效应。

复杂网络基础理论

复杂网络基础理论

无标度网络
定义：无标度网络是指节点的度分布遵循幂律分布的网络即少数节点拥有大量连接大部分节点 只有少数连接。
特性：无标度网络具有高度的异质性其结构可以抵抗随机攻击但容易受到定向攻击。
构建方法：无标度网络的构建通常采用优先连接机制即新节点更倾向于与已经具有大量连接的 节点相连。
应用场景：无标度网络在现实世界中广泛存在如社交网络、互联网、蛋白质相互作用网络等。
07
复杂网络的未来研究方向和挑战
跨领域交叉研究
复杂网络与计算机 科学的交叉：研究 网络算法、网络安 全和网络流量控制 等。
复杂网络与生物学 的交叉：研究生物 系统的网络结构和 功能如蛋白质相互 作用网络和基因调 控网络等。
复杂网络与物理学 的交叉：研究网络 的拓扑结构和动力 学行为如复杂系统 、自组织系统和非 线性系统等。
复杂网络的演化过程中节点和边 的动态变化会导致网络的拓扑结 构和性质发生改变。
添加标题
添加标题
添加标题
添加标题
复杂网络具有非线性和自组织的 特性能够涌现出复杂的结构和行 为。
复杂网络在现实世界中广泛存在 如社交网络、生物网络、交通网 络等。
复杂网络的特征
节点数量巨大且具有自组织、 自相似、小世界等特性
03
复杂网络的基本理论
网络拓扑结构
节点：复杂网络中的基本单元
连通性：网络中节点之间是否存 在路径
添加标题
添加标题
添加标题
添加标题
边：连接节点的线段表示节点之 间的关系
聚类系数：衡量网络中节点聚类 的程度
网络演化模型
节点增长模型：节点按照一定概 率在网络中加入形成无标度网络
节点属性演化模型：节点属性随 时间发生变化影响网络的演化

复杂网络理论基础题

复杂网络理论基础题

复杂网络理论基础题复杂网络理论作为计算机科学和网络科学领域的重要分支，旨在研究复杂系统中的网络拓扑结构及其动态演化规律。

本文将介绍复杂网络理论的基础知识，包括网络拓扑结构、节点度分布、小世界网络和无标度网络等内容。

一、网络拓扑结构网络拓扑结构是指网络中各节点之间连接关系的模式。

最简单的网络拓扑结构是随机网络，其中每个节点以等概率与其他节点相连。

然而，在许多实际网络中，节点的连接并不是完全随机的，而是具有某种特定的模式或结构。

二、节点度分布节点度是指节点连接的边的数量，节点度分布描述了网络中不同节点度值的节点数量。

在随机网络中，节点度分布通常呈现泊松分布，即节点度相差不大。

而在复杂网络中，节点度分布往往呈现幂律分布，即存在少数高度连接的节点（大度节点），大部分节点的度较低。

这也是复杂网络与随机网络的一个显著区别。

三、小世界网络小世界网络是指同时具有较高聚集性和较短平均路径长度的网络。

在小世界网络中，节点之间的平均距离较短，通过少数的中心节点即可实现较快的信息传递。

同时，小世界网络中也存在着高度的聚集性，即节点之间存在较多的局部连接。

四、无标度网络无标度网络是指网络中节点度分布呈现幂律分布的网络。

在无标度网络中，只有少数节点具有极高的度，而大部分节点的度较低。

这些高度连接的节点被称为“超级节点”或“中心节点”，它们在网络中起到关键的作用。

五、复杂网络的动态演化复杂网络的动态演化是指网络随时间发展过程中结构和拓扑特性的变化。

常见的复杂网络动态演化模型包括BA 模型和WS 模型。

BA 模型通过优先连接原则，使具有较高度的节点更容易吸引连接，从而形成无标度网络。

WS 模型则通过随机重连机制，在保持网络聚集性的同时，增加了节点之间的短距离连接。

六、复杂网络的应用复杂网络理论在许多领域都有广泛的应用。

例如，在社交网络中，研究人们之间的联系方式和信息传播规律；在生物学领域中，研究蛋白质相互作用网络和基因调控网络；在物流和供应链中，研究供应商和客户之间的联系。

复杂网络-第二讲

复杂网络-第二讲
t m0 t
网络度分布服从指数分布
P(k )e
k m
（2）特殊情形B： M=t+m0 在这种特殊情形，每个节点的局域世界其 实就是整个网络，因此，局域世界模型就 完全等价于BA无标度网络模型。
模块性与等级网络
模块（module）与模体（motif） 模块是指一组物理上或功能上连接在一起 的、共同完成一个相对独立功能的节点。 模体可能是复杂网络的基本模块。网络的高 聚类性表明网络可能包含由高度连接的节 点构成的子图。如三角形，正方形和五角 形，其中一些子图所占的比例明显高于同 一网络的完全随机化形式中这些子图所占 的比例。这些子图就称为模体。
j
• 可见，适应度模型与BA无标度模型的区别在于，在适应度 模型中的优先连接概率与节点的度和适应度之积成正比， 而不是仅与节点的度成正比，这样，在适应度模型中，如 果一个年轻的节点具有的较高的适应度，那么该节点就有 可能在随后的网络演化过程中获取更多的边。
局域世界演化网络模型
• 在许多实际网络中，每个节点都有各自的局域世界， 研究者们建立了局域世界演化网络模型，其构造算 法如下： • ①增长：网络初始时有m0个节点和e0条边，每次 新加入一个节点和附带的m条边。 • ②局域世界优先连接：随机地从网络已有的节点中 选取M个节点（ M m ），作为新加入节点的局域 世界，新加入的节点根据优先连接概率
Local (ki ) ' (i LW )

j
ki
Local
kj

M m0 t

j
ki
Local
kj
来选择与局域世界中的m个节点相连，其中LW是 由新选择的M个节点组成。
m M m0 t ，因此上述局域世界演化网 在t时刻， 络模型有两个特殊情形：M=m和M=t+m0。 （1）特殊情形A ： M=m 这时，新加入的节点与其局域世界中所有的节点 相连接，这等价于BA无标度网络模型中只保留增 长机制而没有优先连接。此时，第i个节点的度的 ki m 变化率为

复杂网络

复杂网络

• 哈佛大学美国社会心理学家斯坦利•米尔格 伦(Stanley Milgram)在1967年实验后得出 结论：中间的联系人平均只需要5个，他把 这个结论称为“六度分离”（Six Degrees of Separation）； • 六度分离：平均只要通过5个人，你就能与 世界任何一个角落的任何一个人发生联系。 这个结论定量地说明了我们世界的”大 小”，或者说人与人关系的紧密程度； • 六度分离理论一直被作为社会心理学的经 典范例之一。

例：神经网络中的突触有强有弱，可抑制也可兴奋
网络复杂性：即系统内部和系统之间的相互作用可以
看成由节点、边（连接）构成的体系，出现网络复杂 性、小世界特征与无标度特征等。
Hale Waihona Puke 12网络系统的复杂性
（1）结构复杂性
网络连接结构错综复杂、极其混乱，同时又蕴含着丰
富的结构：社区、基序、聚集性、生成规律性等等， 而且网络连接结构可能是随时间变化的。 包括：静态结构的复杂性和结构动态演化的复杂性。 例如：互联网上每天都不停地有页面和链接的产生和 删除。
26
小世界实验 — Erdos数

Fields奖得主的Erdos数都不超过5（只有Cohen和 Grothendieck的Erdos数是5）； Nevanlinna奖得主的Erdos数不超过3（只有Valiant的 Erdos数是3）； Wolf数学奖得主的Erdos数不超过6（只有V.I.Arnold是6， 且只有Kolmogorov是5）； Steele奖的终身成就奖得主的Erdos数不超过4； 其他领域的专家：


比尔盖兹(Bill Gates)， 他的Erdos数是4，通过如下途径实现： Erdos--Pavol Hell--Xiao Tie Deng--Christos H. Papadimitriou-William H. (Bill) Gates； 爱因斯坦的Erdos数是2。

《复杂网络基础与应用》课程教学大纲

课程简介(英文)：
Complex network is a perspective and method to study complex system. It is a way to understand the nature and function of complex system by focusing on the topological structure of individual interaction in the system. Complex network research has penetrated into life science, engineering, mathematics, finance, humanities and many other disciplines. The scientific understanding of the quantitative and qualitative characteristics of complex network has become an extremely important challenge.
《复杂网络基础与应用》是计算机科学与网络工程学院各专业的博士研究生的专业课。本课程是一门研究方法类课程，为博士研究生提供研究复杂网络的具体内容、方法和工具，系统介绍复杂网络领域的基本理论框架，涵盖了复杂网络中的基本概念、网络的拓扑结构性质、小世界网络、无标度网络、社团结构、社会网络结构、博弈、传播动力学等关于复杂网络的研究。由于复杂网络研究具有很强的跨学科特色，并且新的问题和研究成果不断涌现，因此本课程重点着眼于复杂网络研究中经典的理论研究，同时介绍一些最新研究进展。旨在通过介绍复杂网络的基础理论及其应用研究，使学生掌握复杂网络的基本理论及其最新的研究进展，掌握一些相应的网络分析方法，基于复杂网络的视角来认识世界，并且能够联系实际来培养学生的系统思维以及创新意识，为博士研究生在复杂网络及其相关研究领域的研究指明方向，并通过阅读文献，了解复杂网络在相关学科的应用，为进一步的科学研究、工程应用提供理论与技术准备。

复杂网络理论及其应用课件(2011-4-13)

Complex network and its applications高忠科Apr 13, 2011Outline社团结构及其探寻算法4复杂系统与复杂网络1描述复杂网络基本统计量2小世界和无标度网络模型35复杂网络应用举例7关于复杂性关于复杂性我们所关心的问题：大量个体（更典型的是具有适应性的主体）所组成的复杂系统，在没有中心控制、非完全信息、仅仅存在局域相互作用的条件下，通过个体之间的非线性相互作用，可以在宏观层次上涌现出一定的结构和功能。

相互作用与复杂性Internet全局相互作用晶格扩散平均场什么是复杂网络？1复杂网络是对复杂系统的抽象和描述方式，任何包含大量组成单元（或子系统）的复杂系统，当把构成单元抽象成节点、单元之间的相互关系抽象为边时，都可以当作复杂网络来研究。

1复杂网络是研究复杂系统的一种角度和方法，它关注系统中个体相互关联作用的拓扑结构，是理解复杂系统性质和功能的基础。

什么是复杂网络？1Watts DJ and Strogatz SH, Nature393, 440 (1998)Citation: 4911 (Small-world network)Barabási AL and Albert R, Science286, 509 (1999)Citation: 5474（Scale-free network）1复杂网络为研究复杂系统提供了一个全新的视角，对理解真实系统的复杂行为起着重要的作用。

1复杂网络研究的兴起，广泛应用于社会学，物理统计学，经济学，控制学，工程学，生物医学等多个跨学科研究领域。

Emergence of a networked lifeAtomMoleculeCellTissueOrgans OrganismsCommunities为什么研究复杂网络？1复杂系统不能够用分析的方法去研究，必须考虑个体之间的关联和作用；1理解复杂系统的行为应该从理解系统相互作用网络的拓扑结构开始；1网络拓扑结构的信息是构建系统模型、研究系统性质和功能的基础。

复杂网络的基础知识

第二章複雜網路の基礎知識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 ji l D = （2-1） 定義網路の平均路徑長度L 為網路中所有節點對之間距離の平均值。

即∑∑-=+=-=111)1(2N i N i j ij lN N L （2-2）其中N 為網路節點數，不考慮節點自身の距離。

复杂网络理论及其应用研究概述

复杂网络理论及其应用研究概述一、本文概述随着信息技术的飞速发展，复杂网络理论及其应用研究已成为当今科学研究的热点之一。

复杂网络无处不在，从社交网络到生物网络，从互联网到交通网络，它们构成了我们现代社会的基础架构。

复杂网络理论不仅关注网络的结构和性质，还致力于探索网络的行为和演化规律，以及如何利用网络进行优化和控制。

本文旨在全面概述复杂网络理论的基本概念、主要研究方法及其在各领域的应用实践，以期为读者提供一个清晰、系统的复杂网络研究视角。

在本文中，我们首先介绍复杂网络理论的基本概念，包括网络的定义、分类和性质。

然后，我们将重点介绍复杂网络的主要研究方法，包括网络建模、网络分析、网络演化等。

在此基础上，我们将探讨复杂网络理论在各领域的应用实践，包括社交网络分析、生物网络研究、互联网拓扑结构分析、交通网络优化等。

我们将对复杂网络理论的发展趋势和未来挑战进行展望，以期为读者提供一个全面了解复杂网络理论及其应用研究的框架。

二、复杂网络理论基础知识复杂网络理论作为图论和统计物理学的交叉学科，旨在揭示现实世界中复杂系统的结构和动力学行为。

其理论基础主要源自图论、统计物理、非线性科学以及计算机科学等多个学科。

图论为复杂网络提供了基本的数学语言和描述工具。

在网络中，节点代表系统中的个体，边则代表个体之间的关系或交互。

基于图论，可以定义诸如度、路径、聚类系数、平均路径长度等关键的网络参数，从而量化网络的拓扑结构和性质。

统计物理学的概念和方法为复杂网络提供了深入分析大规模网络结构的工具。

例如，通过引入概率分布来描述网络中的节点度、路径长度等属性，可以揭示网络的全局统计特性。

网络中的相变、自组织临界性等现象也为复杂网络理论带来了新的视角和思考。

非线性科学则为复杂网络的动力学行为提供了理论支撑。

在网络中，节点之间的相互作用和演化往往是非线性的，这导致网络的动力学行为表现出复杂的时空特征。

通过研究网络的稳定性、同步性、演化机制等，可以深入理解复杂系统的动力学行为。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

17
2.2.3 度分布
任意给定常数a存在常数b使得F（x）满足F（ax）＝ bF（x）。幂律分布是唯一满足无标度条件的概率分布 函数。许多实际大规模无标度网络，其幂指数通常为 2≤γ≤3，绝大多数节点的度相对很低，也存在少量度值 相对很高的节点（称为hub），把这类网络称为非均匀 网络。 指数度分布网络： P（k）∝e−k/к，式中к＞0为一 常数。
13
2.2.2 集聚系数
下面以节点v1的集聚系数计算为例：采用第一种定 义可知，节点v1与3个节点直接连接，而这3个节点之 间可能存在的最大边数为3（3－1）／2，而实际存在 的边数为1，由此可得C1＝2／［3（3－1）］＝1／3 。 若采用第二种定义可知：与相连的三角形数为N1Δ ＝１，而与v1相连的三元组数为N1Λ＝3，故C1＝1／3 。 也可以利用式 计算，因为 邻接矩阵A的前三次幂为
24
2.3.1 联合度分布和度－度相关性
式中，ki，kj分别表示边eij的两个节点vi，vj的度，M 表示网络的总边数。 容易证明度－度相关系数r的范围为：0≤|r|≤1。 当r<0时，网络是负相关的；当r>0时，网络是正相关 的；当r＝0时，网络是不相关的。
25
2.3.2 集聚系数分布和聚－度相关性
23
2.3.1 联合度分布和度－度相关性
所有度值为k的节点的最近邻平均度值的平均值knn （k）定义为 式中，N为节点总数，P（k）为度分布函数。 如果knn（k）是随着k上升的增函数，则说明度值 大的节点倾向于和度值大的节点连接，网络具有正相 关特性，称之为同配网络；反之网络具有负相关特性 ，称之为异配网络。 3.基于Pearson相关系数的度－度相关性 Newman利用边两端节点的度的Pearson相关系数 r来描述网络的度－度相关性，具体定义为
16
2.2.3 度分布
2.度分布 大多数实际网络中的节点的度是满足一定的概率 分布的。定义P（k）为网络中度为k的节点在整个网络 中所占的比率。 规则网络：由于每个节点具有相同的度，所以其 度分布集中在一个单一尖峰上，是一种Delta分布。 完全随机网络：度分布具有Poisson分布的形式， 每一条边的出现概率是相等的，大多数节点的度是基 本相同的，并接近于网络平均度＜k＞，远离峰值＜k ＞，度分布则按指数形式急剧下降。把这类网络称为 均匀网络。 无标度网络：具有幂指数形式的度分布：P（k） ∝k−γ 。所谓无标度是指一个概率分布函数F（x）对于
2.3.1 联合度分布和度－度相关性
联合节点度分布所包含的拓扑信息最多，节点度 分布次之，平均节点度最少。 2.基于最近邻平均度值的度－度相关性 度－度相关性描述了网络中度大的节点和度小的 节点之间的关系。若度大的节点倾向于和度大的节点 连接，则网络是度－度正相关的；反之，若度大的节 点倾向于和度小的节点连接，则网络是度－度负相关 的。 节点vi的最近邻平均度值定义为 式中，ki表示节点vi的度值，aij为邻接矩阵元素。
11
2.2.2 集聚系数
如何根据无向无权简单图的邻接矩阵A来求节点vi 的集聚系数Ci？ 显然，邻接矩阵二次幂A2的对角元素 表示的是 与节点vi相连的边数，也就是节点vi的度ki。而邻接矩 阵三次幂A3的对角元素 ＝∑（aij· ajl· ali）（j≠l）表示 的是从节点vi出发经过三条边回到节点vi的路径数，也 就是与节点vi相连的三角形数的两倍（正向走和反向走 ）。因此，由集聚系数的定义可知
1.集聚系数分布 集聚系数分布函数P（C）表示从网络中任选一节 点，其集聚系数值为C的概率
式中，δ（x）为单位冲激函数。 2.聚－度相关性 局部集聚系数C（k）定义为度为k的节点的邻居之 间存在的平均边数＜Mnn（k）＞与这些邻居之间存在 的最大可能的边数的比值，即
26
2.3.2 集聚系数分布和聚－度相关性
2.3.3 介数和核度
1.介数 要衡量一个节点的重要性，其度值当然可以作为 一个衡量指标，但又不尽然，例如在社会网络中，有 的节点的度虽然很小，但它可能是两个社团的中间联 络人，如果去掉该节点，那么就会导致两个社团的联 系中断，因此该节点在网络中起到极其重要的作用。 对于这样的节点，需要定义另一种衡量指标，这就引 出网络的另一种重要的全局几何量——介数。 介数分为节点介数和边介数两种，反映了节点或 边在整个网络中的作用和影响力。
全局集聚系数C则定义为
式中，＜k2＞为度的二阶矩。 显然，局部集聚系数C（k）与k的关系刻画了网络 的聚－度相关性。许多真实网络如好莱坞电影演员合 作网络、语义网络中节点的聚－度相关性存在近似的 倒数关系C（k）∝k−1 。把这种倒数关系的聚－度相关 性称为层次性，把具有层次性的网络称为层次网络。
27



2.2.4 实际网络的统计特征
5
2.2.1 平均距离
1.网络的直径与平均距离 网络中的两节点vi和vj之间经历边数最少的一条简 单路径（经历的边各不相同），称为测地线。 测地线的边数dij称为两节点vi和vj之间的距离（或 叫测地线距离）。 1／dij称为节点vi和vj之间的效率，记为εij。通常 效率用来度量节点间的信息传递速度。当vi和vj之间没 有路径连通时，dij＝∞，而εij＝0，所以效率更适合度 量非全通网络。 网络的直径D定义为所有距离dij中的最大值
2.距离与邻接矩阵的关系 定义
对于无权简单图来说，当l＝1时， 。容易证明无 权简单图邻接矩阵A的l次幂Al的元素 表示节点vi和vj 之间通过l条边连接的路径数。当l＝2时，容易推出 式中，U表示单位指示函数，即当x＞0，U（x）＝1； 否则U（x）＝0。当i＝j时，δij＝1；否则δij＝0。
8
19
2.2.4 实际网络的统计特征
返回 目录
20
2.3 无向网络的静态特征
ቤተ መጻሕፍቲ ባይዱ
2.3.1 联合度分布和度－度相关性 2.3.2 集聚系数分布和聚－度相关性 2.3.3 介数和核度 2.3.4 中心性 2.3.5 网络密度





2.3.6 连通集团（子图）及其规模分布
21
2.3.1 联合度分布和度－度相关性
28
2.3.3 介数和核度
节点的介数Bi定义为
式中，Njl表示节点vj和vl之间的最短路径条数，Njl（i ）表示节点vj和vl之间的最短路径经过节点vi的条数。 边的介数Bij定义为
式中，Nlm表示节点vl和vm之间的最短路径条数，Nlm （eij）表示节点vl和vm之间的最短路径经过边eij的条数 。
12
2.2.2 集聚系数
【例2.1】计算下面简单网络的直径、平均距离和各节 点的集聚系数。
解：首先计算出所有节点对的距离：d12＝1；d13＝1； d14＝2；d15＝1；d16＝2；d23＝1；d24＝1；d25＝2； d26＝2；d34＝2；d35＝2；d36＝1；d45＝3；d46＝1； d56＝3。由此可得直径和平均距离为
3
2.1 引言
静态特征指给定网络的微观量的统计分布或宏观 统计平均值。 在本章中我们将对网络的各种静态特征做一小结 。由于有向网络与加权网络有其特有的特征量，我们 将分开讨论无向、有向与加权网络。
返回 目录
4
2.2 网络的基本静态几何特征

2.2.1 平均距离 2.2.2 集聚系数 2.2.3 度分布
30
2.3.3 介数和核度
3.核度 一个图的k－核是指反复去掉度值小于k的节点及 其连线后，所剩余的子图，该子图的节点数就是该核 的大小。 若一个节点属于k－核，而不属于（k＋1）－核， 则此节点的核度为k。 节点核度的最大值叫做网络的核度。 节点的核度可以说明节点在核中的深度，核度的 最大值自然就对应着网络结构中最中心的位置。k－核 解析可用来描述度分布所不能描述的网络特征，揭示 源于系统特殊结构的结构和层次性质。
18
2.2.3 度分布
3.累积度分布 可以用累积度分布函数来描述度的分布情况，它 与度分布的关系为 它表示度不小于k的节点的概率分布。 若度分布为幂律分布，即P（k）∝k−γ，则相应的 累积度分布函数符合幂指数为γ－1的幂律分布
若度分布为指数分布，即P（k）∝e−k/к，则相应 的累积度分布函数符合同指数的指数分布
14
2.2.2 集聚系数
故
＝2，
＝3，从而
同理可得其他各节点的集聚系数为 C2＝1／3；C3＝1／3；C4＝0；C5＝0；C6＝0 由此很容易算出该网络的集聚系数
15
2.2.3 度分布
1.节点的度 在网络中，节点vi的邻边数ki称为该节点vi的度。 对网络中所有节点的度求平均，可得到网络的平 均度＜k＞ 无向无权图邻接矩阵A的二次幂A2的对角元素 就是节点vi的邻边数，即 。实际上，无向无权图 邻接矩阵A的第i行或第i列元素之和也是度。从而无向 无权网络的平均度就是A2对角线元素之和除以节点数 ，即＜k＞＝tr（A2）／N。式中，tr（A2）表示矩阵 A2的迹，即对角线元素之和。
29
2.3.3 介数和核度
2.介数分布和介－度相关性 节点的介数与度之间有很强的相关性，而且不同 类型的网络，其介数分布也大不一样。 介－度相关性可以用B（k）～k表示，它定义为所 有度为k的节点的介数平均值随着k的变化关系。 节点介数分布Pv（B）定义为网络中节点介数为B 的节点数占网络节点总数的比例。 边介数分布Pe（B）定义为网络中边介数为B的边 数占网络总边数的比例。 研究表明，节点的最大介数与网络的同步能力密 切相关：节点的最大介数越大，网络的同步能力越弱 。
6
2.2.1 平均距离
平均距离（特征路径长度）L定义为所有节点对之 间距离的平均值，它描述了网络中节点间的平均分离 程度，即网络有多小，计算公式为
对于无向简单图来说，dij＝dji且dii＝0，则上式可 简化为
很多实际网络虽然节点数巨大，但平均距离却小 得惊人，这就是所谓的小世界效应。