-
Notifications
You must be signed in to change notification settings - Fork 2
/
newman_girvan_split.m
71 lines (61 loc) · 1.83 KB
/
newman_girvan_split.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
function [group1 group2 modularity] = newman_girvan_split(W,aux_indices)
%% INITIALIZE
A = W>0;
N = size(A,1);
if ~exist('aux_indices','var')
aux_indices = 1:N;
end
PopularEdges = zeros(N,N,N);
%Aoriginal = A;
Woriginal = W;
%iteration=1;
%separation_flag=false;
%% STEPS
while true;
%% (RE)CALCULATE POPULARITIES GIVEN STEP
for startnode=1:N
[distances weights] = weighted_shortest_paths(W,startnode);
if isinf(sum(distances))
%separation_flag=true;
group1 = find(~isinf(distances));
group2 = find(isinf(distances));
modularity = get_modularity({group1;group2},W)
group1 = aux_indices(find(~isinf(distances)));
group2 = aux_indices(find(isinf(distances)));
return;
else
SP = weighted_SP_tree(W,distances,weights,startnode);
PopularEdges(:,:,startnode) = edge_popularity_given_startnode(W,startnode,distances,weights,SP);
end
end
%% REMOVE MOST POPULAR EDGE
%if ~separation_flag
%end
P=sum(PopularEdges(:,:,:),3)./W;
%iteration = iteration+1;
[x y] = find_matrix_max(P);
A(x,y)=0;
A(y,x)=0;
W(x,y)=0;
W(y,x)=0;
% x
% y
% disp('-----------')
end
end
%% GET MODULARITY FOR GIVEN SPLIT
% function m = get_mod(group1,group2,W)
% %A = W>0;
% total_edges = sum(sum(triu(W)));
% e = zeros(2);
%
% e(1,1) = sum(sum(triu(W(group1,group1))));
% e(2,2) = sum(sum(triu(W(group2,group2))));
% e(2,1) = sum(sum(W(group2,group1)));
% e(1,2) = e(2,1);
%
% e = e./total_edges;
% a = sum(e,2);
%
% m = trace(e) - sum(a.^2);
% end