Community Detection

Emilio Ferrara (Professor of Computer Science at USC) & (HUmans | MAchines | Networks | Society) Lab


CONCLUDE (COmplex Network CLUster DEtection) is a fast community detection algorithm.

The strategy consists of three steps:

  1. (re)weight edges by using a particular random walker;
  2. calculate the distance between each pair of connected nodes;
  3. partition the network into communities so to optimize the weighted network modularity.

CONCLUDE is computationally efficient since its cost is near linear with respect to the number of edges in the network.

The adoption of this community detection method has been proved worthy in different contexts, such as for studying online social networks and biological networks.

The only term of usage of this algorithm is the following:

  • The corresponding papers are cited

Related Papers

Please cite this work if you use CONCLUDE.

CONCLUDE is an improved version of the algorithm presented in the following paper, you might cite too:

  • Generalized Louvain method for community detection in large networks.
    P De Meo, E Ferrara, G Fiumara, and A Provetti.
    ISDA ’11: Proceedings of the 11th International Conference on Intelligent Systems Design and Applications, 2011.

    Useful links: PDF | Arxiv | IEEE

Download CONCLUDE

You can download an early implementation of CONCLUDE from HERE.

USER GUIDE
**********

To launch the community detection algorithm type:

java -jar CONCLUDE.jar input-filename output-filename delimiter(optional) compute-weights-only(optional)

input-filename: the name of the file containing the edgelist representing the network

output-filename: the output filename

delimiter: this parameter is optional, default "\t" (tab-separated values); example of other options: "," (csv) or " " (space-separated values)

compute-weights-only: this parameter is optional; default: 0; setting to 1, the algorithm will compute just the weights of the edges, without clustering the network.

Example line commands:
  • java -jar CONCLUDE.jar facebook-links.txt partition-facebook-links.txt
This call will invoke CONCLUDE passing the input network file called facebook-links, prepared as an edgelist of tab-separated values.
  • java -Xmx4G -jar CONCLUDE.jar facebook-links.txt partition-facebook-links.txt
This call will invoke CONCLUDE asking the Java Virtual Machine to allocate 4G of memory to this process. This parameter is usually required because CONCLUDE is an in-memory execution algorithm which manages possibly very large matrices.
  • java -Xmx4G -jar CONCLUDE.jar facebook-links.txt partition-facebook-links.txt " "
This invokation is required for passing a "space-separated" edgelist.
  • java -Xmx4G -jar CONCLUDE.jar facebook-links.txt reweighted-facebook-links.txt "\t" 1
These options allow to execute only the first step of the algorithm in order to obtain a weighted network, without the clustering steps. Note that if you specify the compute the weights only, you have to pass the delimiter.

Visit REGULARITY AI for Consultancy & Expert Witness Services