复杂网络第二讲网络拓扑基本模型及其性质李凯凯 规则网络 随机图 小世界网络模型 无标度网络模型 局域世界演化网络模型 模块性与等级网络 复杂网络的自相似性规则网络系统中节点及其与边的关系是固定的。（a）全局耦合网络； （b）最近邻耦合网络； （c）星形网络全局耦合网络全局耦合网络具有最小的平均路径长度Lgc =1和最大的聚类 系数Cgc =1；最近邻耦合网络最近邻耦合网络:包包含N个围成一个环的点，其中每个节点都 与它左右各K/2个邻居点相连（K为偶数），对于较大的K 值，最近邻耦合网络的聚类系数为因此，这样的网络是高度聚类的。对于固定的K值，网络平 均路径长度为星形耦合网络星形耦合网络：有一个中心点，其余N-1个点都只与这个中 心点连接，其平均路径长度为聚类系数为 随机图 随机图是与规则网络相反的网络，一个典型模型是Erdos 和Renyi于40多年前开始研究的随机图模型。假设有大量的纽扣（N1）散落在地上，并以相同的概率 p给每对纽扣系上一根线。这样就会得到一个有N个节点， 约pN(N-1)/2条边的ER随机图的实例。ER随机图的性质随机图理论的一个主要研究课题是： 当概率p为多大时，随机图会产生一些特殊的属性？ Erdos和Renyi系统地研究了当 时，ER随机图的性质与概 率p之间的关系，他们采用了如下定义： 如果当 时产生一个具有性质Q的ER随机图的概率为1，那 么就称几乎每一个ER随机图都具有性质Q。 Erdos和Renyi的最重要的发现时ER随机图具有如下的涌现或相 变性质： ER随机图的许多重要的性质都是突然涌现的。也就是说，对 于任意给定的概率p，要么几乎每一个图都具有性质Q，要 么几乎每一个图都不具有该性质。 上述纽扣网络，如果p大于某个临界值 ，那么几乎 每一个随机图都是连通的。ER 随机图的平均度是 ,平均路径长度 。LER为网络规模的对数增长函数是典 型的小世界特征。ER随机图的聚类系数是C=p=/N1 ，这意味着大规模的稀疏ER随机图没有聚类特性。实际 网络的聚类系数要比相同规模的ER随机图的聚类系数要 高得多。 ER随机图的度分布可用Poission分布来表示：因此，ER随机图也称为“Poission随机图”。小世界网络模型作为从完全规则网络向完全随机图的过渡，Watts和Strogtz于1998年引 入了一个小世界网络模型，称为WS小世界模型。其构造算法如下： 从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个 环，其中每个节点都与它左右相邻的各K/2个节点相连，K是偶数。 随机化重连：以概率p随机地重连网络中的每个边，即将边的一个端点 保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定 ，任意两个不同节点之-间至多只能有一条边，并且每一个节点都不 能有边与自身相连。P=0对应于完全规则网络，p=1对应于完全随机网络。 具有较短的平均路径长度又具有较高的聚类系数的网络就 称为小世界网络。Newman和Watts提出了NW小世界模型，用“随机化加边” 取代WS小世界模型构造中的“随机化重连”。算法如下： 从规则图开始：含有N 个节点的最近邻耦合网络。 随机化加边：以概率P在随机选取的一对节点之间加上 一条边。NW小世界模型中，p=0对应于原来的最近邻耦合网络， p=1对应于全局耦合网络。小世界网络的性质 1.聚类系数WS小世界网络的聚类系数为NW小世界网络的聚类系数为 2.平均路径长度其中f（u）为一普适标度函数，满足Newman等人基于平均场方法给出了如下近似表达式： 3.度分布 在基于“随机化加边”机制的NW小世界模型中，每个节 点的度至少为K，因此当 时，一个随机选取的 节点的度为k的概率为：而当k1.1Nrandi 。等级网络等级网络具有与网络规模无关的较高的聚类系数 ，等级模块性的一个最重要的量化标志是节点聚类系数服从幂律 。这表明度很小的节点具有较高的聚类 系数，相反度很高的节点具有低的聚类系数，其作用只是把不同的模块连接起来。ER随机图和BA无标度网络都不具有等级拓扑，在这两类网络中节点的聚类系数C（k）与该节点的度k无关。复杂网络的自相似性 等级网络看上去有一个明显的特征，就是该网络部 分与整体具有很明显的相似性，即自相似性，正是 分形的一个基本特征。 Sierpinski三角形： 复杂网络的小世界特征意味着网络的平均 路径长度l可以用网络规模N的对数函数来表 示，即 ，等价于其中L0表示特征长度，上式意味着网络规模 是网络平均路径长度的指数函数。而自相 似性要求满足某种幂律关系，然而，Song 等人的研究指出，许多实际网络，包括 WWW，蛋白质交互作用网络和细胞网络等 ，在某种长度-标度下确实是自相似的。与自相似性密切相关的一个概念是分数维，计算自 相似分形的维数的一种常用的方法是盒记数法。基 本思想是用边长为lB的盒子来覆盖该图形，并统计 完全覆盖该图形需要的最少的盒子数NB(lB)图形维数的近似计算公式为等价地有幂律标度公式 例：对于Sierpinski三角形，假设这个大三角形的 边长为1，如果用边长为1/2的正方形覆盖 Sierpinski三角形，那么需要3个正方形，如果用边 长为1/4的正方形覆盖Sierpinski三角形，需要9个 正方形，如果用边长为1/8的正方形覆盖它，则需 要27个正方形，依次类推，有以下公式： Song等人通过采用重整化过程，揭示出自 相似性和无标度分布在网络的所有粗粒化 阶段都成立，在把所有节点都分配到盒子 中之后，再把每个盒子用单个节点来表示 ，这些节点称为重整化节点，如果在两个 未重整化盒子之间至少存在一条边，那么 两个重整化节点之间就有一条边相连，这 样就得到一个新的重整化网络。这种重整 化过程可以一直进行下去，直到这个网络 被规约为单个节点。重整化网络的度分布P（k）在重整化下具有不变 性。下图显示了www的度分布在不同盒子尺寸lB重整 化下的不变性。参考文献 1Barabasi A L,Bonabeau E.Scale-free networks.Scientific American,May 2003,5059 2 Barabasi A L,Oltvai Z N.Network biology:Understanding the cells functional organization.Nature Reviews- Genetics,2004,5:101-114 3Song C,Havlin S,Makse H A.Self-similarity of complex networks.Nature,2005,433:392395