节点重要度算法-MATLAB源代码

节点收缩算法：

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:n for j=1:n if j==i H(i,j)=0; elseif a(I,j)==1 H(i,j)=1; else H(i,j)=inf; end end end %用Floyd法计算节点收缩前的最短就离矩阵D D=H； for k=1:n for i=1:n for j=1:n If D(i,k)+D(k,j)

%计算节点重要度 D2=zeros(size(D)); for i=1:n %得到与节点i邻接的节点向量I I=zeros(1,0); T=0; for j=1:n if a(i,j)=1 T=t+1; I=[i,j]; end end

%计算收缩后最短距离矩阵D2

ò为d’(pq) D为d(pq) for p=1:n for q=1:n If p~=1&q~=i If 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 D(p,i)+D(i,q)==D(p,q)+2 D2(p,q)=D(p,q); end elseif p==i｜q==i D2(p,q)=D(p,q)-1; else D2(p,q)=0; end end end

N3=n-t;%收缩后的节点数n3

D3=D2;%计算收缩后的最短距离矩阵D3，D3为D D3(I,:)=[];%删除与节点i邻接的节点对应的行 D3(:,I)=[];%删除与节点i邻接的节点对应的列 %计算节点收缩后的节点重要度 s=0; for p=1:n3 for q=p:n3 s=s+D3(p,q); end end l=s/(n3*(n3-1)/2);%为n

Z(i)=1/(n3*l); end

===================================节点介数========================= 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==0 for k=1:N for i=1:N

if i~=k %两端节点不算

for j=i+1:N %因为是无向的，所以正向、反向只算一次，所以只算一半； %都算的话累加一起就是两倍了，也不影响 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); end end end end end end else

for k=1:N for i=1:N

if i~=k %两端节点不算 for j=1:N

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); end end end end end

end 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:N %**************************************** C(i,i)=1; %不管有没有自连接，自身到自身的最短路数为1，

end %因为nm的其中一点可能与i或j重合，若不设为1，会算少 %**************************************** if a==0

for n=1:N

for m=1:N %边介数没有什么记不计入端点一说

for i=1:N

for 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间最短路径经过边enm B(n,m)=B(n,m)+C(i,n)*C(m,j)/C(i,j); B(m,n)=B(n,m); end end end end end else

for n=1:N

for m=1:N %****注意：有向、无向网络的边介数算出来是一样的， %因为虽然无向网络正反向只算一次，但同时nm不考虑通过顺序，二者抵消了 for i=1:N for j=1:N

if D(i,j)==D(i,n)+D(n,m)+D(m,j)&C(i,j)~=0&A(n,m)~=0 %满足条件即证明ij间最短路径经过边eik B(n,m)=B(n,m)+C(i,n)*C(m,j)/C(i,j);

end end end end end end

for i=1:N

B(i,i)=0; %不考虑自连接，就相当于计算节点介数时不考虑端点一样 end

======================需要调用函数求节点间最短路径数==============================

function [D,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表示两点间无连接，所以连接数记为0 C((C~=0))=1;%原先直接相连的边记为1，可以有自连接（若A为赋权图，自连接信息就没了） D((D==0))=inf;%将邻接矩阵变为邻接距离矩阵，两点无边相连时赋值为无穷大 %自身到自身的距离为0

for i=1:N

D(i,i)=0; %自身到自身的距离为0 end

for k=1:N %Floyd算法求解任意两点的最短路径长度 for i=1:N

for 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); %更新与最短距离相同的路径数 end end end end end

aver_D=sum(sum(D))/(N*(N-1)); %平均最短路径长度

% if aver_D==inf

% disp('该网络图不是连通图'); % end

本文来源：https://www.bwwdw.com/article/d6ew.html