任务：

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

《复杂网络建模》课程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 链接

[Network Analysis] 复杂网络分析总结

第一章 引论
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）随机网络

随机网络对随机节点故障具有高度的脆弱性。