GirvanNewman.m

function [A, q] = GirvanNewman( A, k )
%GIRVANNEWMAN Detect communities in a graph
%   Input 
%       A is a graph
%       k is the number of communities

% Save A
B = sparse(adjacency(A));

% Initiale counter for components
i = 0;  
while i < k
    % First calculate betweenness 
    betweenness = centrality(A, 'betweenness');
    
    % Remove edge
    % Find vertex with highest betweenness
    [~,maxBetweenness] = max(betweenness(:));
    nextNode = 0;
    nextBetweenness = 0;
    % Find vertex' neighbor with highest betweenness
    neighborNodes = neighbors(A, maxBetweenness);
    for n = 1:numel(neighborNodes)
        node = neighborNodes(n);
        if nextBetweenness < betweenness(node) 
            nextBetweenness = betweenness(node);
            nextNode = node;
        end
    end
    % Remove edge between both vertices
    A = rmedge(A, maxBetweenness, nextNode);
    % Calculate components
    m = sparse(adjacency(A));
    [i,com] = graphconncomp(m);
end

% Modularity
q = 0;

aEdges = size(B,1);
for c=1:i
    % Select component
    indices=find(com==i);
    % Create subgraph
    sub = subgraph(graph(B),indices);
    e_mm = size(sub.Edges,1)/aEdges;
    a_m = sum(sum(B(indices,:)))/aEdges-e_mm;
    q = q + (e_mm - a_m^2);
end
end