西安电子科技大学：《复杂网络与群体智能》课程教学课件（研究生）第二讲 复杂网络的基本概念

历安毛子代枚大兽 第二讲：基本概念与结构模型 XIDIAN UNIVERSITY >基本概念 (1)网络的图表示 (2)节点的聚类系数 (3)节点的介数 (4) 平均度和度分布 >结构模型 (1)小世界网络 (2)无标度网络 (3)社区网络 2

基本概念 （1）网络的图表示 （2）节点的聚类系数 （3）节点的介数 （4）平均度和度分布 结构模型 （1）小世界网络 （2）无标度网络 （3）社区网络 第二讲：基本概念与结构模型 2

历些毛子种枝大学 第二讲：基本概念 XIDIAN UNIVERSITY 1. 网络的图表示 无向网络与有向网络：如果网络中的边是没有方向的，e,与e是同一条边 (a) (b Pkdl Nppc Fosll Apexl Mapkl Rhoa Calca Glplr Jund Junb iun Ccna2 Nr4al Vgf Grinl Il6 Timpl Th Fnl Dbh Mmp3 Mmp13 Sst Ccnal The gene regulatory network of TF family APl in rat 3

1. 网络的图表示 第二讲：基本概念 3 3 1 2 4 5 (b) 3 1 2 4 5 (a) Ccna2 Nr4a1 Vgf Grin1 II6 Timp1 Th Fn1 Dbh Mmp3 Mmp13 Sst Ccna1 Pkd1 Nppc Fosl1 Apex1 Mapk1 Rhoa Calca Glp1r 92 Jund Junb Jun Fos The gene regulatory network of TF family AP1 in rat. 3 1 2 4 5 (c) 无向网络与有向网络: 如果网络中的边是没有方向的，eij与eji是同一条边

面些毛子种枚大票 第二讲：基本概念 XIDIAN UNIVERSITY 1. 网络的图表示 无权网络与加权网络：()无权网络；(b)加权网络。 a b 二分网络。网络中的节点也可以有不同的类型，比如描述网上销售 行为的网络，一类节点是消费者（购买者），另一类节点则是商品。 一个消费者购买过一种商品，则它们之间有一条连边，这样的网络 称为二分网络。二分网络中同类节点之间没有连边

1. 网络的图表示 第二讲：基本概念 4 3 1 2 4 5 (a) 无权网络与加权网络：(a) 无权网络；(b) 加权网络。 3 1 2 4 5 0.8 1.2 1.1 0.9 0.9 (b) 二分网络。网络中的节点也可以有不同的类型，比如描述网上销售 行为的网络，一类节点是消费者（购买者），另一类节点则是商品。 一个消费者购买过一种商品，则它们之间有一条连边，这样的网络 称为二分网络。二分网络中同类节点之间没有连边

历些毛子代枝大学 第二讲：基本概念 XIDIAN UNIVERSITY 1. 网络的图表示 邻接矩阵。网络的连接关系也可以用一个N×N的矩阵A=[a,]表示，称为邻接 矩阵。如果节点y有到节点v,的连边，则a,=1,否则a,=0。对无向网络，邻接 矩阵一定是对称的，而且其主对角线一定为零；对无向网络而言，邻接矩阵 一般是非对称的。 (a) 00 0 0 1 01 A= 0 1 1 00 100 1 0 100 5

1. 网络的图表示 第二讲：基本概念 5 3 1 2 4 5 (a) 邻接矩阵。网络的连接关系也可以用一个N×N的矩阵A=[aij]表示，称为邻接 矩阵。如果节点vi有到节点vj的连边，则aij=1，否则aij=0。对无向网络，邻接 矩阵一定是对称的，而且其主对角线一定为零；对无向网络而言，邻接矩阵 一般是非对称的

面些毛子种枚大票 第二讲：基本概念 XIDIAN UNIVERSITY 1. 网络的图表示 图的连通性。在一个有向图G中，如果存在从节点y,到节点y,的路径，则称y 和y是连通的。如果图中任意两点都是连通的，那么这个图是连通图。如果G 是无向图，如果存在从节点v,到节点y的路径，那么也必然存在从y,到y,的路径。 强连通图：对于有向图G,若对于任意两个不同的节点y,和y,都存在从v到y 以及从v,到y,的路径，则称G是强连通图。 弱连通图：对于有向图G,将所有的有向边替换为无向边，所得到的图称为 原有向图的基图。如果一个有向图的基图是连通图，则该有向图是弱连通图。 (c) 问题：左图是强连通图还是弱连通图？ 6

1. 网络的图表示 第二讲：基本概念 6 图的连通性。在一个有向图 G 中，如果存在从节点vi到节点vj的路径，则称vi 和vj是连通的。如果图中任意两点都是连通的，那么这个图是连通图。如果G 是无向图，如果存在从节点vi到节点vj的路径，那么也必然存在从vj到vi的路径。 强连通图：对于有向图 G，若对于任意两个不同的节点vi和vj，都存在从vi到vj 以及从vj到vi的路径，则称 G是强连通图。 弱连通图：对于有向图 G，将所有的有向边替换为无向边，所得到的图称为 原有向图的基图。如果一个有向图的基图是连通图，则该有向图是弱连通图。 3 1 2 4 5 (c) 问题：左图是强连通图还是弱连通图？

历要毛子种技大” 第二讲：基本概念 XIDIAN UNIVERSITY >平均路径长度L 。} 两个节点之间的距离。假定d表示任意两个节点y,与y,的距离，两个节点 之间通常有多条边，每条路径的距离长度通常也不同，d,指的是y,与y,之 间最短路径的距离。 ·网络直径。d在整个网络的最大值称为网络的直径。 假定每条边的距离都是1，则距离d,就是这两个节点之间最短路径上边的 个数。简单地说，要计算网络直径，可利用遍历的方法计算每个节点到 其他节点的最短路径，则其最大值就是网络直径。 7

