GenLouvain»Gen Louvain

GenLouvain.GenLouvain History

Hide minor edits - Show changes to output

Changed line 7 from:
To help identify relevant resolution and interlayer coupling parameters, and to resolve some questions that arise because of the stochasticity of computational heuristics for community detection, we also encourage you to consider using the CHAMP package available at https://github.com/wweir827/champ , implementing the method described in "[[http://dx.doi.org/10.3390/a10030093|Post-Processing Partitions to Identify Domains of Modularity Optimization]]".
to:
To help identify relevant resolution and interlayer coupling parameters, and to resolve some questions that arise because of the stochasticity of computational heuristics for community detection, we also encourage you to use the '''CHAMP package''' available at https://github.com/wweir827/champ , implementing the method described in "[[http://dx.doi.org/10.3390/a10030093|Post-Processing Partitions to Identify Domains of Modularity Optimization]]".
Added lines 7-8:
To help identify relevant resolution and interlayer coupling parameters, and to resolve some questions that arise because of the stochasticity of computational heuristics for community detection, we also encourage you to consider using the CHAMP package available at https://github.com/wweir827/champ , implementing the method described in "[[http://dx.doi.org/10.3390/a10030093|Post-Processing Partitions to Identify Domains of Modularity Optimization]]".
Deleted line 19:
Changed line 3 from:
If you use this code in your work, please cite it as follows:
to:
If you use this code in your work, please cite it as follows:\\
Changed line 10 from:
* Version 2.1 (November 2016): [[(Attach:)GenLouvain2.1.1.zip]]
to:
* Version 2.1 (November 2016): [[(Attach:)GenLouvain2.1.zip]]
August 28, 2017, at 02:02 PM by PJM - 2.1.1 and explicit citation (not just in readme)
Changed lines 3-4 from:
The most recent package file is [[(Attach:)GenLouvain2.1.zip]]. Please see the @@README@@ file there. For ongoing development and pre-release versions see the  [[https://github.com/GenLouvain/GenLouvain|GitHub]] page.
to:
If you use this code in your work, please cite it as follows:
Lucas G. S. Jeub, Marya Bazzi, Inderjit S. Jutla, and Peter J. Mucha,
"A generalized Louvain method for community detection implemented in MATLAB," http://netwiki.amath.unc.edu/GenLouvain (2011-2017).

The most recent package file is [[(Attach:)GenLouvain2.1.1.zip]] (February 2017)
. Please see the @@README@@ file there. For ongoing development and pre-release versions see the  [[https://github.com/GenLouvain/GenLouvain|GitHub]] page.
Added line 10:
* Version 2.1 (November 2016): [[(Attach:)GenLouvain2.1.1.zip]]
Deleted line 9:
Changed lines 9-14 from:
These codes are essentially similar to (but have been optimized to be faster than) those used in our paper "Community structure in time-dependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.-P. Onnela, ''Science'' '''328''', 876-878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876|definitive version]] of this paper is freely available via referring links on Mucha's "[[http://mucha.web.unc.edu/networks/|networks]]" page.
to:
The functions @@genlouvain.m@@ with a default parameter choice are essentially similar to (but have been optimized to be faster than) the code used in our paper "Community structure in time-dependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.-P. Onnela, ''Science'' '''328''', 876-878 (2010). (The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876|definitive version]] of this paper is freely available via referring links on Mucha's "[[http://mucha.web.unc.edu/networks/|networks]]" page.) However, some of the GenLouvain versions contain additional important features:

* Version 1.2: only speed improvement
* Version 2.0: speed improvement over 1.2 and randomisation option 'moverand' in @@genlouvain.m@@ (helpful in a multilayer setting)
* Version 2.1: speed improvement over 2.0, additional randomisation option 'moverandw' in @@genlouvain.m@@ (helpful in a multilayer setting), additional main function @@iterated_genlouvain.m@@ that produces better output partitions in a multilayer setting when used with the recommended input options, and a "HelperFunctions" folder with many useful functions for a multilayer setting

Changed line 11 from:
The development of these codes was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project), and an EPSRC CASE studentship (Jeub). Additional thanks go to our users whose experiences have helped improve this code, especially Dani Bassett, Marya Bazzi, Jesse Blocher, Mason Porter and Simi Wang.
to:
The development of these codes was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project), and two EPSRC CASE studentships (Jeub and Bazzi). Additional thanks go to our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, Mason Porter and Simi Wang.
November 29, 2016, at 03:53 PM by Lucas G S Jeub - Add links to old versions
Added lines 4-7:

Previous versions:
* Version 2.0 (July 2014):  [[(Attach:)GenLouvain2.0.zip]]
* Version 1.2 (July 2012): [[(Attach:)GenLouvain1.2.zip]]
November 29, 2016, at 03:44 PM by Lucas G S Jeub - Update package file
Changed line 3 from:
The most recent package file is [[(Attach:)GenLouvain2.0.zip]]. Please see the @@README@@ file there. For ongoing development and pre-release versions see the  [[https://github.com/GenLouvain/GenLouvain|GitHub]] page.
to:
The most recent package file is [[(Attach:)GenLouvain2.1.zip]]. Please see the @@README@@ file there. For ongoing development and pre-release versions see the  [[https://github.com/GenLouvain/GenLouvain|GitHub]] page.
November 29, 2016, at 12:26 PM by Lucas G S Jeub - Add pointer to GitHub page
Changed line 3 from:
The most recent package file is [[(Attach:)GenLouvain2.0.zip]]. Please see the @@README@@ file there.
to:
The most recent package file is [[(Attach:)GenLouvain2.0.zip]]. Please see the @@README@@ file there. For ongoing development and pre-release versions see the  [[https://github.com/GenLouvain/GenLouvain|GitHub]] page.
Changed lines 40-41 from:
!!!Example 2: Ordered Multislice Matrix
to:
!!!Example 2: Ordered Multislice Network
Changed line 96 from:
!!!Example 3: Categorical Multislice Matrix
to:
!!!Example 3: Categorical Multislice Network
Changed lines 9-10 from:
Please also note that [[http://perso.uclouvain.be/vincent.traag/|Vincent Traag]] has released his [[https://launchpad.net/louvain|Louvain Community Detection]] software with a variety of options, including multislice contributions. I am very hopeful that new and efficient codes will soon be released by [[http://www.springerlink.com/content/w041065h32733022/|Giuseppe Mangioni and his collaborators]]. I also hear from Bruce Rogers that he is developing an R code for multislice community detection.
to:
Please also note that [[http://perso.uclouvain.be/vincent.traag/|Vincent Traag]] has released his [[https://launchpad.net/louvain|Louvain Community Detection]] software with a variety of options, including multislice contributions. I am very hopeful that new and efficient codes will soon be released by [[http://www.springerlink.com/content/w041065h32733022/|Giuseppe Mangioni and his collaborators]].

Please note that the examples below do not represent all possible uses of this generalized Louvain code. The intention of the "generalized" part here is that the code itself can in principle be used for any community
detection problem that can be cast as a quality function summing over B(i,j) elements for i and j in the same community. The examples below are just some simple, clean situations wherein that might happen. As an example of a more general setting with nodes coming and going in the temporal network, consider the temporal roll call proof-of-concept in our paper.

Please pay attention to the different options below, particularly the use of function handles for larger networks. For very large networks with many layers, it may be possible to even make the outputs of these B(i) function calls as sparse; but such sparse B(i) do not appear to be compatible with the latest combinations of our code and the way we have it implemented in MATLAB
.
Changed line 144 from:
B = @(i) sparse(AA(:,i) - gamma*kcell{ceil(i/(N+eps))}*kvec(i));
to:
B = @(i) AA(:,i) - gamma*kcell{ceil(i/(N+eps))}*kvec(i);
Changed line 160 from:
B=sparse(N,N);
to:
B=zeros(N,N);
August 04, 2015, at 10:29 AM by PJM - fixed publications link
Changed line 5 from:
These codes are essentially similar to (but have been optimized to be faster than) those used in our paper "Community structure in time-dependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.-P. Onnela, ''Science'' '''328''', 876-878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876|definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubs.html#multislice|publications]]" page.
to:
These codes are essentially similar to (but have been optimized to be faster than) those used in our paper "Community structure in time-dependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.-P. Onnela, ''Science'' '''328''', 876-878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876|definitive version]] of this paper is freely available via referring links on Mucha's "[[http://mucha.web.unc.edu/networks/|networks]]" page.
Changed line 145 from:
!!!Bipartite Networks
to:
!!!Example 4: Bipartite Network
Changed lines 147-148 from:
Code for bipartite networks is available upon request.
to:
Represent the network by an m-by-n adjacency matrix A between the two types (of m and n nodes, respectively).

[@
[m,n]=size(A);
N=m+n;
k=sum(A,2);
d=sum(A,1);
mm=sum(k);
B1=A-gamma*k*d/mm;
B=sparse(N,N);
B(1:m,m+1:N)=B1;
B(m+1:N,1:m)=B1';
@]


Deleted lines 164-165:

Coming later, including...
July 29, 2014, at 01:29 PM by Lucas Jeub - Uploaded GenLouvain2.0
Changed lines 3-4 from:
The most recent package file is [[(Attach:)GenLouvain1.2.zip]]. Please see the @@README@@ file there.
to:
The most recent package file is [[(Attach:)GenLouvain2.0.zip]]. Please see the @@README@@ file there.
Changed lines 7-8 from:
The development of these codes was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project), and an EPSRC CASE studentship (Jeub). Additional thanks go to our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, Mason Porter and Simi Wang.
to:
The development of these codes was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project), and an EPSRC CASE studentship (Jeub). Additional thanks go to our users whose experiences have helped improve this code, especially Dani Bassett, Marya Bazzi, Jesse Blocher, Mason Porter and Simi Wang.
Changed line 54 from:
[S,Q] = genlouvainmex(B);
to:
[S,Q] = genlouvain(B);
Changed line 87 from:
[S,Q] = genlouvainmex(B);
to:
[S,Q] = genlouvain(B);
Changed line 111 from:
[S,Q] = genlouvainmex(B);
to:
[S,Q] = genlouvain(B);
Changed line 141 from:
[S,Q] = genlouvainmex(B);
to:
[S,Q] = genlouvain(B);
Changed line 157 from:
[[(Attach:)spectral23.m]] provides various options for spectral bipartitioning and tripartitioning to optimize modularity. If you use this code, please cite T. Richardson, P. J. Mucha, and M. A. Porter, "Spectral tripartitioning of networks," ''Physical Review E'' '''80''', 036111 (2009).
to:
[[(Attach:)spectral23.m]] provides various options for spectral bipartitioning and tripartitioning to optimize modularity. If you use this code, please cite T. Richardson, P. J. Mucha, and M. A. Porter, "Spectral tripartitioning of networks," ''Physical Review E'' '''80''', 036111 (2009). Please also be sure that you understand that nothing about this code has been optimized for speed; rather, it was designed for proof of concept.
Changed lines 145-155 from:
!!!Example 4: Bipartite Network

Coming soon
...

!!!!Example 4a: Ordered Bipartite Slices

Lucas has some code specific to this case that we will post here in the not too distant future.

!!!Other Examples

''I am happy to continue to post other examples here if people find them helpful. Let me know what situations you would like to see included here.''
to:
!!!Bipartite Networks

Code for bipartite networks is available upon request
.
Added lines 144-151:

!!!Example 4: Bipartite Network

Coming soon...

!!!!Example 4a: Ordered Bipartite Slices

Lucas has some code specific to this case that we will post here in the not too distant future.
Deleted lines 0-1:
'''''An updated version of this code is in testing, with documentation and examples. As soon as it is available, it will be posted to this site for public use.'''''
Changed line 9 from:
The development of these codes was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project), and an EPSRC CASE studentship (Jeub). Additional thanks go to all of our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, Mason Porter and Simi Wang.
to:
The development of these codes was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project), and an EPSRC CASE studentship (Jeub). Additional thanks go to our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, Mason Porter and Simi Wang.
Changed line 161 from:
[[(Attach:)klnb.m]]...
to:
[[(Attach:)klnb.m]] is our implementation of Newman's description of Kernighan-Lin node-swapping steps for improving modularity.
Changed lines 159-161 from:
[[(Attach:)klnb.m]]

[[(Attach:)spectral23
.m]]
to:
[[(Attach:)spectral23.m]] provides various options for spectral bipartitioning and tripartitioning to optimize modularity. If you use this code, please cite T. Richardson, P. J. Mucha, and M. A. Porter, "Spectral tripartitioning of networks," ''Physical Review E'' '''80''', 036111 (2009).

[[(Attach:)klnb.m]]...
Changed line 3 from:
This "generalized Louvain" MATLAB code for community detection allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method, with the important distinction that the Louvain passes work directly with the modularity matrix, not the adjacency matrix. That is, the main @@genlouvain.m@@ code can be used with any quality function specified in terms of a modularity matrix; but as such it does not take advantage of any particular structure to those matrices (cf. the excellent [[http://sites.google.com/site/findcommunities/|findcommunities]] code).
to:
This "generalized Louvain" MATLAB code for community detection allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method, with the important distinction that the Louvain passes in the codes here work directly with the modularity matrix, not the adjacency matrix. That is, the main @@genlouvain.m@@ code can be used with any quality function specified in terms of a modularity matrix; but as such it does not take advantage of any particular structure to those matrices (cf. the excellent [[http://sites.google.com/site/findcommunities/|findcommunities]] code).
Changed line 143 from:
[S,Q] = genlouvainrand(B);
to:
[S,Q] = genlouvainmex(B);
Changed line 52 from:
   B(indx,indx)=A{s}-k'*k/twom;
to:
   B(indx,indx)=A{s}-gamma*k'*k/twom;
Changed lines 65-68 from:
!!!Example 3: Categorical Multislice Matrix

The distinction between ordered slices and categorical slices manifests in the call below by the presence of all-to-all identity arcs between slices (cf. the nearest-slice couplings in the above example):

to:
!!!!Example 2a: Larger Networks
Changed line 70 from:
B=spalloc(N*T,N*T,(N+T)*N*T);
to:
ii=[]; jj=[]; vv=[];
Added lines 73-75:
   indx=[1:N]'+(s-1)*N;
    [i,j,v]=find(A{s});
    ii=[ii;indx(i)]; jj=[jj;indx(j)]; vv=[vv;v];
Added line 77:
   kv=zeros(N*T,1);
Changed lines 80-81 from:
   indx=[1:N]+(s-1)*N;
    B(indx,indx)=A{s}-k'*k/twom;
to:
   kv(indx)=k/twom;
    kcell{s}=kv;
Changed lines 83-85 from:
twomu=twomu+T*omega*N*(T-1);
all2all = N*[(-T+1):-1,1:(T-1)];
B = B + omega*spdiags(ones(N*T,2*T-2),all2all,N*T,N*T);
to:
AA = sparse(ii,jj,vv,N*T,N*T);
clear ii jj vv
kvec = full
(sum(AA));
AA = AA + omega*spdiags(ones(N*T,2),[-N,N],N*T,N*T);
twomu=twomu+2*omega*N*(T-1);
B = @(i) AA(:,i) - gamma*kcell{ceil(i/(N+eps))}*kvec(i
);
Changed lines 94-97 from:

!!!Example 4: Multislice Function Handles

Coming Soon
to:
!!!Example 3: Categorical Multislice Matrix

The distinction between ordered slices and categorical slices manifests in the call below by the presence of all-to-all identity arcs between slices (cf. the nearest-slice couplings in the above example):

[@
N=length(A{1});
T=length(A);
B=spalloc(N*T,N*T,(N+T)*N*T);
twomu=0;
for s=1:T
    k=sum(A{s});
    twom=sum(k);
    twomu=twomu+twom;
    indx=[1:N]+(s-1)*N;
    B(indx,indx)=A{s}-gamma*k'*k/twom;
end
twomu=twomu+T*omega*N*(T-1);
all2all = N*[(-T+1):-1,1:(T-1)];
B = B + omega*spdiags(ones(N*T,2*T-2),all2all,N*T,N*T);
[S,Q] = genlouvainmex(B);
Q = Q/twomu
S = reshape(S,N,T);
@]

!!!!Example 3a: Larger Networks

[@
N=length(A{1});
T=length(A);
ii=[]; jj=[]; vv=[];
twomu=0;
for s=1:T
    indx=[1:N]'+(s-1)*N;
    [i,j,v]=find(A{s});
    ii=[ii;indx(i)]; jj=[jj;indx(j)]; vv=[vv;v];
    k=sum(A{s});
    kv=zeros(N*T,1);
    twom=sum(k);
    twomu=twomu+twom;
    kv(indx)=k/twom;
    kcell{s}=kv;
end
AA = sparse(ii,jj,vv,N*T,N*T);
clear ii jj vv
kvec = full(sum(AA));
all2all = N*[(-T+1):-1,1:(T-1)];
AA = AA + omega*spdiags(ones(N*T,2*T-2),all2all,N*T,N*T);
twomu=twomu+T*omega*N*(T-1);
B = @(i) sparse(AA(:,i) - gamma*kcell{ceil(i/(N+eps))}*kvec(i));
[S,Q] = genlouvainrand(B);
S = reshape(S,N,T);
@]
Added lines 109-110:

----
Changed lines 98-100 from:
!Related Codes
to:
----

!
!Related Codes
Changed lines 13-14 from:
!!!Example 1 -- Small Network
to:
!!!Example 1: Small Network
Changed lines 30-31 from:
!!!!Example 1a -- Larger Network
to:
!!!!Example 1a: Larger Network
Changed lines 38-39 from:
!!!Example 2 -- Ordered Multislice Matrix
to:
!!!Example 2: Ordered Multislice Matrix
Changed lines 65-66 from:
!!!Example 3 -- Categorical Multislice Matrix
to:
!!!Example 3: Categorical Multislice Matrix
Changed lines 90-91 from:
!!!Example 4
to:
!!!Example 4: Multislice Function Handles
Added lines 93-96:

!!!Other Examples

''I am happy to continue to post other examples here if people find them helpful. Let me know what situations you would like to see included here.''
Changed lines 38-39 from:
!!!!Example 2 -- Ordered Multislice Matrix
to:
!!!Example 2 -- Ordered Multislice Matrix
Changed lines 65-66 from:
!!!!Example 3 -- Categorical Multislice Matrix
to:
!!!Example 3 -- Categorical Multislice Matrix
Changed lines 90-91 from:
!!!!Example 4
to:
!!!Example 4
Changed lines 94-95 from:
!!Related Codes
to:
!Related Codes
Changed line 104 from:
!!!!License
to:
!!!License
Added line 16:
Added line 33:
Changed lines 38-40 from:
!!!!Example 2 -- Ordered Multislice

Define
the cell array A of square symmetric NxN matrices of equal size each representing one of the T ordered, undirected network "slices". After setting values for the resolution parameters @@gamma@@ and @@omega@@, the multislice modularity is calculated by
to:
!!!!Example 2 -- Ordered Multislice Matrix

Define
the cell array A of square symmetric NxN matrices of equal size each representing one of the T ordered, undirected network "slices". After setting values for the parameters @@gamma@@ and @@omega@@, the multislice modularity with nearest-slice identity arcs of equal strength @@omega@@ is calculated by
Changed lines 63-90 from:
!!!!Example 3 -- Categorical Multislice
to:
''It is important to stress here that multislice modularity is not limited to undirected network slices, nor does it require the same N nodes to be present in all slices; rather, these restrictions placed in this example are merely for the simplicity of the resulting function calls. For that matter, it does not require that ordered slices be connected by equal-valued nearest-slice couplings; but this is a simple way to treat ordered slices in the absence of other guidance. The multislice modularity methodology is as flexible as one's ability to cast the null models in terms of a quality function. No matter how many indices that quality function might have in its easiest-to-express form, it should be recast in terms of an equivalent modularity matrix B for input into @@genlouvain@@ codes.''

!!!!Example 3 -- Categorical Multislice Matrix

The distinction between ordered slices and categorical slices manifests in the call below by the presence of all-to-all identity arcs between slices (cf. the nearest-slice couplings in the above example):

[@
N=length(A{1});
T=length(A);
B=spalloc(N*T,N*T,(N+T)*N*T);
twomu=0;
for s=1:T
    k=sum(A{s});
    twom=sum(k);
    twomu=twomu+twom;
    indx=[1:N]+(s-1)*N;
    B(indx,indx)=A{s}-k'*k/twom;
end
twomu=twomu+T*omega*N*(T-1);
all2all = N*[(-T+1):-1,1:(T-1)];
B = B + omega*spdiags(ones(N*T,2*T-2),all2all,N*T,N*T);
[S,Q] = genlouvainmex(B);
Q = Q/twomu
S = reshape(S,N,T);
@]


!!!!Example 4
Changed line 15 from:
If you have an NxN adjacency matrix A representing an undirected network with N small enough that you can expect a fully dense NxN B matrix to fit in memory, the following commands will run @@genlouvain@@ for modularity at the default resolution (@@gamma = 1@@) and rescale modularity appropriately:
to:
Define the NxN adjacency matrix A representing an undirected network with N small enough that you can expect a fully dense NxN B matrix to fit in memory, the following commands will run @@genlouvain@@ for modularity at the default resolution (@@gamma = 1@@) and rescale modularity appropriately:
Changed lines 38-58 from:
Coming Soon
to:
Define the cell array A of square symmetric NxN matrices of equal size each representing one of the T ordered, undirected network "slices". After setting values for the resolution parameters @@gamma@@ and @@omega@@, the multislice modularity is calculated by
[@
N=length(A{1});
T=length(A);
B=spalloc(N*T,N*T,N*N*T+2*N*T);
twomu=0;
for s=1:T
    k=sum(A{s});
    twom=sum(k);
    twomu=twomu+twom;
    indx=[1:N]+(s-1)*N;
    B(indx,indx)=A{s}-k'*k/twom;
end
twomu=twomu+2*omega*N*(T-1);
B = B + omega*spdiags(ones(N*T,2),[-N,N],N*T,N*T);
[S,Q] = genlouvainmex(B);
Q = Q/twomu
S = reshape(S,N,T);
@]

Note that the last command conveniently reshapes the community assignment vector into an N (nodes) by T (slices) matrix so that the movement of identified nodes between communities can be easily tracked through the slices.
Changed lines 3-5 from:
This "generalized Louvain" MATLAB code for community detection allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method, with the important distinction that the Louvain passes work directly with the modularity matrix, not the adjacency matrix. That is, the main genlouvain.m code can be used with any quality function specified in terms of a modularity matrix; but as such it does not take advantage of any particular structure to those matrices (cf. the excellent [[http://sites.google.com/site/findcommunities/|findcommunities]] code).

The most recent package file is [[(Attach:)GenLouvain1.2.zip]].
to:
This "generalized Louvain" MATLAB code for community detection allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method, with the important distinction that the Louvain passes work directly with the modularity matrix, not the adjacency matrix. That is, the main @@genlouvain.m@@ code can be used with any quality function specified in terms of a modularity matrix; but as such it does not take advantage of any particular structure to those matrices (cf. the excellent [[http://sites.google.com/site/findcommunities/|findcommunities]] code).

The most recent package file is [[(Attach:)GenLouvain1.2.zip]]. Please see the @@README@@ file there.
Changed lines 13-15 from:
!!!!Example 1 -- Small Network

If you have an NxN adjacency matrix A with N small enough that you can expect a fully dense NxN B matrix to fit in memory, the following commands will run @@genlouvain@@ at the default resolution (@@gamma = 1@@) and rescale modularity appropriately:
to:
!!!Example 1 -- Small Network

If you have an NxN adjacency matrix A representing an undirected network with N small enough that you can expect a fully dense NxN B matrix to fit in memory, the following commands will run @@genlouvain@@ for modularity at the default resolution (@@gamma = 1@@) and rescale modularity appropriately:
Changed lines 27-28 from:
!!!!Example 2
to:
Again, the primary point of this code is if you have a different null model than that used in modularity for the standard network cases; but it nevertheless will work (albeit less efficiently) for such standard cases if you define B appropriately.

!!!!Example 1a -- Larger Network

If your adjacency matrix A is large enough that you cannot expect to fit a fully dense NxN B matrix into memory, then you need to define B as a function handle such that B(i) returns the ith column of the B matrix. For modularity of an undirected network with resolution parameter @@gamma@@, replace the B call in Example 1 above with the command
[@
B = @(i) A(:,i) - gamma*k'*k(i)/twom;
@]

!!!!Example
2 -- Ordered Multislice
Changed lines 40-44 from:
!!!!Related Codes
to:
!!!!Example 3 -- Categorical Multislice

Coming Soon

!!Related Codes
Changed lines 13-15 from:
!!!!Example 1

Coming Soon
to:
!!!!Example 1 -- Small Network

If you have an NxN adjacency matrix A with N small enough that you can expect a fully dense NxN B matrix to fit in memory, the following commands will run @@genlouvain@@ at the default resolution (@@gamma = 1@@) and rescale modularity appropriately:
[@
gamma = 1;
k = full(sum(A));
twom = sum(k);
B = full(A - gamma*k'*k/twom);
[S,Q] = genlouvain(B);
Q = Q/twom
@]

To force deterministic (cf. pseudorandom) results, see the documentation (@@help genlouvain@@) about how to set the 4th input appropriately, or directly reset the random stream yourself (e.g., @@reset(RandStream.getGlobalStream)@@ or @@reset(RandStream.getDefaultStream)@@, depending on your version of MATLAB).
Changed lines 9-11 from:
The development of these codes was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project), and an EPSRC CASE studentship (Jeub). Additional thanks go to all of our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, and Simi Wang.

Please also note that [[http://perso.uclouvain.be/vincent.traag/|Vincent Traag]] has released his [[https://launchpad.net/louvain|Louvain Community Detection]] software includes a variety of options, including multislice contributions. I am also very hopeful that new and efficient codes will soon be released by [[http://www.springerlink.com/content/w041065h32733022/|Giuseppe Mangioni and his collaborators]]. I hear from Bruce Rogers that he is developing an R code for multislice community detection.
to:
The development of these codes was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project), and an EPSRC CASE studentship (Jeub). Additional thanks go to all of our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, Mason Porter and Simi Wang.

Please also note that [[http://perso.uclouvain.be/vincent.traag/|Vincent Traag]] has released his [[https://launchpad.net/louvain|Louvain Community Detection]] software with a variety of options, including multislice contributions. I am very hopeful that new and efficient codes will soon be released by [[http://www.springerlink.com/content/w041065h32733022/|Giuseppe Mangioni and his collaborators]]. I also hear from Bruce Rogers that he is developing an R code for multislice community detection.
Added lines 15-16:
Coming Soon
Changed lines 19-23 from:
!!!!Related Codes (Coming Soon)
to:
Coming Soon

!!!!Related Codes

Coming later, including...
Changed line 3 from:
This "generalized Louvain" MATLAB code for community detection allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method, with the important distinction that the Louvain passes work directly with the modularity matrix, not the adjacency matrix. That is, the main codes (genlouvain.m, genlouvainrand.m, and genlouvainrand_dense.m) codes can be used with any quality function specified in terms of a modularity matrix; but as such it does not take advantage of any particular structure to those matrices (cf. the excellent [[http://sites.google.com/site/findcommunities/|findcommunities]] code).
to:
This "generalized Louvain" MATLAB code for community detection allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method, with the important distinction that the Louvain passes work directly with the modularity matrix, not the adjacency matrix. That is, the main genlouvain.m code can be used with any quality function specified in terms of a modularity matrix; but as such it does not take advantage of any particular structure to those matrices (cf. the excellent [[http://sites.google.com/site/findcommunities/|findcommunities]] code).
Changed lines 17-18 from:
!!!!Related Codes
to:
!!!!Related Codes (Coming Soon)
Added lines 20-23:

[[(Attach:)klnb.m]]

[[(Attach:)spectral23.m]]
Changed line 23 from:
All codes included in this directory are provided for broad use under the same terms as a "[[http://en.wikipedia.org/wiki/BSD_licenses#2-clause_license_.28.22Simplified_BSD_License.22_or_.22FreeBSD_License.22.29|FreeBSD License]]", with copyright holders and dates as indicated in individual files or directories.
to:
All codes included here are provided for broad use under the same terms as a "[[http://en.wikipedia.org/wiki/BSD_licenses#2-clause_license_.28.22Simplified_BSD_License.22_or_.22FreeBSD_License.22.29|FreeBSD License]]", with copyright holders and dates as indicated in individual files or directories.
Changed lines 19-23 from:
[[(Attach:)zrand.m]] calculates the z-Rand score and Variation of Information distance between a pair of partitions. If you use this code, please cite Amanda L. Traud, Eric D. Kelsic, Peter J. Mucha, and Mason A. Porter, "Comparing Community Structure to Characteristics in Online Collegiate Social Networks," ''SIAM Review'' '''53''', 526-543 (2011).
to:
[[(Attach:)zrand.m]] calculates the z-Rand score and Variation of Information distance between a pair of partitions. If you use this code, please cite Amanda L. Traud, Eric D. Kelsic, Peter J. Mucha, and Mason A. Porter, "Comparing Community Structure to Characteristics in Online Collegiate Social Networks," ''SIAM Review'' '''53''', 526-543 (2011).

!!!!License

All codes included in this directory are provided for broad use under the same terms as a "[[http://en.wikipedia.org/wiki/BSD_licenses#2-clause_license_.28.22Simplified_BSD_License.22_or_.22FreeBSD_License.22.29|FreeBSD License]]", with copyright holders and dates as indicated in individual files or directories
.
Changed line 19 from:
[[(Attach:)zrand.m]] calculates the z-Rand score and Variation of Information distance between a pair of partitions. If you use this code, please cite Amanda L. Traud, Eric D. Kelsic, Peter J. Mucha, and Mason A. Porter, "Comparing Community Structure to Characteristics in Online Collegiate Social Networks," '''SIAM Review''' ''53'', 526-543 (2011).
to:
[[(Attach:)zrand.m]] calculates the z-Rand score and Variation of Information distance between a pair of partitions. If you use this code, please cite Amanda L. Traud, Eric D. Kelsic, Peter J. Mucha, and Mason A. Porter, "Comparing Community Structure to Characteristics in Online Collegiate Social Networks," ''SIAM Review'' '''53''', 526-543 (2011).
Changed line 19 from:
[[(Attach:)zrand.m]] calculates the z-Rand score and Variation of Information distance between a pair of partitions. If you use this code, please cite A. L. Traud, (2011).
to:
[[(Attach:)zrand.m]] calculates the z-Rand score and Variation of Information distance between a pair of partitions. If you use this code, please cite Amanda L. Traud, Eric D. Kelsic, Peter J. Mucha, and Mason A. Porter, "Comparing Community Structure to Characteristics in Online Collegiate Social Networks," '''SIAM Review''' ''53'', 526-543 (2011).
Changed line 5 from:
The most recent package file is GenLouvain1.2.zip (see [[Release Notes]]).
to:
The most recent package file is [[(Attach:)GenLouvain1.2.zip]].
Changed lines 3-4 from:
This "generalized Louvain" MATLAB code for community detection allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method, with the important distinction that the Louvain passes work directly with the modularity matrix, not the adjacency matrix. That is, the main genlouvain.m (and genlouvainrand.m) codes can be used with any quality function specified in terms of a modularity matrix; but as such it does not take advantage of any particular structure to those matrices (cf. the excellent [[http://sites.google.com/site/findcommunities/|findcommunities]] code).
to:
This "generalized Louvain" MATLAB code for community detection allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method, with the important distinction that the Louvain passes work directly with the modularity matrix, not the adjacency matrix. That is, the main codes (genlouvain.m, genlouvainrand.m, and genlouvainrand_dense.m) codes can be used with any quality function specified in terms of a modularity matrix; but as such it does not take advantage of any particular structure to those matrices (cf. the excellent [[http://sites.google.com/site/findcommunities/|findcommunities]] code).
Changed lines 9-12 from:
These codes remain under development. We will continue to try to improve these codes, so would appreciate any comments or experiences that you have with them.

The development of this distribution
was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project), and an EPSRC CASE studentship (Jeub). Additional thanks go to all of our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, and Simi Wang.
to:
The development of these codes was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project), and an EPSRC CASE studentship (Jeub). Additional thanks go to all of our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, and Simi Wang.
Changed lines 13-115 from:
----

 genlouvain  Louvain-like community detection, specified quality function.
    Version 1.2pre (June 5, 2012).
 
    [S,Q] = genlouvain(B) with B a matrix implements a Louvain-like greedy
    community detection method using the modularity/quality matrix B which
    encodes the quality function Q obtained by summing over all elements
    B(i,j) such that nodes i and j are placed in the same community.
    Following Blondel et al. 2008, the algorithm proceeds in two phases
    repeated iteratively: quality is optimized by moving one node at a
    time until no such moves improve quality; the communities found to that
    point are then aggregated to build a new network where each node
    represents a community.  The output vector S encodes the obtained
    community assignments, with S(i) identifying the community to which
    node i has been assigned.  The output Q gives the quality of the
    resulting partition of the network.
 
    [S,Q] = genlouvain(B) with B a function handle such that B(i) returns
    the ith column of the modularity/quality matrix uses this function
    handle (to reduce the memory footprint for large networks) until the
    number of groups is less than 10000 and then builds the B matrix
    corresponding to the new aggregated network in subsequent passes. Use
    [S,Q] = genlouvain(B,limit) to change this default=10000 limit.
 
    Example
          k = full(sum(A));
          twom = sum(k);
          B = @(v) A(:,v) - k'*k(v)/twom;
          [S,Q] = genlouvain(B);
          Q = Q/twom;
      finds community assignments for the undirected network encoded by the
      symmetric adjacency matrix A.  For small networks, one may obtain
      reasonably efficient results even more simply by handling the full
      modularity/quality matrix
          B = A - k'*k/twom;
      instead of the function handle.  Intended use also includes the
      "multislice" network quality function of Mucha et al. 2010, where B
      is built in the multislice wrapper codes listed below.
 
    See also
        non-randperm version:      genlouvain
        other heuristics:          SPECTRAL23
        Kernighan-Lin improvement:  KLNB
        Multislice wrapper:        multibuild, MULTIBUILDF
 
    Notes:
      The matrix B is assumed to be both symmetric and square.  This
      assumption is not checked here.
 
      This algorithm is only "Louvain-like" in the sense that the two
      phases are used iteratively in the same manner as in the Louvain
      algorithm (Blondel et al. 2008).  Because it operates on a general
      quality/modularity matrix B, it does not include any analytical
      formulas for quickly identifying the change in modularity from a
      proposed move nor any improved efficiency obtained by their use.
 
      Past versions had a problem where accumulated subtraction error might
      lead to an infinite loop with each pass oscillating between two or
      more partitions yet incorrectly identifying increases in quality.  We
      believe this problem has been ameliorated by the 1*eps terms in lines
      168 and 238.  If you encounter this problem in your use, try
      different multipliers and please notify Peter Mucha (mucha@unc.edu).
 
      The output Q provides the sum over the appropriate elements of B
      without any rescaling.  As such, the example above rescales the
      Q output by genlouvain by 2m = sum(k) so that Q <= 1.  In contrast,
      the MULTIBUILD wrapper includes standard rescaling directly in B.
 
      The '~' for ignoring function returns (used for "max" below) are not
      supported prior to R2009b. Replace with 'dummy' for earlier versions.
 
      By using this code, the user implicitly acknowledges that the authors
      accept no liability associated with that use.  (What are you doing
      with it anyway that might cause there to be a potential liability?!?)
 
    References:
      Blondel, Vincent D., Jean-Loup Guillaume, Renaud Lambiotte, and
      Etienne Lefebvre, "Fast unfolding of communities in large networks,"
      Journal of Statistical Mechanics: Theory and Experiment, P10008
      (2008).
 
      Fortunato, Santo, "Community detection in graphs," Physics Reports
      486, 75-174 (2010).
 
      Mucha, Peter J., Thomas Richardson, Kevin Macon, Mason A. Porter, and
      Jukka-Pekka Onnela. "Community Structure in Time-Dependent,
      Multiscale, and Multiplex Networks," Science 328, 876-878 (2010).
 
      Porter, M. A., J. P. Onnela, and P. J. Mucha, "Communities in
      networks," Notices of the American Mathematical Society 56, 1082-1097
      & 1164-1166 (2009).
 
    Acknowledgments:
      A special thank you to Stephen Reid, whose greedy.m code was the
      original version that has over time developed into the present code.
      Thank you also to Dani Bassett, Jesse Blocher, and Simi Wang for
      inspiring improvements to the code.
 
    Citation: If you use this code, please cite as
        Inderjit S. Jutla, Lucas G. S. Jeub, and Peter J. Mucha,
        "A generalized Louvain method for community detection implemented
        in MATLAB," http://netwiki.amath.unc.edu/GenLouvain (2011-2012).
to:
!!!!Example 1

!!!!Example 2

!!!!Related Codes

[[(Attach:)zrand.m]] calculates the z-Rand score and Variation of Information distance between a pair of partitions. If you use this code, please cite A. L. Traud,  (2011).
Changed line 7 from:
These codes are essentially similar to (but have been optimized to be faster than) those used in our paper "Community structure in time-dependent, multiscale, and multiplex networks", P.&nbsp;J.&nbsp;Mucha, T.&nbsp;Richardson, K.&nbsp;Macon, M.&nbsp;A.&nbsp;Porter and J.-P.&nbsp;Onnela, ''Science'' '''328''', 876-878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876|definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubareas.html#multislice|by research area]]" page.
to:
These codes are essentially similar to (but have been optimized to be faster than) those used in our paper "Community structure in time-dependent, multiscale, and multiplex networks", P.&nbsp;J.&nbsp;Mucha, T.&nbsp;Richardson, K.&nbsp;Macon, M.&nbsp;A.&nbsp;Porter and J.-P.&nbsp;Onnela, ''Science'' '''328''', 876-878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876|definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubs.html#multislice|publications]]" page.
Changed line 13 from:
Please also note that [[http://perso.uclouvain.be/vincent.traag/|Vincent Traag]] has released his [[https://launchpad.net/louvain|Louvain Community Detection]] software includes a variety of options, including multislice contributions. I am also very hopeful that new and efficient codes will soon be released by [[http://www.springerlink.com/content/w041065h32733022/|Giuseppe Mangioni and his collaborators]].
to:
Please also note that [[http://perso.uclouvain.be/vincent.traag/|Vincent Traag]] has released his [[https://launchpad.net/louvain|Louvain Community Detection]] software includes a variety of options, including multislice contributions. I am also very hopeful that new and efficient codes will soon be released by [[http://www.springerlink.com/content/w041065h32733022/|Giuseppe Mangioni and his collaborators]]. I hear from Bruce Rogers that he is developing an R code for multislice community detection.
Changed line 11 from:
The development of this distribution was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project) and later by NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project). Additional thanks go to all of our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, and Simi Wang.
to:
The development of this distribution was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project), and an EPSRC CASE studentship (Jeub). Additional thanks go to all of our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, and Simi Wang.
Changed lines 1-10 from:
We now have available a preliminary version of our "generalized Louvain" MATLAB code for community detection that is appropriate for wider distribution. This code allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method, with the important distinction that the Louvain passes work directly with the modularity matrix, not the adjacency matrix. That is, the main genlouvain.m (and genlouvainrand.m) codes can be used with any quality function specified in terms of a modularity matrix; but as such it does not take advantage of any particular structure to those matrices (cf. the excellent [[http://sites.google.com/site/findcommunities/|findcommunities]] code).

The most recent package file is GenLouvain0.99.zip, but more recent versions of individual
.m files are also available in the development of Version 1.00 (see [[Release Notes]]).

In particular, these codes are essentially similar
to those used in our paper "Community structure in time-dependent, multiscale, and multiplex networks", P.&nbsp;J.&nbsp;Mucha, T.&nbsp;Richardson, K.&nbsp;Macon, M.&nbsp;A.&nbsp;Porter and J.-P.&nbsp;Onnela, ''Science'' '''328''', 876-878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876|definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubareas.html#multislice|by research area]]" page.

Tese codes remain under development. For instance, there are clearly still some memory leaks, and the constraint of only taking one pass with function handles described in the documentation is very limiting. We will continue to try to improve these codes, so would appreciate any comments or experiences that you have with them.

If you are interested in obtaining access to this code, please email Peter Mucha
.
to:
'''''An updated version of this code is in testing, with documentation and examples. As soon as it is available, it will be posted to this site for public use.'''''

This "generalized Louvain" MATLAB code for community detection allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method, with the important distinction that the Louvain passes work directly with the modularity matrix, not the adjacency matrix. That is, the main genlouvain.m (and genlouvainrand.m) codes can be used with any quality function specified in terms
of a modularity matrix; but as such it does not take advantage of any particular structure to those matrices (cf. the excellent [[http://sites.google.com/site/findcommunities/|findcommunities]] code).

The most recent package file is GenLouvain1.2.zip (see [[Release Notes]])
.

These codes are essentially similar to (but have been optimized
to be faster than) those used in our paper "Community structure in time-dependent, multiscale, and multiplex networks", P.&nbsp;J.&nbsp;Mucha, T.&nbsp;Richardson, K.&nbsp;Macon, M.&nbsp;A.&nbsp;Porter and J.-P.&nbsp;Onnela, ''Science'' '''328''', 876-878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876|definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubareas.html#multislice|by research area]]" page.

These codes remain under development. We will continue to try to improve these codes, so would appreciate any comments or experiences that you have with them.
Deleted lines 14-15:
'''''A new version with important contributions by Lucas Jeub that greatly speed up and broaden the application of this code is coming soon.'''''
Changed lines 17-18 from:
 GENLOUVAIN  Louvain-like community detection, specified quality function.
    Version 1.00, January 5, 2012.
to:
 genlouvain  Louvain-like community detection, specified quality function.
    Version 1.2pre (June 5, 2012).
Changed line 20 from:
   [S,Q] = GENLOUVAIN(B) with B a matrix implements a Louvain-like greedy
to:
   [S,Q] = genlouvain(B) with B a matrix implements a Louvain-like greedy
Changed lines 33-36 from:
   [S,Q] = GENLOUVAIN(B) with B a function handle such that B(i) returns
    the ith column of the modularity/quality matrix uses this function for
   the first pass of the algorithm and then builds the B matrix
    corresponding to the new aggregated network in subsequent passes.
to:
   [S,Q] = genlouvain(B) with B a function handle such that B(i) returns
    the ith column of the modularity/quality matrix uses this function
   handle (to reduce the memory footprint for large networks) until the
    number of groups is less than 10000 and then builds the B matrix
    corresponding to the new aggregated network in subsequent
passes. Use
    [S,Q] = genlouvain(B,limit) to change this default=10000 limit
.
Changed line 56 from:
       randperm-enabled version:  genlouvainrand
to:
       non-randperm version:     genlouvain
Changed line 59 from:
       Multislice wrappers:        multiord, multiordf, multicat, multicatf
to:
       Multislice wrapper:         multibuild, MULTIBUILDF
Deleted lines 64-69:
     This version operates deterministically, considering nodes in their
      indexed order.  Because of the potentially large number of
      nearly-optimal partitions (Good et al. 2010), one is encouraged to
      investigate results of repeated applications from reindexing of the
      nodes or from the randperm-enabled version, GENLOUVAINRAND.
 
Changed lines 72-80 from:
     The current version takes only one pass through the two phases using
      the function handle, if provided; that is, the first pass through the
      community aggregation phase returns a quality matrix B which is then
     used in the subsequent pass.  Because the resulting matrix might not
     fit in RAM, the function returns in error if this second-pass graph
      is larger than 10,000 nodes at lines 159-162.  Such difficulty is
      particularly expected for highly-resolved partitions of small
      communities.  If you encounter this problem in your use, please
      contact
Peter Mucha (mucha@unc.edu).
to:
     Past versions had a problem where accumulated subtraction error might
 
    lead to an infinite loop with each pass oscillating between two or
 
    more partitions yet incorrectly identifying increases in quality.  We
 
  believe this problem has been ameliorated by the 1*eps terms in lines
 
  168 and 238.  If you encounter this problem in your use, try
 
    different multipliers and please notify Peter Mucha (mucha@unc.edu).
Deleted lines 78-85:
     This code has a known potential problem where accumulated subtraction
      error might lead to an infinite loop with each pass oscillating
      between two or more partitions yet incorrectly identifying increases
      in quality.  In many cases, this problem can be addressed by
      increasing the 1*eps term in line 144.  If you encounter this problem
      in your use, try different multipliers and please notify Peter Mucha
      (mucha@unc.edu).
 
Changed lines 81-82 from:
     Q output by genlouvain by 2m = sum(k) so that Q <= 1.
to:
     Q output by genlouvain by 2m = sum(k) so that Q <= 1.  In contrast,
      the MULTIBUILD wrapper includes standard rescaling directly in B
.
Added lines 84-86:
     The '~' for ignoring function returns (used for "max" below) are not
      supported prior to R2009b. Replace with 'dummy' for earlier versions.
 
Deleted lines 99-102:
     Good, Benjamin H., Yves-Alexandre de Montjoye, and Aaron Clauset,
      "Performance of modularity maximization in practical contexts,"
      Physical Review E 81, 046106 (2010).
 
Added lines 111-112:
     Thank you also to Dani Bassett, Jesse Blocher, and Simi Wang for
      inspiring improvements to the code.
Changed lines 115-117 from:
       Inderjit S. Jutla and Peter J. Mucha, "A generalized Louvain method
        for community detection implemented in MATLAB,"
 
    http://netwiki.amath.unc.edu/GenLouvain (2011-2012).
to:
        Inderjit S. Jutla, Lucas G. S. Jeub, and Peter J. Mucha,
         "A generalized Louvain method for community detection implemented
         in MATLAB," http://netwiki.amath.unc.edu/GenLouvain (2011-2012).
Added lines 14-15:

'''''A new version with important contributions by Lucas Jeub that greatly speed up and broaden the application of this code is coming soon.'''''
Changed line 11 from:
The development of this distribution was supported at different times by NSF DMS-0645369 and NIGMS R21-GM099493. Additional thanks to all of our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, and Simi Wang.
to:
The development of this distribution was supported at different times by NSF DMS-0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project) and later by NIGMS R21-GM099493 (supporting Mucha's contributions of improving such codes as a specific aim of this project). Additional thanks go to all of our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, and Simi Wang.
Changed line 11 from:
The development of this distribution was supported at different times by NSF DMS-0645369 and NIGMS R21-GM099493. Additional thanks to all of our users whose experiences have helped improve this code, especially Jesse Blocher and Dani Bassett.
to:
The development of this distribution was supported at different times by NSF DMS-0645369 and NIGMS R21-GM099493. Additional thanks to all of our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, and Simi Wang.
Changed lines 7-8 from:
Please note that these codes remain under development. For instance, there are clearly still some memory leaks, and the constraint of only taking one pass with function handles described in the documentation is very limiting. We will continue to try to improve these codes, so would appreciate any comments or experiences that you have with them.
to:
Tese codes remain under development. For instance, there are clearly still some memory leaks, and the constraint of only taking one pass with function handles described in the documentation is very limiting. We will continue to try to improve these codes, so would appreciate any comments or experiences that you have with them.
Changed lines 11-15 from:
The development of this distribution was supported at different times by NSF DMS-0645369 and NIGMS R21-GM099493.

Note also that [[http://perso.uclouvain.be/vincent.traag/|Vincent Traag]] has released his [[https://launchpad.net/louvain|Louvain Community Detection]] software includes a variety of options, including multislice contributions
.

Additional thanks to all of our users whose experiences have helped improve this code, especially Jesse Blocher and Dani Bassett.
to:
The development of this distribution was supported at different times by NSF DMS-0645369 and NIGMS R21-GM099493. Additional thanks to all of our users whose experiences have helped improve this code, especially Jesse Blocher and Dani Bassett.

Please also note that [[http://perso.uclouvain.be/vincent.traag/|Vincent Traag]] has released his [[https://launchpad.net/louvain|Louvain Community Detection]] software includes a variety of options, including multislice contributions. I am also very hopeful that new and efficient codes will soon be released by [[http://www.springerlink.com/content/w041065h32733022/|Giuseppe Mangioni and his collaborators]].
Changed line 1 from:
We now have available a preliminary version of our "generalized Louvain" MATLAB code for community detection that is appropriate for wider distribution. This code allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method.
to:
We now have available a preliminary version of our "generalized Louvain" MATLAB code for community detection that is appropriate for wider distribution. This code allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method, with the important distinction that the Louvain passes work directly with the modularity matrix, not the adjacency matrix. That is, the main genlouvain.m (and genlouvainrand.m) codes can be used with any quality function specified in terms of a modularity matrix; but as such it does not take advantage of any particular structure to those matrices (cf. the excellent [[http://sites.google.com/site/findcommunities/|findcommunities]] code).
Changed line 92 from:
     increasing the 2*eps term in line 144.  If you encounter this problem
to:
     increasing the 1*eps term in line 144.  If you encounter this problem
Changed line 92 from:
     increasing the 1*eps term in line 144.  If you encounter this problem
to:
     increasing the 2*eps term in line 144.  If you encounter this problem
Added lines 14-15:

Additional thanks to all of our users whose experiences have helped improve this code, especially Jesse Blocher and Dani Bassett.
Changed line 18 from:
   Version 0.99, August 23, 2011.
to:
   Version 1.00, January 5, 2012.
Changed lines 55-56 from:
       other heuristics:          spectral23
        Kernighan-Lin improvement:  klnb
to:
       other heuristics:          SPECTRAL23
        Kernighan-Lin improvement:  KLNB
Changed lines 89-90 from:
     in quality.  We believe this problem has been ameliorated by the
     20000*eps terms in lines 144 and 205.  If you encounter this problem
to:
     in quality.  In many cases, this problem can be addressed by
     increasing the 1*eps term in line 144.  If you encounter this problem
Changed line 130 from:
       http://netwiki.amath.unc.edu/GenLouvain (2011).
to:
       http://netwiki.amath.unc.edu/GenLouvain (2011-2012).
Added lines 2-3:

The most recent package file is GenLouvain0.99.zip, but more recent versions of individual .m files are also available in the development of Version 1.00 (see [[Release Notes]]).
Added lines 10-11:

Note also that [[http://perso.uclouvain.be/vincent.traag/|Vincent Traag]] has released his [[https://launchpad.net/louvain|Louvain Community Detection]] software includes a variety of options, including multislice contributions.
Added lines 4-5:

Please note that these codes remain under development. For instance, there are clearly still some memory leaks, and the constraint of only taking one pass with function handles described in the documentation is very limiting. We will continue to try to improve these codes, so would appreciate any comments or experiences that you have with them.
Added lines 6-7:

The development of this distribution was supported at different times by NSF DMS-0645369 and NIGMS R21-GM099493.
Added lines 1-122:
We now have available a preliminary version of our "generalized Louvain" MATLAB code for community detection that is appropriate for wider distribution. This code allows the user to define a quality function in terms of a generalized-modularity null model framework and then follows a two-phase iterative procedure similar to the "Louvain" method.

In particular, these codes are essentially similar to those used in our paper "Community structure in time-dependent, multiscale, and multiplex networks", P.&nbsp;J.&nbsp;Mucha, T.&nbsp;Richardson, K.&nbsp;Macon, M.&nbsp;A.&nbsp;Porter and J.-P.&nbsp;Onnela, ''Science'' '''328''', 876-878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876|definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubareas.html#multislice|by research area]]" page.

If you are interested in obtaining access to this code, please email Peter Mucha.

----

 GENLOUVAIN  Louvain-like community detection, specified quality function.
    Version 0.99, August 23, 2011.
 
    [S,Q] = GENLOUVAIN(B) with B a matrix implements a Louvain-like greedy
    community detection method using the modularity/quality matrix B which
    encodes the quality function Q obtained by summing over all elements
    B(i,j) such that nodes i and j are placed in the same community.
    Following Blondel et al. 2008, the algorithm proceeds in two phases
    repeated iteratively: quality is optimized by moving one node at a
    time until no such moves improve quality; the communities found to that
    point are then aggregated to build a new network where each node
    represents a community.  The output vector S encodes the obtained
    community assignments, with S(i) identifying the community to which
    node i has been assigned.  The output Q gives the quality of the
    resulting partition of the network.
 
    [S,Q] = GENLOUVAIN(B) with B a function handle such that B(i) returns
    the ith column of the modularity/quality matrix uses this function for
    the first pass of the algorithm and then builds the B matrix
    corresponding to the new aggregated network in subsequent passes.
 
    Example
          k = full(sum(A));
          twom = sum(k);
          B = @(v) A(:,v) - k'*k(v)/twom;
          [S,Q] = genlouvain(B);
          Q = Q/twom;
      finds community assignments for the undirected network encoded by the
      symmetric adjacency matrix A.  For small networks, one may obtain
      reasonably efficient results even more simply by handling the full
      modularity/quality matrix
          B = A - k'*k/twom;
      instead of the function handle.  Intended use also includes the
      "multislice" network quality function of Mucha et al. 2010, where B
      is built in the multislice wrapper codes listed below.
 
    See also
        randperm-enabled version:  genlouvainrand
        other heuristics:          spectral23
        Kernighan-Lin improvement:  klnb
        Multislice wrappers:        multiord, multiordf, multicat, multicatf
 
    Notes:
      The matrix B is assumed to be both symmetric and square.  This
      assumption is not checked here.
 
      This version operates deterministically, considering nodes in their
      indexed order.  Because of the potentially large number of
      nearly-optimal partitions (Good et al. 2010), one is encouraged to
      investigate results of repeated applications from reindexing of the
      nodes or from the randperm-enabled version, GENLOUVAINRAND.
 
      This algorithm is only "Louvain-like" in the sense that the two
      phases are used iteratively in the same manner as in the Louvain
      algorithm (Blondel et al. 2008).  Because it operates on a general
      quality/modularity matrix B, it does not include any analytical
      formulas for quickly identifying the change in modularity from a
      proposed move nor any improved efficiency obtained by their use.
 
      The current version takes only one pass through the two phases using
      the function handle, if provided; that is, the first pass through the
      community aggregation phase returns a quality matrix B which is then
      used in the subsequent pass.  Because the resulting matrix might not
      fit in RAM, the function returns in error if this second-pass graph
      is larger than 10,000 nodes at lines 159-162.  Such difficulty is
      particularly expected for highly-resolved partitions of small
      communities.  If you encounter this problem in your use, please
      contact Peter Mucha (mucha@unc.edu).
 
      This code has a known potential problem where accumulated subtraction
      error might lead to an infinite loop with each pass oscillating
      between two or more partitions yet incorrectly identifying increases
      in quality.  We believe this problem has been ameliorated by the
      20000*eps terms in lines 144 and 205.  If you encounter this problem
      in your use, try different multipliers and please notify Peter Mucha
      (mucha@unc.edu).
 
      The output Q provides the sum over the appropriate elements of B
      without any rescaling.  As such, the example above rescales the
      Q output by genlouvain by 2m = sum(k) so that Q <= 1.
 
      By using this code, the user implicitly acknowledges that the authors
      accept no liability associated with that use.  (What are you doing
      with it anyway that might cause there to be a potential liability?!?)
 
    References:
      Blondel, Vincent D., Jean-Loup Guillaume, Renaud Lambiotte, and
      Etienne Lefebvre, "Fast unfolding of communities in large networks,"
      Journal of Statistical Mechanics: Theory and Experiment, P10008
      (2008).
 
      Fortunato, Santo, "Community detection in graphs," Physics Reports
      486, 75-174 (2010).
 
      Good, Benjamin H., Yves-Alexandre de Montjoye, and Aaron Clauset,
      "Performance of modularity maximization in practical contexts,"
      Physical Review E 81, 046106 (2010).
 
      Mucha, Peter J., Thomas Richardson, Kevin Macon, Mason A. Porter, and
      Jukka-Pekka Onnela. "Community Structure in Time-Dependent,
      Multiscale, and Multiplex Networks," Science 328, 876-878 (2010).
 
      Porter, M. A., J. P. Onnela, and P. J. Mucha, "Communities in
      networks," Notices of the American Mathematical Society 56, 1082-1097
      & 1164-1166 (2009).
 
    Acknowledgments:
      A special thank you to Stephen Reid, whose greedy.m code was the
      original version that has over time developed into the present code.
 
    Citation: If you use this code, please cite as
        Inderjit S. Jutla and Peter J. Mucha, "A generalized Louvain method
        for community detection implemented in MATLAB,"
        http://netwiki.amath.unc.edu/GenLouvain (2011).