精华内容
下载资源
问答
  • 复杂网络建模的实现(哈工大深圳复杂网络建模课程Project)
    千次阅读 多人点赞
    2017-10-28 14:34:20

    任务:
    1,三张不同的网络:已知某人的名称。已知某人的家乡。已知某人的方言。
    分析这三者各自的网络性能(节点度数分布、平均最短路径长度、集聚系数)以及动态行为(在刻意攻击(intentional attack)和随机攻击(random attack)下的鲁棒性)

    2,计算三个网络的核数(coreness)

    3,画出必要的图片的来显示模拟的结果,以支持观察的结果。

    4,(附加内容)设计一个小系统(包括友好的界面以及图形化的展示)来显示整体网络的布局。

    节点度数分布
    节点i的度数:与该节点所连的边的总数
    平均度数:所以节点的度数的平均值
    可以直接求

    平均最短路径长度:任意两个节点之间的距离的平均值
    两节点之间的距离:节点i与节点j之间的边的条数,注意,是最短的边的条数,也就是说两节点之间的距离就是最短的距离(边的条数)
    这个需要对图进行分开处理找到的子图

    聚集系数:
    假设节点i有k(i)条边,也就是说它有k(i)个邻居
    定义E(i):这k(i)个邻居实际有的边的条数
    T(i):这k(i)个邻居可以有的边的条数(k(i)*[K(i)-1]/2)
    因此节点i的聚集系数C(i)=E(i)/T(i)

    随机攻击:
    随机删除节点,查看网络的平均最短路径以及最大连通子图中节点的个数占原先最大连通子图节点个数的比例。

    刻意攻击:
    每次删除的都是度数最大的节点。评价方式与随机攻击相同。

    该实验利用matlab语言进行实现:

    • 计算节点的度
    function [node_degree]=DegreeDistribution(G)
    % 计算每个节点的度
    
    node_degree = sum(G');
    figure(1);
    bar(node_degree,'r');
    title('Node Degree Distribution');
    xlabel('Node');
    ylabel('Degree');
    avg_degree = sum(node_degree)/(length(node_degree));
    legend(num2str(avg_degree),'Location','NorthEastOutside');
    hold;
    
    figure(2);
    md = max(node_degree);
    for i=1:md+1
        n_deg(i) = length(find(node_degree == i-1));
    end
    bar([0:md],n_deg,'r');
    title('Node Degree Distribution');
    xlabel('Degree');
    ylabel('Node');
    avg_degree = sum(node_degree)/(length(node_degree));
    legend(num2str(avg_degree),'Location','NorthEastOutside');
    end
    
    
    
    • 计算图的平均最短路径
    function [mean_path]=AveragePath( G ,FLAG)
    %求一个图的平均最短路径(Average Shortest Path Length)
    
    len=length(G);%节点个数
    m = G;
    m(m==0)=len*2; %设置为最大距离的两倍,也就是不可达
    
    for i=1:len
        m(i,i)=0;%邻接矩阵的对角线元素均为0
    end
    
    if len<=1%少于一个点
        mean_path = 0;
    end
    
    for k=1:len%弗洛伊德算法
        for i=1:len
            for j=1:len
                if m(i,j)>m(i,k)+m(k,j)
                   m(i,j) = m(i,k)+m(k,j);
                end
            end
        end
    end
    
        
    for i=1:len
        m(m==len*2)=0;%不可达点的距离化为0
    end
        
       
        each_path = sum(m')/(length(m)-1);%每个点的平均最短路径长度,减一是减去到自己的距离(不存在)
        mean_path = sum(sum(m'))/length(nonzeros(m'));%整个网络的平均最短路径长度
        
        
        if nargin==1%输入的参数为一个,也就是不输入FLAG的值
         bar(each_path,'b');
         title('Average Shortest Path-Length');
         xlabel('Node');
         ylabel('Path length');
         legend(num2str( mean_path),'Location','NorthEastOutside');
        end  
    
    
    
    
    • 找出最大连通子图并计算最短路径
    function [max_1,Max_Sub,s,Q,min_path]=MaxSubPath(G,FLAG)
    %求最大连通子图的平均最短路径
    %C 顶点所分的块数
    %con 每行表示一个连通域中的节点标号
    %s 各连通域规模(节点数)
    %min_path 平均最短路径的长度
    %Max_Sub 最大连通子图所在的标号
    n=size(G,1);%将矩阵G的行数的值赋给n,也即节点的个数
    m=sum(sum(G))/2;
    c=1;
    q=zeros(n,1);%n*1的全0矩阵
    Q=zeros(n,1);
    for i=1:n
        if sum(G(i,:))==0  %G整行的和为0,说明i为孤立点
            q(i)=c;
            c=c+1;
        else   
            for j=1:n  
                if G(i,j)==1
                    if q(i)==q(j)   %若两者之间有边且标记相同,则属于同一块
                        if q(i)==0
                            q(i)=c;q(j)=c;
                            c=c+1;
                        end
                    else    %两者之间有边但标记不同
                        if q(i)==0   %i点尚未获得标记
                            q(i)=q(j);
                        elseif q(j)==0  %j点尚未获得标记
                            q(j)=q(i);
                        else   
                            for k=1:n   %更新标记
                                if q(k)==q(i)
                                    q(k)=q(j);
                                end
                            end
                        end
                    end
                end
            end
        end
    end
    
    %重新编号,排除空的块号
    C=0;
    for k=1:c-1
        if ~isempty(find(q==k, 1))%利用find函数找到q==k的下标
            C=C+1;
            Q(q==k)=C;%存储各个节点所在的块号
            s(C,1)=length(find(q==k)); 
        end
    end
    
    sort(s,1,'descend');
    
    Max_Sub=find(s==max(s));%最大连通子图所在的标号
    len_Q = length(Q);
    
    
    M = zeros(len_Q,len_Q)%创建一个新的矩阵存储最大连通子图的邻接矩阵
    for i=1:len_Q
      if Q(i)==Max_Sub
          for j=1:len_Q
              M(i,j)=G(i,j);
          end
      end
    end
    
    max_1 = s(1);%找到最大连通子图的节点数
       for i=1:length(s)
           if s(i)>max_1
               max_1 = s(i);
           end
       end
       
    A1=sum(abs(M'));%删除所有为0的行
    index=find(A1==0);
    M(index,:)=[];
    
    A2=sum(abs(M));%删除所有为0的列
    index=find(A2==0);
    M(:,index)=[];
    
    if nargin==1
        AveragePath(M);%计算最大连通子图的平均最短路径
    else
        min_path = AveragePath(M,FLAG);%计算最大连通子图的平均最短路径
    end  
    
    
    
    
    
    
    
    
    • 计算各节点的聚集系数
    function [C]=Coefficient(G)
    %计算每个节点的聚集系数(Cluster Coefficient)
    
    K = sum(G');%每个节点的度
    C = zeros(1,length(G));%记录每个节点的聚集系数
    
    for i=1:length(G)
        a = find(G(i,:)>0);
        E=0;
        for j=1:length(a)
          for k=j+1:length(a)
              if G(a(j),a(k))==1
                E = E+1;%邻居已有的边的条数
              end
          end
        end
        if K(i)==1||K(i)==0
            C(i)=0;
        else
            C(i) = 2*E/(K(i)*(K(i)-1));
        end
    end
    
    
    mean_c = sum(C)/length(C);
    bar(C,'g');
    title('Clustering Coefficient');
    xlabel('Node');
    ylabel('Coefficient');
    legend(num2str(mean_c),'Location','NorthEastOutside');
    end
    
    
    
    • 计算网络的核数
    function [CORENESS]=Coreness(G)
    %计算每个节点以及整个网络的核数(Coreness)
    CORENESS = zeros(1,length(G));%1*n的全0矩阵,即所有节点的核数均为0
    nodes_degree = sum(G');%每个点的度
    max = length(G)+ 1;%max即节点所能达到的最大度数+1,也即不能达到的度数
    pre_min = 0;%负责记录上一轮中的最小的度数
    counted_num=0;%负责记录查找并计算过的节点的数
    
    for i=1:length(nodes_degree)
       m = min(nodes_degree);%返回度数的最小值,是一个数值
       min_node = find(nodes_degree==m);%是一个列向量,返回最小度数的节点所在的列的下标,也即度数最小的节点序号
       counted_num = counted_num + length(min_node);
       if pre_min>m
       CORENESS(min_node) = pre_min;
       else
           CORENESS(min_node) = m;
       end
       
       if length(min_node)>1     %一个以上的最小度数的点
          for j=1:length(min_node)
              x = min_node(j);
              for k=1:length(G)
                  if G(k,x)==1%节点k与最小度数节点相连            
                      if CORENESS(k)==0%且该节点尚未在计算核数的范围内
                        nodes_degree(k) = nodes_degree(k)-1;%更新度数
                      end
                  end
              end
          end
       else     %只有一个最小度数的点
           for j=1:length(G)
              if G(j,min_node)==1;
                  if CORENESS(j)==0
                     nodes_degree(j) = nodes_degree(j)-1;%更新度数
                  end
              end
           end
       end
       
       nodes_degree(min_node) = max;%将这些原先度数最小的点的度化为max,目的是为了下一轮找最小度数节点不会再找到它们
       pre_min = m;%记录上一轮中的最小度数
       if counted_num>=length(nodes_degree)%查找完毕,提前跳出整个for循环
           break;
       end
    end
    
    
    bar(CORENESS,'m');
    title('Node Coreness');
    xlabel('Node');
    ylabel('Coreness');
    
    
    max_coreness = CORENESS(1);%找到最大的核数作为整个网络的核数
    for i=1:length(CORENESS)
        if CORENESS(i)>max_coreness
            max_coreness = CORENESS(i);
        end
    end
    
    legend(num2str(max_coreness),'Location','NorthEastOutside');
    
    end
    
    
    • 随机攻击
    function [mean_path]=RandomAttack1( G )
    %对网络进行随机攻击,查看其对平均最短路径的影响(RandomAttack)
    mean_path = zeros(1,length(G));
    [max,~,~,~,~] = MaxSubPath(G,2);
    MaxSubNum = max;
    max_sub_num = zeros(1,length(G));
    temp = G;
    
    
    for i=1:length(G)-1
       temp(1,:)=[];%去掉第1行
       temp(:,1)=[];%去掉第1列
       [~,~,~,~,min_path] = MaxSubPath(temp,2);
       mean_path(i) = min_path;
       [max_1,~,~,~,~] = MaxSubPath(temp,2);
       max_sub_num(i) = max_1/MaxSubNum;
    end
    
    figure(1);
    x = (1:length(G));
    plot(x,mean_path,'bx');
    title('Robustness Against Random Attack');
    xlabel('Node');
    legend('Average Shortest Path of Largest SubGraph','Location','NorthEastOutside');
    hold on;
    figure(2);
    plot(x,max_sub_num,'ro')
    title('Robustness Against Random Attack');
    xlabel('Node');
    legend('Percentage of Largest SubGraph','Location','NorthEastOutside');
    end
    
    
    • 刻意攻击
    function [keep_path]=IntentionalAttack1( G)
    %对网络进行随机攻击,查看其对平均最短路径的影响(IntentionalAttack)
    degree = sum(G');
    mean_path = zeros(1,length(G));
    [max_2,~,~,~,~] = MaxSubPath(G,2);
    MaxSubNum = max_2;
    max_sub_num = zeros(1,length(G));
    temp = G;
    
    for i=1:length(G)-1
      degree = sum(temp');
      j = find(degree==max(degree));
      if length(j)>1%不止一个的话就取第一个
          j = j(1);
      end
      temp(j,:)=[];
      temp(:,j)=[]; 
       
       [~,~,~,~,min_path] = MaxSubPath(temp,2);
       mean_path(i) = min_path;
       [max_1,~,~,~,~] = MaxSubPath(temp,2);
       max_sub_num(i) = max_1/MaxSubNum;
       
    end
    
    
    figure(1);
    x = (1:length(G));
    plot(x,mean_path,'bx');
    title('Robustness Against Intentional Attack');
    xlabel('Node');
    legend('Average Shortest Path of Largest SubGraph','Location','NorthEastOutside');
    hold on;
    figure(2);
    plot(x,max_sub_num,'ro')
    title('Robustness Against Intentional Attack');
    xlabel('Node');
    legend('Percentage of Largest SubGraph','Location','NorthEastOutside');
    end
    
    
    
    更多相关内容
  • 复杂网络建模

    2013-04-27 14:30:47
    复杂网络建模,用C编写,运行时先选择“BA无标度网络”,再选择“度分布”
  • 复杂网络建模工具

    2013-08-13 03:57:13
    一种比较实用的复杂网络建模工具和开发工具。
  • 哈工大深圳复杂网络建模课程设计,代码,报告,PPT都有,有演示视频
  • 复杂网络建模总结

    千次阅读 2020-10-27 23:29:38
    本文针对数学建模美赛中的复杂网络题,做了一些总结,具体涉及一些该题的注意事项。 注意事项 定义点和边的意义 制定连接规则,删除孤立节点(代表影响很小的点),可以限制网络的大小,减小运算量,同时也可以...

    本文针对数学建模美赛中的复杂网络题,做了一些总结,具体涉及一些该题的注意事项。

    注意事项

    1. 定义点和边的意义
    2. 制定连接规则,删除孤立节点(代表影响很小的点),可以限制网络的大小,减小运算量,同时也可以克服PageRank的不足点
    3. 网络根据有向/无向,有环/无环,有/无标度,可以根据其性质,制定不同的算法,简化传统的算法
    4. 常用度量的指标:度,中心性,聚类系数,密度,中介性Degree, Centrality, Clustering coefficient,  Density,  Betweenness一定要将各种指标联系实际,分析每种情况的特性
    5. 结合现实考虑,即使简化了也要表明出来
    6. 除了重要性,还应该考虑节点的权威性(如时间)等现实因素
    7. 考虑节点的时间因素,现实中的一切都是因果的,比如引用模型中,只能引用比自己先发表的论文,而且此时满足偏序关系
    8. 注意关系的自反性、对称性、传递性
    9. 关系网络:相容关系、等价关系、偏序关系;对分析出来的关系做说明,即使没有什么用也可以说明,来体现对该网络性质的研究
    10. 对网络关系性质的分析也是一个重点,网络的性质和建立网络的规则有关,规则又是由实际的问题情况决定
    11. 网络的稳定性探究也是很重要的一点,可以分析参数对排序或者其他结果的影响,还可以考虑节点缺失对网络造成的影响
    12. 拥有关系和引用关系类似
    13. 对于性质类似的网络,对不同问题采用不同的量化方法,制定规则量化为适合模型的值,使得模型可以推广
    14. 对于一道题搭了几个网络,可以将这几个网络的性质进行对比分析,最好还能说出各自的用途
    15. 扩散可以用到矢量分析与场论的知识,用梯度、散度、旋度来分析
    16. 传染病模型也经常用在网络题里面
    17. 1959年,汉森首次提出了交通可达性的概念,这被定义为接受道路网络中节点之间相互作用的机会。
    18. 可以自己定义算法,把边的权重转换到点上,这样就可以使用修正的PageRank算法求解点的重要性

    使得初始时点的权重为1,但是每条边的传递权重不同,而其邻接边的权重相加仍然为1(参考2014C--25318

     

    编程和图表

    1. 对于外行难懂的复杂网络图,最好给出图的解释,各种东西代表什么
    2. 对自己定义的网络规则最好用图来展示一下
    3. 复杂网络考虑计算复杂度,特别是在有改进的情况下说明复杂度的改善
    4. 网络有很重要的一点就是测试其稳定性

    数据预处理

    1. 复杂网络的题也常常涉及大数据,对于空白数据的处理很重要,对于空缺太多的数据直接删掉
    2. 接着对剩余数据处理;或者通过聚类,被聚类到一起的点,空缺数值可以用该类中数值完整的值的均值和方差来生成;最常用的就是插值,不过没有什么亮点
    3. C/D题,数据支撑和合理性很重要
    4. 归一化、标准化、中心化特别重要,记得说明各自的意义

    ​​​​​​​过程

    1. 一开始建立各项指标,用数据对属性进行描述,为数据预处理提供依据。同时这些指标的分类不同,可能作用于底层网络或者顶层网络,可能是节点指标也可能是边的指标(可以给边加权,可以给点加权注意两种网络的适用算法不同)
    2. 接着设置算法,选择算法;结合实际的问题,分析其是否有什么不合理的地方,对于不合理的地方想一想改进的措施
    3. 必要时考虑一下计算复杂度,考虑是否改善,对复杂度改善后可以使用原算法来验证正确性;考虑是否有可以用来类比的模型
    4. 建立好静态的网络结构之后,接下来就是要确定规则(类似于仿真规则),使网络变成动态模型
    5. 网络的改善就是不停对规则进行更改
    6. 注意模型建立好之后先验证合理性,再应用​​​​​​​

    一般情况都用双层网络,既不会过于简单,也不会计算量太大

    相关性很强(同一地区、同一背景等)的各集团作为高一层的节点,底层的网络由各个单独的节点构成

    采用双层网络模型有两种思路:

    1、先手动根据节点的某种/某些相似性把一些满足相似性的节点规定为一个集团,各个集团作为上层网络的节点

    2、直接所有节点一视同仁,然后用节点划分的方法,对网络进行分割,分割后每个集团作为底层网络,然后更改边的类型,集团内保持不变,集团间建立新的连接方式

    灵敏性/稳健性分析

    1. 研究网络是否是无标度性。(有些结论已经有了,比如社交网络就是无标度,先了解背景,如果没有研究文献再自己计算)其实复杂网络的无标度特性与网络的鲁棒性分析具有密切的关系。无标度网络中幂律分布特性的存在极大地提高了高度数节点存在的可能性,因此,无标度网络同时显现出针对随机故障的鲁棒性和针对蓄意攻击的脆弱性。这种鲁棒且脆弱性对网络容错和抗攻击能力有很大影响。研究表明,无标度网络具有很强的容错性,但是对基于节点度值的选择性攻击而言,其抗攻击能力相当差,高度数节点的存在极大地削弱了网络的鲁棒性,一个恶意攻击者只需选择攻击网络很少的一部分高度数节点,就能使网络迅速瘫痪。
    2. 删除重要节点,看对网络的影响
    3. 改变指标值/删除指标,分析影响
    4. 用斜率来度量影响是一种非常常见的方法,和灵敏度分析中分析参数的影响类似,特别是有解析式的时候
    5. 网络一般分析结果都是
      从节点的变化分析
      从边的参数变化分析
      从这个网络的演变(传播过程)分析
    展开全文
  • 安全技术-网络信息-产业复杂网络建模及应用.pdf
  • NetworkX提供了4种常见网络建模方法,分别是:规则图,ER随机图,WS小世界网络和BA无标度网络。 一. Networkx的下载安装 画图之前先将NetworkX装好,直接pip install Networkx的话会特别慢,而且通常会失败,所以...


    NetworkX提供了4种常见网络的建模方法,分别是:规则图,ER随机图,WS小世界网络和BA无标度网络。

    一. Networkx的下载安装

    画图之前先将NetworkX装好,直接pip install Networkx的话会特别慢,而且通常会失败,所以我一般都是先把库下载下来,再在本地安装。

    1、下载传送门:https://pypi.org/project/networkx/#files
    我下载的这个:
    在这里插入图片描述2、放到自己指定的文件夹(随意)
    3、本地安装
    在这里插入图片描述

    二. 规则图

    规则图差不多是最没有复杂性的一类图,random_graphs.random_regular_graph(d, n)方法可以生成一个含有n个节点,每个节点有d个邻居节点的规则图。
    下面一段示例代码,生成了包含20个节点、每个节点有3个邻居的规则图:

    import networkx as nx
    import matplotlib.pyplot as plt
    #生成了包含20个节点、每个节点有3个邻居的规则图
    RG = nx.random_graphs.random_regular_graph(3, 20)
    #spectral布局
    pos = nx.spectral_layout(RG)
    
    nx.draw(RG, pos, with_labels = False, node_size = 30)
    plt.show()
    

    在这里插入图片描述

    三、ER随机图

    ER随机图是早期研究得比较多的一类“复杂”网络,模型的基本思想是以概率p连接N个节点中的每一对节点。
    用random_graphs.erdos_renyi_graph(n,p)方法生成一个含有n个节点、以概率p连接的ER随机图:

    import networkx as nx
    import matplotlib.pyplot as plt
    #生成一个含有20个节点、以概率p = 0.2连接的ER随机图:
    ER = nx.random_graphs.erdos_renyi_graph(20, 0.2)
    #shell布局
    pos = nx.shell_layout(ER)
    nx.draw(ER, pos, with_labels = False, node_size = 30)
    plt.show()
    

    在这里插入图片描述

    四、WS小世界网络

    用random_graphs.watts_strogatz_graph(n, k, p)方法生成一个含有n个节点、每个节点有k个邻居、以概率p随机化重连边的WS小世界网络。

    import networkx as nx
    import matplotlib.pyplot as plt
    #生成一个含有20个节点、每个节点有4个邻居、以概率p=0.3随机化重连边的WS小世界网络
    WS = nx.random_graphs.watts_strogatz_graph(20, 4, 0.3)
    # circular 布局
    pos = nx.circular_layout(WS)
    nx.draw(WS, pos, with_labels = False, node_size = 30)
    plt.show()
    

    在这里插入图片描述

    五、BA无标度网络

    用random_graphs.barabasi_albert_graph(n, m)方法生成一个含有n个节点、每次加入m条边的BA无标度网络。

    import networkx as nx
    import matplotlib.pyplot as plt
    #生成一个含有20个节点、每次加入1条边的BA无标度网络。
    BA = nx.random_graphs.barabasi_albert_graph(20, 1)
    # spring 布局
    pos = nx.spring_layout(BA)
    nx.draw(BA, pos, with_labels = False, node_size = 30)
    plt.show()
    

    在这里插入图片描述

    六. 总结

    (1)基本绘图流程:
    在NetworkX中,绘制一个网络使用nx.draw()方法,它至少接受一个参数:即你希望绘制的网络G。实际上这个方法非常复杂,它可以指定20多个关键字参数,后边会介绍一些常用的参数,我们先从最简单的情况入手,看看下边的例子:

    import networkx as nx               #导入networkx包
    import matplotlib.pyplot as plt     #导入绘图包matplotlib(需要安装,方法见第一篇笔记)
    G =nx.random_graphs.barabasi_albert_graph(100,1)   #生成一个BA无标度网络G
    nx.draw(G)                      #绘制网络G
    #plt.savefig("ba.png")          #输出方式1: 将图像存为一个png格式的图片文件
    plt.savefig("ba_svg.svg")       #svg矢量图通常放入自己的论文中
    plt.show()                      #输出方式2: 在窗口中显示这幅图像
    

    在这里插入图片描述
    在这里插入图片描述

    (2)运用样式
    上边的代码虽然简单,但生成的图形略显单调。NetworkX提供了一系列样式参数,可以用来修饰和美化图形,达到我们想要的效果。常用的参数包括:
    - node_size: 指定节点的尺寸大小(默认是300,单位未知,就是上图中那么大的点)
    - node_color: 指定节点的颜色 (默认是红色,可以用字符串简单标识颜色,例如’r’为红色,'b’为绿色等,具体可查看手册)
    - node_shape: 节点的形状(默认是圆形,用字符串’o’标识,具体可查看手册)
    - alpha: 透明度 (默认是1.0,不透明,0为完全透明)
    - width: 边的宽度 (默认为1.0)
    - edge_color: 边的颜色(默认为黑色)
    - style: 边的样式(默认为实现,可选: solid|dashed|dotted,dashdot)
    - with_labels: 节点是否带标签(默认为True)
    - font_size: 节点标签字体大小 (默认为12)
    - font_color: 节点标签字体颜色(默认为黑色)
    灵活运用上述参数,可以绘制不同样式的网络图形,例如:nx.draw(G,node_size = 30,with_labels = False) 是绘制节点尺寸为30、不带标签的网络图。

    (3)运用布局
    NetworkX在绘制网络图形方面提供了布局的功能,可以指定节点排列的形式。这些布局包括:
    circular_layout:节点在一个圆环上均匀分布
    random_layout:节点随机分布
    shell_layout:节点在同心圆上分布
    spring_layout: 用Fruchterman-Reingold算法排列节点(这个算法我不了解,样子类似多中心放射状)
    spectral_layout:根据图的拉普拉斯特征向量排列节点?我也不是太明白
    布局用pos参数指定,例如:nx.draw(G,pos = nx.circular_layout(G))。

    我的第二篇博客,部分参考了他人的,参考链接在底部。初学者,欢迎交流!
    参考:https://www.cnblogs.com/forstudy/archive/2012/03/20/2407954.html
    https://www.cnblogs.com/gispathfinder/p/5790949.html

    展开全文
  • 复杂网络建模》课程project

    千次阅读 2019-10-29 18:09:57
    复杂网络建模》课程projectA.B. project内容![在这里插入图片描述](https://img-blog.csdnimg.cn/2019102918131634.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9...

    A.前言

    昨天晚上顺利考完张海军老师《复杂网络建模》的final exam,这门课算是彻底结束了。于是想把跟这门课有关的东西整理一下(但其实从时间线的角度来说,这部分这部分内容不该属于这里)。

    B. project内容

    在这里插入图片描述
    总结来说就是:三人一组,自己搞数据构建一个网络,然后去分析这个网络的一些特征。
    老师之前提到过,网络的节点越多,得分也会相应更高。我所做的是深圳的公交网络,小组三人分工,一人做UI、绘图,一人收集和处理数据并写报告什么的,我负责写核心代码。

    C.实验过程

    a.数据来源

    深圳公交线路的数据在网上直接能找到,最后拿到了944条公交线路的数据。每条线路存成一个文件,文件内容如下:
    车站名之间用权值分割,终点站后的权值为0
    车站名之间用权值分割,终点站后的权值为0
    理想的权值是两站之间的时间,但由于拿不到这个数据,这里的权值是随机生成的。

    b.数据结构

    点(node)

    typedef struct node {
        int id;
        int *line;
        int edge_num;  //  degree.    
    } node;

    边(edge)

    typedef struct edge {
        node *node_id;
        int weight;    
        struct edge *next;
    } edge;

    网络(network)

    struct {
        int sum;    
        char **name;    
        edge **e;    
        node **subway_station;
    } bus_net;

    有了这些接下来的就好说了。

    c. 特点

    1、我们的节点数是班上所有小组里最多的:5800+。我记得第二名有3000+,大家普遍在1000以内。当然节点多不代表一定好,节点少也不代表一定差。
    2、由于节点太多,会导致运算时间爆炸长(一个用python跑300+节点的同学说要40分钟,一个用matlib跑800+节点的同学也说要40分钟)。于是我选择使用C语言写核心代码来提高效率(其实是自己的研究方向经常写C,所以C最熟练 ^ _ ^)。
    3、大家普遍采用邻接矩阵保存图,似乎只有我采用了邻接链表。第一个原因同上,使用邻接链表可以很快速地定位到节点的边;第二个原因是公交线路节点的度大多数都为2,所以采用邻接矩阵太浪费空间,效率太低。
    4、负责做UI和绘图的同学用的python,所以为了配合他,我将C代码编译成了动态链接库;并写好了python接口。

    d.测试

    测试的具体结果就不贴了,平台是WSL-Ubuntu 18.04。只攻击一次的话,运行时间大概5分钟,时间上的优势可以说非常大了。
    放几张队友根据结果画的图:
    网络结构,红色点代表度大于等于5,蓝色为2-4,黄色为1
    网络结构,红色点代表度大于等于5,蓝色为2-4,黄色为1

    网络的度分布图
    网络的度分布图
    刻意攻击80%的节点后网络的结构
    刻意攻击80%的节点后网络的结构

    值得一提的是,这些结果都是在Windows下跑出来的,据我测试这跟真实值是有一定出入的。具体结果应该以在Linux下跑出的结果为准。

    C. 结束与反思

    1、最后这个project是要做一个presentation来介绍的,然后同学之间打分占60%,老师打分占40%。这就决定了UI的重要性,因为根据我的经验,同学打分受UI的影响极大。而我们的UI就是一个窗口加几个button,我在台上讲的时候真是尴尬死了,其他组的那些大佬们UI一个比一个酷炫。
    2、报告也没写好,队友在临交之前才写;PPT也是,马上要上台了我还在做PPT。
    3、以上主要原因:动手太晚,应该在国庆假期就开始做;我分工没做好,一门心思钻进代码里,也没督促队友进度;想carry全场却没那个实力,中间大大小小出了无数次bug,浪费了很长时间。

    总的来说,分工+实力都不够好,班上很多大佬都做得很好,自己还需修行。

    D.一个印象深刻的BUG

    在创建网络的produce_net_from_files()函数中,因为要打开900+个线路文件读取信息,所以在循环里用了一个fopen函数。这么个小细节导致了意想不到的bug,我找了很久也没找到问题所在,浪费了很长时间。最终我的同门帮我找到问题所在:没有fclose。这里出bug的具体原理留待以后分析。

    E.完整代码和数据

    只包含我写的C代码和python代码(均可运行)。
    代码 Github 链接

    展开全文
  • 复杂网络的基于matlab的网络基本模型,用matlab仿真复杂网络的同步,希望对大家有所帮助。
  • 以下部分摘自上一篇文章:如何建立复杂网络实体网络的Space L模型 地铁网络,一般都有三四百个节点,线路十几条左右,看地铁图的是一个眼花缭乱。若是人工统计出来数据也是一项大工程。看着就想放弃,但其实掌握...
  • 复杂网络建模的一些展望_王雄_上海交大,介绍复杂网络的一些最新研究成果及未来研究的方向
  • 复杂网络建模的SCI论文,绝对好论文,欢迎下载学习!
  • 基于复杂网络理论的制造网格建模及分析,尹勇,,制造网格是近几年出现的热门技术之一,引起国内外众多学者的广泛关注。本文从全局的角度出发,将制造网格资源节点作为复杂网络
  • 级联故障建模: 基于节点和边的混合动态模型:用eij来表示节点i、j之间的信息传递效率,eij∈[0,1],eij越大代表传输效率越高。用平均效率来衡量网络破坏的程度。 结论:ER随机图抵抗级联故障的能力比BA无标度网络...
  • 近年来的研究发现,许多现实系统都可以用一个复杂网络来描述。 这些复杂网络具有一些相同的特征,如网络平均距离较小、聚集系数较大、节点度分度服从幂律分布等,这些特性是复杂网络为完成某些特定功能而逐渐演化的...
  • 基于复杂网络的作战体系网络建模与优化研究
  • 安全技术-网络信息-基于复杂网络理论的复杂电力网络建模.pdf
  • 主要是用MATLAB来实现几类典型的复杂网络模型的仿真
  • 基于matlab的神经元网络复杂系统建模
  • 复杂网络演化博弈,学习建模的过程,一起学习。
  • 安全技术-网络信息-产业复杂网络建模仿真.pdf
  • 基于城市公交网络的相关特性,采用复杂网络建模机制,通过研究公交站点的复杂网络模型,得到了西安公交网络的度分布、中心性等指标,对西安公交线路结构现状做出了评价,结果表明西安市公交站点网络具有无标度的特征...
  • 针对复杂多态系统可靠性分析与评估的需求,本文从部件状态分析、系统结构分析入手,对存在认知不确定性同时考虑失效相关性的复杂多态系统进行可靠性建模与分析.由于现代复杂多态系统信息输入及系统故障影响因素的多样...
  • 关键的挑战是,在典型的大型多代理系统中,稀疏分布的代理只能与很少的其他代理直接通信,并且网络通常被建模为自适应复杂网络。 在本文中,我们介绍了构建用于对以网络为中心的多智能体系统的协调进行建模的模拟...
  • 3-1 基于复杂网络的图像建模与特征提取方法研究.xdf 图像检索传统方法的基础,KNN
  • python复杂网络分析库networkx

    万次阅读 多人点赞 2019-10-13 23:00:35
    文章目录1 简介安装支持四种图绘制网络图基本流程2...networkx是一个用Python语言开发的图论与复杂网络建模工具,内置了常用的图与复杂网络分析算法,可以方便的进行复杂网络数据分析、仿真建模等工作。 利用networ...
  • BioNet-Finder是一个基于网络的基因组数据建模项目,得到了Pavia大学(意大利Pavia)的大脑和行为科学系的多元统计实验室的支持,目的是共享数据,方法和代码,以进行基于网络的分析复杂的疾病。 我们的目标是提供...
  • 该程序将展示如何使用复杂网络对空域进行建模以及如何创建网络。 因此,创建了自由航线空域的数学模型。 该模型显示为图形的复杂网络。 图的边位于邻接矩阵文件 (FRA_matrix.csv) 和顶点列表文件 (FRA_list.csv) 中...
  • NetworkX 提供了常用的图论经典算法,例如DFS、BFS、最短路、最小生成树、最大流等等,非常丰富,如果不做复杂网络,只作图论方面的工作,也可以应用 NetworkX作为基本的开发包。具体的算法调用方法我就不一一介绍了...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 95,075
精华内容 38,030
关键字:

复杂网络建模