平均路径长度L • 两个节点之间的距离。假定dij表示任意两个节点vi与vj的距离，两个节点 之间通常有多条边，每条路径的距离长度通常也不同，dij指的是vi与vj之 间最短路径的距离。 • 网络直径。dij在整个网络的最大值称为网络的直径。 • 假定每条边的距离都是1，则距离dij就是这两个节点之间最短路径上边的 个数。简单地说，要计算网络直径，可利用遍历的方法计算每个节点到 其他节点的最短路径，则其最大值就是网络直径。 第二讲：基本概念 7

历些毛子种找大学 第二讲：基本概念 XIDIAN UNIVERSITY >平均路径长度L 平均路径长度。网络的平均路径长度是网络中两个节点之间路径长度d,对 整个网络的平均，即： Ezidy L=NN-)/2 。 式中的分子是对所有节点对之间的距离求和，分母是网络中节点对的个 数。 8

平均路径长度L • 平均路径长度。网络的平均路径长度是网络中两个节点之间路径长度dij对 整个网络的平均，即: • 式中的分子是对所有节点对之间的距离求和，分母是网络中节点对的个 数。 第二讲：基本概念 8

历些毛子代枝大学 第二讲：基本概念 XIDIAN UNIVERSITY >网络密度 节点的度：对于无向网络，一个节点的度是与其相连的边的数目 k=%1a 对于有向网络，还有出度和入度之分。出度：该节点指向其它节点的边 数；入度：其它节点指向该节点的边数。有向网络的度是出度与入度之 和。 平均度。网络中所有节点的度的平均值称为网络节点的平均度，记为<k~。 网络密度。网络密度是网络中存在的边数与可能存在的最大边数的比值。 对于一个节点数为W的无向网络，可能存在的最大边数为W(N-1)/2,已存 在边数为E,则网络密度为： 2M D=- (N-1) 对于节点数为N的有向网络，可能存在的最大有向边数为N(N-1),已存在 有向边数为ME,则网络密度为： M D= 9 N(W-1)

第二讲：基本概念 9 网络密度 节点的度：对于无向网络，一个节点的度是与其相连的边的数目 对于有向网络，还有出度和入度之分。出度：该节点指向其它节点的边 数；入度：其它节点指向该节点的边数。有向网络的度是出度与入度之 和。 平均度。网络中所有节点的度的平均值称为网络节点的平均度，记为。 网络密度。网络密度是网络中存在的边数与可能存在的最大边数的比值。 对于一个节点数为N的无向网络，可能存在的最大边数为N(N-1)/2，已存 在边数为M=|E|, 则网络密度为： 对于节点数为N的有向网络，可能存在的最大有向边数为N(N-1)，已存在 有向边数为M=|E|，则网络密度为：

历安毛子代枚大学 第二讲：基本概念 XIDIAN UNIVERSITY >度分布 度分布。度分布是指网络中具有各种度值的节点数目分布情况，也可以 理解成任意给定一个节点y。它的度k,等于k的概率。度分布通常用度函数 P(k)来表示。ER随机网络的度分布是泊淞(Poisson)分布，即： 入k P(k:=内=Ge 可以看到随着度的增大，其存在的概率是指数下降的。图()为一个由ER 随机图模型(N=5000,p=0.003)生成的服从泊淞分布(1=Np=15)的度分布图。 (a600 (b)800 500 600 400 300 400 200 200 100 10 0 10 20 30 10 20 30 40

第二讲：基本概念 10 度分布 度分布。度分布是指网络中具有各种度值的节点数目分布情况，也可以 理解成任意给定一个节点vi , 它的度ki等于k的概率。 度分布通常用度函数 P(ki )来表示。ER随机网络的度分布是泊淞(Poisson)分布，即： 可以看到随着度的增大，其存在的概率是指数下降的。图(a)为一个由ER 随机图模型(N=5000,p=0.003)生成的服从泊淞分布(λ=Np=15)的度分布图。 0 10 20 30 0 100 200 300 400 500 600 k 对应度k处节点的数量 (a) (b) 10 20 30 40 0 200 400 600 800 k 对应度处节点的数量

历安毛子代枚大等 第二讲：基本概念 XIDIAN UNIVERSITY >度分布 度分布。然而，近几年来的研究发现，在许多实际网络中随着度的增加， 节点存在的概率不是指数下降的，度分布不是服从泊淞分布，而是服从幂 律分布，即： P(k:=k)kY 按照幂律分布，随着度的增加其节点存在的概率下降要比指数下降缓慢的 多。图(b)为一个由社区网络模型（N=5000,y=2)生成的服从幂律分布的度 分布图。(@600 (b)800 500 600 400 200 100 10 20 30 10 20 k30 40

第二讲：基本概念 11 度分布 度分布。然而，近几年来的研究发现，在许多实际网络中随着度的增加， 节点存在的概率不是指数下降的，度分布不是服从泊淞分布，而是服从幂 律分布，即： 按照幂律分布，随着度的增加其节点存在的概率下降要比指数下降缓慢的 多。图(b)为一个由社区网络模型（N=5000,γ=2）生成的服从幂律分布的度 分布图。 0 10 20 30 0 100 200 300 400 500 600 k 对应度k处节点的数量 (a) (b) 10 20 30 40 0 200 400 600 800 k 对应度处节点的数量