转载

复杂网络介绍

温馨提示:
本文最后更新于 2021年12月08日,已超过 163 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

复杂网络研究的历史

网络,数学上称为图,最早研究始于1736年欧拉的哥尼斯堡七桥问题,但是之后关于图的研究发展缓慢,直到1936年,才有了第一本关于图论研究的著作。

随着研究的深入,越来越多关于复杂网络的性质被发掘出来,其中很重要的一项研究是2002年Girvan和Newman在PNAS上的一篇文章《Community structure in social and biological networks》,指出复杂网络中普遍存在着聚类特性,每一个类称之为一个社团(community),并提出了一个发现这些社团的算法。从此,人们对复杂网络中的社团发现问题进行了大量研究,并产生了大量的算法。

网络研究的历史的总结

  • 1736,欧拉:哥尼斯堡七桥Euler 开启了数学图论
  • 抽象为顶点与边的集合图论是网络研究的基础
  • 网络结构是理解复杂世界的关键
  • 1950, Erdos, Renyi: 随机图论
  • 1998, Strogatz; 
  • 1999, Barabasi: 小世界和无标度网络

网络的复杂性体现在

  • 结构复杂性
  • 节点复杂性
  • 结构与节点之间的相互影响
  • 网络之间的相互影响

网络科学的主要研究内容

  • 发现。揭示刻画网络系统结构的拓扑性质,以及度量这些性质的合适方法
  • 建模。建立合适的网络模型以帮助人们理解这些统计性质的意义与产生机理
  • 分析。基于单个节点的特性和整个网络的结构性质分析与预测网络的行为
  • 设计。提出改善已有网络性能和设计新的网络的有效防范
  • 从网络科学到网络工程

网络的静态几何量和统计性质

度、聚集系数、最短路径、介数、权、相关性

网络上的聚类分析

  • 对网络结构的描述——几何量及其分布
  • 度(Degree):朋友的个数
  • 集聚系数(群系数)(Clustering coefficient):朋友的朋友还是不是朋友的情况
  • 最短路径(Shortest path):两个顶点之间边数最少的路径
  • 介数(Betweenness):经过我的最短路径的条数

网络的演化性质和机制模型

  • 时间演化性质,偏好性的检验
  • Small World Network , Scale Free Network-BA 模型
  • 网络的结构与功能
  • 网络的容错与抗攻击能力
  • 网络上的动力学性质

复杂网络的4种结构

规则网络

随机网络

  • 度分布:Poisson 分布
  • 齐次特征:每个节点大约有相同的连接数
  • 节点数不增加

小世界网络

  • 齐次性:每个节点有大约相同的连接数
  • 节点数不增加

无标度网络

  • 度分布:Power Law Degree Distribution(幂律度分布)
  • 非齐次性
  • 很少的节点有很多连接,很多节点只有很少的连接
  • 节点数增加

同向匹配&反向匹配

如果网络中度值高的顶点倾向于与其他高度值的顶点相互连接,则称网络具有同向匹配性质;
例如:社会网络
如果网络中度值高的顶点倾向于与度值低的顶点相互连接,则称网络具有反向匹配性质;
例如:大部分生物、技术网络

复杂网络中的社团结构

社团内部连接紧密,社团之间连接相对稀疏
网络模体---Network Motifs 模体——在网络中密度明显较高的子图(基 本结构单元)
网络的结构与功能

网络上的动力学行为和过程

动力系统:自旋、振子或混沌的同步、可激发系统…
传播过程:信息传播与拥堵、网络搜寻、运输过程、疾病传播、谣言的传播、舆论形成…
博弈与其他社会行为:囚徒困境、少数者博弈…
其他过程:电力网的级联失效等…

不同领域的复杂网络

  • 社会网:演员合作网,朋友网,姻亲关系网,科研合作网
  • Email网,短信网…
  • 生物网:食物链网,神经网,新陈代谢网,蛋白质网,基因网络…
  • 信息网络: WWW,专利使用,论文引用, …
  • 技术网络:电力网, Internet,电话线路网 ...
  • 交通运输网:航线网,铁路网,公路网,自然河流网
  • 经济系统:投入产出网,国际贸易网
正文到此结束
该篇文章的评论功能已被站长关闭