精华内容
下载资源
问答
  • WS小世界网络 平均最短路径 聚类系数

    WS小世界网络算是复杂网络的基本入门实验了,虽然基础,但是极其重要,里面包含了复杂网络这门学科的很多重要想法。首先,简单介绍一下WS小世界网络,就是具有很小的平均最短路径和很高的聚类系数的一种网络,通俗一点,就是模仿日常生活中人们之间的联系的一种网络,再通俗一点,大马路上任选两个不认识的人,你会发现,他俩只要通过四五个人介绍一下,就认识了,这四五个人,就是他俩的距离,叫做最短路径。另一个例子,Tom和Jack是好朋友,有一天他们聊天,突然发现,Mary是Tom的高中同学,是Jack的大学同学,缘分呐,这种缘分一量化,就叫聚类系数。

    一般做这个实验,用1000个点模仿一千个人,从规则图(专业术语叫最近邻耦合网络)开始,经过随机化重连(有规定的重连规则)后,开始做分析(此时,有连线,代表认识,无连线,代表不认识)。

    首先,你需要安装matlab(捂脸,看这篇文章的肯定知道的),然后,开始根据规则和公式敲代码了,代码全文如下

    %小世界网络

    function ws_worldnet(N,K);

    tic;

    %N=400;%随机节点数

    %K=2;%左(右)最邻近节点数


    %生成节点

    %angle=0:2*pi/N:2*pi-2*pi/N;

    %x=100*sin(angle);

    %y=100*cos(angle);


    %计算L0

    B=zeros(N);%全0的n维矩阵

    for i=1:N

        for j=i+1:i+K

            jj=j;

            if j>N

                jj=mod(j,N);

            end

            B(i,jj)=1;

            B(jj,i)=1;

        end

    end

    %计算L0 不需要断边重连 直接开始算节点间的最短路径

    D=B;

    for i=1:N

        for j=1:N

            if D(i,j)==0

                if i==j

                    D(i,j)=0;

                else

                    D(i,j)=inf;

                end

            end

        end

    end

    E=B;%矩阵E是做过变换的邻接矩阵,只用来计算聚类系数C0

    for n=1:N

        for i=1:N

            for j=1:N

                if D(i,n)+D(n,j)<D(i,j)

                    D(i,j)=D(i,n)+D(n,j);

                end

            end

        end

    end

    L0=sum(sum(D))/(N*(N-1));

    %disp(D);



    %计算聚类系数C0

    Ci0=zeros(N,1);

    for i=1:N

        aa=find(E(i,:)==1);%按行找矩阵的邻接节点

        if isempty(aa)

            Ci0(i)=0;%如果没有 那么节点i的邻居节点数为0

        else

            m1=length(aa);

            if m1==1

                Ci0(i)=0;%规定邻居节点数只有1个的话,该点的聚类系数为0(为1也是可以的)

            else

                B1=E(aa,aa);%特别注释1

                Ci0(i)=length(find(B1==1))/(m1*(m1-1));

            end

        end

    end

    C0=sum(Ci0)/N;

    %disp(C0);



    %生成邻接矩阵,模拟节点之间的连线

    for x=1:14

        P(x)=1/(2^(x-1));

        for y=1:20

    A=zeros(N);%全0的n维矩阵

    for i=1:N

        for j=i+1:i+K

            jj=j;

            if j>N

                jj=mod(j,N);

            end

            A(i,jj)=1;

            A(jj,i)=1;

        end

    end


    %根据概率断边后重新连接(随机化重连)


    for i=1:N

        for j=i+1:N

            if A(i,j)==1

                p1(y)=rand(1,1);

                if p1(y)<P(x)

                    A(i,j)=0;A(j,i)=0;

                    rand_point=unidrnd(N);

                    while rand_point==i

                        rand_point=unidrnd(N);

                    end

                    A(i,rand_point)=1;

                    A(rand_point,i)=1;

                end

            end

        end

    end



    %根据重连后的邻接矩阵,计算Ci

    Ci0=zeros(N,1);

    E=A;

    for i=1:N

        aa=find(E(i,:)==1);%按行找矩阵的邻接节点

        if isempty(aa)

            Ci0(i)=0;%如果没有 那么节点i的邻居节点数为0

        else

            m1=length(aa);

            if m1==1

                Ci0(i)=0;%规定邻居节点数只有1个的话,该点的聚类系数为0(为1也是可以的)

            else

                B1=E(aa,aa);

                Ci0(i)=length(find(B1==1))/(m1*(m1-1));

            end

        end

    end

    Ci(y)=sum(Ci0)/N;%计算20次


    %计算平均路径长度

    %根据floyd算法求平均最短路径

    %首先,将邻接矩阵变成做变换,点与点之间有线连接,距离记为1,没有线连接,距离记为inf,点自己到自己的距离记为0

    D=A;

    for i=1:N

        for j=1:N

            if D(i,j)==0

                if i==j

                    D(i,j)=0;

                else

                    D(i,j)=inf;

                end

            end

        end

    end

    % D(find(D==0))=inf;

    % for i=1:N

    %     D(i,i)=0;

    % end

    %disp(D);

    for n=1:N%特别注释2

        for i=1:N

            for j=1:N

                if D(i,n)~=inf&&D(n,j)~=inf&&(D(i,n)+D(n,j)<D(i,j))

                    D(i,j)=D(i,n)+D(n,j);

                end

            end

        end

    end

    %disp(D);

    M(y)=sum(sum(D))/(N*(N-1));

        end

    L(x)=sum(M)/20;

    C(x)=sum(Ci)/20;

    %disp(C);

    %disp(M);

    end

    %disp(L0);

    figure;

    semilogx(P,L/L0,'rd','markersize',4);%画图函数

    hold on;

    semilogx(P,C/C0,'go','markersize',4);

    hold on;

    toc;

    重要的该注释的已经注释的很清楚了,特地说三处地方,当时花了很长时间才搞明白,第一,取点是很有技巧的,不然得到的图像就很难看,一般都如我上文所示取点,每个概率做20次后算平均值;第二,上文特别注释1处,就是去掉该点所在行所在列,得到的邻接矩阵,也就是得到了与改点连接的点之间的连线的矩阵;第三,上文特别注释2处,弗洛伊德算法求最短路径,外层循环必须是中间节点的遍历,放到内层,会出错,原因的话,自己拿草稿纸画画就知道了

    最后,结果大概像这个样子(PS:实验室工作站花了一个小时跑出来的。。。。。。)

    展开全文
  • 小世界网络

    千次阅读 2015-11-24 14:29:35
    20世纪末,很多科学家发现研究过的自然、社会和技术网络中,大都具有这些特征:...其中有两类模型被深入地进行了研究,分别是小世界网络和无尺度网络,这里结合原始论文谈谈对小世界网络的认识。  1998年,邓肯·瓦

    20世纪末,很多科学家发现研究过的自然、社会和技术网络中,大都具有这些特征:高度的集群性、不均衡的度分布以及中心节点结构。这些特征的出现不是偶然的,为什么现实世界中的网络会具有这些特征呢?这是网络科学的主要问题,目前基本上已经通过建立网络的发展模型解决了。其中有两类模型被深入地进行了研究,分别是小世界网络和无尺度网络,这里结合原始论文谈谈对小世界网络的认识。

          1998年,邓肯·瓦特和斯托加茨在《自然》杂志上发表了关于小世界网络模型的论文Collectivedynamics of‘small-world’ networks,首次提出并从数学上定义了小世界概念,并预言它会在社会、自然、科学技术等领域具有重要的研究价值。

           所谓小世界网络,就是相对于同等规模节点的随机网络,具有较短的平均路径长度和较大的聚类系数特征的网络模型。以前,人们认为网络分为完全规则网和完全随机网,这两类网络具有各自的特征。规则网具有较大的特征路径长度,聚类系数也较大,而随机网络具有较小的特征路径长度,但是聚类系数较小。难道特征路径长度较大(小)一定伴随着较大(小)的聚类系数?另外,很多现实中的网络如电网,交通网络,脑神经网络,社交网络,食物链等都表现出小世界特性,即具有较小的特征路径长度。

    Watt采用一种随机重连边的方法,以探求位于规则网和随机网的中间地带。如图:

      

            规则网有N个节点,每个节点与K个最近邻节点相连(K是偶数)。上图的规则网有20个节点,每个节点与相邻的4个节点互联。然后,对每条边进行以概率P进行随机重连(0<=P<=1)。P=0时对应规则网,P=1时对应完全随机网,通过调整P的值可以得到位于两种网络中间的网络模型,然后探究其特征。

     通过实验并统计网络呈现出的特征,得到下图(归一化处理后)。


              可见,在P较小时(P<0.01),特征路径长度急剧下降,而聚类系数几乎没有变化。这样,我们发现这些网络具有较短的特征路径长度和较大的聚类系数,我们称其为“小世界网络”。为了验证试验结果的稳定性,作者采用了多种不同的规则网络和随机重连算法进行试验,得到了相同的结果.

           那么为什么会出现这种特征呢?关键是“捷径”的添加。所谓“捷径”,即随机重连过程中添加的长边。如试验中P<0.01时,规则网络中会添加极少量的长边,不仅使长边两端的节点(假定A和B)路径长度变小,而且A节点的和B节点的邻居乃至B的邻居的邻居之间距离都变小了。于此同时,随机重连对网络的聚类系数影响很小,至多是线性减少。于是,P较小时生成的网络具有小世界特征。当P较大时,随着长边的增多,网络的聚类系数开始迅速变小,向完全随机化网络演变。

         在论文中,通过对三个现实中的案例:美国西部的电力网络、电影演员的协作网络、蠕虫的神经网络分析,发现三者都具有小世界特征,如下图。

     

            人们发现在具有小世界特征的动力系统中,信息的传播能力、计算能力等都得到了增强。瓦茨认为;局部行为导致了全局性的结果,而局部动态特性和全局动态特性之间的关系,则主要依赖于网络的结构。在这篇论文中,作者利用人群中传染病的传播、博弈论中合作的演化、元胞自动机的计算能力、耦合相位振子的同步等具有小世界特征的动力系统进行了研究,并对小世界的前途进行了展望

        为什么很多现实网络具有“小世界特征”?

    结合现有假说和自己的理解,可能是以下原因;

    1、由于现实的需要,如交流、效率、成本等原因,真实网络中存在着“捷径”。

    2、“捷径”的数量与需求相匹配。

    3、“捷径”的生成和维护往往需较高的“代价”

     

    附:文中图1的演变规则

    任取一节点为起始点,设为A,对其顺时针方向的且与最近邻节点相连的边以概率P随机重连。重复对每个节点执行,直至到最后节点。要求任意2节点最多存在1条边且不能存在到自身的边,如果以P重新选择出现上述情况,则该边不重连。

    然后,顺时针对与起始点A长度为2的边以概率P随机重连。对其余节点执行…

    然后,顺时针对与起始点A长度为3的边以概率P随机重连。对其余节点执行…

    直到所有的原始边别处理一次(规则图中共有NK/2条边,所以rewiring过程在K/2步后停止s)

    特征路径长度L

    又称为平均路径长度,全局特征量。

    网络中任意两点的最短连通路径的边数成为2点的特征路径长度。网络中所有对节点的特征路径长度和的平均值成为网络的特征路径长度。

    聚类系数C

    局部特征量。

    某节点的边数和该节点可构造的最多边数的比值。

    展开全文
  • 小世界网络的定义和性质可以参考wiki百科:小世界网络如果一个网络满足: - 其平均聚集系数远大于在同一个顶点集合中构造的随机图的平均聚集系数; - 并且,其平均最短路径长度和这个随机图基本相同 那么这个...

    版權聲明

    简介

    这是社会网络管理与分析的作业。老师要求每组各举一个小世界网络的例子。因为以前刚好下载过武汉公交路线的数据,因此我们组讲的是这个示例。

    小世界网络的定义和性质可以参考wiki百科:小世界网络

    如果一个网络满足:
    - 其平均聚集系数远大于在同一个顶点集合中构造的随机图的平均聚集系数;
    - 并且,其平均最短路径长度和这个随机图基本相同
    那么这个网络便可以称为小世界网络。

    公交信息通过百度地图API获取,包括公交路线的坐标的经纬度坐标(可以生成GIS中的线要素),每个公交站点的经纬度坐标和名称。武汉公交站点的名称基本上都是以该站点所在街道开头命名,很有规律,例如建设大道双墩,解放大道中山公园等,这为数据处理和网络分析提供了很大方便。

    将真实的地理路网映射到抽象的网络有好几种方法,每种方法都有一定的优缺点。这里用到的方法类似于路名对偶法,将一条道路作为网络中的结点,道路与道路的交叉路口作为相连的边。如下图所示。
    路名对偶法道路映射

    但是手头上的数据只是公交路网的数据,毕竟和真实的道路交通网络还有差别,而且身边缺少一些工具,因此采用了简化的路名对偶法来映射公交道路网络。当然这样的映射会造成一些问题。

    公交路网映射方法

    基本上,武汉公交站点名称的前缀都是该站点所在道路名称,且该名称都是以道、路、街结尾,因此用这三个字将每条公交路线的站点名称截断,得到该公交路线经过的街道名称,然后再删除重复的道路名称。

    映射时基于如下假设:在同一条公交线路中,相邻的两条道路必是相连的。因此遍历所有公交线路的所有站点,按顺序将公交线路中的站点两两相连。这样就将公交路网映射到了网络图中。

    但是这样简化的映射方法会产生一些问题:

    1. 无法完全反应真实的道路信息
    2. 会产生一个非连通图(因为道路交通网应该是一个连通图)

    在这个作业中通过取网络图中结点最多的连通子图来解决。

    数据处理

    python的网络分析库Networkx功能强大好用。因为python对中文支持不太好,所以用anjuke库将结点名称全部转为拼音。Networkx可以从这里下载:Networkx

    Networkx的基本操作如下:

    import networkx as nx
    import matplotlib.pyplot as plt
    
    G = nx.Graph() # 定义一个图
    vertex1 = 1 # 结点可以是字符串,也可以是数字
    vertex2 = 2
    G.add_node(vertex1) # 添加一个结点
    G.add_node(vertex2)
    G.add_edge(vertex1, vertex2) # 以vertex1和vertex2为顶点添加一条边
    
    # 绘制网络,使用spring布局,结点大小设置为10,透明度设置为0.6
    nx.draw_networkx_nodes(G,pos=nx.spring_layout(G), nodesize = 10, alpha = 0.6)
    plt.show() # 使用matplot将图绘制出来

    全部的处理代码如下:

    # _*_ coding: utf-8 _*_
    import networkx as nx
    import codecs
    from anjuke import pinyin #汉字转拼音
    import matplotlib.pyplot as plt
    
    originalPath = "StationName_distinct_utf.txt" # 去除重复项的中文顶点文件
    pinyinPath = "StationName_distinct_pinyin.txt" # 去除重复项的拼音顶点文件
    NameNoPath = "StationNameNo_distinct.txt" # 公交路线和站点名称文件,中文
    
    
    # 汉字转拼音
    def ConvertPinyin(originalPath, pinyinPath):
        fileOriginal = codecs.open(originalPath, "r", "utf-8")
        fileNodes_pinyin = open(pinyinPath, "w")
    
        fileOriginal.seek(0,0)
        line = fileOriginal.readline()
        converter = pinyin.Converter()
        while line: 
            name = converter.convert(line)
            fileNodes_pinyin.write(name)
            print name
            line = fileOriginal.readline()
    
        fileOriginal.close()
        fileNodes_pinyin.close()
    
    # 存储格式:每一行都是一个站点名
    def CreateNodes(originalPath):
        fileOriginal = codecs.open(originalPath, "r", "utf-8")
        fileOriginal.seek(0,0)
        vertex = fileOriginal.readline()
        vertex = vertex.strip()
        while vertex:
            G.add_node(vertex)
            vertex = fileOriginal.readline()
        fileOriginal.close()
    
    # 根据公车的行使特征,每两个相邻的站点的道路应该是相连的,当然也有不相连的,这里简化了
    # 存储格式:第一列为公交编号,第二列为站名(去除重复项),tab符分隔
    def CreateEdges(originalPath):
        fileOriginal = codecs.open(originalPath, "r", "utf-8")
        fileOriginal.seek(0,0)
        line = fileOriginal.readline()
        if line.strip() == "":
            return
    
        converter = pinyin.Converter() # 转拼音
        preBusNo = line.split("\t")[0]
        preStopName = line.split("\t")[1]
        preStopName = converter.convert(preStopName)
        while line:
            content = line.split("\t")
            curBusNo = content[0]
            curStopName = converter.convert(content[1]) # 转拼音
            if preBusNo == curBusNo: # 同一条路线
                if preStopName != curStopName: # 若相邻的两条路不同,则他们相连,有交点,构成一条边
                    G.add_edge(preStopName, curStopName)
                    #print preStopName + "----" + curStopName
                    preStopName = curStopName
            else: # 若不是同一条路线
                preBusNo = curBusNo
                preStopName = curStopName
            line = fileOriginal.readline()
    
        fileOriginal.close()
    
    #创建一个图
    G = nx.Graph()
    #ConvertPinyin(originalPath, pinyinPath)
    CreateNodes(originalPath)
    CreateEdges(NameNoPath)
    
    print nx.number_of_nodes(G) #输出图的顶点数
    print nx.number_of_edges(G) #输出图的边数
    print nx.number_connected_components(G) #输出图的连通子图数量
    
    lst = list(nx.connected_component_subgraphs(G)) #提取图中所有连通子图,返回一个列表,默认按照结点数量由大到小排序
    H = lst[0] #取顶点数最多连通子图来分析
    print nx.number_of_nodes(H)
    print nx.number_of_edges(H)
    print nx.average_shortest_path_length(H) #计算平均最短路径长度
    print nx.average_clustering(H) #计算平均聚集系数
    nx.draw_networkx_nodes(H,pos=nx.spring_layout(H), nodesize = 10, alpha = 0.6) #使用spring绘制图
    plt.show()
    #plt.savefig("path.png")

    结果与分析

    最后得到的网络共有476个结点,941条边。即,一共有476条路,941个交叉路口。原始的非连通图有900多个结点。如下图所示。
    这里写图片描述

    然后通过Networkx计算了该网络的平均最短路径长度和平均聚集系数。
    平均最短路径长度:5.454
    平局聚集系数:0.195

    平均最短路径长度表示任意选择两条路,坐公交车的话平均要经过大概5个路口就可以到达。小世界网络中,平均最短路径长度要远远小于结点数。而平均聚集系数要远远大于同一个顶点集合的随机图的平均聚集系数。下面用WS网络模型来验证。

    WS模型是用来解释小世界网络的一个模型,1998年由瓦茨和斯特罗加茨提出。WS模型基于一个假设:小世界模型是介于规则网络和随机网络之间的一个网络。因此模型从一个完全规则的网络出发,以一定的概率将网络中的连接打乱重连。作业中使用Networkx生成了WS网络模型。概率p分别设为0.1(接近规则网络),0.4和0.9(接近随机网络)。每个结点的平均邻居设为5。python代码如下:

    import networkx as nx
    import matplotlib.pyplot as plt
    
    # 生成一个WS网络,结点数476,平均邻居数为5,概率p为0.9
    WS = nx.random_graphs.watts_strogatz_graph(476, 5, 0.9)
    print nx.average_shortest_path_length(WS) #计算平均最短路径长度
    print nx.average_clustering(WS) #计算平均聚集系数
    nx.draw_networkx(WS,pos=nx.spring_layout(WS),nodesize = 10, width = 0.8, with_labels = False, node_color = 'b', alpha = 0.6)
    plt.show()

    结果图如下。
    *p*=0.1时的WS网络
    p=0.1时的WS网络

    *p*=0.4时的WS网络
    p=0.4时的WS网络

    *p*=0.9时的WS网络
    p=0.9时的WS网络

    三种概率的WS网络和武汉公交网络的平均最短路径长度和平均聚集系数如下:

    项目 公交路网 WS(p=0.1) WS(p=0.4) WS(p=0.9)
    平均最短路径长度 5.454 7.66 5.080 4.745
    平均聚集系数 0.195 0.378 0.105 0.006

    可以看到当p=0.4时的WS网络和武汉公交路网的指标接近。而当p=0.4的网络的平均最短路径长度与p=0.9(随机网络)的WS网络相当,但平均聚集系数要大于p=0.9的WS网络。符合前面提到的小世界网络特征。而武汉公交路网的指标也与p=0.4的WS网络相当,因此公交路网也符合小世界网络的特征。

    展开全文
  • 文章目录小世界网络复杂网络的特性平均路径长度L聚集系数C分布小世界效应规则网络随机网络小世界网络无标度网络python 代码生成小世界网络规则网络 小世界网络 [百度百科]:小世界网络模型是一类具有较短的...


    喜欢的话请关注我们的微信公众号~《你好世界炼丹师》。

    • 公众号主要讲统计学,数据科学,机器学习,深度学习,以及一些参加Kaggle竞赛的经验。
    • 公众号内容建议作为课后的一些相关知识的补充,饭后甜点。
    • 此外,为了不过多打扰,公众号每周推送一次,每次4~6篇精选文章。

    微信搜索公众号:你好世界炼丹师。期待您的关注。


    小世界网络

    [百度百科]:小世界网络模型是一类具有较短的平均路径长度又具有较高的聚类系数的网络的总称。

    小世界网络(small-world network)是指网络中大部分节点都不彼此相邻、但大部分节点都彼此联通的网络。简单来说,就是大部分节点都不直接与许多节点连接,但到网络中其他大部分节点都有通路存在。这种现象通常在社交网络里很常见:大部分人一生的熟人圈子(社交网络相邻节点)也只有几百人这个数量级,但通常任意在社交网络中找两个人,他们之间的是存在社交通路(朋友链)的。六度理论也告诉我们在实际的社交网络中,节点之间的距离(最短路径长度)通常不会太大,也就是说街上随便找一个人,你通常总有朋友的朋友的朋友的朋友的朋友认识他。

    小世界神经网络可能是指在大脑等生物神经网络中常见的现象,即大部分神经细胞都只和临近的少量神经细胞直接接触(少量是相对于整个网络的大小),而整个神经网络是靠这种小的邻接结构联通的。神经网络里出现小世界特性的一个假说是“生物经济性(biologically economic)”,即为了让整个网络联通并有较小的网络半径(网络上最长的最短路径长度,可以认为是网络里最长的通信延迟),每个神经元只通过树突或者轴突和(相对)邻近的若干神经元联系是一种比较经济可行、节约“神经元材料”的网络结构。许多计算神经学中的稀疏权值(或局部权值)模型即来源于这种假设。

    复杂网络的特性

    目前科学家还没有给出复杂网络的严格定义。从过去十几年的研究来看,复杂网络至少包含以下几层意思:

    • 首先,它是大量真是复杂系统的拓扑抽象;
    • 其次,在感觉上比规则网络和随机网络复杂

    平均路径长度L

    在网络中,两点之间的距离为连接两点的最短路径上所包含的边的数目。网络的平均路径长度指网络中所有节点对的平均距离,她便命网络中节点的分离成都,反应了网络的全局特性。

    聚集系数C

    在网络中,节点的聚集系数是指与该节点相邻的所有节点之间连边的数目占这些相邻节点之间最大可能连边数目的比例。而网络的聚集系数则是指网络中所有节点聚集系数的平均值,它表明网络中节点的聚集情况即网络的聚集性,也就是说同一个节点的两个相邻节点仍然是相邻节点的概率有多大,它反映了网络的局部特性。

    度及度分布

    在网络中,点的度是指与该点相连的节点数目,即连接该点的变得数目。而网络的度指网络中所有节点度的平均值。度分布P(k)指网络中一个任意选择的节点,它的度恰好为k的概率。

    小世界效应

    复杂网络的小世界效应是指尽管网络的规模很大(网络节点数目N很大),但是两个节点之间的距离比我们想象的要小得多。也就是网络的平均路径长度L随网络的规模呈对数增长,即L~In N。大量的实证研究表明,真实网络几乎都具有小世界效应。

    规则网络

    最简单的网络就是规则网络,它是指系统中个元素之间的关系可以用一些规则的结构表示,也就是说,网络中任意两个节点之间的联系遵顼既定的规则,通常每个节点的近邻数目都相同。

    • 全局耦合网络(完全图)
    • 最近邻耦合网络
    • 星型耦合网络

    随机网络

    从某种意义上讲,随机网络和规则网络是两个极端,而复杂网络处于两者之间。节点不是按照确定的规则连线,如纯粹的随即方式连线,所得的网络为随即网络。如果节点按照某种自组织原则方式 连线,将演化成各种不同的网络。

    小世界网络

    规则的最近邻耦合网络具有高聚类特性,但并不是小世界网络。另一方面,ER随机网络虽然具有小的平均路径长度但却没有高聚类特性。因此,这两类网络模型都不能再现真实网络的一些重要特征,毕竟大部分实际网络既不是完全规则的,也不是完全随机的。作为从完全规则网络向完全随机网络的过渡,Watts和Strogtz于1998年引入了一个小世界网络模型,称为WS小世界模型。

    无标度网络

    很多网络(包括Internet和新陈代谢网络等)都不同程度拥有如下共同特性:大部分节点只有少数几个链接,而某些节点却拥有与其他节点的大量链接,表现在度分布上就是具有幂律形式,即P(k)~k—γ。这些具有大量链接的节点称为“集散节点”,所拥有的链接数可能高达几百、几千甚至几百万。包含这种集散节点的网络,由于网络节点的度没有明显的特征长度,故称为无标度网络。

    python 代码

    生成小世界网络

    import networkx as ne #导入建网络模型包,命名ne
    import matplotlib.pyplot as plt #导入科学绘图包,命名mp
    #WS network graphy
    print('请输入网络节点总数NETWORK_SIZE:')
    NETWORK_SIZE=int(input())
    print('请输入规则网络要连的邻接个数k:')
    k=int(input())
    print('请输入重连概率p:')
    p=float(input())
    ws=ne.watts_strogatz_graph(NETWORK_SIZE,k,p)
    ps=ne.circular_layout(ws)#布置框架
    ne.draw(ws,ps,with_labels=False,node_size=30)
    plt.show()
    

    在这里插入图片描述

    规则网络

    如果把重练概率改为0,则为规则网络
    代码同上
    在这里插入图片描述

    展开全文
  • 著名的小世界实验发现了社会群体中人和人之间六度分离的关系(任意两个人之间的平均路径经过了约6个中间人)。如何解释一个人所认识的人并不多,但是却总是有六度分离的现象,就有人提出了小世界的模型。   即...
  • 浅谈小世界网络

    万次阅读 2012-12-01 17:36:44
    20世纪末,很多科学家发现研究过的自然、社会和技术网络中,大都具有这些特征...其中有两类模型被深入地进行了研究,分别是小世界网络和无尺度网络,这里结合原始论文谈谈对小世界网络的认识。  1998年,邓肯·瓦特和
  • 网络理论中,无尺度网络(或称无标度网络)是带有一类特性的复杂网络,其典型特征是在网络中的大部分节点只和很少节点连接(节点的’‘很),而有极少的节点与非常多的节点连接(节点的’‘非常高)。...
  • 小世界网络的集体动力学

    千次阅读 2013-09-04 11:03:24
    小世界网络的集体动力学 watts and strogatz  网络耦合动态系统已经被应用在了对生物振荡器的建模上,约瑟夫逊结,激动的媒体,神经网络,空间游戏,基因空网络和许多其他的自组织系统。一般来说,连接拓扑被假定...
  • 小世界网络是具有高聚类系数,相对较短的平均路径长度和可以扩展的熵的系数网络。小世界效应:随着少数随机链路添加到有结构的网络上,平均路径长度会快速减少。典型的,主要是由于当规则网络的少数链路随机化时发生...
  • 复杂性思维第二版 三、小世界

    万次阅读 2017-11-03 01:39:53
    三、小世界图现实世界中的许多网络,包括社交网络在内,具有“小世界属性”,即节点之间的平均距离,以最短路径上的边数来衡量,远远小于预期。在本章中,我介绍了斯坦利·米拉格(Stanley Milgram)的著名的“...
  • 小世界模型简介

    千次阅读 2019-03-14 19:40:14
    小世界模型 “小世界现象”源于社会心理学家Stanley Milgram在20世纪60年代所做的试验。Milgram设计了一个实验,他在美国内布拉斯加州奥马哈市或者堪萨斯州戚奇托市,随机选取了一些用户,给在波士顿的日标用户送信...
  • 包括BA网络构建,邻接矩阵存储,分布计算与存储等,此部分用C++实现,将邻接矩阵和分布分别存储在文件freeScale.txt和文件freeScale_degree.txt最后用python进行可视化操作。 BA网络构建过程参照这篇博客BA无...
  • 本文出自Google的Federated Learning of Deep Networks using Model Averaging,主要介绍使用模型平均方法的联邦式学习。 文章目录引言一、 简介二、 联邦式学习三、 联邦式优化四、 联邦平均算法五、 实验结果六、...
  • 今天我们使用经典的BP神经网络进行回归训练,目的是为了预测出上海市多个维度因素影响下的地表气温预测 先上图: BP神经网络是什么 BP(Back-propagation,反向传播)神经网络是最传统的神经网络。也就是使用了...
  • 复杂网络

    千次阅读 2018-10-28 16:31:28
    文章目录复杂网络复杂网络基本概念平均路径长度聚类系数分布网络拓扑基本模型及其性质规则网络全局耦合网络最近邻耦合网络星型耦合网络随机图(ER随机图)小世界网络模型WS小世界模型NW小世界模型小世界网络的...
  • 复杂网络研究及其前沿概述

    千次阅读 2019-02-22 21:25:26
    复杂网络研究及其前沿概述1 引言2 复杂网络研究史2.1 七桥问题2.2 随机图理论2.3 小世界网络、无标度网络3 复杂网络的研究特点3.1 网络规模大3.2 网络结构具有复杂性和多元性3.3 网络具有时空复杂性3.4 复杂网络存在...
  • 网络世界强权崛起,全球竞相取经

    千次阅读 2007-05-23 06:18:00
    二○○七年四月二十一日韩国首尔最热闹的大学街上,Cyworld举行一年一度盛会CyDay,虚拟世界中的可爱造型人物,走在... 这场庆典不但打破虚拟与现实的界线,也象征着这个世界上宽带网络最发达国家所主宰的虚拟世界
  • 转自: http://www.flickr.com/photos/caseorganic/4510691991/in/set-72157624621620243 图 大图Network Models - Random network, Scale-free network, Hierarchical network随机网络The Erdös–Rényi (ER)...
  • 复杂网络的统计特征

    千次阅读 2018-12-05 16:08:07
    小世界效应:大的簇系数和小的平均距离。  无标度特性:节点服从幂律分布—具有某个特定的节点数目与这个特定之间的关系可用一个幂函数近似表示。  统计特征: (1) 簇系数:用来衡量网络节点聚类的情...
  • 超星慕课透过性别看世界章节作业答案 1.1 1 【单选题】 性别其实是一种(C)。 A、 个人选择 B、 先天特征 C、 再现 D、 个性 2 【单选题】刻板的两性气质中,要求男性(B)。 A、依赖性 B、控制性 C、连续性 D...
  • 依据这些特征将复杂网络分为随机网络、小世界网络、无标度网络、超小世界网络、社区网络、分形网络等。 1.2.1 随机网络 1959年Erdos和Renyi提出了可以通过网络节点间以不变的概率p随机的布置连线来有效模拟通 信和...
  • 生成式对抗网络—简称GANs—将成为深度学习的下一个热点,它将改变我们认知世界的方式。准确来讲,对抗式训练为指导人工智能完成复杂任务提供了一个全新的思路,某种意义上他们(人工智能)将学习如何成为一个专家。...
  • 随机网络和无标度网络

    千次阅读 2015-11-24 14:38:33
    传统的随机网络(如ER模型),尽管连接是随机设置的,但大部分节点的连接数目会大致相同,即节点的分布方式遵循钟形的泊松分布,有一个特征性的“平均数”...现实世界网络大部分都不是随机网络,少数的节点往往拥有大
  • Linux下网络监控工具总结

    万次阅读 2016-10-17 23:23:15
    GitHub Linux下网络监控工具总结 AderXCoding/system/tools/network_monitor本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可, 转载请注明出处 对任何规模的业务来说, 网络监控工具都...
  • 【计算机网络】谢希仁教材轻松解读 概述篇

    千次阅读 多人点赞 2019-02-26 22:40:10
    谢希仁老师的《计算机网络》是一本很不错的书,讲的很详细,在术语方面用词,也非常的准确,但是因为书籍页数比较多,内容比较浓缩,很多人都读不进去,其实分析好每一章节的脉络,以及把握住关键词和关键内容,这...
  • 2. 图卷积网络的两种类型2.1 vertex domain(spatial domain):顶点域(空间域)2.2 spectral domain:频域方法(谱方法)3. 什么是拉普拉斯矩阵?3.1 常用的几种拉普拉斯矩阵普通形式的拉普拉斯矩阵对称归一化的...
  • Gretna网络分析之先验知识

    千次阅读 热门讨论 2019-05-06 09:08:32
    1.1 小世界网络 1.2 平均路径长度 2.功能键介绍 2.1 Global Networkmetrics 2.2Nodal and modular network metrics 3.彩蛋 (转载请注明来自Ressan博客) 1. 简介 网络:由节点和连线构成的图/模型,用来...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,275
精华内容 14,110
热门标签
关键字:

小世界网络的平均度