GN算法，matlab

社区发现 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（1length（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            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））                    t=tvs（i3）;
                    tvs（i3）=tvs（i4）;
                    tvs（i4）=t;
                end
            end
        end
        tmat=zeros（n）;  %temp matrix to save the betweenness
        T=zeros（1n）;   %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（i2i3）>t）
                t=smat（i2i3）;
                cut（i1:）=[i2 i3 smat（i2i3）];
            end
        end
    end
    %save（‘tmat.txt‘‘mat‘‘-ascii‘）;
    mat（cut（i11）cut（i12））=0;
    mat（cut（i12）cut（i11））=0;
end
cut

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2803  2009-03-11 16:14  GN.m

----------- ---------  ---------- -----  ----

                 2803                    1