About The Project

In this project we have implemented and evaluate three community detection algorithms.

• Louvain Algorithm
• Label Propagation Algorithm
• Girvan-Newman Algorithm

Students:

• Andreas Panayiotou
• Theodoros Kyriakou

Prerequisites

Below are shown the necessary python libraries to run the algorithms.

• NetworkX

  pip install networkx

• Matplotlib

  pip install matplotlib

• NumPy (Only for Louvain)

  pip install numpy

• scikit-learn (Used for evaluation measures)

  pip install scikit-learn

Usage

• Louvain Algorithm
  • You can change randomBool global variable to True for random visit sequence and set a random seed.

  python Louvain.py

• Label Propagation Algorithm
  • You can set the number of maximum iterations in ITERATIONS global variable.

  python LabelPropagation.py

• Girvan Newman Algorithm
  • You can set the value of centralityValue global variable. This value is used in the calculation of betweenness centrality. If its None use all nodes of the network. In case of large network you can set a number of nodes k (where k <= number of nodes) to find an approximation of betweenness centrality.

  python GirvanNewman.py

Output Samples

In this section you can see the output of each algorithm on Zachary's karate club Network.

Louvain Algorithm

Label Propagation Algorithm

Girvan Newman Algorithm