## Community Detection: Girvan-Newman Algorithm

Nov 21, 2014 by Kazem

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.