% Newman-Girvan community finding algorithm
% source: Newman, M.E.J., Girvan, M., "Finding and evaluating community structure in networks"
% Algorithm idea:
% 1. Calculate betweenness scores for all edges in the network.
% 2. Find the edge with the highest score and remove it from the network.
% 3. Recalculate betweenness for all remaining edges.
% 4. Repeat from step 2.
% INPUTs: adjacency matrix (adj), number of modules (k)
% OUTPUTs: modules (components) and modules history - each "current" module, Q - modularity metric
% Other routines used: edge_betweenness.m, subgraph.m, numedges.m
% GB, April 17, 2006, computing modularity, added April 28, 2011
function [modules,module_hist,Q] = newmangirvan(adj,k)
n=size(adj,1);
module_hist{1} = [1:n]; % current component
modules{1}=[1:n];
curr_mod=1;
adj_temp=adj;
while length(modules)