脑科学与复杂网络研究.ppt

1、复杂网络与脑科学研究,大连海事大学信息科学技术学院,1,概要,复杂网络研究的重要性 真实网络介绍 网络三个基本参数及介数 规则网络 随机图 小世界网络 无尺度网络 复杂网络应用于脑科学研究进展,2,1、复杂网络研究的重要性,目前对复杂网络的研究非常火爆，这是为什么呢？我们首先还是从问题谈起： Internet和万维网与我们生活息息相关，在某种程度上，可以说我们的生活已经对这两种网络产生很大的依赖性。但是，网络到底有多可靠呢？ 2000年，爱虫病毒侵犯了英国议会的电子邮件系统，导致该系统瘫痪。于是可以自然地提出下面的问题：计算机病毒如何在万维网上传播而导致流行？面对黑客的攻击，我们又该如何保护这

2、些网络？ 2003年美加电网的大崩溃事故让纽约人感到惶恐不安。经历这一事件后，我们不禁又要问：“网络到底有多可靠？” 传染病（如非典）对人类的威胁很大，非典对于宏观经济的和人的生命安全都产生巨大的负面影响。那么在特定的社会网络中，传染病（非典）如何通过接触关系传播而导致流行呢？ 我们目前正处在信息时代，信息时代需要时代信息。可是，在信息网络（如万维网）信息如何传播呢？我们如何尽快获取所需要的信息呢？,3,癌症是让人类头疼的一种疾病，在复杂的基因网络中，故障节点是如何相互作用而引发癌症的呢? 语言是人类区别动物的主要标志之一，可是我们今天使用的语言是如何演化成的呢？为什么只有人类才具有复杂语言呢

3、？人脑为什么接触到某一事物后，可以很快的联想到其它事物呢？ 上个世纪九十年代，人类启动了基因组工程，目前这一工程已进入“后基因组时代” 。20世纪中叶分子生物学的诞生时，科学家们提出，生命的行为可以还原到分子层次，可以通过单个生物大分子如基因或蛋白质的物理、化学性质来解释。但是，系统功能并等于要素功能的简单相加。现在，研究者意识到，生命现象必须要在成千上万个生物分子组成的复杂系统的层面上予以认识。可是如何去研究这一复杂系统呢？ 以上所有这些复杂系统方面的问题都与我们今天的主题复杂网络有关系！,4,网络定义： 网络为节点和边组成的集合。节点为系统元素，边为元素间的互相作用（关系）。,Euler

4、(1736),七桥问题,5,真实世界中的网络,真实世界中的网络大致分为四种：社会网络，信息网络，技术网络和生物网络。,6,合作网络,7,ACTOR CONNECTIVITIES,Nodes: actors Links: cast jointly,N = 212,250 actors k = 28.78,P(k) k-,Days of Thunder (1990) Far and Away (1992) Eyes Wide Shut (1999),=2.3,Actors,8,Communication networks,Hyperlinks (directed),Hosts, servers,

5、routers through physical cables (not directed),Flow of information within a company: employees process information Phone call networks (=2),9,Internet-Map,10,What does it mean?,Airlines,11,复杂网络的发展历程：,19591960年，匈牙利数学家艾尔德（P.Erds）和莱利（A.Rnyi），随机图（ER模型） 1998年，康奈尔大学的社会学家Watts和Strogatz ,小世界网络（WS模型） 1999年，圣

6、母大学的物理学家Barabasi和Albert，无尺度网络（BA模型） 1999年演化网络,12,2. 网络的三个基本参数,度分布 节点的度也称为连通度，它指的是与该节点连接的边数。度分布P(k)函数表示节点有k条边连接（即有k个最近邻居）的概率。 Ka=2, Kb=2, Kc=3, Kd=1,D(ab)=1, D(ac)=1, D(ad)=2 D(bc)=1, D(bd)=2 D(cd)=1 L=(1+1+2+1+2+1)/6 = 8/6,b,a,c,d,平均路径长度 网络中的任意两点间有一条最短的路径，它等于沿这条路径从一点走到另一点所经过的最少边数，平均路径长度表示网络中所有的节点对之间

7、的最短路径的平均值。,13,集聚系数 社会上形成了许多派系（Clique）或集团，同一派系里的人两两相互认识。为了描述网络中与同一节点直接相连的节点之间的连接关系，人们引进了集聚系数这一概念：假定某一节点i有Ki个最近邻，那么在这些最近邻的点之间最多可能存在Ki(Ki-1)/2条边，用Ci表示这些可能存在的边中实际上存在的百分比。对网络中所的Ci取平均值，就得到集聚系数C，它描述了网络中点与点集结成团的趋势。,Ca=1 (because b and c connected) Cb=1 (because a and b connected) Cc=1/3 (a-b, not b-d, not a

8、-d) Cd=0 Average clustering = (7/3) /4=7/12,c,b,a,d,14,2020/6/27,15,介数,介数这个概念最早出现在社会学文献中。如果一对节点一共有M条不同的最短路，其中m条经过了某节点x，那么这对节点对x的介数的贡献就是m/M。把所有节点对对x的贡献累加起来再除以节点对总数，就得到了节点的介数。类似的，可以定义边的介数。 介数体现了点或边在网络信息流动中的重要性,现实网络特征,现实网络一般表现出三个特性：,1.幂律度分布：,2.小世界特性(六度分离),3.集聚程度高(演员流派、科研合作 网的学派等)。,16,3. 规则网络,人们把一维链、二维正

