Community Detection in Social Networks

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

Implementation period: Oct 2010

people communities

Technical details:
The implemented algorithm works as follows [1].

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

  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 in Q.
  9. If Q > BestQ then save the current decomposition of G as the best division in BestComps.
  10. 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

[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.


You should follow Follow @kjahanbakhsh me on Twitter.