节点重要度算法-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);