《节点重要度算法-MATLAB源代码.docx》由会员分享，可在线阅读，更多相关《节点重要度算法-MATLAB源代码.docx（5页珍藏版）》请在三一文库上搜索。
1、节点收缩算法：function Z=node(a,dy)%a 为邻接矩阵 a(a=inf)=0;a(=0)=1;n=size(a,1);%矩阵维数Z=zeros(n,1);%节点重要度向量%由邻接矩阵a得到直接矩阵H%H 表示 c(i j)H=zeros(size(a);for i=1:nfor j=1:nif j=iH(i,j)=0;elseif a(I,j)=1H(i,j)=1;elseH(i,j)=inf;endendend%用Floyd法计算节点收缩前的最短就离矩阵DD=H;for k=1:nfor i=1:nfor j=1:nIf D(i,k)+D(k,j)<D(iI,j)D(
2、i,j)=D(i,k)+D(k,j);endendendend%计算节点重要度D2=zeros(size(D);for i=1:n%得到与节点i邻接的节点向量II=zeros(1,0);T=0;for j=1:nif a(i,j)=1T=t+1;I=i,j;endend%计算收缩后最短距离矩阵D2%D2 为 d'(pq) D 为 d(pq)for p=1:nfor q=1:nIf p=1&q=iIf D(p,i)+D(i,q)=D(p,q) D2(p,q)=D(p,q)-2;elseifD(p,i)+D(i,q)=D(p,q)+1 D2(p,q)=D(p,q)-1;elseif
3、 D(p,i)+D(i,q)=D(p,q)+2 D2(p,q)=D(p,q);endelseif p=i | q=i D2(p,q)=D(p,q)-1;elseD2(p,q)=0; end endendN3=n-t;%收缩后的节点数n3D3=D2;%计算收缩后的最短距离矩阵D3, D3为DD3(I,:)=;%删除与节点i邻接的节点对应的行 D3(:,I)=;%删除与节点i邻接的节点对应的列 %计算节点收缩后的节点重要度 s=0;for p=1:n3 for q=p:n3s=s+D3(p,q);endendl=s/(n3*(n3-1)/2);% 为 n Z(i)=1/(n3*l);end=点介数
4、function B=betweenness_node(A,a)%求网络节点介数，BY QiCheng%思想：节点i、j间的距离等于节点i、k间距离与节点k、j间距离时，i、j间的最短路径 经过k。%因为i、j节点的最短路径经过k时，i到k与k到j必定都是最短路，这个可以用反证法来证明。% A网络邻接矩阵，亦可以是赋权图% a=0为无向网络；a=1为有向网络；% B一节点介数N=size(A,1);B=zeros(1,N);D,C,aver_D=Distance_F(A); %C是 ij 间最短路径条数if a=0for k=1:Nfor i=1:Nif i=k溯端节点不算for j=i+1:
5、N %H为是无向的，所以正向、反向只算一次，所以只算一半；都算的话累加一起就是两倍了，也不影响if j=k %!端节点不算if D(i,j)=D(i,k)+D(k,j)&C(i,j)=0潮足条件即证明ij间最短路径经过k节点B(k)=B(k)+C(i,k)*C(k,j)/C(i,j);endendendendendendelsefor k=1:Nfor i=1:Nif i=k溯端节点不算for j=1:Nif j=k%f端节点不算if D(i,j)=D(i,k)+D(k,j)&C(i,j)=0醐足条件即证明ij间最短路径经过k节点B(k)=B(k)+C(i,k)*C(k,j)/
6、C(i,j);endendendendendend end=魅介数=function B=betweenness_edge(A,a)%求网络边介数，BY QiCheng%思想：节点i、j间的距离等于节点i、k间距离与节点k、j间距离时，i、j间的最短路径 经过k。%因为i、j节点的最短路径经过 k时，i到k与k到j必定都是最短路，这个可以用反证法 来证明。% A网络邻接矩阵，亦可以是赋权图% a=0为无向网络；a=1为有向网络；% B边介数N=size(A,1);B=zeros(N,N);D,C,aver_D=Distance_F(A); %C是 ij 间最短路径条数for i=1:NC(i,
7、i)=1;end时*都管有没有自连接，自身到自身的最短路数为1,温为nm的其中一点可能与i或j重合，若不设为1,会算少%*if a=0for n=1:Nfor m=1:N%&介数没有什么记不计入端点一说for i=1:Nfor j=1+i:N 咖向网络对称，正向、反向只算一次，所以只算一半；全算就是两倍if D(i,j)=D(i,n)+D(n,m)+D(m,j)&C(i,j)=0&A(n,m)=0涮足条件即证明ij间最短路径经过边 enmB(n,m)=B(n,m)+C(i,n)*C(m,j)/C(i,j);B(m,n)=B(n,m);endendendendendels
8、efor n=1:Nfor m=1:N%*注意：有向、无向网络的边介数算出来是一样的，羯为虽然无向网络正反向只算一次，但同时nm不考虑通过顺序，二者抵消了for i=1:Nfor j=1:Nif D(i,j)=D(i,n)+D(n,m)+D(m,j)&C(i,j)=0&A(n,m)=0涮足条件即证明ij间最短路径经过边 eikB(n,m)=B(n,m)+C(i,n)*C(m,j)/C(i,j);endendendendendendfor i=1:NB(i,i)=0; %不考虑自连接，就相当于计算节点介数时不考虑端点一样end=需要调用函数求节点间最短路径数=function D
9、,C,aver_D=Distance_F(A)%求复杂网络中两节点的距离、平均最短路径长度以及节点间最短路径条数%采用Floyd算法计算任意两节点的距离，并求最短路径条数用于计算介数% A网络图的邻接矩阵，*亦可以是赋权图*% D网络的距离矩阵% C节点间最短路径条数% aver_D网络的平均路径长度N=size(A,2);%N为矩阵A的列数D=A;C=A;C(C=inf)=0;%若A为赋权图，inf表示两点间无连接，所以连接数记为0C(C=0)=1;9源先直接相连的边记为1,可以有自连接(若A为赋权图，自连接信息就没了)D(D=0)=inf;%将邻接矩阵变为邻接距离矩阵，两点无边相连时赋值为
10、无穷大%自身到自身的距离为0for i=1:ND(i,i)=0;%自身到自身的距离为 0endfor k=1:N%Floyd算法求解任意两点的最短路径长度for i=1:Nfor j=1:N %可以只算一半，因为是对称的,*不影响结果大小*,但是记得加上 D(j,i)=D(i,j)if D(i,j)>D(i,k)+D(k,j)D(i,j)=D(i,k)+D(k,j);脸新 ij 间距离C(i,j)=C(i,k)*C(k,j);藏新最短路径条数elseif D(i,j)=D(i,k)+D(k,j)if k=i&&k=j %为避免重复计数，这里排除端点；C(i,j)=C(i,j)+C(i,k)*C(k,j); %新与最短距离相同的路径数endendendendendaver_D=sum(sum(D)/(N*(N-1); % 平均最短路径长度% if aver_D=inf% disp（'该网络图不是连通图'）;% end