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 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(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
