2 复杂网络的统计指标及典型模型介绍
2.1复杂网络的定义
当观察一张渔网时可以发现整张渔网是由一条条的绳子和一个个由绳子打成的结扣组成的,这便是人们最早认知的网络的样子。把绳子和结扣抽象成为边集ECG)和节点集那么渔网便形成了一个网络G = (y,£0。£(G)中的每条边e;都有中的一对节点0;, Vy)与其一一对应。如果任意的节点对口y)与对应的是不同的边,那么这个网络称为有向网络,否则称为无向网络。如果给网络中所有的边加上不同的数值(权值),那么这个网络就叫做加权网络,否则称为无权网络。实际上,无权网络可以看作是边权值相等的加权网络的特例。邻接矩阵是使用计算机研宄相关网络时一种很好的表示方法。对于图G = (V,E),可以用一个矩阵>1 = 表示,其中《是图中所有节点个数,a表示节点之间的连边。如果节点i与节点j之间有边连接,则令.,否则aiy = 0。在加权图中,若边e;的权值为W;,那么令aiy=w;,如果节点与节点y之间没有边连接,则令边e;的权值W;权值为无穷大。即从节点/要经过无穷多步才能到达节点。不难看出无向网络的邻接矩阵是一个对称矩阵,无权网络的邻接矩阵是一个(0,1)矩阵,而大部分网络的邻接矩阵是一个稀疏矩阵。现实中的网络无处不在,例如人与人之间的社会关系网络,生态系统中各种物种之间的捕食关系网络,网站中网页之间的超链接网络等等。这些网络是真真实实在我们身边我们能感受到的,但是由于这些网络节点关系错综复杂性,它们又是最难以捕捉到和难以分析的。我们把这些网络称为复杂网络。通过观察和简单的分析,可以获知这些复杂网络都有着如下的特性:
1.网络的大规模性,网络中节点的数量是非常庞大的,可以有成牛上万,甚至会更多;
2.网络连接的稀疏性,虽然网络中节点的数目庞大,但连边的数量却相对稀疏,一个含有N个节点的全稱合网络的连边数目为OCiV2),而现实中的大型网络边的数目仅为0(AO;
3.连接结构的复杂性,网络中节点的连接结构会随着时间的变化而变化,网络中节点间的连边会有不同的方向和权值,例如连接各个神经节点的突触有兴奋有抑制、刺激有强有弱并且有刺激传导具有方向性;
4.节点的复杂性,网络中会存在不同类型的节点,例如互联网中会有计算机和路由器两种节点;
5.网络与网络之间也会存在相互联系和影响,网络是各种复杂因素相互作用的结果,例如电力网络的故障可能会导致计算机网络传输速度变慢、交通瘫疾、运输系统失去控制等。为了研宄这些网络的特性以及更好的利用复杂网络这些特性为人类服务,学者们提出了不同的建模方法来模拟真实网络,提出了平均路径长度、聚类系数、度与度分布、网络弹性等指标来验证所建网络的优劣,下面论文将详细的介绍这些统计指标和网络模型。
2.2复杂网络的统计指标
2.2.1平均路径长度
网络中连接节点/和节点y之间的所有路径中最短的路径经过的边的数量称为这两个节点间的距离,记作其中网络的直径定义为的最大值,记作D。网络的平均路径长度定义为的平均值,记作:
2复杂网络的统计指标及........................................7
2.1复杂网络的定义......................................7
2.2复杂网络的统计......................................8
2.3复杂网络的典型模型......................................11
3基于社团和分层结构的......................................18
3.1建模思想......................................18
3.2建模方法......................................20
4算法实验与性能......................................27
4.1实验环境......................................27
4.2模型度分布分析......................................27
5CHEN模型改进......................................41
5.1针对网络脆弱性的模型......................................41
6总结与展望
6.1 总结
首先,本文将节点赋予权值,优先连接时同时考虑节点的度和节点的权值,在选择节点时采用转轮思想,这样既保证了优先连接概率大的节点获得新节点的机会大,又保证了优先连接概率小的节点有机会获得新节点,在优先的基础上兼顾公平原则。其次,设定度饱和值Kma;c,当节点的度达到度饱和值时便停止演化,这进一步弱化了超级节点的出现,能使网络更好的抵御外界的蓄意攻击。
再次,CHEN模型改善了局域世界模型中随机选择M个节点作为局域世界加入的规则,这个规则的缺陷是每次产生的局域世界都是随机选择节点组成的,每次产生的局域世界都存在极大的不确定性,无法真正体现网络中的局域世界。CHEN模型在考虑节点加入的同时考虑了社团的加入,这样新节点在加入时先选择一个社团加入,一个社团即为一个局域世界,解决了局域世界模型中局域世界不确定性的问题。
另外,在加入节点和社团的基础上又考虑了删除节点,这充分体现了真实网络的动态演化规则是复杂多样的。最后,本文在第一层网络的基础上提取出每个社团中度大的节点作为Hub节点映射到上层网络中,上层Hub节点是下层Node节点的复制影像,在上层中采用全连接形式存储,形成一个虚拟层,上层网络不影响下层网络的性质。Hub节点拥有本社团内所有节点的信息,在搜索时只需在上层网络中查找即可,当找到目的节点所在的社团后再返回下层寻找,这样将节点的搜索由整个网络缩小为一个社团,提高了搜索的效率。通过理论分析和实验验证,可以得出新建模型的社团规模分布和度分布服从幂律分布,可以将其看作无标度网络模型。将CHEN模型与BA模型的统计指标I作对比得出:(l)CHEN模型的平均路径长度略大于BA模型,从图像上可以看出两者差距的数量级为10人即小于一步的差距,由于在路由搜索时所经过的节点数为整数,故此差距在搜索所经过的步数上可以忽略,并且CHEN模型的平均路径可以通过改变p3等参数值来改善;(2)CHEN模型的聚类系数明显大于BA模型,这与真实网络的聚类系数往往较大的特点相符(电影演员合作网C = 0.78,数学家.