Girvan Newman Algorithm: Simpler Modularity Calculation

Hi! My name is Rick Lattin, and I am a second-year Computer Science and Psychology student attending Southern Methodist University. Some of my hobbies include video games and film-making.

Part 1 and 2 were completed by my partners Cameron Miller and Josh Ayodele.

Part 1 Link: https://medium.com/@jayodele/c3a48c8fc80c

Part 2 Link: https://medium.com/@millerct/girvan-newman-algorithm-simpler-modularity-calculation-d0a237b4d278

Part 3 — Opposite removal

I. Girvan Newman Algorithm and Community Detection

In typical community detection algorithms, the algorithm loops through every path and finds the highest traversed edge and proceeds to remove it. When considering this we implemented the opposite methodology by removing the least traversed path. When doing this, a problem arose of it removing connections only traversed once between two nodes. This would do the opposite of what we desired causing the algorithm to have no purpose.

II. Removal of all edges above a threshold

When considering how we could continue with this method, by changing it to instead remove all edges until the highest traversed path until the most traversed path is above a certain threshold worked exactly as intended. By creating a minimum value of 10 traversals, the algorithm would continue removing edges of the highest value until the lowest traversed path is only traversed 10 times.

This is the resultant graph for this method.

This method will work only for medium and larger sized graphs, while it won’t work on smaller graphs because all paths in a smaller graphs possibly will have edges of traversals less than 10 passes inherently.