Louvain快速社区发现算法Fast unfolding算法

目前社区发现算法中计算速度最快的算法，由Vincent D.Blondel等人在2008年提出，基于modularity optimization启发式算法，代码可直接使用，在Vincent D.Blondel个人官网上下载的

% 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））;
  mod = co

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        187  2016-06-26 18:24  Community_BGLL_Louvain\A2.mat

     文件       5658  2008-07-15 13:52  Community_BGLL_Louvain\cluster_jl.m

     文件       4166  2008-07-15 13:52  Community_BGLL_Louvain\cluster_jl_cpp.m

     文件       5904  2016-05-30 21:41  Community_BGLL_Louvain\cluster_jl_orient.m

     文件       5621  2008-07-15 13:59  Community_BGLL_Louvain\cluster_jl_orientT.m

     文件       4056  2008-07-15 13:59  Community_BGLL_Louvain\cluster_jl_orientT_cpp.m

     文件       3859  2008-07-15 13:52  Community_BGLL_Louvain\cluster_jl_orient_cpp.m

     文件       5546  2008-07-15 13:52  Community_BGLL_Louvain\jl_clust.cpp

     文件      13241  2008-07-15 13:52  Community_BGLL_Louvain\jl_clust.mexglx

     文件       5856  2008-07-15 13:55  Community_BGLL_Louvain\jl_clust_orient.cpp

     文件      14264  2008-07-15 13:56  Community_BGLL_Louvain\jl_clust_orient.mexglx

     文件       1843  2008-06-26 15:32  Community_BGLL_Louvain\jl_mnew.cpp

     文件       8756  2008-07-15 13:52  Community_BGLL_Louvain\jl_mnew.mexglx

     文件       1502  2016-05-13 18:19  Community_BGLL_Louvain\readme.txt

     目录          0  2016-07-23 15:30  Community_BGLL_Louvain

----------- ---------  ---------- -----  ----

                80459                    15