Louvain算法Matlab版本

Louvain算法Matlab版本

% Iplementation : Antoine Scherrer
% antoine.scherrer@ens-lyon.fr
% Apply clustering after :
% “Fast unfolding of community hierarchies in large networks“
% Vincent D. Blondel Jean-Loup Guillaume Renaud Lambiotte
% Etienne Lefebvre
% http://arxiv.org/abs/0803.0476
%
% NON ORIENTED VERSION USING SYMETRIC MATRIX A = M + M^t INSTEAD OF 
% （POSSIBLY NON SYMETRIC） INPUT MATRIX M
%
% FULL MATLAB VERSION （SLOWER）
%
% Inputs : 
% M : weight matrix （the matrix is symetrized with
% the sum of weights in both directions）
% s : 1 = Recursive computation
%   : 0 = Just one level computation
% self : 1 = Use self weights
%        0 = Do not use self weights
% debug   : 1 = outputs some debug messages
% verbose : 1 = outputs some messages
%
% Output :
% COMTY structure with the following information
% for each level i :
%   COMTY.COM{i} : vector of community IDs （sorted by community sizes）
%   COMTY.SIZE{i} : vector of community sizes
%   COMTY.MOD（i） : modularity of clustering
%   COMTY.Niter（i） : Number of iteration before convergence
%
function [COMTY ending] = cluster_jl（Msselfdebugverbose）

if nargin < 1
  error（‘not enough argument‘）;
end

if nargin < 2
  s = 1;
end

if nargin < 3
  self = 1;
end

if nargin < 4
  debug = 0;
end

if nargin < 5
  verbose = 0;
end

S = size（M）;
N = S（1）;

ddebug = 0;
ending = 0;

% Symetrize matrix taking the sum of weights
M = M + M‘;
if （self == 0）
  M（（N+1）.*[0:N-1]+1） = 0;
end
M2 = M;
M2（（N+1）.*[0:N-1]+1） = 0;

m = sum（sum（M））;
Niter = 1;

if m==0 | N == 1
%   fprintf（‘No more possible decomposition\n‘）;
  ending = 1;
  COMTY = 0;
  return;
end

% Main loop
K = sum（M）; % Sum of wieght incident to node i
SumTot = sum（M）;
SumIn = diag（M）; % Sum of weight inside community i
COM = 1:S（1）; % Community of node i
for k=1:N
  Neighbor{k} = find（M2（k:））;
end

sCost = 10;
gain = 1;
while （gain == 1）
  Cost = zeros（1N）;
  gain = 0;
  for i=1:N
    Ci = COM（i）;
    NB = Neighbor{i};
    G = zeros（1N）; % Gain vector
    best_increase = -1;
    Cnew = Ci;
    COM（i） = -1;
    SumTot（Ci） = SumTot（Ci） - K（i）;
    CNj1 = find（COM==Ci）;
    SumIn（Ci） = SumIn（Ci） - 2*sum（M（iCNj1）） - M（ii）;
    for j=1:length（NB）
      Cj = COM（NB（j））;
      if （G（Cj） == 0）
        CNj = find（COM==Cj）;
        Ki_in = 2*sum（M（iCNj））;
        G（Cj） = Ki_in/m - 2*K（i）*SumTot（Cj）/（m*m）;
        if （ddebug）
%           fprintf（‘Gaim for comm %d => %g\n‘Cj-1G（Cj））;
        end
        if G（Cj） > best_increase;
          best_increase = G（Cj）;
          Cnew_t = Cj;
        end
      end
    end
    if best_increase > 0
      Cnew = Cnew_t;
      if （debug）
%         fprintf（‘Move %d => %d\n‘i-1Cnew-1）;
      end
      Cost（i） = best_increase;
    end
    Ck = find（COM==Cnew）;
    SumIn（Cnew） = SumIn（Cnew） + 2*sum（M（iCk））;
    SumTot（Cnew） = SumTot（Cnew） + K（i）;
    COM（i） = Cnew;
    if （Cnew ~= Ci）
      gain = 1;
    end
    
  end
  sCost = sum（Cost）;
  [C2 S2] = reindex_com（COM）;
  Nco = length（unique（COM））;
  Nco2 = length（S2（S2>1））;
  mo

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-07-18 13:08  Louvain-matlab-win\
     文件       13876  2014-10-20 14:23  Louvain-matlab-win\Louvain.rar
     目录           0  2016-07-18 13:08  Louvain-matlab-win\Louvain\
     文件         330  2012-10-28 08:56  Louvain-matlab-win\Louvain\writefile.m
     文件         970  2013-01-17 14:33  Louvain-matlab-win\Louvain\karate1.dat
     文件        2904  2014-10-20 12:18  Louvain-matlab-win\Louvain\FastUnfording.m
     文件        1080  2013-01-17 13:43  Louvain-matlab-win\Louvain\convert2one.m
     文件        3859  2008-07-15 05:52  Louvain-matlab-win\Louvain\cluster_jl_orient_cpp.m
     文件        4056  2008-07-15 05:59  Louvain-matlab-win\Louvain\cluster_jl_orientT_cpp.m
     文件        5621  2008-07-15 05:59  Louvain-matlab-win\Louvain\cluster_jl_orientT.m
     文件        5907  2013-01-17 14:35  Louvain-matlab-win\Louvain\cluster_jl_orient.m
     文件        4166  2008-07-15 05:52  Louvain-matlab-win\Louvain\cluster_jl_cpp.m
     文件        5674  2013-01-17 14:42  Louvain-matlab-win\Louvain\cluster_jl.m