Advanced Machine Learning, Data Mining, and Online Advertising Services
In this post we describe Girvan-Newman algorithm and an implementaton of it in Python.
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.
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.