精华内容
下载资源
问答
  • ComplexNetwork_TMU Tarbiat Modares大学的复杂网络课程
  • 复杂网络PPT

    2014-05-15 22:27:42
    复杂网络课程,十分详细的介绍了复杂网络基本知识,目前的研究现状和主要的应用领域
  • 咳咳,复杂网络建模project,哈工大深圳课程的项目作业。

    任务:
    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
    
    
    
    展开全文
  • 复杂网络复杂网络课程的大学项目
  • 哈工大深圳复杂网络建模课程设计,代码,报告,PPT都有,有演示视频
  • 复杂网络建模》课程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 链接

    展开全文
  • 复杂网络学习笔记

    2014-04-10 21:36:21
    复杂网络学习笔记,课程笔记,简单摘录,适合了解课程主要内容。
  • [Network Analysis] 复杂网络分析总结
    展开全文
  • 1.当今社会越来越多的现象会涉及复杂网络相关应用 举例:社交网络、搜索引擎 2.Internet的拓扑结构 原因:为预测和提高Internet的性能,特此引入Internet的拓扑结构 具体形式:(1)IP层次 (2)路由器层次 (3)...

    第一章 引论

    1.复杂网络相关应用

    随着信息技术的飞速发展,当今社会越来越多的现象会涉及到复杂网络相关应用。
    举例:社交网络、搜索引擎

    2.Internet的拓扑结构

    原因:为预测和提高Internet的性能,特此引入Internet的拓扑结构
    具体形式:(1)IP层次 (2)路由器层次 (3)自治系统层次
    表现:随时间的推移,IPv4中的IP地址和AS数量逐渐增加

    3.WWW

    表现:万维网地位的提高以及发展,与搜索引擎的迅速发展密不可分,而搜索引擎属于复杂网络的一个应用领域,因此可见,研究复杂网络有所重要。

    4.金融网络和经济网络

    背景:经济全球化的大势,给世界上各个国家带来诸多机遇和挑战。提高国际地位的关键,在于成为相对应网络中的关键节点
    表现:在产品空间(Product Space) 相关知识中,我们可以了解到附加价值越高的产品会集中在中心位置,附加价值越低的产品会集中在边缘位置,类比于全球的金融网络和经济网络,我们会发现位于网络中心位置的往往是传播能力强的发达国家。

    在这里插入图片描述

    5.社会网络

    背景:六度分离理论的提出
    发展:为探究六度分离理论的正确性,科学家们进行了Internet上的小世界实验,进而提出了弱连带和强连带的概念。
    弱连带与强连带的示意图

    6.网络科学的研究目的与研究内容

    研究目的:网络科学所要研究的是各种复杂网络之间的共性和处理他们的普适方法
    研究内容:网络科学着眼于复杂网络的定量与定性特征的科学理解。
    (1)发现 (2)建模 (3)分析 (4)设计
    在这里插入图片描述

    网络系统的复杂性主要体现在:
    (1)结构复杂性
    (2)节点复杂性
    (3)结构与节点之间的相互影响
    (4)网络之间的相互影响(不同领域网络之间相互作用)

    第二章 网络与图

    1.图的引入

    图:用抽象的点和线表示各种实际网络。
    图的拓扑性质:主要与网络中结点个数哪些节点有边直接相连相关。
    好处:研究抽象的图,我们可以通过比较不同网络拓扑性质的异同点来建立网络拓扑性质的有效算法。

    2.图的类型

    (1)加权有向图 (加权和有向指的是
    (2)加权无向图
    (3)无权有向图
    (4)无权无向图

    3.简单图

    类型:没有重边和闭环的无权无向图
    假设边数为M,顶点数为N,则无向图中边数与顶点数的关系为:

    极端情形:
    (1)空图 (2)完全图
    假设边数为M,顶点数为N,则有向图中边数与顶点数的关系为:
    在这里插入图片描述

    4.图的计算机表示

    (1)邻接矩阵(稠密图)
    (2)邻接表(稀疏图)
    (3)三元组(加权有向图)

    5.共引与文献耦合

    共同点:都属于有向网络到无向网络的对偶方法
    (1)共引:有向网络中节点i和j的共引数(Cij)定义为同时有出边指向节点i和节点j的节点数
    在这里插入图片描述特殊情况:Cii表示节点i的入度
    转换到无向网络:基于共引矩阵,一个有向网络对应的无向网络定义为:如果Cij>0,那么节点i和j之间就有一个边。
    (2)文献耦合:有向网络中节点i和j的文献耦合(Cij)定义为两个节点同时指向其他节点的数量
    在这里插入图片描述
    结论:共引程度反映的是两篇文章同时被多少篇其他文章引用;文献耦合程度反映的是两篇文章引用了多少篇相同的参考文献。

    6.路径与连通性

    简单路径:各个顶点都互不相同的路径是简单的。
    判断网络是否连通
    (1)当且仅当I+A+A2+…+AN-1是正矩阵,即所有元素都是正的。
    (2)当且仅当邻接矩阵是不可约的。

    7.Menger定理(门杰定理)

    点形式:所需去除的顶点的最少数目等于连接两个顶点的独立的简单路径的最大数目。->点割集
    边形式:所需去除的边的最少数目等于连接两个顶点不相交的简单路径的最大数目。 ->边割集

    8.最小生成树

    Prim算法:适合计算边稠密的网络的最小生成树。
    Kruskal算法:适合计算边稀疏的网络的最小生成树。

    9.二分图

    定义:图中的每条边的两个节点分别属于顶点集的两个子集中。
    在这里插入图片描述
    二分图的匹配:设G=(X,E,Y)为二分图,F为边集E的一个子集。如果F中任意两条边都没有公共端点,就称F为图G的一个匹配。

    第三章 网络基本拓扑性质

    1.网络稠密性与稀疏性

    网络的密度ρ:在这里插入图片描述
    网络稠密:当N趋于无穷时,ρ为非零常数,表示网络是稠密的;
    网络稀疏:当N趋于无穷时,ρ为0,表示网络是稀疏的.

    2.平均路径长度与直径

    节点i与j之间的距离:连接这两个节点的最短路径上的边的数目。
    平均路径长度:任意两个节点之间的距离的平均值。
    注意:一个含有N个节点和M条边的网络的平均路径长度可以用时间量级为O(MN)的广度优先搜索算法来确定。
    直径:网络中任意两个节点之间的距离最大值称为网络的直径。

    第五章 节点重要性与相似性

    1.无向网络节点重要性指标

    (1)度中心性(Degree Centrality,DC)
    定义:一个节点的度越大,意味着该节点在网络中越重要。
    公式:度中心值(DC)
    在这里插入图片描述
    (2)介数中心性(Betweenness Centrality,BC)
    定义:表示经过该边或该点的最短路径的数量。
    公式:边介数/点介数(BC)
    在这里插入图片描述
    (3)接近中心性(Closeness Centrality,CC)
    定义:若一个点到其他所有点的平均距离为d,则接近中心性为1/d(d的倒数)。
    公式:接近数(CC)
    在这里插入图片描述
    (4)k壳与k核
    k壳分解:按度数递增k从0开始,依次去除掉图中度为k的节点,最后剩下的节点即为最重要的节点。
    优点:k壳分解相比度中心性的优点在于,可以排除一些度很大但并不是最重要的节点。
    在这里插入图片描述
    (5)特征向量中心性(Eigenvector centrality,EC)
    基本思想:一个节点的重要性既取决于其邻居节点的数量,也取决于其邻居节点的重要性
    公式:特征向量中心性
    在这里插入图片描述

    2.HITS算法

    基本思想:每个网页的重要性有两个刻画指标——权威性枢纽性。其中一个网页的权威值由指向这个网页的所有页面的枢纽值确定,而一个网页的枢纽值由该网页指向的所有页面的权威值决定。
    枢纽值 ——> 权威值
    快速理解:举一个例子,一篇具有创新性的文章被很多人引用,那么这篇文章可以说具有权威性;一篇综述概况总结很多高权威的论点,那么这篇综述可以说具有枢纽性。

    3.PageRank算法

    基本思想:WWW上一个页面的重要性取决于指向它的其他页面的数量和质量,根据网页PR值的大小确定页面的重要程度。
    计算公式:
    在这里插入图片描述
    ​其中,Bu是所有链接到网页u的网页集合,网页v是属于集合Bu的一个网页,L(v)则是网页v的对外链接数(即出度).
    步骤
    (1)给每个网页一个PR值。
    (2)通过(投票)算法不断迭代,直至达到平稳分布为止。
    补充:网络中PR值的总和为1。

    4.链路预测

    (1)链路预测
    定义:它是指如何通过已知的各种信息预测给定网络中尚不存在连边的两个节点之间产生连接的可能性。
    基本假设:如果两个节点的相似性越大,那么两个节点之间有链接的可能性越大。
    应用:朋友推荐
    (2)衡量指标

    • AUC:测试集中的边的分数值比随机选择的一个不存在的边的分数值高的概率。
      在这里插入图片描述
    • Precision:只考虑排在前L位的边是否预测准确,即前L个预测边中预测准确的比例。
      在这里插入图片描述

    5.节点相似性指标

    (1)基于局部信息的相似性指标
    典型代表:共同邻居(CN)
    (2)基于全局信息的相似性指标
    典型代表:局部路径指标(LP)——在共同邻居的基础上,考虑了三阶邻居的影响。
    (3)基于随机游走的相似性指标

    第六章 随机网络模型

    1.全局耦合网络

    定义:如果一个网络中的任意两个节点之间都有边直接相连,那么就称该网络为一个全局耦合网络。
    局限性:大型实际网络都是稀疏的,边数目最多有O(n)。
    聚类系数:1

    2.最近邻耦合网络

    定义:如果在一个网络中,每一个节点只和它周围的邻居节点相连,那么就称该网络为最近邻耦合网络。
    特征:网络的拓扑结构是由节点之间的相对位置决定的,随着节点位置的变化网络拓扑结构可能发生切换。

    3.星形耦合网络

    定义:它有一个中心点,其余的N-1个点都只与这个中心点连接,而它们彼此之间不连接。
    聚类系数:0

    4.ER随机图模型

    (1)具有固定边数的ER随机图模型 G(N,M)
    定义:N个节点的图中,在任意两个节点之间添加M条边,其中选择的是两个不同的没有边连接的节点对。
    (2)具有固定连边概率的ER随机图模型 G(N,p)
    定义:把N个节点中任意两个不同的节点之间有一条边的概率固定为p,生成随机数r(0-1之间),若r<p,则在两个节点之间添加边。

    第七章 小世界网络模型

    第八章 无标度网络模型

    1.鲁棒性

    定义:对于给定的网络,如果在移走少量节点后网络中的绝大部分节点是连通的,那么就称该网络的连通性对节点故障具有鲁棒性。

    2.随机网络和无标度网络鲁棒性的比较

    (1)无标度网络
    无标度网络对随机节点故障具有较高的鲁棒性
    无标度网络对蓄意攻击具有高度的脆弱性
    原因: 无标度网络的网络度分布具有极端非均匀性,即绝大多数节点的度较小,只有一小部分节点的度较大。
    (2)随机网络
    随机网络对随机节点故障具有高度的脆弱性

    展开全文
  • 复杂网络】网络级联模型

    千次阅读 2019-05-24 11:04:18
    经典的信息扩散模型 数据驱动的信息扩散模型 网络级联模型的一些补充:...首先,我们将社交网络抽象为一个有向图,其中,为节点的集合,是边的集合,网络中的节点有两个状态——激活...
  • 复杂网络相关资源,持续更新……

    千次阅读 2015-10-13 16:26:40
    整理下自己在网上扒到的复杂网络相关资源,方便自己以后找-_-|||包括大牛主页,代码,数据集,软件,公开课等等个人主页 Albert-László Barabási及其实验室主页 http://www.barabasi.com/index.php ...
  • 复杂网络实验7:pagerank算法(matlab)

    千次阅读 多人点赞 2019-05-29 17:51:35
    可以证明:从网络中随机选出一个节点,顺着有向边行走K步之后,位于节点i的概率, 等于运用pagerank算法k步后得到的节点i的PR值。 这个结论很厉害,写在书上的应该错不了,书上也没给出证明,就先把这个结论当个...
  • 关于快速刷网络课程网络视频方法的探索

    万次阅读 多人点赞 2019-08-16 23:23:44
    快速刷完网络视频课程的一些思路分享与记录,目前主要有加速法、翻页法和POST法
  • NetworkX是一个Python软件包,用于创建,操纵和研究复杂网络的结构,动力学和功能。 复杂网络软件 图,有向图和多重图的数据结构 许多标准图算法 网络结构与分析措施 经典图,随机图和合成网络的生成器 节点可以是...
  • 复杂网络学习记-7-24

    千次阅读 2012-07-24 08:10:50
    是为了软件维护和反向工程而建立的复杂网络模型,另外一个 ”usingneural network to analyse software complexcity” 还没有仔细看完,但是这两篇都提到用神经网络的类似模型,还有一点就是动态的演化。 虽然...
  • SNAP(Stanford Large Network Dataset Collection)实验数据集 主要包含以下数据集 ...Social networks : online social networks, edges represent interactions ... between peopleNetworks with ground-truth...
  • 网络科学导论

    热门讨论 2013-05-24 22:23:01
    汪小帆 网络科学导论 课件 复杂网络 课程资源
  • 《网络嗅探器的设计与实现》计算机网络课程设计 目 录 1实验要求… 1 2实验内容 …1 2.1背景… 1 2.2基本概念和原理 …2 3设计思路 …5 3.1 设计流程图 …5 3.2 主要代码… 5 4运行与测试… 10 5总结 …11 参考文献...
  • 计算机网络课程设计—组建小型企业网络

    万次阅读 多人点赞 2011-12-30 13:32:23
    哈尔滨理工大学荣成学院 ...计算机网络基础 课程设计   学生姓名: 李秉鹏 学 号: 1030370216    学 院: 哈尔滨理工大学荣成学院    系 别: 软件工程系    专业班级: 计应10-
  • 目录1 引言2 复杂网络的图要素3 复杂网络度量4 复杂网络模型5 网络表示学习6 主题模型 1 引言 社会计算是指社会科学和计算技术交叉融合而成的一个研究领域,研究如何利用计算系统帮助人们进行沟通与协作,研究如何...
  • 神经网络课程(下)

    千次阅读 2018-06-13 22:53:30
    第5讲 神经网络的泛化理论 5.1 正则化方法对泛化能力的影响神经网络设计时使用的正则化方法时[WeRu1991, GiJo1995,Mack1992b],通常被称为“权衰减法”,该方法的工作机理可以用先验分布的角度加以解释。...
  • 计算机网络课程设计(一)

    万次阅读 2019-07-08 16:14:59
    静态路由具有简单、高效、可靠和网络安全保密性高的优点,但一旦静态路由的拓扑结构和链路状态发生变化,路由器中的静态路由信息需要大范围地调整,这一工作的难度和复杂程度非常高。 8. 思考题 在Cisco的路由器中...
  • 前言:搜罗来一些不错的网络课程,比如Coursera, edX, Udacity上 一、计算机类 算法类首推Coursera上普林斯顿大学的Robert Sedgewick,讲课特点是能把复杂的算法讲解清楚(典型例子:红黑树,KMP算法) ...
  • 这样会造成两个后果,一是神经网络结构复杂,数据量相对不够,容易出现过拟合;二是所需内存、计算量较大。解决这一问题的方法就是使用卷积神经网络(CNN)。 ### 2. Edge Detection Example 对于CV问题,我们在...
  • 神经网络课程(上)

    千次阅读 2018-06-12 22:21:21
    PDF 下载链接第二章 基本的神经元模型1)神经元模型最简单的MP模型,右图是“与”逻辑的数学表达:神经元模型 基函数表示“如何组合” 激活函数表示“是否到阈值”“最后网络表达的方式”基函数类型1:线性函数 基...
  • 本套视频课程的讲师刘硕是清华大学出版社出版的《精通Scrapy网络爬虫》的作者,该视频课程为此书的配套课程, 在书中内容的基础...适合有一定Python语言基础,想学习编写复杂网络爬虫的程序员及网络爬虫工程师使用。...
  • 这一节主要是介绍了三种主要的神经网络模型:前向网络、循环神经网络和对称网络前向网络 Feed-forward Neural Networks如果把神经元看做节点,把神经元的输出到另一个神经元的输入看做有向边,那么神经网络可以看做...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 79,757
精华内容 31,902
关键字:

复杂网络课程