**General description**: We have implemented the Girvan-Newman community detection algorithm for weighted graphs in Python.

**Implementation period**: Oct 2010

**Technical details**:

The implemented algorithm works as follows [1].

Girvan-Newman Alg (Input: A weighted graph G, Output: A list of components of G.)

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

***** You can download the source code for community detection from its github repository: community**.

Language: Python

No of lines: 184

Used data structures: Graphs

Used libraries: Python NetworkX & Python Matplolib

**Refs**:

[1] M. Girvan and M. E. J. Newman, Community structure in social and biological networks, Proceedings of the National Academy of Sciences of the United States of America, p.p. 7821--7826, vol. 99, June 2002.

Tweet

You should follow Follow @kjahanbakhsh me on Twitter.