Girvan Newman Algorithm: Simpler Modularity Calculation
Cameron Miller is a junior Computer Science student at Southern Methodist University. His hobbies include video games and building computers.
Part 1 was completed by my partner Josh Ayodele https://medium.com/@jayodele/c3a48c8fc80c
Part 2— Our take on modularity calculation
I. Differences between standard calculation and our method
Modularity calculation is important for the community detection algorithm because it allows the algorithm to calculate connectivity. “Modularity is the degree to which a system’s components are made up of relatively independent components or parts which can be combined”. We took this definition and created our own calculation of modularity that isn’t the standard implementation.
To calculate modularity, we treated it as the number of incomplete paths over the number of complete paths. In attempting creation of a path between two nodes, if the path is unreachable, it is counted as an incomplete paths. If it is reachable it is counted as a complete path. In order to create incomplete paths, the algorithm removes the highest traversed edge in the graph and removes it. By repeating this process, the graph will slowly create increasingly traversed paths as the communities are becoming more distinct. Eventually the most traversed path will be the only path connecting two communities and be removed, completely separating the communities and creating incomplete paths.
II. Our implementation
We implemented this modularity by calling community detection and removing an edge until modularity reaches a value of .15 or lower. By using this method, the run time is marginally improved as it is much less calculation per call of the function.
To test our community detection algorithm, we used a dataset of college football games from Fall of 2000. This graph has 114 different teams playing with edges describing the other teams that they will play off against. By using community detection we will be able to see groupings of conferences within football teams. This is the resultant graph using this method.
This clearly defines 11 separate communities ,or conferences in this case, within the graph. There is also one team isolated from all other groupings meaning it is not a part of any conference in particular.
Part 3 was completed by my partner Rick Lattin. https://medium.com/@rlattin/girvan-newman-algorithm-simpler-modularity-calculation-6920fb3fdfff
