小世界现象在P2P网络中的应用研究
!第"#卷!第$期南京邮电大学学报（自然科学版）
%&’("#!)&($
!!"**#年+月,&-./0’&1)0/23/45/367.839:&1;&8980/<=7’7>&??-/3>093&/8（)09-.0’@>37/>7）A-4("**#
!!文章编号：B#CDEF$DG （"**#）*$E**+#E*$
小世界现象在!"!网络中的应用研究
李玲娟，姬同亮，王汝传
南京邮电大学计算机学院，
江苏南京()!"B***D 摘!要：简要介绍了@?0’’EH&.’<模型和@>0’7EI.77模型，详细介绍了小世界现象在;";网络中资源搜
索以及网络安全方面可能的D 个应用点，并提出了一种基于“小世界现象”的高效的资源搜索策略———关键节点资源搜索法。该搜索法将中央索引模型和泛洪请求模型相结合，一方面增强了可伸缩性和容错性，另一方面避免了消息泛滥，使得搜索效率明显增强。关键词：小世界；无标度；对等；捷径；关键节点中图分类号：=;DGD(*"!!!文献标识码：J
#$%&’’()*+,)-./%0%+1*$-234+((56-1(7!$%.-4%.+
).!"!8%,9-1:0
;<;).=5>?+.，@<#-.=5()+.=，6&8A /?5*$?+.
K&’’747&1K&?L-97.，)0/23/45/367.839:&1;&8980/<=7’7>&??-/3>093&/8，)0/23/4"B***D ，()
KM3/0&B0,1+*,：=M38L0L7.13.89N.371’:3/9.&<->789M7@?0’’EH&.’<0/<@>0’7EI.77?&<7’8(=M7/393/9.&<->783/<7E 903’9M.77L&97/930’0LL’3>093&/8&1@?0’’EH&.’
C%D 9-170：@?0’’EH&.’<；@>0’7EI.77；;77.E9&E;77.；@M&.9>-9；@93>P3/4EL&3/9
!!收稿日期："**FE*GE*C ；修回日期："**FEB"E*G 基金项目：国家自然科学基金（C*"CB*F*）、江苏省自然科学基
金（JT"**FB$#）、江苏省自然科学基金预研项目（JT"**$"B+）、江苏省高技术研究计划（JU"**$**$）、江苏省计算机信息处理技术重点实验室基金（P28*F***B ）资助项目
EF 引F 言
;";（;77.E9&E;77.）网络即对等网络，是一种点对点计算模式，因其强大的资源共享和平衡网络负载的能力，被誉为第三代网络。它区别于K V @结构或J V @结构最显著的特点是整个网络不存在中心节点，其中的每一个节点大都同时具有信息消费者、
信息提供者和信息通讯等D 方面的功能。网络终端节点的计算和存储能力以及连接带宽持续保持类摩尔定律式的增长，为;";提供了更为广阔的前景。但是现有的;";网络在资源搜索和查询效率以及通信安全等方面的性能仍需进一步提高。
基于已有的经验和理论成果，依据网络的连通性分布!（"），可把复杂网络分成两类。第一类称为指数网络，是指!（"）呈指数分布，例如HE@小世界模型。第二类称为无标度网络，是指!（"）呈幂律分布。很多网络，如HHH 、S/97./79和U/-97’’0等都属于这一类。很多科学家将上述规律称之为“小世界（@?0’’H&.’<）现象”。
万方数据
数据挖掘在社交网络中的隐私保护
数据挖掘在社交网络中的隐私保护 唐伟晨(学号:111220114) (南京大学计算机科学与技术系, 南京210093) Privacy-Preserving Data Mining in Online Communities Weichen Tang (Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China) Abstract: Online communities are the most dense area of individual privacy. With the rapid development of online communities, the number of privacy-disclosure problems has been increasing. This article shows the privacy-preserving data mining technology, including how to preserve privacy, the challenges we face and the benefits of privacy-preserving data mining in online communities. Key words: data mining; social networks; privacy protection 摘要: 在线社区是网络中个人隐私最为密集的区域。在线社区的飞速发展的同时，隐私泄露的问题也日益增多。本文介绍隐私保护数据挖掘技术，包括隐私保护的方法、面临的挑战以及实现在社交网络中隐私保护的数据挖掘的优势。 关键词: 数据挖掘；社交网络；隐私保护 中图法分类号: TP301文献标识码: A 1 引言 近年来在线社区发展迅速，规模越来越大。截至2013年底我国微博用户为2.81亿，人人网注册用户2.8亿，还有许多大型论坛、企业社区、地方社区等等。可见在线社区用户规模庞大，可想而知在线社区中的数据规模也是十分庞大的。庞大的数据，又有各种应用数据挖掘技术的工具对这些数据进行着分析，就会很自然地引发关于隐私方面的争论。由于对数据挖掘技术的不了解，很多人都在批判将数据挖掘应用于在线社区等隐私集中的区域。本文将介绍数据挖掘是如何在发挥自身长处的同时保护用户隐私的。 2 背景介绍 1. 在线社区简介 在线社区是建立在网络上的虚拟社区。用户通过注册来使用在线社区的扩展功能。在线社区既可以是互不相识的人们之前的交友平台，也可以是早已认识的两人的联络途径。在线社区的主要分类有两种，一种是所有人都可以在其中发布信息的，例如微博、BBS等，另一种则是拥有一定权限的人才可以在其中发布信息，例如博客，人人网个人主页等。 2. 数据挖掘的隐私和安全 随着数据挖掘的广泛应用，人们越来越多担心如此大规模的应用数据挖掘，可能会对自己的隐私造成侵
小世界网络
4.2 小世界网络 4.2.1 小世界网络简介 1998年, Watts和Strogatz 提出了小世界网络这一概念，并建立了WS模型。实证结果表明，大多数的真实网络都具有小世界特性（较小的最短路径）和聚类特性（较大的聚类系数）。传统的规则最近邻耦合网络具有高聚类的特性，但并不具有小世界特性；而随机网络具有小世界特性但却没有高聚类特性。因此这两种传统的网络模型都不能很好的来表示实际的真实网络。Watts和Strogatz建立的小世界网络模型就介于这两种网络之间，同时具有小世界特性和聚类特性，可以很好的来表示真实网络。 4.2.2 小世界模型构造算法 1、从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。 2、随机化重连：以概率p随机地从新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。 在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p 的值就可以控制从完全规则网络到完全随机网络的过渡。 相应程序代码（使用Matlab实现） ws_net.m （位于“代码”文件夹内） function ws_net() disp('小世界网络模型') 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); disp(A); for i=1:N if i+K<=N for j=i+1:i+K A(i,j)=1; end else for j=i+1:N A(i,j)=1; end for j=1:((i+K)-N) A(i,j)=1; end
复杂网络的基础知识
第二章复杂网络的基础知识 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) 二维无限规则网络
2.2 复杂网络的基本特征量 描述复杂网络的基本特征量主要有：平均路径长度（average path length ）、簇系数（clustering efficient ）、度分布（degree distribution ）、介数（betweenness ）等，下面介绍它们的定义。 2.2.1 平均路径长度（average path length ） 定义网络中任何两个节点i 和j 之间的距离l ij 为从其中一个节点出发到达另一个节点所要经过的连边的最少数目。定义网络的直径（diameter ）为网络中任意两个节点之间距离的最大值。即 }{max ,ij j i l D = （2-1） 定义网络的平均路径长度L 为网络中所有节点对之间距离的平均值。即 ∑∑-=+=-=111)1(2N i N i j ij l N N L （2-2） 其中N 为网络节点数，不考虑节点自身的距离。网络的平均路径长度L 又称为特征路径长度（characteristic path length ）。 网络的平均路径长度L 和直径D 主要用来衡量网络的传输效率。 2.2.2 簇系数（clustering efficient ） 假设网络中的一个节点i 有k i 条边将它与其它节点相连，这k i 个节点称为节点i 的邻居节点，在这k i 个邻居节点之间最多可能有k i (k i -1)/2条边。节点i 的k i 个邻居节点之间实际存在的边数N i 和最多可能有的边数k i (k i -1)/2之比就定义为节点i 的簇系数，记为C i 。即 ) 1(2-=i i i i k k N C (2-3) 整个网络的聚类系数定义为网络中所有节点i 的聚类系数C i 的平均值，记
WS小世界网络模型的程序代码(matlab)
程序仿真实例 例一、请输入最近邻耦合网络中节点的总数N:30 请输入最近邻耦合网络中每个节点的邻居数K:4 请输入随机化重连的概率p:0.9 例二、请输入最近邻耦合网络中节点的总数N:40 请输入最近邻耦合网络中每个节点的邻居数K:2 请输入随机化重连的概率p:0.7
Matlab的m文件代码如下： N=input('请输入最近邻耦合网络中节点的总数N:'); K=input('请输入最近邻耦合网络中每个节点的邻居数K:'); if K>floor(N-1)|mod(K,2)~=0; disp('参数输入错误：K值必须是小于网络节点总数且为偶数的整数'); return ; end angle=0:2*pi./N:2*pi-2*pi/N; angle=0:2*pi/N:2*pi-2*pi/N; x=100*sin(angle); y=100*cos(angle); plot(x,y,'ro','MarkerEdgeColor','g','MarkerFaceColor','r','MarkerSize',8); hold on; A=zeros(N); for i=1:N for j=i+1:i+K/2 jj=j; if j>N jj=mod(j,N); end A(i,jj)=1; A(jj,i)=1; end end %WS小世界网络的代码 p=input('请输入随机化重连的概率p:'); for i=1:N for j=i+1:i+K/2
jj=j; if j>N jj=mod(j,N); end p1=rand(1,1); if p1
复杂网络基础2(M.Chang)
复杂网络基础理论 第二章网络拓扑结构与静态特征
第二章网络拓扑结构与静态特征 l2.1 引言 l2.2 网络的基本静态几何特征 l2.3 无向网络的静态特征 l2.4 有向网络的静态特征 l2.5 加权网络的静态特征 l2.6 网络的其他静态特征 l2.7 复杂网络分析软件 2
2.1 引言 与图论的研究有所不同，复杂网络的研究更侧重 于从各种实际网络的现象之上抽象出一般的网络几何 量，并用这些一般性质指导更多实际网络的研究，进 而通过讨论实际网络上的具体现象发展网络模型的一 般方法，最后讨论网络本身的形成机制。 统计物理学在模型研究、演化机制与结构稳定性 方面的丰富的研究经验是统计物理学在复杂网络研究 领域得到广泛应用的原因；而图论与社会网络分析提 供的网络静态几何量及其分析方法是复杂网络研究的 基础。 3
2.1 引言 静态特征指给定网络的微观量的统计分布或宏观 统计平均值。 在本章中我们将对网络的各种静态特征做一小结 。由于有向网络与加权网络有其特有的特征量，我们 将分开讨论无向、有向与加权网络。 4 返回目录
2.2 网络的基本静态几何特征 ￠2.2.1 平均距离 ￠2.2.2 集聚系数 ￠2.2.3 度分布 ￠2.2.4 实际网络的统计特征 5
2.2.1 平均距离 1.网络的直径与平均距离 网络中的两节点v i和v j之间经历边数最少的一条简 单路径（经历的边各不相同），称为测地线。 测地线的边数d ij称为两节点v i和v j之间的距离（或 叫测地线距离）。 1／d ij称为节点v i和v j之间的效率，记为εij。通常 效率用来度量节点间的信息传递速度。当v i和v j之间没 有路径连通时，d ij＝∞，而εij＝0，所以效率更适合度 量非全通网络。 网络的直径D定义为所有距离d ij中的最大值 6
社交网络数据的实用性
了解消费者。与消费者达到最简洁快速的沟通。这就需要通过数据分析找到消费者所在的圈子，进而找到圈子中的意见领袖，通过意见领袖让企业想传达的信息进一步扩大，辐射整个圈子。从而吸纳更多的忠实消费者。 社交网络分析与圈子划分 社交网络的分析存在着许多有意思的研究课题。例如，在社交网络中社区圈子的识别、社交网络中人物影响力的计算、信息在社交网络上的传播模型、虚假信息和机器人账号的识别、基于社交网络信息对股市、大选以及传染病的预测等。社交网络的分析和研究是一个交叉领域的学科，在研究过程中，通常会利用社会学、心理学甚至是医学上的基本结论和原理作为 指导，通过人工智能领域中使用的机器学习、图论等算法对社交网络中的群体行为和未来的趋势进行模拟和预测。 社交圈子的划分并不仅局限于用户主动建立起来的关系上，还可以通过其隐性圈子的划分，如兴趣属性。当两个人在社交网络中互动很频繁时，他们在线下是否也是真实的好友？从算法的角度来说，这是个很难解决的问题，但如果我们换一个角度来思考这个问题，想想我们的线下联系方式，如果A跟B互相拥有对方的手机号，那他们是线下真实好友的可能性就非常大了。包括飞信、米聊、微信等产品，如果真的能够做成基于手机通讯录的社交网络，我们就可以通过异构的社交网络对社交圈子进行综合性的判断，其价值不可估量。 企业基于社交网络数据的收获 1.潜在商机的发现 通过数据挖掘与分析，可以发现某个用户的活动商圈是否在企业的商圈覆盖范围内；可以知道某个用户的消费能力；可以知道某个用户的喜好及最近的购买习惯；可以知道某个用户会购买自己产品的概率;可以知道竞争对手的策略。 2.危机预警 通过数据挖掘与分析，可以对一些网络中突然发布的一条可能对企业产生危机的信息即时的监控起来。并追踪其传播路径，找到其中的关键节点。利用＂乱石＂打散其传播轨迹。从而让危机尽快消失。一个企业面对社交媒体中网民创造的成千上万，甚至几百万的讨论内容，想要通过人工去判断哪些口碑对品牌有利，哪些将会成为品牌危机是个不可能完成的任务。而舆情监测则可以围绕某一监测领域或事件，经过科学部署的不间断的数据收集与分析的过程，前期需要对收集范围和关键词群进行设置，中期对采集的数据进行过滤、分组、聚类等预处理，后期对数据进行分析，并以分析报告的形式让品牌了解到自身的口碑状况。 3.效果预测
小世界网络的研究现状与展望
小世界网络的研究现状与展望 !"#$%#&#’()#&#*%+",-(.*(-/’*’01/%#+*&(/2("#,3*445/%406#(7/%8 黄萍张许杰刘刚 （华东理工大学商学院管理科学与工程系上海%$$$&’） 摘要近年来，真实网络中小世界效应和无标度特性的发现激起了学术界对复杂网络的研究热潮，基于小世界网络的知识管理研究也得到了一定发展。在对小世界网络的研究背景、基础概念以及各个领域的研究进行简单综述的基础上，提出了其今后可能的发展趋势。 关键词复杂网络小世界网络流言传播无标度网络 现实世界中许许多多的复杂网络都是具有小世界或无尺度特征的复杂网络：从生物体中的大脑结构到各种新陈代谢网络，从()*+,)+*到---，从大型电力网络到全球交通网络，从科研合作网络到各种政治、经济、社会关系网络等等，数不胜数。各种网络的研究目前在世界上受到了高度的重视，形成了日益高涨的热潮，已成为一个极其重要而且富有挑战性的前沿科研方向。 !小世界网络研究背景及其基本概念 !.!复杂网络拓扑结构人们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构［%］。网络拓扑结构经过以下&个发展阶段：在最初的!$$多年里，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示。到了!"世纪/$年代末，数学家们想出了一种新的构造网络的方法，即两个节点之间连边与否不再是根据一个概率决定的［!］，这样生成的网络叫做随机网络（01)234），在接下来的5$年里它一直被认为是描述真实系统最好的网络。直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的网络。这样的一些网络被科学家们叫做复杂网络，对于复杂网络的研究标志着第三阶段的到来［5%］。 复杂网络拓扑结构的不确定性是复杂网络研究的基本问题。%$世纪中叶，6,237和0+)89突破传统图论，用随机图描绘了复杂网络拓扑。近年来研究发现，很多实际的复杂网络既不完全规则也不完全随机，而是介于完全规则和完全随机这两个极端之间，既具有类似规则网络的较大集聚系数，又具有类似于随机网络的较小平均路径长度，这就是小世界网络。人际关系网络中的“六度分离”就是小世界网络的经典例子。 大多数早期文献中都有关于六度分离的描述，!":’年，哈佛大学社会心理学家斯坦利?米尔格拉姆（;*1)<+8=9<> ?,14）作了这样的一个实验，他要求&$$多人发信把他的一封信寄到某市一个“目标”人。于是形成了发信人的链条，链上 的每个成员都力图把这封信寄给他们的朋友、家庭成员、商业同事或偶然认识的人，以便尽快到达目标人。实验结果是，一共:$个链条最终到达目标人，链条中平均步骤大约为:。人们把这个结果说成“六度分离”并广为传播［&!!!］。 应该注意到三种概念在当代对复杂网络的思考中占有重要地位。1.小世界的概念。它以简单的措辞描述了大多数网络尽管规模很大但是任意两个节点间却有一条相当短的路径的事实。@.集群即集聚度（A function [DeD,aver_DeD]=Degree_Distribution(A) %% 求网络图中各节点的度及度的分布曲线 %% 求解算法：求解每个节点的度，再按发生频率即为概率，求P(k) %A————————网络图的邻接矩阵 %DeD————————网络图各节点的度分布 %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,但要同时考虑到度为0的节点的存在性 N_DeD(i)=length(find(DeD==i-1)); % DeD=[2 2 2 2 2 2] end P_DeD=zeros(1,M+1); P_DeD(:)=N_DeD(:)./sum(N_DeD); bar([0:M],P_DeD,'r'); xlabel('节点的度 K'); ylabel('节点度为K的概率 P(K)'); title('网络图中节点度的概率分布图'); 平均路径长度 function [D,aver_D]=Aver_Path_Length(A) %% 求复杂网络中两节点的距离以及平均路径长度 %% 求解算法：首先利用Floyd算法求解出任意两节点的距离，再求距离的平均值得平均路 中图分类号：TP274 学校代码：10252 学号：092400354上海理工大学硕士学位论文 基于社会网络的数据挖掘方法研究 姓名陆晓野 系别光电信息与计算机工程学院 专业计算机应用技术 研究方向数据挖掘 指导教师陈玮副教授 学位论文完成日期2011年12月 University of Shanghai for Science and Technology Master Dissertation Data Mining Method Based on Social Networks Name Lu Xiaoye Department School of Optical-Electrical and Computer Engineering Specialty Computer Application Technology Research Direction Data Mining Supervisor Associate Professor Chen Wei Complete Date December 2011 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学位论文保留并向国家有关部门或机构送交论文的复印件和电子版。允许论文被查阅和借阅。本人授权上海理工大学可以将本学位论文的全部内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 学位论文作者签名： 指导教师签名： 年 月 日 年 月 日 保 密 年 □ 不保密 □ 声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下,独立进行研究工作所取得的成果。除文中已注明引用的内容外，本论文不包含任何其他个人或集体已经公开发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 学位论文作者签名： 年月日 关于小世界网络的文献综述 一、小世界网络概念方面的研究 Watts和Strogatz开创性的提出了小世界网络并给出了WS小世界网络模型。小世界网络的主要特征就是具有比较小的平均路径长度和比较大的聚类系数。所谓网络的平均路径长度，是指网络中两个节点之间最短路径的平均值。聚类系数被用来描述网络的局部特征，它表示网络中两个节点通过各自相邻节点连接在一起的可能性，以及衡量网络中是否存在相对稳定的子系统。规则网络具有大的特征路径长度和高聚类系数，随机网络则有短的特征路径长度和比较小的聚类系数[1]。 Guare于1967年在《今日心理学》杂志上提出了“六度分离”(Six Degrees of Separation) 理论，即“小世界现象”。该理论认为，在社交网络中存在短路径，即人们只要知道自己认识的人，就能很快地把信息传递到任何远方目标[2]。 .Stanleymilgram的邮件试验，后来的“培根试验”，以及1998年《纽约时代周刊》的关于莱温斯基的讽刺性游戏，都表现出：似乎在庞大的网络中各要素之间的间隔实际很“近”，科学家们把这种现象称为小世界效应[3]。研究发现，世界上任意两个人可以平均通过6个人联系在一起，人们称此现象为“六度分离” [2]。 二、小世界网络模型方面的研究 W-S模型定义了两个特征值：a.特征路径的平均长度L。它是指能使网络中各个结点相连的最少边长度的平均数，也就是上面说的小世界网络平均距离。b.集团化系数C。网络结点倾向于结成各种小的集团,它描述网络局部聚类特征。 稍后，Newman和WattS对上述的WS模型作了少许改动，提出了另一个相近但较好的(NW)小世界网络模型[5]，其做法是不去断开原来环形初始网络的任何一条边、而只是在随机选取的节点对之间增加一条边(这时，新连接的边很可能是长程边)。这一模烈比WS模型容易分析，因为它在形成过程中不会出现孤立的竹点簇。 其次，还有Monasson小世界网络模型[6]以及一些其它的变形模型包括BW 小世界网络模型等等[7]。 三、小世界网络应用方面的研究 ①、在生物学领域的应用 Wdt怡和StrogatZ证明疾病全球传播所需的时间和特征路径长度非常相似，只要在传播网络中加人一些捷径就可以使传播速度明显加快。运用病毒在小世界网络中的传播性质可推出信息在一个平均分离度为6的网络中传播要比在平均分离度为一百或一百万的网络中快得多[8]。 许多知名的生物网络表现出了小世界网络节点间的关连性。一般的小世界网络模型,也利用了网络的无向和无标度特性来展示网络中各节点之间的联系。这种网络模型能模拟一些神经网络的重要性质，例如，染色体结合的方向和标度。 [9][10]。 有学者研究了基于神经网络的有小世界结构的联想记忆模型。这一网络检索某一存储的模型的有效性展示了混乱的有限价值的阶段转换。更加常规化的网络很难恢复这个模型，而对混合的不对称的状态更有效。[11]。 ②、在博弈论方面的应用 小世界网络简介及MATLAB建模 1.简介 小世界网络存在于数学、物理学和社会学中，是一种数学图的模型。在这种图中大部份的结点不与彼此邻接，但大部份结点可以通过任一其它节点经少数几步就可以产生联系。若将一个小世界网络中的点代表一个人，而联机代表人与人之间是相互认识的，则这小世界网络可以反映陌生人通过彼此共同认识的人而起来产生联系关系的小世界现象。 在日常生活中，有时你会发现，某些你觉得与你隔得很“遥远”的人，其实与你“很近”。小世界网络就是对这种现象的数学描述。用数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外，小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。许多经验中的图可以用小世界网络来作为模型。因特网、公路交通网、神经网络都呈现小世界网络的特征。 小世界网络最早是由邓肯·瓦茨（Duncan Watts）和斯蒂文·斯特罗加茨（Steven Strogatz）在1998年引进的，将高聚合系数和低平均路径长度作为特征，提出了一种新的网络模型，一般就称作瓦茨-斯特罗加茨模型（WS模型），这也是最典型的小世界网络的模型。 由于WS小世界模型构造算法中的随机化过程有可能破坏网络的连通性，纽曼(Newman)和瓦茨(Watts)提出了NW小世界网络模型，该模型是通过用“随机化加边”模式来取代WS小世界网络模型构造中的“随机化重连”。 在考虑网络特征的时候，使用两个特征来衡量网络：特征路径长度和聚合系数。 特征路径长度（characteristic path length）：在网络中，任选两个节点，连同这两个节点的最少边数，定义为这两个节点的路径长度，网络中所有节点对的路径长度的平均值，定义为网络的特征路径长度。这是网络的全局特征。 聚合系数(clustering coefficient)：假设某个节点有k个边，则这k条边连接的节点之间最多可能存在的边的个数为k(k-1)/2，用实际存在的边数除以最多可能存在的边数得到的分数值，定义为这个节点的聚合系数。所有节点的聚合系数的均值定义为网络的聚合系数。聚合系数是网络的局部特征，反映了相邻两个人之间朋友圈子的重合度，即该节点的朋友之间也是朋友的程度。 我们可以发现规则网络具有很高的聚合系数，大世界（large world，意思是特征路径长度很大），其特征路径长度随着n(网络中节点的数量)线性增长，而随机网络聚合系数很小，小世界（small world，意思是特征路径长度小），其特征路径长度随着log(n)增长中说明，在从规则网络向随机网络转换的过程中，实际上特征路径长度和聚合系数都会下降，到变成随机网络的时候，减少到最少。但这并不是说大的聚合系数一定伴随着大的路径长度，而小的路径长度伴随着小的聚合系数，小世界网络就具有大的聚合系数，而特征路径长度很小。试验表明，少量的short cut的建立能够迅速减少特征路径长度，而聚合系数变化却不大，因为某一个short cut的建立，不仅影响到所连接的节点的特征路径长度，而且影响到他们邻居的路径长度，而对整个网络的聚合系数影响不大。这样，少量的short cut的建立就能使整个网络不知不觉地变成小世界网络。 实际的社会、生态、等网络都是小世界网络，在这样的系统里，信息传递速度快，并且少量改变几个连接，就可以剧烈地改变网络的性能，如对已存在的网络进行调整， 课题：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); 社交网络数据挖掘方法研究 对于现在的我们来说，网络应该是最熟悉的，它影响着我们生活得方方面面，通过网络进行社交活动也是现在网络的一个巨大的作用，各种各样的社交软件层出不穷，研究社交网络数据也变得越来越重要。巨大的数据量和复杂的数据形式导致研究社交网络数据挖掘方法存在许多困难。社交网络数据挖掘的第一步也是基础步骤就是数据分类。下文中研究的数据类型主要是数值型数据，这就大大减小了数据处理的难度，研究的内容是微博用户信息，通过常用的数据挖掘方法决策树算法，研究微博用户分类的有效的规则，得出用户分类信息。 1.1 研究背景 社交网络的发展和壮大使社交网络数据得到越来越多的关注，其价值也是毋庸置疑的，如何能利用这些信息帮助企业发展是目前研究的重点。与传统的网络形式相比，社交网络具有它独特的性质，首先，对于用户来说，他给用户更多的权限和自主性。这也就使得社交网络的数据更加的多样和复杂，内容也越来越丰满，社交网络还呈现出更加明显的群体特征，他会将具有相同特质的用户更紧密的来联系在一起。最最重要的特征是他传播信息的速度，这个速度是及时的，非常迅速，扩散范围特别的广，传统的研究方法与模型应用于社交网络数据时，推广率极低，错误率较高，传播速度低，所以创新数据挖掘方法是研究重点。在研究社交网络数据时，必须分析选择合适的挖掘方法。 目前，国内流行的社交软件有微博、微信、QQ、知乎等新兴APP，只微博就有腾讯、新浪、搜狐等几家公司，其中新浪微博是目前看来中国最具影响力的微博之一。新浪微博已经渗透到年轻人生活的点点滴滴之中，影响舆论，改变人们的思想方式，对人们产生的影响是不容小觑的。在对社交网络数据进行分析时，我们选择了新浪微博软件，因为新浪微博使用群体多，具有典型性，网站的点击量也是最大的，所以，选择微博用户信息进行研究挖掘，分析微博用户的信息数据，能得到更具有代表性和准确性的结论[1]。 小世界网络小世界网络简介及简介及MATLAB 建模 1.简介 小世界网络存在于数学、物理学和社会学中，是一种数学图的模型。在这种图中大部份的结点不与彼此邻接，但大部份结点可以通过任一其它节点经少数几步就可以产生联系。若将一个小世界网络中的点代表一个人，而联机代表人与人之间是相互认识的，则这小世界网络可以反映陌生人通过彼此共同认识的人而起来产生联系关系的小世界现象。 在日常生活中，有时你会发现，某些你觉得与你隔得很“遥远”的人，其实与你“很近”。小世界网络就是对这种现象的数学描述。用数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除了社会人际网络以外，小世界网络的例子在生物学、物理学、计算机科学等领域也有出现。许多经验中的图可以用小世界网络来作为模型。因特网、公路交通网、神经网络都呈现小世界网络的特征。 小世界网络最早是由邓肯·瓦茨（Duncan Watts ）和斯蒂文·斯特罗加茨（Steven Strogatz ）在1998年引进的，将高聚合系数和低平均路径长度作为特征，提出了一种新的网络模型，一般就称作瓦茨-斯特罗加茨模型（WS 模型），这也是最典型的小世界网络的模型。 由于WS 小世界模型构造算法中的随机化过程有可能破坏网络的连通性，纽曼(Newman)和瓦茨(Watts)提出了NW 小世界网络模型，该模型是通过用“随机化加边”模式来取代WS 小世界网络模型构造中的“随机化重连”。 在考虑网络特征的时候，使用两个特征来衡量网络： 特征路径长度和聚合系数。 特征路径长度（characteristic path length ）：在网络中，任选两个节点，连同这两个节点的最少边数，定义为这两个节点的路径长度，网络中所有节点对的路径长度的平均值，定义为网络的特征路径长度。这是网络的全局特征。 聚合系数(clustering coefficient)：假设某个节点有k 个边，则这k 条边连接的节点之间最多可能存在的边的个数为k(k-1)/2，用实际存在的边数除以最多可能存在的边数得到的分数值，定义为这个节点的聚合系数。所有节点的聚合系数的均值定义为网络的聚合系数。聚合系数是网络的局部特征，反映了相邻两个人之间朋友圈子的重合度，即该节点的朋友之间也是朋友的程度。 我们可以发现规则网络具有很高的聚合系数，大世界（large world ，意思是特征路径长度很大），其特征路径长度随着n(网络中节点的数量)线性增长，而随机网络聚合系数很小，小世界（small world ，意思是特征路径长度小），其特征路径长度随着log(n)增长中说明，在从规则网络向随机网络转换的过程中，实际上特征路径长度和聚合系数都会下降，到变成随机网络的时候，减少到最少。但这并不是说大的聚合系数一定伴随着大的路径长度，而小的路径长度伴随着小的聚合系数，小世界网络就具有大的聚合系数，而特征路径长度很小。试验表明，少量的short cut 的建立能够迅速减少特征路径长度，而聚合系数变化却不大，因为某一个short cut 的建立，不仅影响到所连接的节点的特征路径长度，而且影响到他们邻居的路径长度，而对整个网络的聚合系数影响不大。这样，少量的short cut 的建立就能使整个网络不知不觉地变成小世界网络。 实际的社会、生态、等网络都是小世界网络，在这样的系统里，信息传递速度快，并且少量改变几个连接，就可以剧烈地改变网络的性能，如对已存在的网络进行调整， 基于数据挖掘的校园社交网络用户行为分析毕业设计论文 1 绪论 1.1 选题背景 社交网络，简称SNS（social network service），在Web2.0浪潮中已发展为社会化媒体中一个主要平台。据最新的中国互联网络信息中心(CNNIC)2013年1月15 日发布的第31次《中国互联网络发展状况统计报告》，截至2012年12月底，我国网民规模达5.64亿，互联网普及率为42.1%，较2011年底提升3.8个百分点。同时报告显示，社交网络应用持续呈现增长趋势，截止2012年12月，国内社交网络用户总数已达2.75亿，占到了全部网民人数的48.8%，增速保持在10%以上。 与此同时在2010年之后社交网络又出现两大新增长点：其一微博用户持续增长，微博用户规模在2012年达到3.09亿，较2011年底增长了5873万。虽然微博急速扩张的阶段已经结束，但年增幅仍能达到23.5%；其二用户逐渐移动化成为了社交网络用户增长的又一亮点，截至2012年12月底，我国手机网民规模为4.2亿，较上年底增加约6440万人，网民中使用手机上网的人群占比由上年底的69.3%提升至74.5%，随着手机智能化，相当一部分用户访问和发送微博的行为发生在手机终端上，为社交网站的进一步发展提供了可能。此外“社交化”已经作为一种重要的功能元素，正在全面融合到各类互联网应用中。一方面，2012年涌现出大批具备社交基因的新应用，包括图片社交、私密社交、购物分享等，尤其在移动互联网领域，由于手机天生的通讯功能，2012年许多热门移动应用都具备社交功能；另一方面，搜索、网购、媒体等互联网应用正在融合社交因素，以丰富自身的功能、提升用户体验，创新服务和盈利模式。在整个互联网都走向社交化的大趋势下，传统的实名制社交网站也不断增加平台功能，在原 小世界网络及其性质 复杂网络是多主体系统的一个子集，对它的研究是计算经济学的一个重要研究领域。而贸易网络又是复杂网络在社会科学领域的一个子集，因此要讨论贸易网络，首先要关注关于复杂网络的一般性研究。在本章中，我们先介绍复杂网络研究的一个重要成果，即小世界模型，这为后面讨论贸易网络做准备。因为小世界模型只是一个纯粹的数学问题，并不包含某一学科的特殊含义，因此要首先讨论贸易网络的经济学意义，这是从一个简单的分工协调问题开始的。之后，我们进一步的追问，贸易网络是否也具有小世界这样一个普遍存在的性质。 1、多主体系统中的复杂网络 我们生活在各种各样的网络之中。在与同学、朋友、老师交往的时候，我们处于一个人际关系网络中；在我们使用各种电器的时候，我们处于一个电力网络中，很多发电厂、变电所、输电线构成了这个网络；我们去银行取钱的时候，便处于一个银行网络之中，而银行又可以与各种投资者，贷款人联系，这又是一个更大的网络。复杂网络是最近几年新兴起来的一个研究方向，如图 3.1 所示，复杂网络是多主体系统的一个子集，它里面还包括了社会关系网络（社会学）、神经网络（生物学）、计算机网络（计算机科学）、贸易网络（经济学）等等诸多的网络类别。复杂网络是多主体系统研究的一个重要分支，对社会网络、贸易网络的分析是计算经济学（ACE）的一个主要领域。 ACE 在社会科学角度对复杂网络的研究主要关注以下几个方面：（1）市场或 人际关系网络的拓扑结构究竟是什么样的。（2）这些网络结构的微观基础是什么，即如何从个体的行为出发，通过自下而上的建模涌现出这样的网络。（3）社会科学领域的网络与其它领域的网络能否找到一致的共性特征。社会科学可 复杂网络度分布的研究 (1) 1. 复杂网络的研究对象........................................................................................ 1 2. 复杂网络的研究内容........................................................................................ 1 3. 复杂网络中的三个概念.................................................................................... 1 4. 复杂网络的几何量............................................................................................ 1 5. 社会网络与其它网络的判别指标.................................................................... 2 6. 随机网络－ER 模型 ......................................................................................... 2 7. 随机网络的研究宗旨........................................................................................ 2 8. 子图出现的临界概率........................................................................................ 3 9. 子图临界概率存在的证明................................................................................ 3 10. BA 模型与度的幂指分布 ................................................................................ 4 11. BA 模型构造的网络度符合幂指形式的证明 (4) 复杂网络度分布的研究 － 复杂网络度分布的研究 河北工大硕士论文 陈德伟 指导教师：何文辰 1. 复杂网络的研究对象 用来描述真实网络统计特征的物理量主要有度分布、平均路径长度、聚集系数、相关系数等，都是力求更加详细、精确的描述复杂的真实网络。寻找网络各种宏观统计性质的微观生成机制一直都是网络研究中一项极具意义而且也是极具挑战性的工作。现在人们已经对复杂网络的小世界性质和无标度特征的微观生成机制有了一定的认识，但是度的相关性、团体性质、分层结构等更为复杂的宏观统计性质的微观生成机制的探索还处于起步阶段。对不同结构复杂网络的鲁棒性和脆弱性(vulnerability)的研究也是一个具有广泛应用价值的课题。 2. 复杂网络的研究内容 目前，复杂网络研究的内容主要包括：网络的几何性质，网络的形成机制，网络演化的统计规律，网络上的模型性质，以及网络的结构稳定性，网络的演化动力学机制等问题。 3. 复杂网络中的三个概念 三种概念在当代对复杂网络的思考中占有重要地位。第一，小世界概念；第二，集群即集聚系数的概念；第三，幂律的度分布概念。 4. 复杂网络的几何量 直径：网络的直径是指任意两个顶点之间最短路径的最长长度(包含的边数)。 集聚系数：对于网络中的任意一个节点i 来说，其集聚系数i C 表示与i 相连的节点中任意两点之间相互连接的概率。它可定义如下：如果与节点i 相连的点的数目为i k ，则在这i k 个节点之间最多存在2/)1(-k k 条边，而实际存在的可能只有i E 条边，则得到i 的集聚系数i C 为 ) 1(2-= i i i i k k E C .复杂网络模型的matlab实现
社交网络数据挖掘
小世界网络综述
小世界网络简介及MATLAB建模
课题：WS小世界网络模型构造
社交网络数据挖掘方法研究
看看挺有用的(小世界网络简介及MATLAB建模)
基于数据挖掘的校园社交网络用户行为分析毕业设计论文
小世界网络及其性质
复杂网络度分布的研究