9、方晶格等称为规则网络,17,在规则网络中，每个节点具有相同的度分布、集聚系数和平均路径长度。,度分布为德耳塔函数,集聚系数与协调数和维数有关,一维格的平均路径长度与其阶成线性比例关系,对于高维格，其平均路径长度与N1/d成比例缓慢增长，可见高维格呈现小世界特性,18,4. 随机图,在该模型中，节点数目N固定不变，并且假定任意节点之间有一条边连接的概率为p，因此，整个网络的边数是一个随机变量，其期望值为pN(N-1)/2。另一种与之等价的随机图模型是，在由个N顶点N(N-1)/2条边构成的图中，随机连接M条边形成一随机网络，如果令M= pN(N-1)/2 ，则这两种网络就联系起来了。,19,随机

10、图的度分布 p(k),在有N个节点的随机图里面，某一节点i的度为ki的概率P服从一个二项式分布：,对于较大的N，一个随机图的度分布P(K)可以用一个泊松分布来代替,20,21,随机网络的集聚系数,由于在随机图中，一个节点邻居中任意两点相连的概率就等于在整个网络中任意两点相连的概率。因此，随机图的集聚系数可以写为：,22,随机图的平均路径长度,随机图的平均路径长度可以用下式来描述：,考察随机图一个顶点v，假设其邻居数为，由于其集聚系数较小，每个邻居的邻居很少重复，于是从v出发经过两次居邻可以找到正比于2的新顶点，因此最多经过步logN就可遍历整个网络。,23,5. 小世界网络,小世界网络指集聚系

11、数较大且平均路径长度较小的网络 Watts-Strogatz(W-S) 模型,W-S模型的构建: (1)从一个有N个节点的一维规则圆环开始，每一个点与它的K个最近邻居连结。(2)以概率P按顺时针方向对规则圆环中每一条边进行重新连结。在重连过程中，不能进行自我连结和重复连结。,N=20 K=4 p=0.075,24,小世界网络的度分布,25,对于 ，,W-S模型的度分布方程为：,小世界网络的度分布,26,27,小世界网络的平均路径长度,被随机选择又重新连结的边称为长程连接（捷径），它对整个网络的平均路径长度有着很大的影响，试验表明：当P=2/NK，即在保证系统中至少出现一条长程的情况下，系统的平

12、均路径长度开始下降。即使是相当少的长程连接，也能够显著地减小网络的平均路径长度。这是因为每出现一条长程连接，它对整个系统是的影响是非线性的，它不仅影响到被这条线直接连着的两点，也影响到了这两点的最近邻居、次近邻居等等。,28,L的一般标度形式为: 函数f(u) 满足以下关系： u1,29,30,除了有比较短的平均路径长度外，小世界网表 现出相对比较大的集聚系数。对于W-S模型， 其集聚系数为,小世界网络的集聚系数,与规则网络一样，WS模型的集聚系数与网络大小无关,31,32,33,6. 无标度网络,Barabasi-Albert(B-A)模型 无尺度网络形成的两个基本机制： (1)增长。 (2

13、)择优选择。,34,(1)网络的增长：在初始时刻，假定系统中已有m0个点，在以后的每一个时间步长中，我们新增一个度为m的点(m=m0)，这m条边连向网络中已经存在的m个不同的点。,B-A 模型的构建,(2)择优连结：当我们在原来网络中选择一些点被新增加的边连结时，这些点被连结的概率与这些点自身的度的大小成正比。比如度为Ki的点i 被新增点连结的概率为：,35,给定一个节点i,其度Ki 与时间的关系可以写为：,无标度网络的度分布,36,37,38,39,Barabasi-Albert 网络的平均路径长度与 N 的对数近似成正比：,无尺度网络的平均路径长度,40,在相同的网络尺度和平均连结度下，无尺度网络的集聚系数大约是随机图集聚系数的5倍。,无尺度网络的集聚系数,BA模型的集聚系数为：,41,无标度网络的特性：,很多复杂系统拥有共同的重要特性:大部分节点只有少数几个连结，而某些节点却拥有大量的连结。这些具有大量连结的节点称为“集散节点”。 “集散节点”拥有的连结可能高达数百、数千甚至数百万(马太效应)。,42,复杂网络应用于脑科学研究进展,1、Victor M. Eguilu