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/a10030093PostProcessing 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/a10030093PostProcessing Partitions to Identify Domains of Modularity Optimization]]".
Added lines 78:
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/a10030093PostProcessing 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]]
Changed lines 34 from:
The most recent package file is [[(Attach:)GenLouvain2.1.zip]]. Please see the @@README@@ file there. For ongoing development and prerelease versions see the [[https://github.com/GenLouvain/GenLouvainGitHub]] 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 (20112017).
The most recent package file is [[(Attach:)GenLouvain2.1.1.zip]] (February 2017). Please see the @@README@@ file there. For ongoing development and prerelease versions see the [[https://github.com/GenLouvain/GenLouvainGitHub]] page.
Added line 10:
* Version 2.1 (November 2016): [[(Attach:)GenLouvain2.1.1.zip]]
Changed lines 914 from:
These codes are essentially similar to (but have been optimized to be faster than) those used in our paper "Community structure in timedependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.P. Onnela, ''Science'' '''328''', 876878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876definitive 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 timedependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.P. Onnela, ''Science'' '''328''', 876878 (2010). (The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876definitive 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 DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21GM099493 (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 DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21GM099493 (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.
Added lines 47:
Previous versions: * Version 2.0 (July 2014): [[(Attach:)GenLouvain2.0.zip]] * Version 1.2 (July 2012): [[(Attach:)GenLouvain1.2.zip]]
Changed line 3 from:
The most recent package file is [[(Attach:)GenLouvain2.0.zip]]. Please see the @@README@@ file there. For ongoing development and prerelease versions see the [[https://github.com/GenLouvain/GenLouvainGitHub]] page.
to:
The most recent package file is [[(Attach:)GenLouvain2.1.zip]]. Please see the @@README@@ file there. For ongoing development and prerelease versions see the [[https://github.com/GenLouvain/GenLouvainGitHub]] 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 prerelease versions see the [[https://github.com/GenLouvain/GenLouvainGitHub]] page.
Changed lines 4041 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 910 from:
Please also note that [[http://perso.uclouvain.be/vincent.traag/Vincent Traag]] has released his [[https://launchpad.net/louvainLouvain 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/louvainLouvain 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 proofofconcept 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:
to:
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 timedependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.P. Onnela, ''Science'' '''328''', 876878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubs.html#multislicepublications]]" page.
to:
These codes are essentially similar to (but have been optimized to be faster than) those used in our paper "Community structure in timedependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.P. Onnela, ''Science'' '''328''', 876878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876definitive 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:
to:
!!!Example 4: Bipartite Network
Changed lines 147148 from:
Code for bipartite networks is available upon request.
to:
Represent the network by an mbyn 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=Agamma*k*d/mm; B=sparse(N,N); B(1:m,m+1:N)=B1; B(m+1:N,1:m)=B1'; @]
Deleted lines 164165:
Coming later, including...
Changed lines 34 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 78 from:
The development of these codes was supported at different times by NSF DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21GM099493 (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 DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21GM099493 (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:
Changed line 87 from:
[S,Q] = genlouvainmex(B);
to:
Changed line 111 from:
[S,Q] = genlouvainmex(B);
to:
Changed line 141 from:
[S,Q] = genlouvainmex(B);
to:
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 145155 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 144151:
!!!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 01:
'''''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 DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21GM099493 (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 DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21GM099493 (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:
to:
[[(Attach:)klnb.m]] is our implementation of Newman's description of KernighanLin nodeswapping steps for improving modularity.
Changed lines 159161 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 generalizedmodularity null model framework and then follows a twophase 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 generalizedmodularity null model framework and then follows a twophase 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 6568 from:
!!!Example 3: Categorical Multislice Matrix
The distinction between ordered slices and categorical slices manifests in the call below by the presence of alltoall identity arcs between slices (cf. the nearestslice 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:
Added lines 7375:
indx=[1:N]'+(s1)*N; [i,j,v]=find(A{s}); ii=[ii;indx(i)]; jj=[jj;indx(j)]; vv=[vv;v];
Added line 77:
Changed lines 8081 from:
indx=[1:N]+(s1)*N; B(indx,indx)=A{s}k'*k/twom;
to:
kv(indx)=k/twom; kcell{s}=kv;
Changed lines 8385 from:
twomu=twomu+T*omega*N*(T1);
all2all = N*[(T+1):1,1:(T1)];
B = B + omega*spdiags(ones(N*T,2*T2),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*(T1); B = @(i) AA(:,i)  gamma*kcell{ceil(i/(N+eps))}*kvec(i);
Changed lines 9497 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 alltoall identity arcs between slices (cf. the nearestslice 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]+(s1)*N; B(indx,indx)=A{s}gamma*k'*k/twom; end twomu=twomu+T*omega*N*(T1); all2all = N*[(T+1):1,1:(T1)]; B = B + omega*spdiags(ones(N*T,2*T2),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]'+(s1)*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:(T1)]; AA = AA + omega*spdiags(ones(N*T,2*T2),all2all,N*T,N*T); twomu=twomu+T*omega*N*(T1); B = @(i) sparse(AA(:,i)  gamma*kcell{ceil(i/(N+eps))}*kvec(i)); [S,Q] = genlouvainrand(B); S = reshape(S,N,T); @]
Changed lines 98100 from:
to:
Changed lines 1314 from:
!!!Example 1  Small Network
to:
!!!Example 1: Small Network
Changed lines 3031 from:
!!!!Example 1a  Larger Network
to:
!!!!Example 1a: Larger Network
Changed lines 3839 from:
!!!Example 2  Ordered Multislice Matrix
to:
!!!Example 2: Ordered Multislice Matrix
Changed lines 6566 from:
!!!Example 3  Categorical Multislice Matrix
to:
!!!Example 3: Categorical Multislice Matrix
Changed lines 9091 from:
to:
!!!Example 4: Multislice Function Handles
Added lines 9396:
!!!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 3839 from:
!!!!Example 2  Ordered Multislice Matrix
to:
!!!Example 2  Ordered Multislice Matrix
Changed lines 6566 from:
!!!!Example 3  Categorical Multislice Matrix
to:
!!!Example 3  Categorical Multislice Matrix
Changed lines 9091 from:
to:
Changed lines 9495 from:
to:
Changed line 104 from:
to:
Added line 16:
Added line 33:
Changed lines 3840 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 nearestslice identity arcs of equal strength @@omega@@ is calculated by
Changed lines 6390 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 equalvalued nearestslice 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 easiesttoexpress 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 alltoall identity arcs between slices (cf. the nearestslice 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]+(s1)*N; B(indx,indx)=A{s}k'*k/twom; end twomu=twomu+T*omega*N*(T1); all2all = N*[(T+1):1,1:(T1)]; B = B + omega*spdiags(ones(N*T,2*T2),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 3858 from:
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]+(s1)*N; B(indx,indx)=A{s}k'*k/twom; end twomu=twomu+2*omega*N*(T1); 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 35 from:
This "generalized Louvain" MATLAB code for community detection allows the user to define a quality function in terms of a generalizedmodularity null model framework and then follows a twophase 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 generalizedmodularity null model framework and then follows a twophase 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 1315 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 2728 from:
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 4044 from:
to:
!!!!Example 3  Categorical Multislice
Coming Soon
!!Related Codes
Changed lines 1315 from:
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 911 from:
The development of these codes was supported at different times by NSF DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21GM099493 (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/louvainLouvain 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 DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21GM099493 (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/louvainLouvain 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 1516:
Changed lines 1923 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 generalizedmodularity null model framework and then follows a twophase 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 generalizedmodularity null model framework and then follows a twophase 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 1718 from:
to:
!!!!Related Codes (Coming Soon)
Added lines 2023:
[[(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#2clause_license_.28.22Simplified_BSD_License.22_or_.22FreeBSD_License.22.29FreeBSD 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#2clause_license_.28.22Simplified_BSD_License.22_or_.22FreeBSD_License.22.29FreeBSD License]]", with copyright holders and dates as indicated in individual files or directories.
Changed lines 1923 from:
[[(Attach:)zrand.m]] calculates the zRand 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''', 526543 (2011).
to:
[[(Attach:)zrand.m]] calculates the zRand 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''', 526543 (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#2clause_license_.28.22Simplified_BSD_License.22_or_.22FreeBSD_License.22.29FreeBSD License]]", with copyright holders and dates as indicated in individual files or directories.
Changed line 19 from:
[[(Attach:)zrand.m]] calculates the zRand 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'', 526543 (2011).
to:
[[(Attach:)zrand.m]] calculates the zRand 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''', 526543 (2011).
Changed line 19 from:
[[(Attach:)zrand.m]] calculates the zRand 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 zRand 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'', 526543 (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 34 from:
This "generalized Louvain" MATLAB code for community detection allows the user to define a quality function in terms of a generalizedmodularity null model framework and then follows a twophase 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 generalizedmodularity null model framework and then follows a twophase 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 912 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 DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21GM099493 (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 DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21GM099493 (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 13115 from:

genlouvain Louvainlike community detection, specified quality function. Version 1.2pre (June 5, 2012). [S,Q] = genlouvain(B) with B a matrix implements a Louvainlike 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 nonrandperm version: genlouvain other heuristics: SPECTRAL23 KernighanLin 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 "Louvainlike" 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., JeanLoup 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, 75174 (2010). Mucha, Peter J., Thomas Richardson, Kevin Macon, Mason A. Porter, and JukkaPekka Onnela. "Community Structure in TimeDependent, Multiscale, and Multiplex Networks," Science 328, 876878 (2010). Porter, M. A., J. P. Onnela, and P. J. Mucha, "Communities in networks," Notices of the American Mathematical Society 56, 10821097 & 11641166 (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 (20112012).
to:
!!!!Example 1
!!!!Example 2
!!!!Related Codes
[[(Attach:)zrand.m]] calculates the zRand 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 timedependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.P. Onnela, ''Science'' '''328''', 876878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubareas.html#multisliceby 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 timedependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.P. Onnela, ''Science'' '''328''', 876878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubs.html#multislicepublications]]" page.
Changed line 13 from:
Please also note that [[http://perso.uclouvain.be/vincent.traag/Vincent Traag]] has released his [[https://launchpad.net/louvainLouvain 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/louvainLouvain 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 DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project) and later by NIGMS R21GM099493 (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 DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project), NIGMS R21GM099493 (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 110 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 generalizedmodularity null model framework and then follows a twophase 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 timedependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.P. Onnela, ''Science'' '''328''', 876878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubareas.html#multisliceby 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 generalizedmodularity null model framework and then follows a twophase 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 timedependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.P. Onnela, ''Science'' '''328''', 876878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubareas.html#multisliceby 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 1415:
'''''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 1718 from:
GENLOUVAIN Louvainlike community detection, specified quality function. Version 1.00, January 5, 2012.
to:
genlouvain Louvainlike 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 Louvainlike greedy
to:
[S,Q] = genlouvain(B) with B a matrix implements a Louvainlike greedy
Changed lines 3336 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:
randpermenabled version: genlouvainrand
to:
nonrandperm version: genlouvain
Changed line 59 from:
Multislice wrappers: multiord, multiordf, multicat, multicatf
to:
Multislice wrapper: multibuild, MULTIBUILDF
Deleted lines 6469:
This version operates deterministically, considering nodes in their indexed order. Because of the potentially large number of nearlyoptimal partitions (Good et al. 2010), one is encouraged to investigate results of repeated applications from reindexing of the nodes or from the randpermenabled version, GENLOUVAINRAND.
Changed lines 7280 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 secondpass graph
is larger than 10,000 nodes at lines 159162. Such difficulty is particularly expected for highlyresolved 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 7885:
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 8182 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 8486:
The '~' for ignoring function returns (used for "max" below) are not supported prior to R2009b. Replace with 'dummy' for earlier versions.
Deleted lines 99102:
Good, Benjamin H., YvesAlexandre de Montjoye, and Aaron Clauset, "Performance of modularity maximization in practical contexts," Physical Review E 81, 046106 (2010).
Added lines 111112:
Thank you also to Dani Bassett, Jesse Blocher, and Simi Wang for inspiring improvements to the code.
Changed lines 115117 from:
Inderjit S. Jutla and Peter J. Mucha, "A generalized Louvain method
for community detection implemented in MATLAB," http://netwiki.amath.unc.edu/GenLouvain (20112012).
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 (20112012).
Added lines 1415:
'''''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 DMS0645369 and NIGMS R21GM099493. 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 DMS0645369 (in particular in the form of supporting Jutla's Research Experiences for Undergraduates project) and later by NIGMS R21GM099493 (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 DMS0645369 and NIGMS R21GM099493. 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 DMS0645369 and NIGMS R21GM099493. Additional thanks to all of our users whose experiences have helped improve this code, especially Dani Bassett, Jesse Blocher, and Simi Wang.
Changed lines 78 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 1115 from:
The development of this distribution was supported at different times by NSF DMS0645369 and NIGMS R21GM099493.
Note also that [[http://perso.uclouvain.be/vincent.traag/Vincent Traag]] has released his [[https://launchpad.net/louvainLouvain 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 DMS0645369 and NIGMS R21GM099493. 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/louvainLouvain 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 generalizedmodularity null model framework and then follows a twophase 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 generalizedmodularity null model framework and then follows a twophase 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 1415:
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 5556 from:
other heuristics: spectral23
KernighanLin improvement: klnb
to:
other heuristics: SPECTRAL23 KernighanLin improvement: KLNB
Changed lines 8990 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 (20112012).
Added lines 23:
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 1011:
Note also that [[http://perso.uclouvain.be/vincent.traag/Vincent Traag]] has released his [[https://launchpad.net/louvainLouvain Community Detection]] software includes a variety of options, including multislice contributions.
Added lines 45:
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 67:
The development of this distribution was supported at different times by NSF DMS0645369 and NIGMS R21GM099493.
Added lines 1122:
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 generalizedmodularity null model framework and then follows a twophase iterative procedure similar to the "Louvain" method.
In particular, these codes are essentially similar to those used in our paper "Community structure in timedependent, multiscale, and multiplex networks", P. J. Mucha, T. Richardson, K. Macon, M. A. Porter and J.P. Onnela, ''Science'' '''328''', 876878 (2010). The [[http://www.sciencemag.org/cgi/content/abstract/328/5980/876definitive version]] of this paper is freely available via referring links on Mucha's "[[http://www.amath.unc.edu/Faculty/mucha/pubareas.html#multisliceby research area]]" page.
If you are interested in obtaining access to this code, please email Peter Mucha.

GENLOUVAIN Louvainlike community detection, specified quality function. Version 0.99, August 23, 2011. [S,Q] = GENLOUVAIN(B) with B a matrix implements a Louvainlike 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 randpermenabled version: genlouvainrand other heuristics: spectral23 KernighanLin 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 nearlyoptimal partitions (Good et al. 2010), one is encouraged to investigate results of repeated applications from reindexing of the nodes or from the randpermenabled version, GENLOUVAINRAND. This algorithm is only "Louvainlike" 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 secondpass graph is larger than 10,000 nodes at lines 159162. Such difficulty is particularly expected for highlyresolved 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., JeanLoup 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, 75174 (2010). Good, Benjamin H., YvesAlexandre 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 JukkaPekka Onnela. "Community Structure in TimeDependent, Multiscale, and Multiplex Networks," Science 328, 876878 (2010). Porter, M. A., J. P. Onnela, and P. J. Mucha, "Communities in networks," Notices of the American Mathematical Society 56, 10821097 & 11641166 (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).


