[讨论]Scale-free 网络与small-world 网络

多情清秋 · 发表于 2005-9-8 09:47

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？我要加入

x

众所周知, 现实世界存在各种各样的复杂网络, 例如, Internet, WWW, Cells, Social networks, Metabolica network 以及 Power grids 等等, 而这些网络都可以看成由多个结点和联接组成的. 对这些网络的动态以及内部机理的研究始终是一个研究热点, 而且也是一个各学科相互交叉的研究热门.
自从上个世纪四十年代以来, ER random graph 一直是分析上述网络的一种主要模型. 然而, 从1998年以后, 尤其是发现许多实际网络具有small-world 或者scale-free 特性以后, ER random graph 就不能够适应当前复杂网络的研究了. 特别是 small-world network 和 scale-free network 的提出, 对实际网络 (如Internet, WWW, Power grids) 内部机理的研究提供了一个新的研究方向. 大家可以针对这个问题谈谈看法，或者聊聊Scale-free 网络与small-world 网络得相关问题！

雪缘 · 发表于 2005-9-9 10:15

我这里有一个Scale-free网络的生成程序，Matlab语言的，大家分享一下

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 生成scale-free网络，目的是在这个网络结构上展开相关的讨论！
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
tic;
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
% 开发人：：李光正
% 单位：：上海大学数学系
% 开发日期：： 2004年12月6日
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
%**************************************************************************
%%% 网络的全局变量
%**************************************************************************
%%%%%% 四个输入变量
I=30; %% 表示现实的次数,I要大于或者等于3,才能对节点的度数用邻接矩阵进行统计
N=10000; %% 表示网络的节点的个数
m0=3; %% 表示网络的初始节点个数
m=3; %% 表示新点与旧网络连边的数目
%%%%%% 只有一个输出变量realization_of_distribution
realization_of_distribution=sparse(I,N); % 矩阵的每行存储度分布的一个现实
%**************************************************************************
%**************************************************************************
%**************************************************************************
%**************************************************************************
for J=1:I % 对I次现实做平均，然后用这个平均值近似网络的度分布
format long;
adjacent_matrix=sparse(m0,m0); % 用sparse表示邻接矩阵adjacent_matrix，极大地释放内存
for i=1:m0
for j=1:3
if j~=i
adjacent_matrix(i,j)=1;
end
end
end
adjacent_matrix=sparse(adjacent_matrix); %%% 初始网络，这里利用sparse把内存得以释放
%%%%%%%%%%%%%%%%%%%%%%%%
%修改cumsum,目的是使得网络的顶点的个数能够超过10万,而不超过内存空间的限制
node_degree=sparse(1,m0); % node_degree表示各个节点的度数
for p=1:m0
%last_element=sparse(m0,1);
%last_element=cumsum(adjacent_matrix(1:m0,p));
%node_degree(p)=last_element(m0);
node_degree(p)=sum(adjacent_matrix(1:m0,p));
end
%%%%%%%%%%%%%%%%%%%%%%%%%
%**************************************************************************
%**************************************************************************
%**************************************************************************
% 每次加入一个新点，新点和老点之间按照择优概率进行连接，
% 值得注意的是，每次新点加入之后，网络的择优概率都发生变化，
% 每一次循环都是一个相对独立的整体，要把流程进行分割处理
for iteration=4:N
[J,iteration] % 控制现实和迭代的次数
%**************************************************************************
%%%% node_degree是每次循环所需要的唯一输出变量
%**************************************************************************
%%% 为每次迭代配置相关的变量
total_degree=2*m*(iteration-4)+6; %%% 迭代之前的网络各个节点的度数之和
degree_frequency=node_degree/total_degree; %%% 每个节点的度数的频数，这是新点连边的择优概率
cum_distribution=cumsum(degree_frequency); %%% cum_distribution把区间 [0,1] 分成若干个小区间，从而对这些个小区间进行投点实验
interval=cum_distribution(1:(iteration-1)); %%% 这是小区间的端点，是cum_distribution的前 iteration－1 个元素
%**************************************************************************
%%% 下面把 r1 和 [0,1] 内的各个小区间的端点进行比较，落在第 i 小区间，就意味着和第 i 个节点相连边 %%%
choose=zeros(1,m); %%% choose存放的是和新点相连接的三个老点
%r2=rand(1); %||| 任意选择的一个 [0,1] 随机数
%r3=rand(1); %|||
%**************************************************************************
%**************************************************************************
%%% 选出第一个和新点相连接的顶点
r1=rand(1);
if r1 choose(1)=1;
elseif r1>=interval(iteration-2)
choose(1)=iteration-1;
elseif (r1>=interval(1))&(r1 for j=2:iteration-2
if (r1>=interval(j-1))&(r1 choose(1)=j;
break;
end
end
end
%**************************************************************************
%**************************************************************************
%%% 选出第二个和新点相连接的顶点，注意这两个点是不同的，目的是避免重复边的出现
r2=rand(1);
if r2 choose(2)=1;
elseif r2>=interval(iteration-2)
choose(2)=iteration-1;
elseif (r2>=interval(1))&(r2 for j=2:iteration-2
if (r2>=interval(j-1))&(r2 choose(2)=j;
break;
end
end
end
while choose(2)==choose(1)
r2=rand(1);
if r2 choose(2)=1;
elseif r2>=interval(iteration-2)
choose(2)=iteration-1;
elseif (r2>=interval(1))&(r2 for j=2:iteration-2
if (r2>=interval(j-1))&(r2 choose(2)=j;
break;
end
end
end
end
%**************************************************************************
%**************************************************************************
%%% 选出第三个和新点相连接的顶点，注意这三个点是不同的，目的是避免重复边的出现
r3=rand(1);
if r3 choose(3)=1;
elseif r3>=interval(iteration-2)
choose(3)=iteration-1;
elseif (r3>=interval(1))&(r3 for j=2:iteration-2
if (r3>=interval(j-1))&(r3 choose(3)=j;
break;
end
end
end
while (choose(3)==choose(1))|(choose(3)==choose(2))
r3=rand(1);
if r3 choose(3)=1;
elseif r3>=interval(iteration-2)
choose(3)=iteration-1;
elseif (r3>=interval(1))&(r3 for j=2:iteration-2
if (r3>=interval(j-1))&(r3 choose(3)=j;
break;
end
end
end
end
%**************************************************************************
%**************************************************************************
%%% 把新点加入网络后，对邻接矩阵进行相应的改变！
%**************************************************************************
%%% 这是在一次循环下生成的新的邻接矩阵，下一次循环就是在这个邻接矩阵的基础上进行的！
for k=1:m
adjacent_matrix(iteration,choose(k))=1;
adjacent_matrix(choose(k),iteration)=1;
end
% node_degree=sparse(1,N); % node_degree表示各个节点的度数
for p=1:iteration
%last_element=sparse(iteration,1);
%last_element=cumsum(adjacent_matrix(1:iteration,p));
%node_degree(p)=last_element(iteration);
node_degree(p)=sum(adjacent_matrix(1:iteration,p)); % 这个循环的目的是重新给各个节点的度赋值
end
% element_cumsum=sparse(cumsum(adjacent_matrix));
% node_degree=element_cumsum(N,:);
end
% 一次最外层循环的结束
%**************************************************************************
%**************************************************************************
%**************************************************************************
% element_cumsum=sparse(cumsum(adjacent_matrix)); % element_cumsum的最后一行给出各个节点的度数
% node_degree=element_cumsum(N,:);
number_of_nodes_with_equal_degree=zeros(1,N); % 存储度相同的顶点的个数
for i=1:N
difference=node_degree-i*ones(1,N);
number_of_nodes_with_equal_degree(i)=length(find(difference==0)); % 度为i的节点的个数
% node_degree=element_cumsum(N,:);
end
a_realization_of_distribution=number_of_nodes_with_equal_degree;
for i=1:N
realization_of_distribution(J,i)=a_realization_of_distribution(i);
end
%%% 循环完毕之后，清空内存，只保留realization_of_distribution的相关信息，这是唯一有用的数据，
%%% 下面的讨论仅仅与这个数据有关
%clear number_of_nodes_with_equal_degree;
%clear element_cumsum;
%clear node_degree;
%clear adjacent_matrix;
% clear
% clear
% clear
% 开始第二次最外层的循环
%**************************************************************************
end % 外层循环的中止
%**************************************************************************
%**************************************************************************
%**************************************************************************
aaa=cumsum(realization_of_distribution);
bb1=aaa(I,:); %%% 譬如，度为3的节点的个数，由于度数为1,2的节点的个数为0,故可以从度数为3的节点个数开始计算
bb2=bb1(m:N);
bbb=bb2/(I*N); %%% 譬如，度为3的节点的个数在网络中的比例
K=m:N; %%%% 这是
loglog(K,bbb,'*') % 注意，作图的时候，一定要做散点图
axis([1 N 0.0000001 0.9])
hold on;
y1=2*m^2*K.^(-3);
loglog(K,y1,'r'); % 与平均场结果进行比较 p(k)=2*m^2*k^(-3)
%**************************************************************************
%%% 第四步：：全部工作结束
toc; %%% 计算程序运行需要的时间

复制代码

雪缘 · 发表于 2005-9-9 10:19

Steven H. Strogatz的文章Exploring complex networks综述了动力学网络方面的研究。他把网络分成规则网络和复杂网络两种，而复杂网络分为随机网络，小世界网络和自相似网络。小世界网络和自相似网络都介于规则和随机网络之间。自相似指得是这样一种性质，系统在不同尺度上看起来性质相同。小世界网络的定义就没有这么明确，只说它是规则和随机网络的中间物。这种不明确性可能来源于对它了解的缺乏。 对于规则网络，任意两个点（个体）之间的平均距离长（通过多少个体联系在一起），但成簇率高（你是朋友的朋友的朋友的几率高）。对于随机网络，任意两个点之间的平均距离短，但成簇率低。而小世界网络，点之间平均距离小，接近随机网络，而成簇率依旧相当高，接近规则网络。 实际的社会、生态、等网络都是小世界网络，在这样的系统里，信息传递速度快。我理解，那些偶然的短连接（short cut）起了关键作用。

linlin820 · 发表于 2005-9-9 10:22

基于Small-World网络的非结构化DHT算法

A Peer-to-Peer DHT Algorithm Based on Small-World Network

Efficient search technology is a primary key to peer-to-peer systems. In order to address the inefficient routing problem, a DHT algorithm is presented based on the policy of clustering keys of sharing files. Under the key clustering algorithm, the ring-like key space is divided into two layers. Meanwhile, each node obtains a randomly assigned numeric value as its clustering center in key space. The lower layer, which is called AUT layer, is responsible for managing files' keys. The upper layer, HUB layer, is responsible for maintaining the clustering center of nodes. According to the AUT layer and the HUB layer separately, file keys and node clustering centers discovered from bypassing routing messages are clustered towards the clustering center of local node. The algorithm solves the problems of present unstructured algorithms in some degree, in which the datum is organized in a confused situation and routing is proceed in a disordered manner. Further, the outcome of small-world is used to cut down latency of routing hops. To improve the algorithm, a few connections to remote nodes are introduced with a suitable probability into routing table of clustering keys. In another word, the criterion of clustering is not of determination, but of probability. In this way, it is possible to route overlay network with average latency of O(log\+2N) hops.

目前，非结构化的P2P路由算法面临着搜索效率低下的严峻问题，这严重影响了非结构算法的应用领域.提出一种基于关键字聚类的分布式哈希表算法，主要思路是将环状关键字空间分成上下两层，下层(AUT层)负责关键字管理，上层(HUB层)负责节点路由.每个节点用一个随机数值作为它的聚类中心，从过往的路由消息中本地节点将抽取文件关键字和节点聚类中心，以聚类原则将这些数据记录到本地路由表中.除了改进非结构化算法的数据组织无序性，另一个目标是提高搜索效率.于是，上述算法的增强算法利用了small-world理论，在HUB层中加入远距离节点的聚类中心，将确定性聚类转化为概率性聚类，故能保证路由长度为O(log\+2N).

多情清秋 · 发表于 2005-9-10 07:43

楼上的对这两种网络形式作过比较嘛？

lchzxz · 发表于 2005-11-17 11:12

我用了楼上的无标度网络的生成程序,很好用.小世界网络的生成代码还没有,你知道哪里有这种代码?

lchzxz · 发表于 2005-11-17 11:22

请问,如果生成一个网络,你想向别人说明你生成的网络是无标度网络或小世界网络,除需要提到生成机理,度的分布,还要算出别的指标吗?

liujie_hch · 发表于 2006-3-16 20:14

Is it really OK??????? Haha...

liujie_hch · 发表于 2006-3-16 20:21

无尺度网络
From: http://www.swarmagents.com/complex/models/network.htm

   网络有随机网络和无尺度网络，许多网络包括因特网"人类社会和人体细胞
代谢网络等，都是无尺度网络。研究无尺度网络，对于防备黑客攻击、防治流行
病和开发新药等，都具有重要的意义。
(原文:Scale-Free Networks, pp50-59, May2003) 撰文/Albert-Laszlo
Barabasi, Eeic Bonabeau

作者介绍

   Albert-Laszlo Barabasi和Eric Bonabeau研究了从因特网到昆虫群落等一
系列复杂系统的行为和特性。Barabasi是美国圣母大学的霍夫曼物理学教授。并
在校内指导对复杂网络的研究，他著有《连结:网络新科学》一书。Bonabeau为
美国麻省剑桥咨询公司"伊可系统"的首席科学家，专门运用复杂科学方面的工具
来开发商业机会。他与别人合作撰写了《虫群智慧:从自然系统到人工系统》一
书。这是他在本刊上第二次发表文章。

一个实例：

如图所示，因特网是一个无尺度网络，其中某些站点似乎与无数的其他站点相连
结 (参见右图的星爆形结构细节)。本图绘制于2003年2月6日，描绘了从某一测
试站点到其他约10万个站点的最短连结路径。图中以相同的颜色来表示相类似的
站点。

   大脑，是由轴突相连结的神经细胞网络，而细胞本身，又是由生化反应相连
结的分子网络。社会也是一个网络，它由友情、家庭和职业关系彼此连结。在更
大的尺度上，食物链和生态系统可以看作由物种所构成的网络。科技领域的网络
更是随处可见:因特网、电力网和运输系统都是实例。就连在文章中我们用以向
你传递思想的语言，也是一种藉由语法相互串连在一起的文字网络。
   尽管网络是如此重要和普遍，但科学家对它的结构和属性却知之不多。在复
杂的基因网络中，故障节点是如何相互作用而引发癌症的?在特定的社会和通信
系统中，疾病和电脑病毒如何快速传播而导致流行?某些网络即便大部分节点失
效，还能维持运行，原因何在?
   最近的研究开始找到这些问题的答案。过去的几年中，不同领域的研究者发
现，很多网络都是由少数一些具有众多连结的节点所支配的，包括万维网、细胞
代谢系统，以及好莱坞的演员网络在内。包含这种重要节点(或称集散节点)的网
络，我们通常称之为"无尺度"(scale free)网络。在无尺度网络中，有些集散节
点甚至具有数不清的连结，而且不存在代表性的节点。这种网络还具有可预期的
行为特性：例如对意外故障具有惊人的承受力，但面对协同式攻击时则很脆弱。
   这些发现极大地改变了我们对复杂外部世界的认识。集散节点的存在，让我
们认识到了以前的网络理论尚未涉及的问题:各种复杂系统具有相同的严格结
构，都受制于某些基本的法则，这些法则似乎可同等地适用于细胞、计算机、语
言和社会。更进一步，认识这些法则，会帮助我们解决一系列重要问题，包括开
发更好的药物、防止黑客侵人互联网、阻止致命流行病的传播，等等。

概述 /无尺度网络的特性

很多复杂系统拥有共同的重要特性:大部分节点只有少数几个连结，而某些节点
却拥有与其他节点的大量连结。这些具有大量连结的节点称为“集散节点”，所
拥有的连结可能高达数百、数千甚至数百万。由此看来，这一特性似乎能说明网
络是无尺度的。
无尺度网络具有某些重要特性。例如它们都可以承受意外的故障，但面对协同式
攻击却很脆弱。
了解这些特性，可能导致许多领域出现新的应用。例如，电脑科学家可能据此设
计出更有效的策略，以保护因特网免受电脑病毒的侵害。

无尺度网络

   在过去40多年里，科学家惯于将所有复杂网络看作是随机网络。这一思想源
于两位匈牙利数学家的研究，他们是卓越的Erdos以及他的密切合作者Renyi。
1959年，为了描述通信和生命科学中的网络，Erdos和Renyi提出，通过在网络节
点间随机地布置连结，就可以有效地模拟出这类系统。这种方法及相关定理的简
明扼要，导致了图论的复兴，数学界也因此出现了研究随机网络的新领域。
   随机网络理论有一项重要预测：尽管连结是随机安置的，但由此形成的网络
却是高度民主的，也就是说，绝大部分节点的连结数目会大致相同。实际上，随
机网络中节点的分布方式将遵循钟形的泊松分布。连接数目比平均数高许多或低
许多的节点，都十分罕见。有时随机网络也称作指数网络，因为一个节点连接k
个其他节点的概率，会随着k值的增大而呈指数递减。
   因此当1998年，我们与美国圣母大学的郑夏雄及Albert合作，开展一个描绘
万维网的项目时，我们满以为会发现一个随机网络。原因如下：人们会根据自己
的兴趣，来决定将网络文件连结到哪些网站，而个人兴趣是多种多样的，可选择
的网页数量也极其庞大，因而最终的连结模式将呈现出相当随机的结果。
   然而，实测结果却推翻了这个预测。在这个项目中，我们设计了一个软件，
可从一个网页跳转到另一个，尽可能地收集网上的所有连结。虽然这个虚拟机器
人仅仅探索了整个万维网的极小一部分，但它组合出来的图景。却揭示了令人惊
异的事实:基本上，万维网是由少数高连结性的页面串连起来的，80%以上页面的
连结数不到4个。然而只占节点总数不到万分之一的极少数节点，却有1000个以
上的连结(一项后续的网络调查显示，有一份文件已经被超过200万的其他网页所
连结!)。
   我们在计算恰好拥有k个连结的万维网页面的数目时，发现网页的连结分布
遵循所谓的"幂次定律":任何节点与其他k个节点相连结的概率，与l/k成正比。
对于流入的连结而言，n值接近于2，这也就是说，流入连接数只有某站点一半的
站点，在网中的数量却有该站点的4倍之多。幂次定律和表征随机网络的钟形分
布大相径庭。具体来说，幂次定律不像钟形曲线那样具有一个峰值，而是由连续
递减的函数来描述。如果用双对数坐标系来描述幂次定律，得到的是一条直线
[见下图随机网络vs无尺度网络]。与随机网络中连结的民主分布不同，幂次定律
所描述的，是由少数集散节点(如Yahoo和Google)所主控的系统。

   随机网络中绝对不可能出现集散节点。当我们开始描绘万维网时，原本预期
节点会像人类的身高一样遵循钟形分布，但结果却发现有些节点不能如此解释。
我们就像突然发现了很多身高百尺的巨人一样，大吃了一惊。因此，我们想出
了"无尺度"这样的用语。

无尺度网络哪里?

liujie_hch · 发表于 2006-3-16 20:22

过去几年中，研究者在很多不同的系统中都发现了无尺度结构。我们研究万 维网的目标是以超连结彼此串连的虚拟网页网络。相比之下，美国加州大学河滨 分校的Faloutsos、加拿大多伦多大学的Faloutsos以及美国卡耐基梅隆大学的 Faloutsos则是分析因特网的物理结构。这三位电脑科学家兄弟研究了以光纤或 其他通信线路连接的路由器，他们发现，这个实体网络的拓扑结构也是无尺性 的。 研究人员还发现，某些社会网络也是无尺度的。例如，美国波士顿大学和瑞 典斯德哥尔摩大学的科学家的共同研究显示，瑞典民众的性关系网络也遵循幂次 定律:尽管大部分人终其一生只有少数几个性伴侣，但有少数人(集散节点)的性 伴侣多达数百人。德国基尔大学的Bornholdt领导的一项研究表明，电子邮件所 连结的人际网络，也可能是无尺度的。渡士顿大学的Redner则证实，由科学论文 之间引用关系所连结的网络，同样也遵循幂次定律。美国密歇根大学安娜堡分校 的Newman研究了包括物理和计算机等一些学科内科学家之间的合作关系网络，他 发现这些网络同样也是无尺度的，这也印证了我们针对数学家和神经科学家所做 的研究。(有趣的是，在数学界，Erdos本人就是最大的集散节点之一，他写的论 文超过1400篇，其中共同作者不下500人。) 无尺度网络同样也出现在商业领域。美国斯坦福大学的W·Powell、加州大 学lrvine分校的R·White、亚利桑那大学的W·Koput以及密歇根大学的Smith， 共同研究了美国生物技术产业联盟网络的形成。发现存在特定的集散节 点:Gerlzyme、Chiron和Genentech等公司，与其他公司相比，拥有的合作关系数 量就多得不成比例。意大利的研究者对这种类型的网络进行了更深入的研究。利 用意大利锡耶纳大学的"制药工业数据库"所提供的数据(该数据库目前包括超过 7200个组织之间所签定的约20100个研发协议)，研究人员发现，Powell等人所发 现的那些集散节点，实际上也属于某个无尺度网络。 就连好莱坞演员网络也是无尺度的。这个网络因"六度凯文贝肯"的游戏而变 得众所皆知。游戏玩家通过共同出演的电影，尽量让特定的演员与凯文贝肯产生 关联。定量分析显示，这个网络也是由某些集散节点所支配的。具体来说，就是 大部分演员只与为数不多的其他几个人相连结，而少数演员所拥有的连结数却高 达数千个，其申包括Rod Steiger和Donald Pleasence。顺便说一下，在演员连 结数的排行榜上，凯文贝肯自己只排在第876位。 重新回到严肃的话题，无尺度网络也出现在生物学领城。我们与美国西北大 学的细胞生物学家Oltvai一道，发现古菌域、细菌域和真核生物三大生物领域的 43种不同生物里，都存在无尺度的细胞代谢网络结构。在这些网络里，细胞通过 分解复杂分子来燃烧食物并释放能量。每个特定的分子就是一个节点，而节点之 间的连结则是生化反应。我们发现，大部分的分子只参加一种或两种反应，但是 有少数分子(集散节点)会参与大部分的反应，比如水和三磷酸腺苷。 我们还发现，细胞中蛋白质的交互网络也是无尺度的。在这种网络中，如果 两种蛋白质能相互反应，就认为是彼此"连结"的。我们在研究酵母这种最简单的 真核细胞时，在它的数千个蛋白质之间找到了一种无尺度的网络拓扑结构:大部 分蛋白质只与其他一、两种蛋白质发生相互作用，但有几种蛋白质分子却能与大 量的其他蛋白质相结合。我们在另一种与酵母迥然不同的简单细菌——幽门螺杆 菌中，也发现了类似的蛋白质交互作用网络。 事实上。科学家研究的网络越多，发现的无尺度结构也越多。这些发现引发了一 个重要的问题:为什么像细胞和因特网这样本质上不同的系统，却具有相同的结 构并遵从相同的规律?这些不同的网络不仅都是无尺度的，而且还有着一个有趣 的共同点:由于某些未知的原因，幂次定律中kn项中的n值，通常介于2-3之间。 无尺度网络的例子： 网络节点连接 组织代谢参与消化食物以释放能量的分子参与相同的生化反应 好莱坞演员出演同一部电影 因特网路由器光纤及其它物理连接 蛋白质调控网络协助调控细胞活动的蛋白质蛋白质之间的相互作用 研究合作科学家合作撰写论文 性关系人性接触 万维网网页连接地址 集散节点的马太效应 一个更为基本的问题也许是，为什么随机网络理论不能解释集散节点的存 在?我们进一步考察了Erdos和Renyi的研究，发现这里面存在两个原因。 在建立模型的时候，Erdos和Renyi曾假设，他们在安置连结之前能够得到所 有节点的清单。而事实上，万维网的页面数量绝对不是恒定的。1990年整个万维 网只有一个网页，而到今天它的网页数已经超过了30亿。大部分网络也都具有类 似的发展过程。1890年好莱坞只有屈指可数的几位演员，但随着越来越多的人加 入这个行业，新人与之演员建立联系，如今这个网络已经超过了50万人。大约30 年前，整个因特网只有几个路由器，随着新的路由器与网络原有的路由器相连 结，如今路由器的数量已经高达百万。由于现实中的网络具有不断成长的本性， 所以老节点获得连结的机会就比较高。 此外，并非所有的节点都是平等的。在选择将网页连结到何处时，人们可以 从数十亿个网站中进行选择。然而我们大部分人只熟悉整个万维网的一小部分， 这一小部分中往往包含那些拥有较多连结的站点，因为这样的站点更容易为人所 知。只要连结到这些站点，就等于造就或加强了对它们的偏好。这种"优先连 结"的过程，也发生在其他网络。在好莱坞，连结关系较多的影星更容易受到新 秀们的重视。而在因特网上，那些连结较多的路由器通常还拥有更大的带宽，因 而新用户就更倾向于连结到这些路由器上。在美国的生物技术产业内，象 Genzyme这样的知名公司更容易吸引到同盟者，而这又进一步加强了它在未来合 作中的吸引力。类似地，被引用较多的科学文献，会吸引更多的研究者去阅读和 引用。美国著名的社会学家K·Merton将这种现象称之为"马太效应"。这个词来 源于《新约》圣经的内容:"凡有的，还要加给他，叫他有余。" 成长性和优先连结这两种机制，有助于解释集散节点的存在:当新节点出现 时，它们更倾向于连结到已经有较多连结的节点，随着时间的推进，这些节点就 拥有比其他节点更多的连结数目。这种“富者逾富”的过程，有利于早期节 点，它们更有可能成为集散节点。 我与阿Albert一道，进行了计算机模拟和计算，结果显示，具有优先连接的 特性并且持续成长的网络，确实会发展成无尺度网络，并且节点的分布也遵循幂 次定律，虽然这个理论模型过于简化，且需要根据具体情况加以调整，但还是对 现实世界中无尺度网络的普遍存在提供了解释。 成长性和优先连接还能够解释生物系统中为什么会出现无尺度网络。例如， 美国墨西哥大学的Wagner和英国牛津布鲁克斯大学的A·Fell就发现，大肠杆菌 代谢网络中连结性较高的几种分子，一般具有更为久远的进化史:有些甚至被认 为是所谓的RNA世界（DNA出现之前的进化阶段）的遗物，还有的则是最古老的代 谢路径的一部分， 令人感兴趣的是，优先连结的机制常常是线性的。换句话说，如果一个现存节点 的连结数是其相邻节点连结数的两倍，那么新节点与它连结的可能性，也是与邻 近节点连结可能性的两倍。美国波士顿大学的Render及同事研究了不同类型的优 先连结，他们发现。如果这种机制运行得比线性更快(例如，一个节点的连结数 是另一个的两倍，而新节点连接到前者的可能性却是后者的4倍），那就容易出 现一个攫取最多连结的集散节点，在这种"赢者通吃"的情况下，网络最终演变为 拥有一个中心集散节点的星型拓扑结构。

liujie_hch · 发表于 2006-3-16 20:23

无尺度网络的 "软肋" 人们对电力网络和通信网络的依赖程度日益增高，凸现了一个广受关注的问 题:这些网络到底有多可靠?好消息是复杂网络对意外故障具有很强的承受能力。 实际上虽然每时每刻网络上都有数百个路由器失效，但因特网却很少因此受到大 的影响。生命系统同样也具有这种强韧性:虽然细抱内存在诸如突变和蛋白质出 错等数以千计的错误，但人体却极少因此发生严重的后果，这种强韧性的来源是 什么呢？ 直觉告诉我们，如果大部分节点发生瘫痪，将不可避免地导致网络的分裂。 对随机网络而言，这是绝对正确的:随机网络中若有较大部分的节点被去除。网 络必然溃散成彼此无法通讯的小型孤岛:不过无尺度网络的模拟结果，则展现了 全然不同的情况：即使从因特网路由器中随机选择的失效节点比例高达80%，剩 余的路由器还是能组成一个完整的集群并保证任意两个节点间存在通路。要扰乱 细抱内的蛋白质交互网络也同样困难:我们的测量显示，即使在细胞内随机制造 较高比例的突变，那些没有改变的蛋白质还是会正常地继续合作。 总的来说，无尺度网络对意外故障具有惊人的强韧性，这一特性本质上源于 这些网络的非同质拓扑结构。随机去除的方式所破坏的主要是那些不重要的节 点，因为它们的数目远大于集散节点。与那些几乎连结所有节点的集散节点相 此。那些不重要的节点只拥有少量的连结。因而去除它们不会对网络拓扑结构产 生重大的影响。但是，对集散节点的依赖，也带来了一个严重问题:面对蓄意攻 击时，网络可能不堪一击。通过一系列的模拟，我们发现，只要去除少数几个主 要集散节点，就可导致因特网溃散成孤立无援的小群路由器。类似地，对酵母的 实验也显示，去除那些高连结性的蛋白质，比去除其他节点更容易导致酵母菌死 亡。这些集散节点是决定性的，一旦发生使它们无法运作的突变，极有可能会导 致整个细胞死亡。 对集散节点的依赖，视系统的不同，既有利也有弊。对因恃网和细胞而言， 能够应付随机出现的意外故障，当然是个大优点。此外，细胞对集散节点的依 赖，也给药物研究者提供了新的方法:有可能找到这样的药物，能针对性地攻击 细胞或者细菌的集散节点，以便杀死它们而又不会影响健康的组织。不利的情况 也有:少数消息灵通的黑客只要攻击一些集散节点，就足以搞垮整个通信基础网 络，这正是人们关心的焦点。 无尺度网络的这一致命缺陷，引发了这样一个问题:到底有多少集散节点是 必不可少的?最近的研究表明，总的来说，只要有5-10%的集散节点同时失效，就 足以搞垮系统。我们对因特网的实验显示，一次有组织的协同攻击，只要去除掉 若干个集散节点(先去除最大的，再去除次大的，依次类推)，就足以造成重大破 坏。因此，为了避免因恶意攻击带来网络的大规模破坏，最有效的办法就是保护 好集散节点。不过，要想知道特定的网络系统到底有多容易被破坏掉，还有待进 一步的研究。例如，如果Genzyme和Genentech这样的集散节点一起失去作用，是 不是美国的生物产业会因此而崩溃呢? "无尺度"流行病 对无尺度网络的认识，也可用于理解电脑病毒、疾病和时尚的传播。过去数 十年间，无论是流行病学家还是市场营销专家，都在大力研究扩散理论。研究结 果指出，一种传染病要在人群中传播开来，必须要跨越某一临界值。任何病毒、 疾病或时尚的感染力一旦低于这个临界值，将不可避免地自行消亡;而一旦超过 临界值，就会呈指数增长，最终传遍整个系统。 然而，西班牙巴塞罗那加泰罗尼亚理工大学的Pastor-satorras和意大利特 里雅斯特国际理论物理研究中心的Vespigniani，最近却得出了一个令人不安的 结论。他们发现，在无尺度网络里，不存在上面所说的临界值。这就意味着，所 有病毒都可在网络中传播和长期存在，即便是那些传染力很低的病毒也是如此。 这一结论解释了"爱虫"现象，(爱虫是有史以来最具破坏力的电脑病毒，2000年 导致了英国议会电子邮件系统的瘫痪)，这个病毒原本理当绝迹的，但过了一年 之后，却仍然是最普遍的病毒之一。 因为集散节点会连结到很多其他节点、所以任何一个遭受病毒入侵的节点， 都将连带感染至少一个集散节点。而一旦有集散节点被感染，它就会把病毒传播 给众多的其他节点，当中也包括其他的集散节点，这就导致了病毒在整个网络里 的传播。 社会网络在许多情况下也是无尺度的。生物病毒在社会网络里传播的现象， 提醒科学家要再好好研究一下那些探讨网络拓扑结构和流行病之间互动关系的文 献。特别是对于无尺度网络而言，公共卫生中传统的随机接种疫苗的方式可能很 容易失效，因为它极有可能遗漏了某些集散节点。事实上，为了保证集散节点不 被遗漏，几乎人人都得接种疫苗。例如，90%的人口都必须接种麻疹疫苗，才能 够有效防疫。 如果医生放弃随机接种疫苗的方法，而把目标转向集散节点，也即那些最易 感染的个人，情况会如何呢?对无尺度网络的研究指出，只要其中包含集散节 点，即使接种疫苗的人口只占一小部分，这种方法仍有可能会奏效。 然而，要找出社会网络中的集散节点，比其他系统要难得多。尽管如此，以 色列巴伊兰大学的Cohen和HavIin，以及美国克拉克森大学的ben-Avraham已提出 了一个聪明的解决办法:任意选择一群人，请他们随机指定一位相识者，然后对 这一小部分被指定的人接种疫苗。这一程序很可能会把集散节点圈入其中，理由 是，集散节点与许多人都有连结，而连结性高的人更容易被指定。不过这一方法 也存在一些道德上的困境。例如，即使识别出了集散节点，是否他们就有优先接 种疫苗和接受治疗的权力呢?尽管存在这些问题，但对于那些无力照顾到全民的 国家和地区而言，在分配艾滋病或天花疫苗时，这可能是最实用的办法。 出于各种商业目的，有时人们需要引发流行而不是遏制流行。例如所谓的病 毒式行销，通常试图把集散节点当做行销的目标，以加快产品为用户所接受的速 度。显然，这种策略已不是什么新鲜事了。早在1950年代，一项由制药业巨头辉 瑞公司出资进行的研究发现，医生圈子中开始采用新药的速度，与集散节点有很 大的关系。实际上，市场推广人员早就凭直觉知道，某些特定的消费者在促进新 产品或新时尚方面，就是比其他的消费者管用得多。新近的无尺度网络研究，只 是为更严谨地探讨这些现象，提供了一个科学的框架和数学工具。 从理论到应用之路 虽然无尺度网络很普遍，但仍有许多明显的例外。例如，美国的高速公路系 统和电力网络就不是无尺度网络。材料科学中的大部分网络也不是。以晶格为 例，各原子部和同样数目的邻近原子相连结。对于其他的一些网络，我们还难以 得出定论。如反映捕食者与猎物关系的食物链网络，由于网络规模太小，科学家 还难以断定它的型态。此外，由于缺乏大规模的人脑内部连结图，科学家也无法 得知这一重要网络的本质。 确定某一网络是否无尺度，对了解该网络的行为特性是相当重要的，但是其他的 重要指标也值得注意。其中参数之一就是网络的直径，或称为 "路径长度"。它 指的是从一节点到另外的任意节点所需经过的最大的中间段数 [见下框文]。 这毕竟是一个小世界 1967年，美国哈佛大学的社会心理学家Milgram寄出了数百封信给内布拉斯 加州的公众，并请求他们把信转交给某位相识的人，条件是对方必须是最有可能 把信再转给波士顿一位股票经纪人手里的人。为了跟踪每一条不同的传送路径， Milgram请求参与者在转寄信件的同时，也给他寄一张明信片。结果，Milgram发 现，信件到达最终收信人之前平均要经过6个人之手。人与人之间存在所谓 "六 度分离"的说法就来源于这个实验。 虽然Milgram的结果很难说是定论，因为绝大部分的信件并未到达最终收信 人手里·不过科学家最近发现，其他网络也具有这种 "小世界"的特性。例如， 我们发现，细胞内的任意两种化学物质，几乎都能通过三个化学反应组成的路径 连结起来。在万维网上，虽然页面数高达30亿，但一般只要经过19个连结，就可 以从一个网页到达另一个。 这种 "小世界"特性，并不意味着网络中存在神奇的组织原则。即使是一个 完全随机连结的大型网络，也是一个小世界。想想看，假设你认识1000个人，他 们中的每一个人又认识1000个人，那么你只要通过一层中间人，就可以认识100 万人。通过两层中间人，你就可以认识10亿人。要认识地球上所有的人。三层中 间人已经绰绰有余了。这样看来，世界上任意两个陌生人之间存在"六度分离"的 说法，简直就是废话了。然而，进一步的研究让我们对这一说法有了更深刻的认 识。 上图示出了不同层次的集群。在层次式集群中，黄色表示美国著名建筑师Wright 的住宅“落水山庄”的网页集群，绿色表示与此相连的其他有关Wright、著名宅 第和美国宾州景点的网页集群。红色表示它们进一步与其它著名建筑师或建筑相 连接的网页集群。上面我们的简单计算有个前提，那就是你的熟人都是彼 此不相识的。但是在实际生活中，他们中有许多人是互相认识的。事实上，人类 社会可以区分为一个个具有相似特质(例如收入或者兴趣)的小集群。自从1970年 代Granovetter在哈佛大学读研究生时首开对此问题的研究之后，已有大量的社 会心理学文献对这种社会特质进行了探讨。集群现象在其他多种网络中也曾遍存 在。1998年。美国康奈尔大学的Watts和Strogatz发现，在多种不同类型的系统 中，都存在相当明显的集群现象，其中包括美国电力网和线虫的神经网络等。 从表面上看，由高度相互连结的节点组成的孤立集群，似乎与无尺度网络的 拓扑结构不相容·因为在无尺度网络中，有一些集散节点会与所有的节点相连 结，它们的影晌是遍及整个系统的。但是·最近我们发现，这两者其实是相容 的:如果紧密连结的小型节点集群彼此相连，形成较大且较不紧密的大集团，那 这样的网络就能既是高度集群的又是无尺度的 [见左图]。这类结构在很多系统 中都有出现·比如万维网，它的集群就是具有相同主题的网页群。细胞也是如 此，它的集群就是负责特定功能的分子群。 最后，具备网络一般拓扑结构的知识，只能了解系统行为与全面特性的一部 分。例如，在美国高速公路网这样的系统中，为其一指定节点添加一条连结的成 本是极其昂贵的，这就阻止了它向无尺度方向发展。在食物链中，某些猎物比其 他猎物更容易被猎取，这对整个生态系统具有深刻的影响。在社会网络中，家庭 成员之间的关系比点头之交者要密切得多，因而疾病 (和信息)就更容易在这种 连结中散播。对于运输、传送和通信系统 (如因恃网)而言，主要的问题是某些 特定连结的拥堵:其一特定连结的流量过大，将导致该连结中断，而其他连结接 手处理过剩流量，也可能会跟着失效。而且节点本身可能不具有同质性，如某些 网页可能很有吸引力，那它就会严重影响优先连结的机制。 由于上述的种种原因，科学家可以说才刚开始了解无尺度网络的行为。例 如，仅仅对集散节点免疫，也许并不足以阻止疾病的蔓延;更好的办法是，不仅 仅考虑某人的连结数目，还要考虑这些连结的频度和接触时间。 基本上，我们在开始研究复杂网络时，会先忽略个别连结和节点的细节。通 过远离这些细节，我们才能找出这些看似无法理解的系统背后的组织原则。我们 的一些研究成果，至少已让研究者重新审视许多基本的假设。例如，研究者过去 都把因特网视作随机网络，用来测试新的路由协议对系统塞车现象的影响。现在 我们知道，因特网其实是一个无尺度网络，它的行为特性与随机网络有天壤之 别。因此，像W·Byers和他在波士顿大学的同事们这样的研究者，正在修改因特 网的电脑模拟模型。了解无尺度网络的特性，对其他许多领域都是有价值的，特 别是当我们超越网络拓扑结构，进一步探讨复杂系统内部深奥得难以理解的动力 学的时候。 无尺度网络的潜在意义 运算 具有无尺度结构的计算机网络，例如万维网，对意外故障具有极强的承受能力， 但面对蓄意的攻击和破坏却可能不堪一击。 要想在因特网上彻底清除病毒，即使是已知的病毒，也是不可能的。 医学 对天花等严重疾病的疫苗接种，如果能针对集散节点（即那些与很多人具有连结 关系的人）进行，也许可以达到最大的效果，但要找出属于集散节点的人非常困 难。 弄清人体细胞内的网络结构，将有助于研究者发现和控制药物的副作用。此外， 若能识别出那些与特定疾病有关的集散点分子，就可开发只针对这些集散节点作 用的新药物。 商业 了解公司、产业与经济之间的连结方式，有助于研究人员监控和预防大规模的经 济衰退。 研究流行病在无尺度网络中的传播现象，为市场人员传播他们的新产品提供了新 方法。 [何毓嵩/译曾少立/校]

liujie_hch · 发表于 2006-3-16 20:26

[此贴子已经被作者于2006-3-16 20:29:30编辑过]

liujie_hch · 发表于 2006-3-16 20:27

<DIV>A Group for Discussing dynamical behaviours on complex networks! 1- How to analyze complex dynamical behaviours on complex networks? 2- How to modelling different dynamical networks? 3- What tools are used and how to use it for beginners? 4- How to publish your related papers on a professional Journal? 5- Related international conference and workshop informations FYI. 6- etc. See: <a href="http://groups.yahoo.com/group/dynamicalnetworks/" target="_blank" >http://groups.yahoo.com/group/dynamicalnetworks/</A></DIV>

[此贴子已经被作者于2006-3-16 20:32:33编辑过]

hesuhong · 发表于 2006-5-17 11:29

生成scale free 的那个程序有点问题, 多情清秋能给我一个可运行的程序吗?

中原 · 发表于 2007-1-18 16:57

关于－网络结构和动力学
国内做这方面研究的人
刘曾荣1、周进2、王家赠1
1、上海大学理学院数学系
2、上海大学上海市应用数学与力学研究所

这方面的参考文献：

1. 普利高津和斯唐热，从混沌到有序：人与自然的新对话，曾庆宏和沈小峰译，上海译文出版社，上海，1987。
2. 湛垦华、沈小峰等，普利高津和耗散结构理论，陕西科学出版社，西安，1982。
3. 哈肯，高等协同论，郭冶安译，科学出版社，北京，1989。
4. 詹姆斯，混沌：开创新科学，张淑誉译，上海译文出版社，上海，1990。
5. Zhang. S.Y, Bibliography on chaos, In: Hao. B.L, ed, Direction in Chaos, Publishing Co Pte Ltd, Singapore, 1991.
6. Ott. E, Grebogi. C and York. J A, Controlling chaos, Phys.Rev.Lett., 64, p 1196-1199, 1990.
7. Pecora. L.M and Carroll. T.L, Synchronization in chaotic collective systems, Phys.Rev.Lett., 64, p 821-824, 1990.
8. Hopfield. J.J, Neural networks and physical systems with emergent collective computertational abilities, Proc.Nall.Acad.,Sci., 79, p937-946, 1982.
9. 焦李成，神经网络系统理论，西安电子科技大学出版社，西安，1990。
10. 米歇尔.沃尔德罗普，混沌：诞生于秩序与混沌边缘的科学，陈玲译，生活、读书、新知三联书店，上海，1997。
11. 弗里德里希，混沌与秩序：生物系统的复杂结构，柯志阳和员彤译，上海科技教育出版社，上海，2000。
12. 约翰.霍兰，隐秩序：适应性造就复杂性，周晓牧和韩晖译，上海科技教育出版社，上海，2000。
13. R. Albert and A.L.Barabasi, Statistical mechanics of complex networks, Rev.Modern Physics, 74, p 48-97, 2002.
14. M. E. J. Newman, The structure and function of complex networks, SIAM Review, 45, p 167-256, 2003.
15. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D. U. Hwang, Complex networks: Structure and dynamics, Physics Report, 424,p175-308, 2006.
16. O.Mason and M. Verwoerd, Graph theory and networks in biology, p.1-52, (传给我时，文章第一页写明完成日期为2006.4.6).
17. K. I. Goh, E. Oh, B. Kahng and D. Kim, Betweenness centrality correlation in social networks, Phys.Rev.E, 67, 017101, 2003.
18. M. E. J. Newman, Mixing pattern in networks, Phys.Rev.E., 67, 026126, 2003.
19. P. Erdos and A. Renyi, On random graphs, Publicationes Mathematicae, 6, p 290-297, 1959.
20. P Erdos and A. Renyi, On the evolution of random graphs, Publications of the Mathematical Institute of the Hungarian Academy of Science, 5, p 17-61, 1960.
21. D. J. Watt and S. H. Strogatz, Collective dynamics of small-world networks, Nature, 393, p440-442, 1998.
22. R. Monasson, Diffusion,localization and dispersion relations on small-world lattices, Eur. Phys. J. B., 12, p555-567, 1999.
23. M. E. J. Newman and D. J. Watt, Renormalization group analysis of the small-world network model, Phys. Lett. A, 263, p341-346, 1999.
24. M. E. J. Newman, C. Moore and D. J. Watt, Mean-field solution of the small-world network model, Phys.Rev.Lett., 84, p3201-3204, 2000.
25. A. Barrat and M. Weigt, On the properties of small-world networks, Eur. Phys. J. B., 13, p547-560, 2000.
26. A. L. Barabasi and R. Albert, Emergence of scaling in random networks, Science, 286, p509-512, 1999.
27. R. Albert and A. L. Barabasi, Dynamics of complex systems: Scaling laws for the period of Boolean networks, Phys.Rev.Lett., 84, p5660-5663, 2000.
28. R. Albert and A. L. Barabasi, Topology of evolving networks:local events and universality, Phys.Rev.Lett., 85, p5234-5237, 2000.
29. P. L. Krapivsky, S. Redner and F. Leyvraz, Connectivity of growing random networks, Phy.Rev.Lett, 85, p4629-4632, 2000.
30. S. N. Dorogovtsev and J. F. F. Mendes, Effect of the accelerating growth of communications networks on their structure, Phys.Rev.E, 63, 025101, 2001.
31. S. N. Dorogovtsev and J. F. F. Mendes, Scaling behaviour of developing and decaying networks, Europhys.Lett., 52, p33-39, 2000.
32. P. L. Krapivsky and S. Redner, A statistical physics perspective on Web growth, Computer Networks, 39, p261-276, 2002.
33. B. Tadic, Dynamics of directed graphs: The World-Wide Web, Physica A, 293, p273-284, 2001.
34. G Bianconi and A. L. Barabasi, Bose-Einstein condensation in complex networks, Phys.Rev.Lett, 86, p5632-5635, 2001.
35. A. Vazquez  et al, Modeling of protein interaction networks, ComPlexUs, 1, p38-46, 2003.
36. R. Sole et al., A model of large scale proteome evolution, Advances in Complex Systems, 5, p43-54, 2002.
37. F. Chung and L. Lu, Coupling online and offline analyses for random power graphs, Internet Mathematics, 1, p409-461, 2004.
38. A. Bhan, D. Galas and T. G. Dewey, Non-negative matrices in the mathematical sciences, SIAM classics in applied mathematics, P?1994.
39. J. Berg, M. Lassing and A. Wagner, Structure and evolution of protein interaction networks: a statistical model for link dynamics and gene duplications, BMC Evolutionary Biology, 4, p51, 2004.
40. R. Milo et al., Network motifs: simple building blocks of complex networks, Science, 298, p824-827, 2002.
41. M. Newman, Fast algorithm for detecting community structure in networks, Phys.Rev.E, 69, 066133, 2004.
42. M. Newman and M.Girvan, Finding and evaluating community structure in networks, Phys.Rev.E, 69, 026113, 2004.
43. R.Milo et al., Superfamilies of evolved and designed networks, Science, 303, p1538-1542, 2004.
44. F. Radicchi et al., Defining and identifying communities in networks, Proc.Nat.Acad.Sci., 101, p2658-2663, 2004.
45. E. Ziv, M. Middendorf and C. Wiggins, An information-theoretic approach to network modularity, Phys.Rev.E, 71, 046117, 2005.
46. S. Yook, Z. Oltvai and A. Barabasi, Functional and topological characterization of protein interaction networks, Proteomics, 4, p928-942, 2004.
47. S. Wuchty, Z. Oltvai and A. Barabasi, Evolutionary conservation of motif constituents in the yeast protein interaction network, Nature Genetics, 35, p176-179, 2003.
48. E. Segal et al., Module networks: identifying regulatory modules and their condition-specific regulators from gene expression data, Nature Genetics, 34, p166-176, 2003.
49. N. Przulj, D Wigle and I. Jurisica, Functional topology in a network of protein interactions, Bioinformatics, 20, p340-348, 2004.
50. N. Kashtan et al., Topological generalizations of network motifs, Phys.Rev.E, 70, 031909, 2004.
51. S. Fortunato, V. Latora and M. Marchiori, Method to find community structures based on information centrality, Phys.Rev.E, 70, 056104, 2004.
52. M. Girvan and M.Newman, Community structure in social and biological networks, Proc.Nat.Acad.Sci., 99, p7821-7826, 2002.
53. A. Enright, S. Van Dongen and C. Ouzounis, An efficient algorithm for large-scale detection of protein families, Nucleic Acids Research, 30, p1575-1584, 2002.
54. Z. Bar-Joseph et al., Computational discovery of gene modules and regulatory networks, Nature Biotechnology, 21, p1337-1342, 2003.
55. 汪小帆、李翔、陈关荣：复杂网络—理论与应用. 清华大学出版社，2006.
56. C. W. Wu and L. O. Chua, Application of graph theory to the synchronization in an array of coupled nonlinear oscillators. IEEE Trans. Circuits & Systems–I 42, p494–497, 1995.
57. C. W. Wu and L. O. Chua. Synchronization in an array of linearly coupled dynamical systems. IEEE Trans. Circuits & Systems–I 42, p430-447, 1995.
58. C. W. Wu. Synchronization in networks of nonlinear dynamical systems via a directed graph. Nonlinearity 18, p1057-1064, 2005.
59. X. F. Wang and G. R. Chen. Synchronization in small-world dynamical networks. Int. J. Bifurcation & Chaos 12, p187-192, 2002.
60. X. F. Wang and G. R. Chen. Synchronization in scale-free dynamical networks: robustness and fragility. IEEE Trans. Circuits & Systems–I 49, p54-62, 2002.
61. X. Li and Chen G. R. Synchronization and desynchronization of complex dynamical networks: an engineering viewpoint. IEEE Trans. Circuits & Systems-I 50,  p1381-1390, 2003.
62. J. H. Lu, X. H. Yu, G. R. Chen, and D. Z. Cheng Characterizing the synchronizability of small-world dynamical networks. IEEE Trans. Circuits & Systems-I 51, p787-796, 2004.
63. Z. Li and G. R. Chen, Global synchronization and asymptotic stability of complex dynamical networks. IEEE Trans. Circuits & Systems–II 53, p28-33, 2006.
64. L. M. Pecora and T. L. Carroll, Master stability functions for synchronized coupled systems. Phys. Rev. Lett. 80, p2109, 1998.
65. M. Barahona and  L. M. Pecora. Synchronization in small-world systems. Phys. Rev. Lett. 89, p054101, 2004.
66. W. L. Lu and T. P. Chen. New approach to synchronization analysis of linearly coupled ordinary differential equations. Physics D 213, p214-230, 2006.
67. C. G. Li and G. R.Chen. Synchronization in general complex dynamical networks with coupling delays. Physica A 343, p236-278, 2004.
68. J. Zhou and T. P. Chen, Synchronization in general complex delayed dynamical networks, IEEE Trans. Circuits & Systems -I, 53, p733-744，2006.
69. 周进, 陈天平和刘美春, 具有脉冲效应的复杂动力网络模型, 第二届全国复杂动态网络学术论坛论文集，中国高等科学技术中心出版社，170(I), p231-235,2005。
70. G. R. Chen, J. Zhou and S. Celikovsky, On LaSalle’s invariance principle and its application to robust synchronization of general vector Lienard equation, IEEE, Trans, Automat, Control, 49, p869-874. 2005.
71. J. Xu and K. W. Chung, “Effects of time delayed position feedback on van Pol-Duffing oscillator,” Physica D, 180, p17-39, 2003.
72. G. R. Chen, J. Zhou and Z. G. Liu, Global synchronization of coupled delayed neural networks and applications to chaotic CNN models, Int. J. Bifur & Chaos, 14: p2229-2240, 2004.
73. J. Zhou, T. P. Chen and L, Xiang, Robust synchronization of coupled delayed recurrent neural networks, Lecture Notes in Computer Science, Springer-Verlag, Berlin Heidelberg, New York, 3173: p144-149, 2004.
74. J. Zhou, T. P. Chen and L, Xiang, Robust synchronization of delayed neural networks based on adaptive control and parameters identification, Chaos, Solitons, Fractals, 27: p905-913, 2006.
75. J. Zhou, T. P. Chen and L, Xiang, Adaptive synchronization of delayed neural networks based on parameters identification, Lecture Notes in Computer Science, Springer-Verlag, Berlin Heidelberg, New York, 3496: p308-313, 2005.
76. J. Zhou, T. P. Chen L, Xiang and M. C. Liu, Global synchronization of impulsive coupled delayed neural networks, Lecture Notes in Computer Science, Springer-Verlag, Berlin Heidelberg, New York, 3971: p303-308, 2006.
77. J. Zhou, T. P. Chen and  L, Xiang, Chaotic lag synchronization of coupled delayed neural networks and its applications in secure communication, Circuits, Systems and Signal Processing, 25: p599-613, 2005.
78. Y. Kuramoto, In H. Arakai, editor, International Symposium on Mathematical Problems in Theoretical Physics, Volume 39 of Lecture Notes in Physics, Springer, New York, 1975.
79. J. A. Acebron, L. L. Bonilla, C. J. Perez Vicente, F. Ritort and R. Spigler, The Kuramoto model: A simple paradigm for synchronization phenomena, Rev. Mod. Phys., 77, p137-185, 2005.
80. S. H. Strogatz, From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators, Physica D, 143, p1-20, 2000.
81. H. Hong, H. Parkand M. Y. Choi, Collective synchronization in spatially extended systems of coupled oscillators with random frequencies, Phys.Rev.E, 72, 036217, 2005.
82. H. Hong, B. J. Kim, M.Y. Choi and H. Park, Factors that predict better synchronizability on complex networks, Phy.Rev.E., 69, 067105, 2004.
83. H. Hong, M. Y. Choi and B.J.Kim, Synchronization on small-world networks, Phys.Rev.E., 65, 026139, 2002.
84. Y. M. Moreno Vega, M. Vasquez-Prada and A. F. Pacheco, Fitness for synchronization of network motifs, Physica A, 343, p279-287, 2004.
85. F. Liljeros et. al., The Web of Human sexual contact, Nature, 411, p907, 2001.
86. R. Pastor-Satorras et.al, Epidemic spreading in scale-free networks, Phys.Rev.Lett., 86, p3200-3203, 2002
87. R. M. May and A. L. Lloyd, Infection dynamics on scale-free networks, Phys.Rev.E., 64, 066112, 2001.
88. R. Pastor- Satorras, and A. Vespignani, Epidemic dynamics in finite size scale-free networks, Phys.Rev.E., 65, 035108, 2002.
89. M. Boguna, R. Pastor-Satorras and A.Vespignani, Absence of epidemic threshold in scale-free networks with degree correlations, Phys.Rev.Lett., 90, 028701, 2003.
90. R. M. Anderson and R. M. May, Infectious Diseases of Humans: Dynamics and Control, Oxford University Press, 1991.
91. R. M. Anderson and R. M. May, Infectious diseases of humans: dynamics and control, Oxford University Press, 1991.
92. H. Hethcote, The mathematics of infectious diseases, SIAM. Review, 42(3), p599-653, 2000.
93. D. Hwang, et.al, Thresholds for epidemic outbreaks in finite scale- free networks, Mathematical Bioscience and Engineering, 2, p317-327, 2005.
94. A. Enright, S. Van Dongen and C.Ouzounis, An efficient algorithm for large-scale detection of protein families, Nucleic Acids Research, 30, p1575-1584, 2002.
95. M. Boguna and R. Pastor-Satorras, Epidemic spreading in corrected complex networks, Phys.Rev.E., 66, 047104, 2002.
96. Z. Dezso and A. Barabasi, Halting viruses in scale free networks, Phys.Rev.E., 65, 055103, 2002.
97. R Pastor-Satorras and A.Vespignani, Immunization of complex networks, Phys.Rev.E., 65, 036104, 2002.
98. S. Eubank et.al., Modelling disease outbreak in realistic urban social networks, Nature, 429, p180-182, 2004.
99. N. Becker et.al., Controlling emerging infectious diseases like SARS, Mathematical Bioscience, 193, p205-221, 2005.
100.    S. Shen-Orr, R. Milo, S. Mangan and U.Alon, Network motifs in the transcriptional regulatory network of Escherichia coli, Nature Genetics, 31, p64-68, 2002.
101.    Y. M. Moreno Vega, M Vasquez-Prada and A F Pacheco, Fitness for synchronization of network motifs, Physica A., 343, p279-287, 2004.
102.    Z. H. Ma , Z. R. Liu and G.. Zhang, A new method to realize cluster synchronization in connected chaotic network, Chaos, 16, 023103, 2006.
103.    I. Belykh, V. Belykh, and M. Hasler, .Blinking model and synchronization in small-world networks with a time-varying coupling, Physica D, 195, p188-206, 2004.
104.    I. Belykh, V. Belykh, and M. Hasler, Connection graph stability method for synchronized coupled chaotic systems, Physica D, 195, p159-187, 2004.
105.    Daniel J. Stilwell; Erik M. Bollt; D. Gray Roberson; Daniel J. Stilwell; Erik M. Bollt; D. Gray Roberson; Sufficient Conditions for Fast Switching Synchronization in Time-Varying Network Topologies, SIAM Journal on Applied Dynamical Systems ,5 p140-156 2006.

账号		自动登录	找回密码
密码			我要加入

[应用数学] [讨论]Scale-free 网络与small-world 网络

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

回复：（多情清秋）[讨论]Scale-free 网络与small-wor...

评分

回复：（多情清秋）[讨论]Scale-free 网络与small-wor...

回复：（多情清秋）[讨论]Scale-free 网络与small-wor...

回复：（多情清秋）[讨论]Scale-free 网络与small-wor...

回复：（lchzxz）我用了楼上的无标度网络的生成程序,很...

评分

Scale Free Part II

Part III

Part III

Part IV

评分

scale free

回复 #1 多情清秋的帖子

评分

[应用数学] [讨论]Scale-free 网络与small-world 网络

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

回复：（多情清秋）[讨论]Scale-free 网络与small-wor...

评分

回复：（多情清秋）[讨论]Scale-free 网络与small-wor...

回复：（多情清秋）[讨论]Scale-free 网络与small-wor...

回复：（多情清秋）[讨论]Scale-free 网络与small-wor...

回复：（lchzxz）我用了楼上的无标度网络的生成程序,很...

评分

Scale Free Part II

Part III

Part III

Part IV

评分

scale free

回复 #1 多情清秋 的帖子

评分

回复 #1 多情清秋的帖子