A.I. & Optimization

Advanced Machine Learning, Data Mining, and Online Advertising Services

Community Detection: Girvan-Newman Algorithm



In this post we describe Girvan-Newman algorithm and an implementaton of it in Python.

Girvan-Newman Algorithm

We implemented Girvan-Newman algorithman for community detection problem back in 2010. See below for the algorithm description. You can also find the origimal paper describing the algorithm here: Community structure in social and biological networks.


1. BestQ = 0.
2. Read the input file (the crawled data) and build the corresponding weighted social graph G.
3. Compute the number of components of the graph G (init_ncomp).
4. Calculate the weighted version of edge-betweenness for all edges of the graph G.
5. Find the edge with the highest betweenness and remove it from G.
6. Compute the number of components in G after edge removal (ncomp).
7. If ncomp <= init_ncomp go to step 3.
8. Compute the modularity of the current version of Graph G and store it as Q.
9. If Q > BestQ then keep the current decomposition of the graph as the best division in BestComps.
10. If there is not any edge left in G return BestComps otherwise go to step 2.
      

Python Implementation

Our Python implemntation uses NetworkX & Matplolib libraries. You can clone the community detection source code from its github repository: community.

Also feel free to contact us at info@AIOptify.com if you have a question or want to report a bug.