gn.m

复杂网络中的GN算法...............

clc;
clear;
mat=load('e:\exam\find_coremembers\reference38.txt');
n=length(mat);
m=sum(sum(mat))/2;
 
vs=[1:n];   %vs are the vertices which need to be recalculate
for i1=1:m
    smat=zeros(n);
    %calculate the shortest-path betweenness
    for i2=1:length(vs)
        %BFS
        ln=0;   %number of leaves
        D=zeros(1,length(vs))-1;
        D(vs(i2))=0;
        W(vs(i2))=1;
        pah=1;pat=1;    %two pointers indicate the index of array
        array(pat)=vs(i2);
        pat=pat+1;
        %calculate the distances and weight of vertices
        while(pah<pat)
            tp=array(pah);
            leaf=1; %assume tp is a leaf
            for i3=1:length(vs)
                if(mat(vs(tp),vs(i3)))
                    if(D(vs(i3))==-1)
                        leaf=0; %tp isn't a leaf
                        array(pat)=vs(i3);
                        pat=pat+1;
                        D(vs(i3))=D(vs(tp))+1;
                        W(vs(i3))=W(vs(tp));
                    elseif(D(vs(i3))==D(vs(tp))+1)
                        W(vs(i3))=W(vs(i3))+W(vs(tp));
                    end
                end
            end
            if(leaf)
                ln=ln+1;
                leaves(ln)=tp;
            end
            pah=pah+1;
        end
        %calculate the betweenness of the edges
        tvs=vs;
        for i3=1:length(tvs) %sort vs by des of D
            for i4=i3+1:length(tvs)
                if(D(tvs(i3))<D(tvs(i4)))
                    t=tvs(i3);
                    tvs(i3)=tvs(i4);
                    tvs(i4)=t;
                end
            end
        end
        tmat=zeros(n);  %temp matrix to save the betweenness
        T=zeros(1,n);   %temp array to save the sum of betweenness of the lower edges of a vertex
        for i3=1:length(tvs)
            tp=tvs(i3);
            for i4=1:length(tvs)
                if(mat(tvs(i3),tvs(i4)) && D(tvs(i3))==D(tvs(i4))-1 && D(tvs(i3))~=-1)
                    T(tvs(i3))=T(tvs(i3))+tmat(tvs(i3),tvs(i4));
                end
            end
            for i4=1:length(tvs)
                if(mat(tvs(i3),tvs(i4)) && D(tvs(i3))==D(tvs(i4))+1 && D(tvs(i4))~=-1)
                    tmat(tvs(i3),tvs(i4))=(T(tvs(i3))+1)*W(tvs(i4))/W(tvs(i3));
                    tmat(tvs(i4),tvs(i3))=tmat(tvs(i3),tvs(i4));
                end
            end
        end
        smat=smat+tmat;
    end
    %find the max-betweenness edge
    t=0;
    for i2=1:n
        for i3=1:n
            if(smat(i2,i3)>t)
                t=smat(i2,i3);
                cut(i1,:)=[i2 i3 smat(i2,i3)];
            end
        end
    end
    %save('tmat.txt','mat','-ascii');
    mat(cut(i1,1),cut(i1,2))=0;
    mat(cut(i1,2),cut(i1,1))=0;
end
cut