ppt—复杂网络

《ppt—复杂网络》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、复杂网络概述不同领域的真实网络社会网：演员合作网，友谊网，姻亲关系网，科研合作网，Email网生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络信息网络：WWW，专利使用，论文引用，计算机共享技术网络：电力网，Internet，电话线路网交通运输网：航线网，铁路网，公路网，自然河流网社会网络人物关系网生物网食物链网神经网络信息网络WWW网技术网络电话网交通运输网公路网航空网河流网复杂网络简而言之即呈现高度复杂性的网络。1）结构复杂：表现在节点数目巨大，网络结构呈现多种不同特征。2）网络进化：表现在节点或连接的产生与消失。例如world-widenetwork，网页或链接随时

2、可能出现或断开，导致网络结构不断发生变化。3）连接多样性：节点之间的连接权重存在诧异，且有可能存在方向性。4）动力学复杂性：节点集可能属于非线性动力学系统，例如节点状态随时间发生复杂变化。5）节点多样性：复杂网络中的节点可以代表任何事物，例如，人际关系构成的复杂网络节点代表单独个体，万维网组成的复杂网络节点可以表示不同网页。6）多重复杂性融合：即以上多重复杂性相互影响，导致更为难以预料的结果。例如，设计一个电力供应网络需要考虑此网络的进化过程，其进化过程决定网络的拓扑结构。当两个节点之间频繁进行能量传输时，他们之间的连接权重会随之增加，通过不断的学习与记忆逐步改善网络性能电力系统

3、复杂网络受到随意攻击网络图的基本概念图的基本元素：节点、边关联，邻接有限图，无限图规则图，随机图有向图，无向图度、平均度节点的度分布最短路径与平均路径长度集聚系数aedcb有向图、无向图、不连通图度(degree)：节点i的度ki定义为与该节点连接的其他节点的数目。★直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”（“能力大”）。网络的平均度：网络中所有节点的度和的平均值，记作。度分布函数p(k):随机选定节点的度恰好为k的概率节点的聚类系数（簇系数）：在简单图中，设节点v的邻集为N(v),

4、N(v)

5、=ki，则节点v的聚类系数定义为这ki个节点之间存在边数

6、Ei与总的可能边数ki(ki-1)/2之比，即：Ci=2Ei/ki(ki-1)★节点v的邻点间关系的密切程度复杂网络的统计特征网络的聚类系数C：所有节点i的聚类系数Ci的平均值。（0C1）C=0网络中所有节点都是孤立点C=1网络中任意节点间都有边相连★网络节点间联系的密切程度,体现网络的凝聚力★许多大规模的实际网络都具有明显的聚类效应。事实上，在很多类型的网络(如社会关系网络)中，你的朋友同时也是朋友的概率会随着网络规模的增加而趋向于某个非零常数，即当N→∞时，C=O(1)。这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上具有类似于社会关系网络中“物以类聚，人

7、以群分”的特性。复杂网络的统计特征18最短路径（Shortestpath）:两个节点之间边数最少的路径，最短路径的长度称为两点间的距离.平均路径长度（特征路径长度）L：所有节点对之间的距离的平均值.★研究发现：尽管许多实际复杂网络的节点数巨大，网络的平均路径长度却小的惊人。（小世界效应）复杂网络的统计特征19介数（Betweenness）★点介数：网络中通过该节点的最短路径的条数★边介数：网络中通过该边的最短路径的条数★反映了节点或边的作用和影响力。如果一对节点间共有B条不同的最短路径，其中有b条经过节点i，那么节点i对这对节点的介数的贡献为b/B。把节点i对所有节点对的贡献累加

8、起来再除以节点对总数，就可得到节点i的介数。类似的，边的介数定义为所有节点对的最短路径中经过该边的数量比例。★介数越大，说明经过该节点（边）的最短路径越多。在信息传播过程中，通过该节点（边）的信息量就越大，于是就越容易发生拥塞。★研究表明，节点介数与度之间有很强的相关性，不同类型的网络，其介数分布也大不一样。复杂网络的统计特征20网络介数★网络点介数，网络边介数：所有节点（边）的平均介数★网络介数说明了网络的什么性质？核数★一个图的k-核：反复去掉图中度小于k的节点后，所剩余的子图★若一个节点存在于k-核，而在(k+1)-核中被去掉，则此节点核数为k★节点核数中的最大值称为网络图

9、的核数★节点核数可以表明节点在核中的深度；即便一个节点的度数很高，它的核数也可能很小。例如：包含N个节点的星型网络的中心节点的度数为N-1，但它的核数为1复杂网络的统计特征三、社区结构整个网络是由若干个“社区"或“组’’构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏（网络中的顶点可以分成组,组内连接稠密而组间连接稀疏）。我们将复杂网络的这种结构特征称之为复杂网络的社团结构或社区结构。社区结构是复杂网络的一个重要的特性，社区也被称为簇，大量