精华内容
下载资源
问答
  • 复杂网络建模总结

    千次阅读 2020-10-27 23:29:38
    本文针对数学建模美赛中的复杂网络题,做了一些总结,具体涉及一些该题的注意事项。 注意事项 定义点和边的意义 制定连接规则,删除孤立节点(代表影响很小的点),可以限制网络的大小,减小运算量,同时也可以...

    本文针对数学建模美赛中的复杂网络题,做了一些总结,具体涉及一些该题的注意事项。

    注意事项

    1. 定义点和边的意义
    2. 制定连接规则,删除孤立节点(代表影响很小的点),可以限制网络的大小,减小运算量,同时也可以克服PageRank的不足点
    3. 网络根据有向/无向,有环/无环,有/无标度,可以根据其性质,制定不同的算法,简化传统的算法
    4. 常用度量的指标:度,中心性,聚类系数,密度,中介性Degree, Centrality, Clustering coefficient,  Density,  Betweenness一定要将各种指标联系实际,分析每种情况的特性
    5. 结合现实考虑,即使简化了也要表明出来
    6. 除了重要性,还应该考虑节点的权威性(如时间)等现实因素
    7. 考虑节点的时间因素,现实中的一切都是因果的,比如引用模型中,只能引用比自己先发表的论文,而且此时满足偏序关系
    8. 注意关系的自反性、对称性、传递性
    9. 关系网络:相容关系、等价关系、偏序关系;对分析出来的关系做说明,即使没有什么用也可以说明,来体现对该网络性质的研究
    10. 对网络关系性质的分析也是一个重点,网络的性质和建立网络的规则有关,规则又是由实际的问题情况决定
    11. 网络的稳定性探究也是很重要的一点,可以分析参数对排序或者其他结果的影响,还可以考虑节点缺失对网络造成的影响
    12. 拥有关系和引用关系类似
    13. 对于性质类似的网络,对不同问题采用不同的量化方法,制定规则量化为适合模型的值,使得模型可以推广
    14. 对于一道题搭了几个网络,可以将这几个网络的性质进行对比分析,最好还能说出各自的用途
    15. 扩散可以用到矢量分析与场论的知识,用梯度、散度、旋度来分析
    16. 传染病模型也经常用在网络题里面
    17. 1959年,汉森首次提出了交通可达性的概念,这被定义为接受道路网络中节点之间相互作用的机会。
    18. 可以自己定义算法,把边的权重转换到点上,这样就可以使用修正的PageRank算法求解点的重要性

    使得初始时点的权重为1,但是每条边的传递权重不同,而其邻接边的权重相加仍然为1(参考2014C--25318

     

    编程和图表

    1. 对于外行难懂的复杂网络图,最好给出图的解释,各种东西代表什么
    2. 对自己定义的网络规则最好用图来展示一下
    3. 复杂网络考虑计算复杂度,特别是在有改进的情况下说明复杂度的改善
    4. 网络有很重要的一点就是测试其稳定性

    数据预处理

    1. 复杂网络的题也常常涉及大数据,对于空白数据的处理很重要,对于空缺太多的数据直接删掉
    2. 接着对剩余数据处理;或者通过聚类,被聚类到一起的点,空缺数值可以用该类中数值完整的值的均值和方差来生成;最常用的就是插值,不过没有什么亮点
    3. C/D题,数据支撑和合理性很重要
    4. 归一化、标准化、中心化特别重要,记得说明各自的意义

    ​​​​​​​过程

    1. 一开始建立各项指标,用数据对属性进行描述,为数据预处理提供依据。同时这些指标的分类不同,可能作用于底层网络或者顶层网络,可能是节点指标也可能是边的指标(可以给边加权,可以给点加权注意两种网络的适用算法不同)
    2. 接着设置算法,选择算法;结合实际的问题,分析其是否有什么不合理的地方,对于不合理的地方想一想改进的措施
    3. 必要时考虑一下计算复杂度,考虑是否改善,对复杂度改善后可以使用原算法来验证正确性;考虑是否有可以用来类比的模型
    4. 建立好静态的网络结构之后,接下来就是要确定规则(类似于仿真规则),使网络变成动态模型
    5. 网络的改善就是不停对规则进行更改
    6. 注意模型建立好之后先验证合理性,再应用​​​​​​​

    一般情况都用双层网络,既不会过于简单,也不会计算量太大

    相关性很强(同一地区、同一背景等)的各集团作为高一层的节点,底层的网络由各个单独的节点构成

    采用双层网络模型有两种思路:

    1、先手动根据节点的某种/某些相似性把一些满足相似性的节点规定为一个集团,各个集团作为上层网络的节点

    2、直接所有节点一视同仁,然后用节点划分的方法,对网络进行分割,分割后每个集团作为底层网络,然后更改边的类型,集团内保持不变,集团间建立新的连接方式

    灵敏性/稳健性分析

    1. 研究网络是否是无标度性。(有些结论已经有了,比如社交网络就是无标度,先了解背景,如果没有研究文献再自己计算)其实复杂网络的无标度特性与网络的鲁棒性分析具有密切的关系。无标度网络中幂律分布特性的存在极大地提高了高度数节点存在的可能性,因此,无标度网络同时显现出针对随机故障的鲁棒性和针对蓄意攻击的脆弱性。这种鲁棒且脆弱性对网络容错和抗攻击能力有很大影响。研究表明,无标度网络具有很强的容错性,但是对基于节点度值的选择性攻击而言,其抗攻击能力相当差,高度数节点的存在极大地削弱了网络的鲁棒性,一个恶意攻击者只需选择攻击网络很少的一部分高度数节点,就能使网络迅速瘫痪。
    2. 删除重要节点,看对网络的影响
    3. 改变指标值/删除指标,分析影响
    4. 用斜率来度量影响是一种非常常见的方法,和灵敏度分析中分析参数的影响类似,特别是有解析式的时候
    5. 网络一般分析结果都是
      从节点的变化分析
      从边的参数变化分析
      从这个网络的演变(传播过程)分析
    展开全文
  • NetworkX 提供了常用的图论经典算法,例如DFS、BFS、最短路、最小生成树、最大流等等,非常丰富,如果不做复杂网络,只作图论方面的工作,也可以应用 NetworkX作为基本的开发包。具体的算法调用方法我就不一一介绍了...

    图的类型

    Graph类是无向图的基类,无向图能有自己的属性或参数,不包含重边,允许有回路,节点可以是任何hash的python对象,节点和边可以保存key/value属性对。
    该类的构造函数为Graph(data=None,**attr),其中data可以是边列表,或任意一个Networkx的图对象,默认为none;attr是关键字参数,例如key=value对形式的属性。

    MultiGraph是可以有重边的无向图,其它和Graph类似。
    其构造函数MultiGraph(data=None, *attr)

    DiGraph是有向图的基类,有向图可以有数自己的属性或参数,不包含重边,允许有回路;节点可以是任何hash的python对象,边和节点可含key/value属性对。
    该类的构造函数DiGraph(data=None,**attr),其中data可以是边列表,或任意一个Networkx的图对象,默认为none;attr是关键字参数,例如key=value对形式的属性

    MultiDiGraph是可以有重边的有向图,其它和DiGraph类似。
    其构造函数MultiDiGraph(data=None, *attr)

    图的创建

    import networkx as nx
    
    G=nx.Graph() #创建了一个没有节点和边的空图
    
    G.add_node(1)#一次增加一个节点:
    
    G.add_nodes_from([2,3])#可以是列表、字典、文件的某些行、其它图等
    
    G.add_nodes_from(H) #H is a graph object here
    

    图的边

    #一次增加一条边:
    G.add_edge(1,2)
    #列表
    G.add_edges_from([(1,2),(1,3)])
    # 边集合
    G.add_edges_from(H.edges())  
    

    属性

    对于图,边和节点都能将key/value对作为自己的属性,保存在相关的dictionary中。该关联字典默认为空,但是能通过add_edge,add_node或操作进行修改。
    添加图的属性:

       G=nx.Graph(day="Friday")
    

    添加节点的属性:#主要的方法是add_node()和add_nodes_from()

    G.add_node(1,time=‘5pm‘)  #给节点1加属性对time:5pm
    G.add_nodes_from([3], time=‘2pm‘) #对前一个参数中的所有节点,添加属性对time:2pm
    G.node[1][‘room‘]=714  #为G中的节点1添加属性对room:714
    

    添加边的属性:#主要方法是add_edge(),add_edges()和G.edge

     G.add_edge(1,2,‘weight‘=4.7) #为1和2之间的边,添加属性weight:4.7
    G.add_edges_from([(3,4),(4,5)],color=‘red‘) #为连接3和4、4和5的边添加属性对color:red
    G[1][2][‘weight‘]=4.7
    G.edge[1][2][‘weight‘]=4
    

    其它

    len(G)  #返回G中节点数目
    
    n in G  #检查节点n是否在G中,如在,返回true。
    

    相关函数

    初始化:G=nx.Graph()

    图相关属性的函数:

    nx.degree(G)// 计算图的密度,其值为边数m除以图中可能边数(即n(n-1)/2)

    nx.degree_centrality(G)//节点度中心系数。通过节点的度表示节点在图中的重要性,默认情况下会进行归一化,其值表达为节点度d(u)除以n-1(其中n-1就是归一化使用的常量)。这里由于可能存在循环,所以该值可能大于1.

    nx.closeness_centrality(G)//节点距离中心系数。通过距离来表示节点在图中的重要性,一般是指节点到其他节点的平均路径的倒数,这里还乘以了n-1。该值越大表示节点到其他节点的距离越近,即中心性越高。

    nx.betweenness_centrality(G)//节点介数中心系数。在无向图中,该值表示为节点作占最短路径的个数除以((n-1)(n-2)/2);在有向图中,该值表达为节点作占最短路径个数除以((n-1)(n-2))。

    nx.transitivity(G)//图或网络的传递性。即图或网络中,认识同一个节点的两个节点也可能认识双方,计算公式为3*图中三角形的个数/三元组个数(该三元组个数是有公共顶点的边对数,这样就好数了)。

    nx.clustering(G)//图或网络中节点的聚类系数。计算公式为:节点u的两个邻居节点间的边数除以((d(u)(d(u)-1)/2)。

    实例:

    • 无向图:
    import networkx as nx                            #导入NetworkX包,为了少打几个字母,将其重命名为nx
    G = nx.Graph()                                        #建立一个空的无向图G
    G.add_node(1)                                        #添加一个节点1
    G.add_edge(2,3)                                     #添加一条边2-3(隐含着添加了两个节点2、3)
    G.add_edge(3,2)                                     #对于无向图,边3-2与边2-3被认为是一条边
    print G.nodes()                                       #输出全部的节点: [1, 2, 3]
    print G.edges()                                       #输出全部的边:[(2, 3)]
    print G.number_of_edges()                    #输出边的数量:1
    
    • 有向图
      有向图的建立方式和无向图基本类似,只是在上述代码的第二行,将G = nx.Graph() 改为 G = nx.DiGraph() 。需要注意的是,此时再添加边3-2与边2-3,则被认为是两条不同的边(可以试着运行上述代码,自己查看结果)。
      同时,有向图和无向图是可以相互转化的,分别用到Graph.to_undirected() 和 Graph.to_directed()两个方法。

    • 加权图(网络)
      有向图和无向图都可以给边赋予权重,用到的方法是add_weighted_edges_from,它接受1个或多个三元组[u,v,w]作为参数,其中u是起点,v是终点,w是权重。例如:

    G.add_weighted_edges_from([(0,1,3.0),(1,2,7.5)])
    
    print G.get_edge_data(1,2)    #输出{‘weight‘: 7.5},这是一个字典结构,可以查看python语法了解它的用法。
    
    • 论文中的图
    def build_graph(train_data):
        graph = nx.DiGraph()
        for seq in train_data:
            for i in range(len(seq) - 1):
                if graph.get_edge_data(seq[i], seq[i + 1]) is None:
                    weight = 1
                else:
                    weight = graph.get_edge_data(seq[i], seq[i + 1])['weight'] + 1
                graph.add_edge(seq[i], seq[i + 1], weight=weight)
        for node in graph.nodes:
            sum = 0
            for j, i in graph.in_edges(node):
                sum += graph.get_edge_data(j, i)['weight']
            if sum != 0:
                for j, i in graph.in_edges(i):
                    graph.add_edge(j, i, weight=graph.get_edge_data(j, i)['weight'] / sum)
        return graph
    

    调用图算法
    NetworkX 提供了常用的图论经典算法,例如DFS、BFS、最短路、最小生成树、最大流等等,非常丰富,如果不做复杂网络,只作图论方面的工作,也可以应用 NetworkX作为基本的开发包。具体的算法调用方法我就不一一介绍了,

    其他详见:

    http://www.bubuko.com/infodetail-1718433.html

    https://www.cnblogs.com/kaituorensheng/p/5423131.html

    展开全文
  • 一文读懂复杂网络应用、模型和研究历史)

    万次阅读 多人点赞 2018-05-02 09:40:05
    摘要:随着近几年关于复杂网络(Complex network)理论及其应用研究的不断深入,已有大量关于复杂网络的文章发表在Science,Nature,RL,NAS等国际一流的刊物上,侧面反映了复杂网络已经成为物理界的一个新兴的研究...

    出处:https://yq.aliyun.com/articles/231424?do=login#

    摘要: 随着近几年关于复杂网络(Complex network)理论及其应用研究的不断深入,已有大量关于复杂网络的文章发表在Science,Nature,RL,NAS等国际一流的刊物上,侧面反映了复杂网络已经成为物理界的一个新兴的研究热点。

    f400ea0de4287d8e02e057228fc99cea01df8a97

    随着近几年关于复杂网络(Complex network)理论及其应用研究的不断深入,已有大量关于复杂网络的文章发表在Science,Nature,RL,NAS等国际一流的刊物上,侧面反映了复杂网络已经成为物理界的一个新兴的研究热点。人们开始尝试应用这种新的理论工具来研究现实世界中的各种大型复杂系统,其中复杂系统的结构以及系统结构与系统功能之间的关系是人们关注的热点问题[1]

    在自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与节点之间的连边组成,其中节点用来代表真实系统中不同的个体,而边则用来表示个体间的关系,往往是两个节点之间具有某种特定的关系则连一条边,反之则不连边,有边相连的两个节点在网络中被看作是相邻的。例如,神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络[2];计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络[2]。类似的还有电力网络[3]、社会关系网络[2,4-5]、交通网络[6]、调度网络[7]等等。

    复杂网络的研究由于其学科交叉性和复杂性的特点,涉及了众多学科的知识和理论基础,尤其是系统科学、统计物理、数学、计算机与信息科学等,常用的分析方法和工具包括图论、组合数学、矩阵理论、概率论、随机过程、优化理论和遗传算法等。复杂网络的主要研究方法都是基于图论的理论和方法开展的,并已经取得了可喜的成果。但近几年,统计物理的许多概念和方法也已成功地用于复杂网络的建模和计算,如统计力学、自组织理论、临界和相变理论、渗流理论等[8],如网络结构熵的概念,并用它来定量地度量复杂网络的“序”。复杂网络模型在很多科学领域都得到广泛的应用。

    参考文献:

    [1] 孙玺菁, 司守奎. 复杂网络算法与应用[M]. 国防工业出版社, 2015.

    [2] Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks.[J]. Nature, 1998, 393(6684):440.

    [3] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology[J]. Acm Sigcomm Computer Communication Review, 1997, 29(4):251-262.

    [4] Hofman J M, Sharma A, Watts D J. Prediction and explanation in social systems.[J]. Science, 2017, 355.

    [5] Ebel H, Mielsch L I, Bornholdt S. Scale-free topology of e-mail networks[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2002, 66(3 Pt 2A):035103.

    [6] 吴文祥, 黄海军. 固定需求交通网络的一般系统最优模型与性质[J]. 管理科学学报, 2015, 18(12):58-67.

    [7] 宣琦,吴铁军. 复杂open shop问题的网络模型及调度规则设计[J]. 浙江大学学报(工学版),2011,(06):961-968.

    [8] Albert R, Barabási A. Statistical mechanics of complex networks[J]. Review of Modern Physics, 2002, 74(1):47-97.

     

    1. 复杂网络的研究历史

     

    1736,欧拉:哥尼斯堡七桥问题;1950,Erdos, Renyi: 随机图论;1998,Strogatz, Barabasi:小世界和无标度网络。

     

    c1eff034096c91834b6f096d6e2ec490e99dda4e

     

    两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志:

    一篇是美国康奈尔(Cornell)大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的题为《“小世界”网络的集体动力学》(Collective Dynamics of ‘Small-World’ Networks)的文章;

    另一篇是美国Notre Dame大学物理系的Barabāsi教授及其博士生Albert于1999年10月在Science杂志上发表的题为《随机网络中标度的涌现》(Emergence of Scaling in Random Networks)的文章。这两篇文章分别揭示了复杂网络的小世界特征和无标度性质,并建立了相应的模型以阐述这些特性的产生机理。至此,人们逐渐展开了对复杂网络的研究。

    关于网络的研究,数学家早在两百多年前就开始了,他们已经发展出了成体系的理论与技术,而物理学家的进入只有十几年左右的历史!到底是什么鼓动物理学家来趟这塘浑水,他们的到来有意义吗?

    在我们看来,研究对象特殊的尺度效应是召唤物理学家到来的根本原因。

    数学家经典的网络理论,要么是分析包含几十数百个顶点,可以画在一张纸上从而形成直观印象的网络;要么是讨论不含有限尺度效应,可以精确求解的网络性质。“随机移走一个顶点会对网络的性能产生什么样的影响?”这个问题对于研究有限规则网络的数学家是有意义的,对于拥有几千万个节点,接方式复杂多样的真实网络而言,或许“随机移走 3%的顶点会对网络性能产生什么样的影响?”这个问题更有意义。这个尺度的网络,是被物理学家称作“足够大”的网络,对它们的研究,需要使用统计物理的方法。

    数学家和物理学家在考虑网络的时候,往往只关心节点之间有没有边相连,至于节点到底在什么位置,是长还是短,弯曲还是平直,有没有相交等等都是他们不在意的。在这里,他们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质,相应的结构叫做网络的拓扑结构

    那么,什么样的拓扑结构比较适合用来描述真实的系统呢?两百多年来,这个问题的研究经历了三个阶段。在最初的一百多年里,数学家们认为真实系统各因素之间的关系可以用一些规则的结构表示,如二维平面上的欧几里德格网,看起来像是格子体恤衫上的花纹;又或者最近邻环网,总是会让你想到一群手牵着手围着篝火跳圆圈舞的姑娘。

    到了二十世纪五十年代末,数学家们想出了一种新的构造网络的方法,在这种方法下,两个节点之间连边与否不再是确定的事情,而是根据一个概率决定。数学家把这样生成的网络叫做随机网络,在接下来的四十年里一直被很多科学家认为是描述真实系统最适宜的网络。直到最近几年,由于计算机数据处理和运算能力的飞速发展,科学家们发现大量的真实网络既不是规则网络,也不是随机网络,而是具有与前两者皆不同的统计特征的网络。这样的一些网络被科学家们叫做复杂网络(Complex Networks),对于它们的研究标志着第三阶段的到来。

    国内学者对国外复杂网络理论研究的介绍最早始于汪小帆(2002)发表在国外杂志上的一篇文章[3],文中回顾了近年来国外复杂网络研究所取得的重要成果,其中包括平均路径长度、聚集系数、度分布等网络度量,Internet、www和科学合作网络等现实系统,规则网络、随机网络、小世界网络、无标度网络等网络模型,以及复杂网络上的同步等。

    而在国内刊物上对国外复杂网络理论研究的介绍可追溯到朱涵(2003) [4]在《物理》杂志上发表的“网络‘建筑学”’,文章以小世界、集团化和无标度等概念为中心,介绍了复杂网络的研究进展。

    之后,吴金闪等[5]从统计物理学的角度总结了复杂网络的主要研究结果,对无向网络、有向网络和加权网络等三种不同网络统计性质研究的现状分别作了综述,对规则网络、完全随机网络、小世界网络和无标度网络等网络机制模型进行了总结,并对网络演化的统计规律、网络上的动力学性质的研究进行了概括。

    周涛等(2005)围绕小世界效应和无标度特性等复杂网络的统计特征及复杂网络上的物理过程等问题,概述了复杂网络的研究进展。

    刘涛等[6]从平均路径长度、聚集系数、度分布等复杂网络的统计性质,小世界网络和无标度网络等网络模型等层面简述了复杂网络领域的相关研究

    史定华[7]从对网络节点度和度分布的理解入手,对网络分类、网络的演化机理和模型及结构涌现等方面取得的进展进行了总结

    遗憾的是,目前而言,科学家们还没有给出复杂网络精确严格的定义,从这十几年的研究来看,之所以称其为复杂网络,致少包含以下几层意思:首先,它是大量真实复杂系统的拓扑抽象;其次,它至少在感觉上比规则网络和随机网络复杂,因为我们可以很容易地生成规则和随机网络,但就目前而言,还没有一种简单方法能够生成完全符合真实统计特征的网络;最后,由于复杂网络是大量复杂系统得以存在的拓扑基础,此对它的研究被认为有助于理解复杂系统之所以复杂”这一至关重要的问题。

    参考文献:

    [1] Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks.[J]. Nature, 1998, 393(6684):440.

    [2] Barabási A, Albert R. Emergence of Scaling in Random Networks[J]. Science, 1999, 286(5439):509-512.

    [3] XIAO FAN WANG. COMPLEX NETWORKS: TOPOLOGY, DYNAMICS AND SYNCHRONIZATION[J]. International Journal of Bifurcation & Chaos, 2002, 12(5):885-916.

    [4] 朱涵, 王欣然, 朱建阳. 网络“建筑学”[J]. 物理, 2003, 32(6):364-369.

    [5] 吴金闪, 狄增如. 从统计物理学看复杂网络研究[J]. 物理学进展, 2004, 24(1):18-46.

    [6] 刘涛, 陈忠, 陈晓荣. 复杂网络理论及其应用研究概述[J]. 系统工程, 2005, 23(6):1-7.

    [7] 史定华. 网络——探索复杂性的新途径[J]. 系统工程学报, 2005, 20(2):115-119.

     

     

    2. 复杂网络的统计特征

     

    2.1平均路径长度L

    在网络中,两点之间的距离为连接两点的最短路径上所包含的边的数目。网络的平均路径长度指网络中所有节点对的平均距离,它表明网络中节点间的分离程度,反映了网络的全局特性。不同的网络结构可赋予L不同的含义。如在疾病传播模型中L可定义为疾病传播时间,通网络模型中L可定义为站点之间的距离等。

    2.2聚集系数C

    在网络中,节点的聚集系数是指与该节点相邻的所有节点之间连边的数目占这些相邻节点之间最大可能连边数目的比例。而网络的聚集系数则是指网络中所有节点聚集系数的平均值,它表明网络中节点的聚集情况即网络的聚集性,也就是说同一个节点的两个相邻节点仍然是相邻节点的概率有多大,它反映了网络的局部特性。

    2.3度及度分布

    在网络中,点的度是指与该节点相邻的节点的数目,即连接该节点的边的数目。而网络的度<k>指网络中所有节点度的平均值。度分布P(k)指网络中一个任意选择的节点,它的度恰好为k的概率。

    2.4介数

    包括节点介数和边介数。节点介数指网络中所有最短路径中经过该节点的数量比例,边介数则指网络中所有最短路径中经过该边的数量比例。介数反映了相应的节点或边在整个网络中的作用和影响力。

    2.5小世界效应

    复杂网络的小世界效应是指尽管网络的规模很大(网络节点数目N很大),但是两个节点之间的距离比我们想象的要小得多。也就是网络的平均路径长度L随网络的规模呈对数增长,即L~In N。大量的实证研究表明,真实网络几乎都具有小世界效应。

    2.6无标度特性

    对于随机网络和规则网络,度分布区间非常狭窄,大多数节点都集中在节点度均值<k>的附近,说明节点具有同质性,因此<k>可以被看作是节点度的一个特征标度。而在节点度服从幂律分布的网络中,大多数节点的度都很小,而少数节点的度很大,说明节点具有异质性,这时特征标度消失。这种节点度的幂律分布为网络的无标度特性。

     

    3. 各种网络模型

     

    3.1 规则网络

    最简单的网络模型为规则网络,它是指系统中各元素之间的关系可以用一些规则的结构表示,也就是说网络中任意两个节点之间的联系遵循既定的规则,通常每个节点的近邻数目都相同。常见的具有规则拓扑结构的网络包括全局耦合网络(也称为完全图)、最近邻耦合网络和星型耦合网络。

    b2adf38aafaf481204c92f08c75ff96b4de086c7

    3.2 随机网络

    从某种意义上讲,规则网络和随机网络是两个极端,而复杂网络处于两者之间。节点不是按照确定的规则连线,如按纯粹的随机方式连线,所得的网络称为随机网络。如果节点按照某种自组织原则方式连线,将演化成各种不同网络。

    b0c6161f517cd03b3ed917e9aabdcf4efe346d5f

    3.3 小世界网络

    规则的最近邻耦合网络具有高聚类特性,但并不是小世界网络。另一方面,ER随机网络虽然具有小的平均路径长度但却没有高聚类特性。因此,这两类网络模型都不能再现真实网络的一些重要特征,毕竟大部分实际网络既不是完全规则的,也不是完全随机的。作为从完全规则网络向完全随机网络的过渡,Watts和Strogtz于1998年引入了一个小世界网络模型,称为WS小世界模型。

    c952ab032db15d58f481c8f873862d0e96664ce6

    3.4 无标度网络

    很多网络(包括Internet和新陈代谢网络等)都不同程度拥有如下共同特性:大部分节点只有少数几个链接,而某些节点却拥有与其他节点的大量链接,表现在度分布上就是具有幂律形式,即P(k)~k—γ。这些具有大量链接的节点称为“集散节点”,所拥有的链接数可能高达几百、几千甚至几百万。包含这种集散节点的网络,由于网络节点的度没有明显的特征长度,故称为无标度网络。

    b97cf151f52b69530e21e3e3037126f845d7dd66

     

    3.5 自相似网络

    自相似是相似中的一种特殊情况,它是指系统的部分和整体之间具有某种相似性,这种相似性不是两个无关事物间的偶然近似,而是在系统中必然出现并始终保持的。这种自相似是层次复杂网络共有的拓扑性质,而自相似又是分型的一个基本特征,所以复杂系统与各层次子系统之间的自相似性,可以利用分形加以描述。

    f0846279c4942df98b37e3d5a916adddf87c0776

     

     

    4. 复杂网络主要研究内容及应用

    4.1 主要研究内容

    复杂网络模型:

    • 典型的复杂网络:随机网、小世界网、无标度网等;
    • 实际网络及其分类。

    网络的统计量及与网络结构的相关性:

    • 度分布的定义和意义,聚集性、连通性的统计量及其实际意义等。

    复杂网络性质与结构的关系:

    • 同步性、鲁棒性和稳定性与网络结构的关系。

    复杂网络的动力学:

    • 信息传播动力学、网络演化动力学、网络混沌动力学。

    复杂网络的复杂结构:

    • 社团结构、层次结构、节点分类结构等。

    网络控制:

    • 关键节点控制、主参数控制和控制的稳定性和有效性。

    4.2 复杂网络的应用

    • 复杂网络与生物体的新陈代谢系统、大脑神经网络相结合;
    • 复杂网络与生物传染病相结合、在流行病传播与免疫控制方面的研究;
    • 复杂网络上的博弈;
    • 复杂网络在交通网络与社会经济中的应用;
    • 复杂网络在通信网络中的应用;
    • 复杂网络在计算机网络与互联网中的应用;
    • 复杂网络在传感器网络中的应用;
    • 复杂网络在语言词汇网络和社会意见传播等方面的应用等。

    技术网络:

    6ecb682c71682c50fbf4edd44f6f614d9bcfbc6e

     

    计算机互联网络已经发展成为一个巨大的复杂系统,网络的数以千万计的终端用户通过网关和路由器(网络节点)相连,形成一个非常复杂的不规则的拓扑结构而且,越来越多的信息按照协议通过互联网络由各种信息资源传给不同的终端用户(随着用户数量和网络连接的迅猛增加,网络拓扑结构更为复杂,导致网络传输速率下降和等待时间加长,从而使得网络拥塞网络的拥塞又使得人们不停的改进网络协议和操作系统、增加网络带宽、增加和优化网络资源,以利于网络更为有效合理的使用。[32]

    61d086ecf608b75583a9c1a7952528d3f034ba73

    现实世界中的许多系统都可以用复杂网络来描述,力系统是人类创造的最为复杂的网络系统之一。当前经典的网络模型与实际电力网络存在较大差异。从电力网络本身的演化机理入手,提出并研究了一种可以模拟电力网络演化规律的新型局域世界网络演化模型。[33]

    社会网络:

     

    79b0802dfe4a62960c67b243c0fabc19aa2ab76e

    朋友关系网作为一种典型的社会网络,受到了复杂网络领域诸多学者的关注。顾名思义,朋友关系网是根据人们之间的朋友关系所建立的网络,以人为节点,两人之间若有朋友关系则连接一条边。一些学者之前对朋友关系网的研究也获得了许多成果。[34]

    99f6814b0279e9b1e23963c5a9dbfbf59c016ae9

    引文网络是体现知识生产、传播过程的一个重要方面。随着知识量的迅速增长,引文网络已经形成了一个超大规模的网络系统。然而,科学计量学领域中关于大型引文网络的研究还非常少,关于引文网络中知识生产和传播过程的研究更是少有涉及。

    本文立足于科学学引文网络,整合复杂网络理论和社会网络分析方法,从宏观、微观和中观三个层面对科学学的引文网络进行研究,探讨网络的结构及其对知识的流动传播产生的影响。 对从SCI中下载的数据进行了权威控制并对其进行纠错,力图使研究最接近于真实情况。在此基础上对科学学引文网络的整体结构进行了研究,发现科学学引文网络同时具有复杂网络的“无标度”、“小世界”和“高集聚”的特性。科学学引文网络的整体结构适宜于知识快速流动,但是知识传播的路径还有待于进一步的优化。[35]

    交通运输网络:

    199d2ce69923583bfa756357d3795783740b6f47

    在城市道路交通网络中,于恶劣天气、交通事件等可能造成一个或少数关键路段或路口失效(如堵塞),些失效路段或路口会通过路段、路口间的相互关联引起其它路段或路口失效,成连锁效应,终导致整个网络或局部崩溃,就是级联失效。[36]

    aef1148191a97c7931aec5b1a2c38e3d6624ca0c

    基于整个航空运输网络研究航班延误及其产生的次生衍生突发事件链式效应。以航班延误为中心,讨航班延误及其波及的发生发展过程,立基于阶段细分的航班延误波及模型;

    根据导致航班延误的原因以及次生衍生事件链式效应规律,理由航班延误及其波及导致的下游航班或下游机场航班延误等一系列次生衍生事件链,建航班延误次生衍生事件链式网络;

    通过建立航空运输网络结构,拟航班延误及其次生衍生事件链式效应的传播扩散过程,精确预测航班延误引发的次生衍生事件,量分析航班延误波及效应的影响程度。有助于民航应急管理部门有针对性地预防和管控航班延误可能发生的次生衍生事件,而有效地缓解由航班延误波及引发的次生衍生事件的后果与影响,低航班延误的损失。[37]

    de8d2234bfa87f25282d4cc5496ddda779055dc1

    随着城市化进程的加速,人们出行日益增加,城市的交通拥堵问题越来越严重。公共交通是解决城市拥堵问题最为有效的途径,而城市公共交通网络容量是城市公共交通的一项重要研究。大量的研究如,如何定义城市公共交通网络容量;如何确定影响因素以及计算容量的大小。[38]

    生物网络:

    b83143ff6d7c485be8f2e43415c67fb66d54174d

    生态网络是对生态系统中物质、能量流动进行模拟的结构模型。生态网络分析是指对生态网络进行分析的方法和理论。它在年代后期开始引起人们的注意。其领域涉及生态网络流动分析、信息分析、随机分析、结构分析以及灵敏度分析等。它是系统生态学的重要分支。[39]

    3b778d4697b882a4241176465e9d0557f4ed56ef

     

    随着人类基因组测序工作的完成,蛋白质组学的研究逐渐成为生命科学领域中的研究热点,对其研究有助于人类更好地理解在生物过程中蛋白质的作用。蛋白质相互作用网络是一个生命有机体内所有相互作用的蛋白质连接而成的一种复杂网络。[40]

    8eb5da2347c078be1d840bdfaead2319f17c3a31

     

    人脑是由大量的神经元细胞组成的,神经元的工作产生了人脑的智能,人脑的研究导致了神经网络这一门学科的诞生,以说脑科学和神经科学的发展对神经网络研究的进展起到了很大的帮助和引领作用。模拟人类或者其他高级灵长类动物、哺乳动物、鸟类等的视觉、听觉、语言理解等功能的原理,是神经网络研究的初衷,这也是为什么神经网络领域的研究常常和脑科学以及神经学、认知学等领域存在交叉。

    由此而发展起来的机器学习可以分为两大类:有监督学习和无监督学习。有教师监督的学习指的是所学习的数据样本是标注好的,学习模型在学习的时候知道要学习的结果是什么样,然后根据已知的结果去调节学习的过程和模型本身的参数,监督学习指的是数据样本没有标注,学习模型无法得知学习的最终结果,能按照一定的规则去学习未知的结果。[41]

     

    5. 复杂网络研究相关著作及论文

     

    [1] 谢逢洁. 复杂网络上的博弈[M]. 清华大学出版社, 2016.

    [2] 蒋忠元, 梁满贵. 复杂网络传输容量分析与优化[M]. 北京交通大学出版社, 2016.

    [3] 孙玺菁, 司守奎. 复杂网络算法与应用[M]. 国防工业出版社, 2015.

    [4] 李凤华, 熊金波. 复杂网络环境下访问控制技术[M]. 人民邮电出版社, 2015.

    [5] 苏厚胜, 汪小帆. 复杂网络化系统的牵制控制:英文版[M]. 上海交通大学出版社, 2014.

    [6] 张子柯. 大数据下复杂网络的机遇与挑战[M]. 科学出版社, 2014.

    [7] 傅新楚, MichaelSmall, 陈关荣,等. 复杂网络传播动力学:模型、方法与稳定性分析[M]. 高等教育出版社, 2014.

    [8] 陆再珍. 基于复杂网络理论的城市轨道交通系统[M]. 2013.

    [9] 郭进利. 复杂网络和人类行为动力学演化模型[M]. 科学出版社, 2013.

    [10] 何铮. 复杂网络在管理领域的应用研究[M]. 电子科技大学出版社, 2013.

    [11] 陈关荣, 汪小帆, 李翔. 复杂网络引论[M]. 高等教育出版社, 2012.

    [12] 郭世泽. 复杂网络基础理论[M]. 科学出版社, 2012.

    [13] 王维红. 金融危机沿国际贸易网络跨国传播研究:基于复杂网络理论[M]. 企业管理出版社, 2012.

    [14] 刘颖. 复杂网络视角下的知识传播[M]. 中国人民大学出版社, 2012.

    [15] 温磊. 基于复杂网络的供应链建模与仿真研究[M]. 河北大学出版社, 2012.

    [16] 刘健. 复杂网络社团结构的动力学方法研究[M]. 北京大学, 2011.

    [17] 李岸巍. 细胞自动机及其在复杂网络中的应用[M]. 人民邮电出版社, 2011.

    [18] 谭利. 复杂网络模型及应用研究[M]. 中南大学出版社, 2010.

    [19] 吴建军. 城市交通系统复杂性:复杂网络方法及其应用[M]. 科学出版社, 2010.

    [20] 谭玲玲. 中国煤炭需求复杂网络结构建模研究[M]. 经济管理出版社, 2009.

    [21] 汪小帆. 复杂网络理论及其应用[M]. 清华大学出版社, 2006.

    [22] 郭雷, 许晓鸣. 复杂网络[M]. 上海科技教育出版社, 2006.

    [23] Hofman J M, Sharma A, Watts D J. Prediction and explanation in social systems.[J]. Science, 2017, 355.

    [24] Newman, Barabasi, Watts. The Structure and Dynamics of Networks. Princeton University Press, 2006.

    [25] S.Boccaletti, et al. Complex Networks: Structure and dynamics, Phys. Rep. 424 (2006) 175-308.

    [26] E. Ben-Naim, et al. Complex Networks, Springer, 2004.

    [27] S. N. Dorogovtesev, J.Mendes. Evolving of Networks, Oxford Un. Press, 2003.

    [28] Ebel H, Mielsch L I, Bornholdt S. Scale-free topology of e-mail networks[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2002, 66(3 Pt 2A):035103.

    [29] Albert R, Barabási A. Statistical mechanics of complex networks[J]. Review of Modern Physics, 2002, 74(1):47-97.

    [30] Barabási A, Albert R. Emergence of Scaling in Random Networks[J]. Science, 1999, 286(5439):509-512.

    [31]  Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks.[J]. Nature, 1998, 393(6684):440.

    [32] 刘锋, 任勇, 山秀明. 互联网络数据包传输的一种简单元胞自动机模型[J]. 物理学报, 2002, 51(6):1175-1180.

    [33] 王光增, 曹一家, 包哲静,等. 一种新型电力网络局域世界演化模型[J]. 物理学报, 2009, 58(6):3597-3602.

    [34] 张恺, 马忠军, 李科赞. 朋友关系网络的实证统计研究[J]. 电子科技大学学报, 2014(3):336-341.

    [35] 张美平. 科学引文网络分析及其应用研究[D]. 电子科技大学, 2015.

    [36] 王正武, 王杰, 黄中祥. 控制城市道路交通网络级联失效的关闭策略[J]. 系统工程, 2016(2):103-108.

    [37] 贾萌. 基于航空网络的航班延误次生衍生事件链式效应研究[D]. 南京航空航天大学, 2015.

    [38] 刘岩, 邵岩, 王利杰,等. 城市公共交通网络容量研究[J]. 大连交通大学学报, 2015, 36(s1).

    [39] 韩博平. 生态网络分析的研究进展[J]. 生态学杂志, 1993(6):41-45.

    [40] 韩跃, 冀俊忠, 杨翠翠. 基于多标签传播机制的蛋白质相互作用网络功能模块检测[J]. 模式识别与人工智能, 2016, 29(6):548-557.

    [41]  赵国振. 基于自组织神经网的复杂网络社区发现研究[D]. 吉林大学, 2015.

    展开全文
  • 随着近几年关于复杂网络(Complex network)理论及其应用研究的不断深入,已有大量关于复杂网络的文章发表在Science,ature,RL,NAS等国际一流的刊物上,侧面反映了复杂网络已经成为物理界的一个新兴的研究热点。...

    f400ea0de4287d8e02e057228fc99cea01df8a97

    随着近几年关于复杂网络(Complex network)理论及其应用研究的不断深入,已有大量关于复杂网络的文章发表在Science,ature,RL,NAS等国际一流的刊物上,侧面反映了复杂网络已经成为物理界的一个新兴的研究热点。人们开始尝试应用这种新的理论工具来研究现实世界中的各种大型复杂系统,其中复杂系统的结构以及系统结构与系统功能之间的关系是人们关注的热点问题[1]

    在自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与节点之间的连边组成,其中节点用来代表真实系统中不同的个体,而边则用来表示个体间的关系,往往是两个节点之间具有某种特定的关系则连一条边,反之则不连边,有边相连的两个节点在网络中被看作是相邻的。例如,神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络[2];计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络[2]。类似的还有电力网络[3]、社会关系网络[2,4-5]、交通网络[6]、调度网络[7]等等。

    复杂网络的研究由于其学科交叉性和复杂性的特点,涉及了众多学科的知识和理论基础,尤其是系统科学、统计物理、数学、计算机与信息科学等,常用的分析方法和工具包括图论、组合数学、矩阵理论、概率论、随机过程、优化理论和遗传算法等。复杂网络的主要研究方法都是基于图论的理论和方法开展的,并已经取得了可喜的成果。但近几年,统计物理的许多概念和方法也已成功地用于复杂网络的建模和计算,如统计力学、自组织理论、临界和相变理论、渗流理论等[8],如网络结构熵的概念,并用它来定量地度量复杂网络的“序”。复杂网络模型在很多科学领域都得到广泛的应用。

    参考文献:

    [1] 孙玺菁, 司守奎. 复杂网络算法与应用[M]. 国防工业出版社, 2015.

    [2] Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks.[J]. Nature, 1998, 393(6684):440.

    [3] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology[J]. Acm Sigcomm Computer Communication Review, 1997, 29(4):251-262.

    [4] Hofman J M, Sharma A, Watts D J. Prediction and explanation in social systems.[J]. Science, 2017, 355.

    [5] Ebel H, Mielsch L I, Bornholdt S. Scale-free topology of e-mail networks[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2002, 66(3 Pt 2A):035103.

    [6] 吴文祥, 黄海军. 固定需求交通网络的一般系统最优模型与性质[J]. 管理科学学报, 2015, 18(12):58-67.

    [7] 宣琦,吴铁军. 复杂open shop问题的网络模型及调度规则设计[J]. 浙江大学学报(工学版),2011,(06):961-968.

    [8] Albert R, Barabási A. Statistical mechanics of complex networks[J]. Review of Modern Physics, 2002, 74(1):47-97.


    1. 复杂网络的研究历史


    1736,欧拉:哥尼斯堡七桥问题;1950,Erdos, Renyi: 随机图论;1998,Strogatz, Barabasi:小世界和无标度网络。


    c1eff034096c91834b6f096d6e2ec490e99dda4e


    两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志:

    一篇是美国康奈尔(Cornell)大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的题为《“小世界”网络的集体动力学》(Collective Dynamics of ‘Small-World’ Networks)的文章;

    另一篇是美国Notre Dame大学物理系的Barabāsi教授及其博士生Albert于1999年10月在Science杂志上发表的题为《随机网络中标度的涌现》(Emergence of Scaling in Random Networks)的文章。这两篇文章分别揭示了复杂网络的小世界特征和无标度性质,并建立了相应的模型以阐述这些特性的产生机理。至此,人们逐渐展开了对复杂网络的研究。

    关于网络的研究,数学家早在两百多年前就开始了,他们已经发展出了成体系的理论与技术,而物理学家的进入只有十几年左右的历史!到底是什么鼓动物理学家来趟这塘浑水,他们的到来有意义吗?

    在我们看来,研究对象特殊的尺度效应是召唤物理学家到来的根本原因。

    数学家经典的网络理论,要么是分析包含几十数百个顶点,可以画在一张纸上从而形成直观印象的网络;要么是讨论不含有限尺度效应,可以精确求解的网络性质。“随机移走一个顶点会对网络的性能产生什么样的影响?”这个问题对于研究有限规则网络的数学家是有意义的,对于拥有几千万个节点,接方式复杂多样的真实网络而言,或许“随机移走 3%的顶点会对网络性能产生什么样的影响?”这个问题更有意义。这个尺度的网络,是被物理学家称作“足够大”的网络,对它们的研究,需要使用统计物理的方法。

    数学家和物理学家在考虑网络的时候,往往只关心节点之间有没有边相连,至于节点到底在什么位置,是长还是短,弯曲还是平直,有没有相交等等都是他们不在意的。在这里,他们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质,相应的结构叫做网络的拓扑结构

    那么,什么样的拓扑结构比较适合用来描述真实的系统呢?两百多年来,这个问题的研究经历了三个阶段。在最初的一百多年里,数学家们认为真实系统各因素之间的关系可以用一些规则的结构表示,如二维平面上的欧几里德格网,看起来像是格子体恤衫上的花纹;又或者最近邻环网,总是会让你想到一群手牵着手围着篝火跳圆圈舞的姑娘。

    到了二十世纪五十年代末,数学家们想出了一种新的构造网络的方法,在这种方法下,两个节点之间连边与否不再是确定的事情,而是根据一个概率决定。数学家把这样生成的网络叫做随机网络,在接下来的四十年里一直被很多科学家认为是描述真实系统最适宜的网络。直到最近几年,由于计算机数据处理和运算能力的飞速发展,科学家们发现大量的真实网络既不是规则网络,也不是随机网络,而是具有与前两者皆不同的统计特征的网络。这样的一些网络被科学家们叫做复杂网络(Complex Networks),对于它们的研究标志着第三阶段的到来。

    国内学者对国外复杂网络理论研究的介绍最早始于汪小帆(2002)发表在国外杂志上的一篇文章[3],文中回顾了近年来国外复杂网络研究所取得的重要成果,其中包括平均路径长度、聚集系数、度分布等网络度量,Internet、www和科学合作网络等现实系统,规则网络、随机网络、小世界网络、无标度网络等网络模型,以及复杂网络上的同步等。

    而在国内刊物上对国外复杂网络理论研究的介绍可追溯到朱涵(2003) [4]在《物理》杂志上发表的“网络‘建筑学”’,文章以小世界、集团化和无标度等概念为中心,介绍了复杂网络的研究进展。

    之后,吴金闪等[5]从统计物理学的角度总结了复杂网络的主要研究结果,对无向网络、有向网络和加权网络等三种不同网络统计性质研究的现状分别作了综述,对规则网络、完全随机网络、小世界网络和无标度网络等网络机制模型进行了总结,并对网络演化的统计规律、网络上的动力学性质的研究进行了概括。

    周涛等(2005)围绕小世界效应和无标度特性等复杂网络的统计特征及复杂网络上的物理过程等问题,概述了复杂网络的研究进展。

    刘涛等[6]从平均路径长度、聚集系数、度分布等复杂网络的统计性质,小世界网络和无标度网络等网络模型等层面简述了复杂网络领域的相关研究

    史定华[7]从对网络节点度和度分布的理解入手,对网络分类、网络的演化机理和模型及结构涌现等方面取得的进展进行了总结

    遗憾的是,目前而言,科学家们还没有给出复杂网络精确严格的定义,从这十几年的研究来看,之所以称其为复杂网络,致少包含以下几层意思:首先,它是大量真实复杂系统的拓扑抽象;其次,它至少在感觉上比规则网络和随机网络复杂,因为我们可以很容易地生成规则和随机网络,但就目前而言,还没有一种简单方法能够生成完全符合真实统计特征的网络;最后,由于复杂网络是大量复杂系统得以存在的拓扑基础,此对它的研究被认为有助于理解复杂系统之所以复杂”这一至关重要的问题。

    参考文献:

    [1] Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks.[J]. Nature, 1998, 393(6684):440.

    [2] Barabási A, Albert R. Emergence of Scaling in Random Networks[J]. Science, 1999, 286(5439):509-512.

    [3] XIAO FAN WANG. COMPLEX NETWORKS: TOPOLOGY, DYNAMICS AND SYNCHRONIZATION[J]. International Journal of Bifurcation & Chaos, 2002, 12(5):885-916.

    [4] 朱涵, 王欣然, 朱建阳. 网络“建筑学”[J]. 物理, 2003, 32(6):364-369.

    [5] 吴金闪, 狄增如. 从统计物理学看复杂网络研究[J]. 物理学进展, 2004, 24(1):18-46.

    [6] 刘涛, 陈忠, 陈晓荣. 复杂网络理论及其应用研究概述[J]. 系统工程, 2005, 23(6):1-7.

    [7] 史定华. 网络——探索复杂性的新途径[J]. 系统工程学报, 2005, 20(2):115-119.


    2. 复杂网络的统计特征


    2.1平均路径长度L

    在网络中,两点之间的距离为连接两点的最短路径上所包含的边的数目。网络的平均路径长度指网络中所有节点对的平均距离,它表明网络中节点间的分离程度,反映了网络的全局特性。不同的网络结构可赋予L不同的含义。如在疾病传播模型中L可定义为疾病传播时间,通网络模型中L可定义为站点之间的距离等。

    2.2聚集系数C

    在网络中,节点的聚集系数是指与该节点相邻的所有节点之间连边的数目占这些相邻节点之间最大可能连边数目的比例。而网络的聚集系数则是指网络中所有节点聚集系数的平均值,它表明网络中节点的聚集情况即网络的聚集性,也就是说同一个节点的两个相邻节点仍然是相邻节点的概率有多大,它反映了网络的局部特性。

    2.3度及度分布

    在网络中,点的度是指与该节点相邻的节点的数目,即连接该节点的边的数目。而网络的度<k>指网络中所有节点度的平均值。度分布P(k)指网络中一个任意选择的节点,它的度恰好为k的概率。

    2.4介数

    包括节点介数和边介数。节点介数指网络中所有最短路径中经过该节点的数量比例,边介数则指网络中所有最短路径中经过该边的数量比例。介数反映了相应的节点或边在整个网络中的作用和影响力。

    2.5小世界效应

    复杂网络的小世界效应是指尽管网络的规模很大(网络节点数目N很大),但是两个节点之间的距离比我们想象的要小得多。也就是网络的平均路径长度L随网络的规模呈对数增长,即L~In N。大量的实证研究表明,真实网络几乎都具有小世界效应。

    2.6无标度特性

    对于随机网络和规则网络,度分布区间非常狭窄,大多数节点都集中在节点度均值<k>的附近,说明节点具有同质性,因此<k>可以被看作是节点度的一个特征标度。而在节点度服从幂律分布的网络中,大多数节点的度都很小,而少数节点的度很大,说明节点具有异质性,这时特征标度消失。这种节点度的幂律分布为网络的无标度特性。


    3. 各种网络模型


    3.1 规则网络

    最简单的网络模型为规则网络,它是指系统中各元素之间的关系可以用一些规则的结构表示,也就是说网络中任意两个节点之间的联系遵循既定的规则,通常每个节点的近邻数目都相同。常见的具有规则拓扑结构的网络包括全局耦合网络(也称为完全图)、最近邻耦合网络和星型耦合网络。

    b2adf38aafaf481204c92f08c75ff96b4de086c7

    3.2 随机网络

    从某种意义上讲,规则网络和随机网络是两个极端,而复杂网络处于两者之间。节点不是按照确定的规则连线,如按纯粹的随机方式连线,所得的网络称为随机网络。如果节点按照某种自组织原则方式连线,将演化成各种不同网络。

    b0c6161f517cd03b3ed917e9aabdcf4efe346d5f

    3.3 小世界网络

    规则的最近邻耦合网络具有高聚类特性,但并不是小世界网络。另一方面,ER随机网络虽然具有小的平均路径长度但却没有高聚类特性。因此,这两类网络模型都不能再现真实网络的一些重要特征,毕竟大部分实际网络既不是完全规则的,也不是完全随机的。作为从完全规则网络向完全随机网络的过渡,Watts和Strogtz于1998年引入了一个小世界网络模型,称为WS小世界模型。

    c952ab032db15d58f481c8f873862d0e96664ce6

    3.4 无标度网络

    很多网络(包括Internet和新陈代谢网络等)都不同程度拥有如下共同特性:大部分节点只有少数几个链接,而某些节点却拥有与其他节点的大量链接,表现在度分布上就是具有幂律形式,即P(k)~k—γ。这些具有大量链接的节点称为“集散节点”,所拥有的链接数可能高达几百、几千甚至几百万。包含这种集散节点的网络,由于网络节点的度没有明显的特征长度,故称为无标度网络。

    b97cf151f52b69530e21e3e3037126f845d7dd66


    3.5 自相似网络

    自相似是相似中的一种特殊情况,它是指系统的部分和整体之间具有某种相似性,这种相似性不是两个无关事物间的偶然近似,而是在系统中必然出现并始终保持的。这种自相似是层次复杂网络共有的拓扑性质,而自相似又是分型的一个基本特征,所以复杂系统与各层次子系统之间的自相似性,可以利用分形加以描述。

    f0846279c4942df98b37e3d5a916adddf87c0776



    4. 复杂网络主要研究内容及应用

    4.1 主要研究内容

    复杂网络模型:

    • 典型的复杂网络:随机网、小世界网、无标度网等;
    • 实际网络及其分类。

    网络的统计量及与网络结构的相关性:

    • 度分布的定义和意义,聚集性、连通性的统计量及其实际意义等。

    复杂网络性质与结构的关系:

    • 同步性、鲁棒性和稳定性与网络结构的关系。

    复杂网络的动力学:

    • 信息传播动力学、网络演化动力学、网络混沌动力学。

    复杂网络的复杂结构:

    • 社团结构、层次结构、节点分类结构等。

    网络控制:

    • 关键节点控制、主参数控制和控制的稳定性和有效性。

    4.2 复杂网络的应用

    • 复杂网络与生物体的新陈代谢系统、大脑神经网络相结合;
    • 复杂网络与生物传染病相结合、在流行病传播与免疫控制方面的研究;
    • 复杂网络上的博弈;
    • 复杂网络在交通网络与社会经济中的应用;
    • 复杂网络在通信网络中的应用;
    • 复杂网络在计算机网络与互联网中的应用;
    • 复杂网络在传感器网络中的应用;
    • 复杂网络在语言词汇网络和社会意见传播等方面的应用等。

    技术网络:

    6ecb682c71682c50fbf4edd44f6f614d9bcfbc6e


    计算机互联网络已经发展成为一个巨大的复杂系统,网络的数以千万计的终端用户通过网关和路由器(网络节点)相连,形成一个非常复杂的不规则的拓扑结构而且,越来越多的信息按照协议通过互联网络由各种信息资源传给不同的终端用户(随着用户数量和网络连接的迅猛增加,网络拓扑结构更为复杂,导致网络传输速率下降和等待时间加长,从而使得网络拥塞网络的拥塞又使得人们不停的改进网络协议和操作系统、增加网络带宽、增加和优化网络资源,以利于网络更为有效合理的使用。[32]

    61d086ecf608b75583a9c1a7952528d3f034ba73

    现实世界中的许多系统都可以用复杂网络来描述,力系统是人类创造的最为复杂的网络系统之一。当前经典的网络模型与实际电力网络存在较大差异。从电力网络本身的演化机理入手,提出并研究了一种可以模拟电力网络演化规律的新型局域世界网络演化模型。[33]

    社会网络:


    79b0802dfe4a62960c67b243c0fabc19aa2ab76e

    朋友关系网作为一种典型的社会网络,受到了复杂网络领域诸多学者的关注。顾名思义,朋友关系网是根据人们之间的朋友关系所建立的网络,以人为节点,两人之间若有朋友关系则连接一条边。一些学者之前对朋友关系网的研究也获得了许多成果。[34]

    99f6814b0279e9b1e23963c5a9dbfbf59c016ae9

    引文网络是体现知识生产、传播过程的一个重要方面。随着知识量的迅速增长,引文网络已经形成了一个超大规模的网络系统。然而,科学计量学领域中关于大型引文网络的研究还非常少,关于引文网络中知识生产和传播过程的研究更是少有涉及。

    本文立足于科学学引文网络,整合复杂网络理论和社会网络分析方法,从宏观、微观和中观三个层面对科学学的引文网络进行研究,探讨网络的结构及其对知识的流动传播产生的影响。 对从SCI中下载的数据进行了权威控制并对其进行纠错,力图使研究最接近于真实情况。在此基础上对科学学引文网络的整体结构进行了研究,发现科学学引文网络同时具有复杂网络的“无标度”、“小世界”和“高集聚”的特性。科学学引文网络的整体结构适宜于知识快速流动,但是知识传播的路径还有待于进一步的优化。[35]

    交通运输网络:

    199d2ce69923583bfa756357d3795783740b6f47

    在城市道路交通网络中,于恶劣天气、交通事件等可能造成一个或少数关键路段或路口失效(如堵塞),些失效路段或路口会通过路段、路口间的相互关联引起其它路段或路口失效,成连锁效应,终导致整个网络或局部崩溃,就是级联失效。[36]

    aef1148191a97c7931aec5b1a2c38e3d6624ca0c

    基于整个航空运输网络研究航班延误及其产生的次生衍生突发事件链式效应。以航班延误为中心,讨航班延误及其波及的发生发展过程,立基于阶段细分的航班延误波及模型;

    根据导致航班延误的原因以及次生衍生事件链式效应规律,理由航班延误及其波及导致的下游航班或下游机场航班延误等一系列次生衍生事件链,建航班延误次生衍生事件链式网络;

    通过建立航空运输网络结构,拟航班延误及其次生衍生事件链式效应的传播扩散过程,精确预测航班延误引发的次生衍生事件,量分析航班延误波及效应的影响程度。有助于民航应急管理部门有针对性地预防和管控航班延误可能发生的次生衍生事件,而有效地缓解由航班延误波及引发的次生衍生事件的后果与影响,低航班延误的损失。[37]

    de8d2234bfa87f25282d4cc5496ddda779055dc1

    随着城市化进程的加速,人们出行日益增加,城市的交通拥堵问题越来越严重。公共交通是解决城市拥堵问题最为有效的途径,而城市公共交通网络容量是城市公共交通的一项重要研究。大量的研究如,如何定义城市公共交通网络容量;如何确定影响因素以及计算容量的大小。[38]

    生物网络:

    b83143ff6d7c485be8f2e43415c67fb66d54174d

    生态网络是对生态系统中物质、能量流动进行模拟的结构模型。生态网络分析是指对生态网络进行分析的方法和理论。它在年代后期开始引起人们的注意。其领域涉及生态网络流动分析、信息分析、随机分析、结构分析以及灵敏度分析等。它是系统生态学的重要分支。[39]

    3b778d4697b882a4241176465e9d0557f4ed56ef


    随着人类基因组测序工作的完成,蛋白质组学的研究逐渐成为生命科学领域中的研究热点,对其研究有助于人类更好地理解在生物过程中蛋白质的作用。蛋白质相互作用网络是一个生命有机体内所有相互作用的蛋白质连接而成的一种复杂网络。[40]

    8eb5da2347c078be1d840bdfaead2319f17c3a31


    人脑是由大量的神经元细胞组成的,经元的工作产生了人脑的智能,人脑的研究导致了神经网络这一门学科的诞生,以说脑科学和神经科学的发展对神经网络研究的进展起到了很大的帮助和引领作用。模拟人类或者其他高级灵长类动物、哺乳动物、鸟类等的视觉、听觉、语言理解等功能的原理,是神经网络研究的初衷,这也是为什么神经网络领域的研究常常和脑科学以及神经学、认知学等领域存在交叉。

    由此而发展起来的机器学习可以分为两大类:有监督学习和无监督学习。有教师监督的学习指的是所学习的数据样本是标注好的,学习模型在学习的时候知道要学习的结果是什么样,然后根据已知的结果去调节学习的过程和模型本身的参数,监督学习指的是数据样本没有标注,学习模型无法得知学习的最终结果,能按照一定的规则去学习未知的结果。[41]


    5. 复杂网络研究相关著作及论文


    [1] 谢逢洁. 复杂网络上的博弈[M]. 清华大学出版社, 2016.

    [2] 蒋忠元, 梁满贵. 复杂网络传输容量分析与优化[M]. 北京交通大学出版社, 2016.

    [3] 孙玺菁, 司守奎. 复杂网络算法与应用[M]. 国防工业出版社, 2015.

    [4] 李凤华, 熊金波. 复杂网络环境下访问控制技术[M]. 人民邮电出版社, 2015.

    [5] 苏厚胜, 汪小帆. 复杂网络化系统的牵制控制:英文版[M]. 上海交通大学出版社, 2014.

    [6] 张子柯. 大数据下复杂网络的机遇与挑战[M]. 科学出版社, 2014.

    [7] 傅新楚, MichaelSmall, 陈关荣,等. 复杂网络传播动力学:模型、方法与稳定性分析[M]. 高等教育出版社, 2014.

    [8] 陆再珍. 基于复杂网络理论的城市轨道交通系统[M]. 2013.

    [9] 郭进利. 复杂网络和人类行为动力学演化模型[M]. 科学出版社, 2013.

    [10] 何铮. 复杂网络在管理领域的应用研究[M]. 电子科技大学出版社, 2013.

    [11] 陈关荣, 汪小帆, 李翔. 复杂网络引论[M]. 高等教育出版社, 2012.

    [12] 郭世泽. 复杂网络基础理论[M]. 科学出版社, 2012.

    [13] 王维红. 金融危机沿国际贸易网络跨国传播研究:基于复杂网络理论[M]. 企业管理出版社, 2012.

    [14] 刘颖. 复杂网络视角下的知识传播[M]. 中国人民大学出版社, 2012.

    [15] 温磊. 基于复杂网络的供应链建模与仿真研究[M]. 河北大学出版社, 2012.

    [16] 刘健. 复杂网络社团结构的动力学方法研究[M]. 北京大学, 2011.

    [17] 李岸巍. 细胞自动机及其在复杂网络中的应用[M]. 人民邮电出版社, 2011.

    [18] 谭利. 复杂网络模型及应用研究[M]. 中南大学出版社, 2010.

    [19] 吴建军. 城市交通系统复杂性:复杂网络方法及其应用[M]. 科学出版社, 2010.

    [20] 谭玲玲. 中国煤炭需求复杂网络结构建模研究[M]. 经济管理出版社, 2009.

    [21] 汪小帆. 复杂网络理论及其应用[M]. 清华大学出版社, 2006.

    [22] 郭雷, 许晓鸣. 复杂网络[M]. 上海科技教育出版社, 2006.

    [23] Hofman J M, Sharma A, Watts D J. Prediction and explanation in social systems.[J]. Science, 2017, 355.

    [24] Newman, Barabasi, Watts. The Structure and Dynamics of Networks. Princeton University Press, 2006.

    [25] S.Boccaletti, et al. Complex Networks: Structure and dynamics, Phys. Rep. 424 (2006) 175-308.

    [26] E. Ben-Naim, et al. Complex Networks, Springer, 2004.

    [27] S. N. Dorogovtesev, J.Mendes. Evolving of Networks, Oxford Un. Press, 2003.

    [28] Ebel H, Mielsch L I, Bornholdt S. Scale-free topology of e-mail networks[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2002, 66(3 Pt 2A):035103.

    [29] Albert R, Barabási A. Statistical mechanics of complex networks[J]. Review of Modern Physics, 2002, 74(1):47-97.

    [30] Barabási A, Albert R. Emergence of Scaling in Random Networks[J]. Science, 1999, 286(5439):509-512.

    [31]  Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks.[J]. Nature, 1998, 393(6684):440.

    [32] 刘锋, 任勇, 山秀明. 互联网络数据包传输的一种简单元胞自动机模型[J]. 物理学报, 2002, 51(6):1175-1180.

    [33] 王光增, 曹一家, 包哲静,等. 一种新型电力网络局域世界演化模型[J]. 物理学报, 2009, 58(6):3597-3602.

    [34] 张恺, 马忠军, 李科赞. 朋友关系网络的实证统计研究[J]. 电子科技大学学报, 2014(3):336-341.

    [35] 张美平. 科学引文网络分析及其应用研究[D]. 电子科技大学, 2015.

    [36] 王正武, 王杰, 黄中祥. 控制城市道路交通网络级联失效的关闭策略[J]. 系统工程, 2016(2):103-108.

    [37] 贾萌. 基于航空网络的航班延误次生衍生事件链式效应研究[D]. 南京航空航天大学, 2015.

    [38] 刘岩, 邵岩, 王利杰,等. 城市公共交通网络容量研究[J]. 大连交通大学学报, 2015, 36(s1).

    [39] 韩博平. 生态网络分析的研究进展[J]. 生态学杂志, 1993(6):41-45.

    [40] 韩跃, 冀俊忠, 杨翠翠. 基于多标签传播机制的蛋白质相互作用网络功能模块检测[J]. 模式识别与人工智能, 2016, 29(6):548-557.

    [41]  赵国振. 基于自组织神经网的复杂网络社区发现研究[D]. 吉林大学, 2015.


    原文发布时间为:2017-11-3

    本文作者:谢旺

    本文来自云栖社区合作伙伴“数据派THU”,了解相关信息可以关注“x”微信公众号

    展开全文
  • 尤其是“阿尔法狗”战胜人类,为复杂系统建模仿真研究提供了启示。社会管理、战争决策、经济治理、指挥控制、医疗健康等复杂系统领域,一直存在着对经验、直觉等认知建模的需求。“阿尔法狗”所采用的人工神经元网络...
  • 复杂网络理论及应用

    万次阅读 2015-11-22 10:18:59
    1 基本概念1.1.1 聚类系数:某个顶点 i , 与之相连的三角形数量/与之相连的三元组的数量。 1.1.2 度及度的分布 完全随机网络的度的分布近似为...这样的网络也称为均匀网络。 幂律分布,度的分布ln ( P(k) ) ~ -r ln
  • 复杂网络

    千次阅读 2018-09-06 13:54:36
    NetworkX是一个用Python语言开发的图论与复杂网络建模工具,内置了常用的图与复杂网络分析算法,可以方便的进行复杂网络数据分析、仿真建模等工作。networkx支持创建简单无向图、有向图和多重图(multigraph);内置...
  • 卷积神经网络(CNN)在句子建模上的应用 Posted on 2016-03-11 | In
  • 复杂网络分析总结

    万次阅读 多人点赞 2018-04-08 15:31:40
    参考文献 在我们的现实生活中,许多复杂系统都可以建模成一种复杂网络进行分析,比如常见的电力网络、航空网络、交通网络、计算机网络以及社交网络等等。复杂网络不仅是一种数据的表现形式,它同样也是一种科学...
  • 复杂网络表示的原理,算法和应用

    千次阅读 2020-06-04 14:52:51
    图数据在我们的世界中广泛存在,如社交网络,知识图谱,交通网络等。以知识图谱为例,它已经成为很多智能系统的支柱,如搜索引擎,推荐系统等。知识图谱中的一个核心问题是图结构(包括结点和边)的表示,好的知识...
  • 图与复杂网络

    千次阅读 2018-09-24 12:21:14
    图与复杂网络 图论 特点: 它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案,数学上把这种问题称为最优化或优化(optimization)问题 是它们都易于用图形的形式直观地描述和表达,数学上把...
  • 复杂网络与大数据》第二章:复杂网络模型的学习笔记 ...3.3加权网络建模 4相依网络 4.1相依网络的子网络 4.2相依网络的相依边 4.3相依网络的组合方式 1动态演化网络 演化网络是随着时间的变化而.
  • 神经网络模型简述 实例:交通运输能力预测设计 MATLAB程序及仿真结果 由于货物运输、地方经济及企业发展的紧密联系,因此作为反映货物运输需求的一项重要指标, 货运量预测研究和分析具有较强的实际意义。 常用的...
  • 应用UML进行数据库建模

    万次阅读 多人点赞 2015-12-08 13:33:44
    使用上面提供的标注,我们可以在DBMS层次上,对复杂的数据结构和行为建模。另外,UML还提供表达逻辑实体间关系的标注。 关系 UML数据建模profile定义了两个表间任意一种依赖关系。它表示为一构造型的关联并包括...
  • SolidWorks是一套基于三维建模的机械CAD软件,它具有基于特征、单一数据库、参数化设计及全相关性等特性,广泛应用于机械、汽车和航空等领域。我们这次主要介绍三维建模时常见问题应用Solidworks软件解决的技巧和...
  • 由于基于RGB的行为识别容易受到视角的变化以及复杂背景的干扰,从而导致泛化性能不足,很那应用到实际生活中,基于骨骼点数据的识别可以很好地解决这个问题。将人体定义为25个关键关节点的三维坐标,行为往往以视频...
  • 1.当今社会越来越多的现象会涉及复杂网络相关应用 举例:社交网络、搜索引擎 2.Internet的拓扑结构 原因:为预测和提高Internet的性能,特此引入Internet的拓扑结构 具体形式:(1)IP层次 (2)路由器层次 (3)...
  • 网络流量能直接反映网络性能的好坏,网络流量的建模与预测对于大规模网络的规划设计、网络资源管理以及用户行为的调节等方面都具有积极意义。本课题首先介绍了网络流量的特征,在分析了小波理论的基础上提出了一种...
  • 复杂网络概述

    千次阅读 2017-11-28 09:47:46
    复杂网络概述 1研究背景 通信网络、电力网络、生物网络、和社会网络等分别是通信科学、电力科学、生命科学、和社会学等不同学科的研究对象,而复杂网络理论所要研究的则是各种看上去互不相同的复杂网络之间的共性...
  • 七、物理建模 原文:Chapter 7 Physical modeling 译者:飞龙 协议:CC BY-NC-SA 4.0 自豪地采用谷歌翻译 到目前为止,我们所看到的细胞自动机不是物理模型;也就是说,他们不打算描述现实世界中的...
  • 复杂网络入门读物

    千次阅读 2015-11-22 10:09:18
    综合类专著中目前最全面的当属Newman的《网络引论》[1],最简洁的则是Dorogovtsev的《复杂网络讲义》[2]。2006年普林斯顿大学出过一本三巨头的专著,名字也很大气,叫做《网络结构与动力学》[3],但是不要有太高期望...
  • Network Analysis]复杂网络分析总结

    万次阅读 2015-12-23 17:05:43
    ...1. 复杂网络的特点2.... 在我们的现实生活中,许多复杂系统都可以建模成一种复杂网络进行分析,比如常见的电力网络、航空网络、交通网络、计算机网络以及社交网络等等。复杂网络不仅是一种
  • 本笔记源于CDA-DSC课程,由常国珍老师主讲。该训练营第一期为风控主题,...一、信用风险建模中神经网络应用 申请评分可以将神经网络+逻辑回归联合使用。 《公平信用报告法》制约,强调评分卡的可解释性。所以
  • 复杂网络概括

    千次阅读 2014-09-11 17:20:18
    通信网络、电力网络、生物网络、和社会网络等分别是通信科学、电力科学、生命科学、和社会学等不同学科的研究对象,而复杂网络理论所要研究的则是各种看上去互不相同的复杂网络之间的共性和处理它们的普适方法。...
  • 尽管卷积神经网络(CNNs)通常与图像分类任务相关,但经过适当的修改,它已被证明是进行序列建模和预测的有价值的工具。在本文中,我们将详细探讨时域卷积网络(TCN)所包含的基本构建块,以及它们如何结合在一起创建一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 72,973
精华内容 29,189
关键字:

复杂网络建模应用