图论复杂网络

第二章 5 生成树算法

定义2·13 （1）图G的每条边e赋与一个实数?(e)，称为e的权。图G称为加权图。 （2）设G1是G的子图，则G1的权定义为： ?(G1)???(e)

e?E(G1)定理2·10 Kruskal算法选得的边的导出子图是最小生成树。

l法所得子图T0显然是生成树，下证它的最优性。设证：Kruska算T0?G??e1,e2,?,e??1??不是最小生成树，T1是G的任给定的一个生成树，f(T)是

?e1,e2,?,e??1?中不在T1又E(T0)??e1,e2,?,e??1?，故e1,e2,?,e??1中必有不在E(T)中的

边。设f(T)?k，即e1,e2,?,ek?1在T与T0上，而ek不在T上，于是T?ek中有一个圈C，

?，使ek?在T上而不是在T0上。令T???，显然也是生成树，又（T?ek)?ekC上定存在ek?)，由算法知，ek是使G??e1,e2,?,ek??无圈的权最小的边，?(T?)??(T)??(ek)??(ek???是T之子图，也无圈，则有?(ek?)??(ek)，于是?(T?)??(T)，又G??e1,e2,?,ek

毕 业 论 文

题 目： 复杂网络及其matlab模拟

学 院： 物理与电子工程学院

专 业： 物理学 毕业年限： 2015 学生姓名： 学 号： 指导教师：

复杂网络及其matlab模拟

班级：物理学2班 姓名： 指导教师：

摘 要 近年来,关于复杂网络的研究正方兴未艾,1998年Watts和Strogatz

在Nature杂志上发表文章,引入了小世界(Small一World)网络模型。本文对复杂网络的特性还有无标度与小世界网络进行简单介绍，详细介绍各个模型的生成与算法，并用matlab软件进行了模拟。

关键词 复杂网络 无标度 小世界 模拟

Abstract In recent years

第二章 复杂网络的基础知识

第二章 复杂网络的基础知识

2.1 网络的概念

所谓“网络”（networks），实际上就是节点（node）和连边（edge）的集合。如果节点对（i，j）与（j，i）对应为同一条边，那么该网络为无向网络（undirected networks），否则为有向网络（directed networks）。如果给每条边都赋予相应的权值，那么该网络就为加权网络（weighted networks），否则为无权网络（unweighted networks），如图2-1所示。

图2-1 网络类型示例

(a) 无权无向网络 (b) 加权网络 (c) 无权有向网络

如果节点按照确定的规则连边，所得到的网络就称为“规则网络”（regular networks），如图2-2所示。如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络”（random networks）。如果节点按照某种（自）组织原则的方式连边，将演化成各种不同的网络，称为“复杂网络”（complex networks）。

图2-2 规则网络示例

(a) 一维有限规则网络 (b) 二维无限规则网络

1

第二章 复杂网络的基础知识

2.2

图论与网络优化课程设计

四种基本网络（NCN、ER、WS、BA）

的构造及其性质比较

摘要：网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。通过运用Matlab软件和NodeXL网络分析软件，计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。

关键字：最近邻耦合网络；ER随机网络；WS小世界网络；BA无标度网络；Matlab；NodeXL。

1

四种基本网络（NCN、ER、WS、BA）

的构造及其性质比较

1. 概述

1. 网络科学的概述

网络科学（Network Science）是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学，研究涉及到复杂网络的各种拓扑结构及其性质，与动力学特性（或功能）之间相互关系，包括时空斑图的涌现、动力学同步及其产生机制，网络上各种动力学行为和信息的传播、预测（搜索）与控制，以及工程实际所需的网络设计原

图论

内容提要

第一章 图的基本概念

图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。 路、圈与连通图；最短路问题。 树及其基本性质；生成树；最小生成树。

第二章 图的连通性

割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。

第三章 匹配问题

匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。

第四章 欧拉图与哈密尔顿图

欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。

第五章 支配集、独立集、覆盖集与团

支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。

第六章 图的着色问题

点着色；边着色；平面图；四色猜想；色多项式；色数的应用。

第七章 网络流理论

有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费用流问题；最小费用最大流；网络流理论的应用。

主要参考书

[1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译）。 [2] B.Bollobas, Modern graph theory (现代图论)，科学出版社，2001。 [

一、选择题（每小题2分，共50分）

1、设D??V,E?为有向图，则有（ A ）

(A) E?V?V (B) E?V?V (C)V?V?E (D) V?V?E

2、设G??V,E?为无环的无向图，V＝6，E?16，则G 是（D ）

(A) 完全图 (B) 零图 (C) 简单图 (D) 多重图

3、含有5个结点，3条边的不同构的简单图有（ C ）

(A) 2个 (B) 3个 (C) 4个 (D) 5个

4、设图G有n个结点，m条边，且G中每个结点的度数不是k就是k?1，则G中度为k的结点的个数是（ D ）

(A) n/2个 (B) n(n?1)个 (C)nk个 (D) n(k?1)?2m个

5、给定下列序列，哪一个可以构成无向简单图的结点度数序列（ B ）

(A) (1,1,2,2,3)

function [DeD,aver_DeD]=Degree_Distribution(A) %% 求网络图中各节点的度及度的分布曲线

%% 求解算法：求解每个节点的度，再按发生频率即为概率，求P(k) %A————————网络图的邻接矩阵

TD————————网络图各节点的度分布 %aver_DeD———————网络图的平均度 N=size(A,2); DeD=zeros(1,N); for i=1:N

% DeD(i)=length(find((A(i,:)==1))); DeD(i)=sum(A(i,:)); end

aver_DeD=mean(DeD);

if sum(DeD)==0

disp('该网络图只是由一些孤立点组成'); return; else

figure;

bar([1:N],DeD);

xlabel('节点编号n'); ylabel('各节点的度数K');

title('网络图中各节点的度的大小分布图'); end

figure;

M=max(DeD);

for i=1:M+1; %网络图中节点的度数最大为M,但要同时考虑

function [DeD,aver_DeD]=Degree_Distribution(A) %% 求网络图中各节点的度及度的分布曲线

%% 求解算法：求解每个节点的度，再按发生频率即为概率，求P(k) %A————————网络图的邻接矩阵

TD————————网络图各节点的度分布 %aver_DeD———————网络图的平均度 N=size(A,2); DeD=zeros(1,N); for i=1:N

% DeD(i)=length(find((A(i,:)==1))); DeD(i)=sum(A(i,:)); end

aver_DeD=mean(DeD);

if sum(DeD)==0

disp('该网络图只是由一些孤立点组成'); return; else

figure;

bar([1:N],DeD);

xlabel('节点编号n'); ylabel('各节点的度数K');

title('网络图中各节点的度的大小分布图'); end

figure;

M=max(DeD);

for i=1:M+1; %网络图中节点的度数最大为M,但要同时考虑

复杂网络的构建方法研究与实现

目录

内容摘要 Abstract 第一章绪论1

1.1本文的研究目的和意义1 1.2研究进展概述2 1.3本文主要研究内容2

第二章复杂网络基本理论的分析与研究4 2.1复杂网络的现实状况4 2.2复杂网络的基本特征4 2.3复杂网络的统计特征6 2.4复杂网络的其它性质8

第三章复杂网络模型研究与分析10 3.1复杂网络的分类10

3.2复杂网络的网络特征参数与性能指标及拓扑结构14 3.3复杂网络的几何性质14

第四章复杂网络的物理特性分析16 4.1复杂网络的动力学研究16 4.2混沌同步16

4.3沙堆模型与自组织临界性17 第五章复杂网络的应用分析18 5.1复杂网络的社会研究意义18 5.2复杂网络的科学研究作用18 第六章用VC实现复杂网络20

6.1气象数据e00格式数据的读入与显示20 6.2气象站点复杂网络的构建22 6.3气象站点复杂网络特性的分析23 6.4实验系统的设计与开发25 第七章总结与展望28

7.1本文的主要研究工作28

7.2存在的问题与今后的研究方向28 参考文献 致谢

内容摘要

近年来,学界关于复杂网络的研究正方兴未艾,特别是小世界网络和无标度网络的提出更是吸引了很多国内

复杂网络上的传播动力学

摘要：纵观人类社会的发展，传染病一直持续不断地威胁着人类的健康，从早期的天花、麻疹，到近年来的艾滋病、非典、禽流感，每一次传染病都以极快的速度传播着并且吞噬着人类的生命财产。此外，计算机病毒在因特网上的扩散过程也是极其复杂的系统。其不安全因素有计算机信息系统自身的,也有人为的,计算机病毒的高度隐藏性、快速传播性和严重的破坏性使其成为影响计算机系统使用的最不安全的因素。近年来，真实网络中小世界效应和无标度特性的发现激起了物理学界对复杂网络的研究高潮，其中网络拓扑结构对复杂网络上动力学行为的影响是研究的焦点之一。这篇论文主要从复杂网络的拓扑结构和流行病的感染机制两个方面来探讨当前国内外传播动力学研究的现状和最新进展，指出值得进一步研究的问题。例如动态网络结构下的疾病传播行为和微观感染机制等。

关键词：复杂网络、传播动力学、疾病传播、网络免疫技术、感染机制

Abstract: Throughout the development of human society, infectious diseases has been continuously threatens human health, from the early