任务：

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

复杂网络建模2020fall
10.14晚19:00-21:00,记录一下题目。
第一题
几个判断题，考察概念，具体忘了。

triangle和rectangle是否isomorphism， 是否homomorphism

描述七桥问题，用Eularian graph/ semi-Eularian graph说明是否有解

Eularian graph和Hamiltonian graph 区别。
第二题
定义题：distance，diameter，average path length

七桥问题的图去掉两条边，加一条边。应该是变成了K4。求average degree，diameter，average path length。

七桥问题的图去掉两条边。求node clustering coefficient，node between ness，node coreness，adjacent matrix。
第三题
fully connected graph 每条边以一定概率删除，去掉度为0的点，问形成什么图，这类图的三种性质。

small world 和scale free各三种性质。

Robustness定义，如何考察。
第四题
一棵large size tree，每对点之间加边，加边概率与度数大的节点有关。

此Internet模型好不好，说三点理由。

cascading failure 和epidemic module 异同。
第五题
完全二叉树 第k层节点数$2^{k-1}$,求m层时节点数，边数。

叶节点取两点相连，两种情况是同构图，问鲁棒性是否不同及理由。

有一问没理解意思，大概是说不同类型图integrated形成的图需要分析inter difference，但heterogeneous graph 不用分析，说明原因。
第六题
两个讲过的图，几个属性相同，但eigenvalue不同，分析synchronization

star-shaped 图size不同，分析synchronization是否相同，及原因

《复杂网络建模》课程project
A.前言
B. project内容
C.实验过程
a.数据来源
b.数据结构
点(node)
边(edge)
网络(network)
c. 特点
d.测试
C. 结束与反思
D.一个印象深刻的BUG
E.完整代码和数据

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


总结来说就是：三人一组，自己搞数据构建一个网络，然后去分析这个网络的一些特征。

老师之前提到过，网络的节点越多，得分也会相应更高。我所做的是深圳的公交网络，小组三人分工，一人做UI、绘图，一人收集和处理数据并写报告什么的，我负责写核心代码。
C.实验过程
a.数据来源
深圳公交线路的数据在网上直接能找到，最后拿到了944条公交线路的数据。每条线路存成一个文件，文件内容如下：



车站名之间用权值分割，终点站后的权值为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


网络的度分布图



刻意攻击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 链接

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

注意事项

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



 

编程和图表

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

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

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

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

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

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

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

灵敏性/稳健性分析

研究网络是否是无标度性。（有些结论已经有了，比如社交网络就是无标度，先了解背景，如果没有研究文献再自己计算）。其实复杂网络的无标度特性与网络的鲁棒性分析具有密切的关系。无标度网络中幂律分布特性的存在极大地提高了高度数节点存在的可能性，因此，无标度网络同时显现出针对随机故障的鲁棒性和针对蓄意攻击的脆弱性。这种鲁棒且脆弱性对网络容错和抗攻击能力有很大影响。研究表明，无标度网络具有很强的容错性，但是对基于节点度值的选择性攻击而言，其抗攻击能力相当差，高度数节点的存在极大地削弱了网络的鲁棒性，一个恶意攻击者只需选择攻击网络很少的一部分高度数节点，就能使网络迅速瘫痪。
	
删除重要节点，看对网络的影响
	
改变指标值/删除指标，分析影响
	
用斜率来度量影响是一种非常常见的方法，和灵敏度分析中分析参数的影响类似，特别是有解析式的时候
	
网络一般分析结果都是
	
从节点的变化分析
			
从边的参数变化分析
			
从这个网络的演变（传播过程）分析