下载文档原格式
复杂网络中的小世界性质研究随着互联网的普及，我们已经进入了一个高度连通的时代。
如果把所有人、所有物理设备、所有数字设备联结起来形成一个大网络，这就是一个复杂网络，它已经不再是一棵简单的树形网络，而是拥有了各种各样的连接方式，从而形成了一个复杂的结构。
在这个复杂网络中，人们更容易形成自己的小世界。
什么是小世界性质小世界性质是指，在一个复杂网络中，大多数节点可以在很短的时间内通过不多的步骤到达任意其他节点。
这个现象是由于网络中普遍存在着两种链接：一种是“短链接”，即较短距离内的连接；另一种是“长链接”，即较长距离的连接。
在一个小世界网络中，大多数节点都是通过较短的链接连接的，只有少数节点通过较长的链接才能达到其他节点。
小世界网络的构建小世界网络的构建通常采用“随机重连”算法。
具体方法是：在一个有N个节点的圆环模型上，每个节点与相邻的m个节点相连。
随机地选择一个节点，断开它与其相邻的链接，然后随机地选取一个节点与其相连。
在这个过程中，短链接能够被保留下来，而一部分长链接会被替换成短链接。
通过这样的重连过程，原本的环形结构被打乱，形成了一个小世界网络。
小世界性质在现实生活中的应用小世界性质在现实生活中有着广泛的应用。
例如，社交网络中的朋友关系就是一个小世界网络。
在社交网络中，大多数人认识的人都是通过较少的步骤得到的，而每个人所认识的朋友圈也通常分布在全球范围内。
类似地，物理网络中的交通路径、电力系统、道路网络等也可以被视为小世界网络。
在这些系统中，信息传输的速度都非常快，但是网络之间的连接却比较稀疏。
小世界网络的拓扑结构小世界网络的拓扑结构由短链接和长链接构成，其中大量短链接形成了网络中的大部分路径，而只有少量的长链接连接了远离的节点。
对于一个小世界网络，我们通常关心的是三个指标：网络的直径、聚集系数和节点度分布。
网络的直径是指任意两个节点之间最短路径的最大值。
在一个小世界网络中，网络的直径很小，通常只有几个节点的距离。
课题：WS小世界网络模型构造姓名赵训学号 2班级计算机实验班一、WS 小世界网络简介1998年, Watts和Strogatz 提出了小世界网络这一概念,并建立了WS模型。
实证结果表明,大多数的真实网络都具有小世界特性(较小的最短路径) 和聚类特性(较大的聚类系数) 。
传统的规则最近邻耦合网络具有高聚类的特性,但并不具有小世界特性;而ER 随机网络具有小世界特性但却没有高聚类特性。
因此这两种传统的网络模型都不能很好的来表示实际的真实网络。
Watts 和Strogatz建立的WS小世界网络模型就介于这两种网络之间,同时具有小世界特性和聚类特性,可以很好的来表示真实网络。
二、WS小世界模型构造算法1、从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。
2、随机化重连：以概率p随机地从新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。
其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。
在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡，如图a所示。
图a相应程序代码（使用Matlab实现）ws_net.m （位于“代码”文件夹内）function ws_net()disp('WS小世界网络模型')N=input('请输入网络节点数');K=input('请输入与节点左右相邻的K/2的节点数');p=input('请输入随机重连的概率');angle=0:2*pi/N:2*pi-2*pi/N;x=100*cos(angle);y=100*sin(angle);plot(x,y,'r.','Markersize',30);hold on;%生成最近邻耦合网络；A=zeros(N);for i=1:Nif i+K<=Nfor j=i+1:i+KA(i,j)=1;endelsefor j=i+1:NA(i,j)=1;endfor j=1:((i+K)-N)A(i,j)=1;endendif K<ifor j=i-K:i-1A(i,j)=1;endelsefor j=1:i-1A(i,j)=1;endfor j=N-K+i:NA(i,j)=1;endendenddisp(A);%随机化重连for i=1:Nfor j=i+1:Nif A(i,j)==1pp=unifrnd(0,1);if pp<=pA(i,j)=0;A(j,i)=0;b=unidrnd(N);while i==bb=unidrnd(N); endA(i,b)=1;A(b,i)=1;endendend%根据邻接矩阵连线for i=1:Nfor j=1:Nif A(i,j)==1plot([x(i),x(j)],[y(i),y(j)],'linewidth',1); hold on;endendendhold offaver_path=aver_pathlength(A);disp(aver_path);对应输出（取网络节点数N=16，K=2；p分别取0，0.1，1）。
复杂网络的拓扑结构分析及其应用研究一、引言随着信息技术的飞速发展，网络已经成为了现代社会交流与信息传递的重要载体，给我们带来了方便的同时也带来了各种问题。
这些问题的解决需要我们对网络进行深入的探究研究，而网络的拓扑结构对网络的性质和能力有着重要的影响。
二、复杂网络的概念和特征复杂网络是一类由大量节点和连接构成的系统，具有多种节点类型和连接方式，节点间的关系也是复杂多样的。
复杂网络的典型特征包括：小世界现象、无标度性和社区结构等。
1.小世界现象小世界现象指的是节点间距离很短，任意两个节点之间的路径长度很短，同时网络中存在着很多的“短路路径”。
这种现象来源于网络中的高局部聚集性和低全局聚集性。
2.无标度性无标度性指的是复杂网络在节点度数分布方面的不均衡，即只有少数节点拥有大量的连接，而大多数节点的连接数相对较少。
这种现象决定了网络的鲁棒性和优良的缩放性质。
3.社区结构社区结构指的是网络中具有一定内部连通性、外部隔绝性的子网络。
这种结构在社交网络、生物网络等领域中非常重要，能够帮助我们深刻地理解网络中的群体现象。
三、复杂网络的拓扑结构分析方法复杂网络的拓扑结构分析是研究复杂网络中连通性、聚集性、分布性等方面的一种分析方法，它能够揭示网络的内在结构以及各种特性。
常用的复杂网络拓扑结构分析方法包括：节点中心性分析、子图分析和社区结构分析等。
1.节点中心性分析节点中心性分析是一种评估节点重要程度的方法，其中包括度中心性、接近度中心性和媒介中心性等指标。
度中心性指的是节点的度数，即与该节点直接相连的节点数；接近度中心性指的是节点与网络中其他节点的平均距离的倒数；媒介中心性指的是一个节点在所有最短路径上出现的次数，即节点在网络中扮演的中介角色。
2.子图分析子图分析是一种研究复杂网络重要子结构的方法，可以帮助我们挖掘网络中相互作用的节点组合及其在网络中的作用。
常见的子图包括星形子图、三角形子图等，这些子图通常和网络中的社区结构紧密相关。
一种结合小世界模型改良的NMF社区发现算法赵雨露;张曦煌【摘要】社区发现是当前复杂网络与数据挖掘的热点,非负矩阵分解是社区发现的常用手段.针对当前非负矩阵分解的社区发现算法,为提高算法的准确率与可解释性,提出多阶邻居节点的概念,在小世界模型的基础上构建了规模可控的多阶复合信息矩阵,用后处理的方法减少了算法中随机因素带来的不稳定性.对于真实网络与人工网络的实验证明,新背景下的算法较原算法在性能上有一定的提升.%Community detection is the hotspot of current complex networks and data mining,whose common means is non-negative matrix factorization.To improve the accuracy and interpretability of community detection algorithm,we propose the concept of first-order neighbors.On the basis of the small-world model,this paper constructed a controllable scale multi-stage compound information matrix.Treatment reduced the algorithm after using random factors of instability.Regarding experimental proof of the real network and artificial networks,new algorithms increase in performance compared to the original algorithm.【期刊名称】《计算机应用与软件》【年(卷),期】2017(034)010【总页数】6页(P269-274)【关键词】社区发现;非负矩阵分解;小世界模型;复杂网络【作者】赵雨露;张曦煌【作者单位】江南大学物联网工程学院江苏无锡214122;江南大学物联网工程学院江苏无锡214122【正文语种】中文【中图分类】TP301.6现实世界中存在大量可以抽象为复杂网络的关系形式，例如人际网络、通信网络和软件中API的调用等。
小世界模型平均路径长度小世界模型是网络科学中的一个重要概念，它描述了现实生活中许多网络系统的特征。
其中一个重要指标就是平均路径长度，它衡量了网络中两个节点之间的平均距离。
本文将围绕小世界模型平均路径长度展开讨论，介绍小世界现象、小世界网络的生成机制以及平均路径长度的计算方法。
一、小世界现象小世界现象是指在许多实际网络中，节点之间的平均距离相对较小，远远小于节点总数。
这意味着网络中的节点之间存在着短路径，人们可以通过少数的步骤就能够相互联系。
小世界现象的典型代表是社交网络，比如Facebook、微信等。
在这些社交网络中，我们可以通过共同的朋友或者兴趣爱好迅速找到彼此。
二、小世界网络的生成机制小世界网络的生成机制主要包括随机连接和局部重连两个过程。
首先，随机连接阶段，网络中的节点随机地与其他节点建立连接，形成一个随机网络。
然后，在局部重连阶段，节点会重新连接到与其距离较近的节点，以形成更为紧密的联系。
通过这两个过程的迭代，网络中形成了许多短路径，从而呈现出小世界现象。
三、平均路径长度的计算方法平均路径长度是衡量小世界网络结构特征的一个重要指标。
它表示网络中任意两个节点之间的平均距离。
计算平均路径长度的方法是首先计算网络中每对节点之间的最短路径长度，然后将这些最短路径长度进行平均。
在大型网络中，计算所有节点对之间的最短路径长度是不现实的，因此可以使用一种近似的方法，例如随机选取一部分节点对进行计算，然后将结果进行平均。
四、小世界模型在实际中的应用小世界模型不仅仅是对网络结构的一种描述，它也广泛应用于各个领域。
在社交网络中，小世界模型可以用来解释信息传播的速度和路径选择；在物理学领域，小世界模型可以用来研究粒子之间的相互作用；在生物学领域，小世界模型可以用来研究蛋白质相互作用网络等。
总结：小世界模型平均路径长度是衡量网络中节点之间距离的重要指标。
小世界现象描述了许多实际网络中的特征，而小世界网络的生成机制包括随机连接和局部重连两个过程。
课题：WS小世界网络模型构造姓名赵训学号************班级计算机实验班一、WS 小世界网络简介1998年, Watts和Strogatz 提出了小世界网络这一概念,并建立了WS模型。
实证结果表明,大多数的真实网络都具有小世界特性(较小的最短路径) 和聚类特性(较大的聚类系数) 。
传统的规则最近邻耦合网络具有高聚类的特性,但并不具有小世界特性;而ER 随机网络具有小世界特性但却没有高聚类特性。
因此这两种传统的网络模型都不能很好的来表示实际的真实网络。
Watts 和Strogatz建立的WS小世界网络模型就介于这两种网络之间,同时具有小世界特性和聚类特性,可以很好的来表示真实网络。
二、WS小世界模型构造算法1、从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。
2、随机化重连：以概率p随机地从新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。
其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。
在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡，如图a所示。
图a相应程序代码（使用Matlab实现）ws_net.m （位于“代码”文件夹内）function ws_net()disp('WS小世界网络模型')N=input('请输入网络节点数');K=input('请输入与节点左右相邻的K/2的节点数');p=input('请输入随机重连的概率');angle=0:2*pi/N:2*pi-2*pi/N;x=100*cos(angle);y=100*sin(angle);plot(x,y,'r.','Markersize',30);hold on;%生成最近邻耦合网络；A=zeros(N);for i=1:Nif i+K<=Nfor j=i+1:i+KA(i,j)=1;endelsefor j=i+1:NA(i,j)=1;endfor j=1:((i+K)-N)A(i,j)=1;endendif K<ifor j=i-K:i-1A(i,j)=1;endelsefor j=1:i-1A(i,j)=1;endfor j=N-K+i:NA(i,j)=1;endendenddisp(A);%随机化重连for i=1:Nfor j=i+1:Nif A(i,j)==1pp=unifrnd(0,1);if pp<=pA(i,j)=0;A(j,i)=0;b=unidrnd(N);while i==bb=unidrnd(N); endA(i,b)=1;A(b,i)=1;endendend%根据邻接矩阵连线for i=1:Nfor j=1:Nif A(i,j)==1plot([x(i),x(j)],[y(i),y(j)],'linewidth',1); hold on;endendendhold offaver_path=aver_pathlength(A);disp(aver_path);对应输出（取网络节点数N=16，K=2；p分别取0，0.1，1）。
小世界现象
"六度分离"现象在学术上称为小世界现象，定义是:若网络中任意两点间的平均距离L 随网络格点数N 的增加呈对数增长，即L ~ l n N ，且网络的局部结构上仍具有较明显的集团化特征，则称该网络具有小世界效现象。
小世界现象最初由匈牙利作家F.Karinthy在1929年提出了"小世界现象"的论断。
他认为，地球上的任何两个人都可以平均通过一条由5位联系人组成的链条而联系起来。
在20世纪60年代，美国哈佛大学社会心理学教授斯坦利·米尔格兰姆(Stanley Milgram ) 通过设计一个连锁信件实验，提出了著名的"六度分隔(Six Degrees of Separation) 假说"，大意为任何两个欲取得联系的陌生人之间最多只隔着5个人，便可完成两人之间的联系。
当年，米尔格兰姆给内布拉斯加州奥马哈市随意选择的300多人发信，要求他们把他的这封信寄给波士顿市一个独一无二的"目标"人，分别由每个人独自联系。
米尔格兰姆告诉每个发信人有关目标人的信息,包括姓名、所在地、职业，如果发信人不认识这个目标人，他们把这封信寄给他们认为有可能认识目标人的熟人。
依此类推形成了发信人的链条，链上的每个成员都力图把这封信寄给他们的朋友、家庭成员、或同事熟人，以便使信件尽快到达目标人。
米尔格兰姆发现，有60个链条最终到达目标人，链条中平均步骤大约为6 ，即点与点之间连线数为6，米尔格兰姆由此得出结论:任意两个人都可通过平均5个熟人联系起来。
