Back to home page
In this page, you'll find links to some codes that I or some collaborators have been developing:
Louvain method for optimising modularity
In a collaboration with V. Blondel, J.-L. Guillaume and E. Lefebvre, we have recently proposed a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection method in terms of computation time, e.g. analyzing a web graph of 118 million nodes and more than one billion links only takes a couple of hours on a standard desktop. The accuracy of our algorithm has also been successfully verified on ad-hoc and empirical networks. The code, which has been written by J.-L. Guillaume, is available on findcommunities.googlepages.com and the method described in our paper Fast unfolding of communities in large networks, V.D. Blondel, J.-L. Guillaume, R. Lambiotte and E. Lefebvre, J. Stat. Mech., (2008) P10008.
Optimising "generalised modularities"
In a collaboration with J.-C. Delvenne and M. Barahona, we have shown that the quality of the partition of a network can be quantified by the dynamical properties of a random walk on this network. By doing so, we have introduced a set of quality functions which naturally incorporate time as a resolution parameter and are related to the Hamiltonian formulation of modularity proposed by Reichardt and Bornholdt a few years ago. I have generalized two codes in order to optimise this sets of quantities and therefore uncover modules in networks with the desired resolution. The first code generalises a C implementation of Simulated Annealing developed by R. Guimera while the other code generalises the Louvain method described above and is based on a C++ implementation of J.-L. Guillaume. These two codes are available as a zip file and are described in a short report. The theoretical aspect of our work is described in Dynamics and Modular Structure in Networks by R. Lambiotte, J.-C. Delvenne and M. Barahona.
Alternatively, it is possible to optimise the stability R(t) as defined in our paper. To do so, one first needs to calculate the matrix X described (describing the flux of probability at equilibrium). Here are two simple matlab codes that perform this task for the normalized laplacian dynamics expmat.m and for the combinatorial laplacian dynamics expmatprime.m. These codes produce an edge list for the weighted graph X than can then be optimise by any modularity optimisation method.
Edge partitions for overlapping communities
In a collaboration with T.S. Evans, we propose to partition the edges of a graph in order to uncover overlapping communities of its nodes. Our approach is based on the construction of different types of weighted line graphs, i.e. graphs whose nodes are the edges of the original graph, that encapsulate differently the relations between the edges. Weighted line graphs provide an alternative, valuable representation of the system's topology, and have important applications in community detection, as the usual node partition of a line graph naturally leads to an edge partition of the original graph. This identification allows us to use traditional partitioning methods in order to address the long-standing problem of the detection of overlapping communities. A description of our work can be found in Line Graphs, Link Partitions and Overlapping Communities by T.S. Evans and R. Lambiotte, Phys. Rev. E 80, (2009) 016105. Codes to produce weighted line graphs and optimise their modularity can be found here.
Back to home page