Code Implementation

Today, Christina, Jennifer, and I met to work together on implementing the metrics in the Louvain algorithm.

Jennifer and I worked on the silhouette index. We began by discussing the psuedo code that I wrote up recently and identifying the first few tasks we needed to accomplish in order to implement this metric. We realized that an important part of calculating the silhouette index involves solving the all pairs shortest path graph problem. Conveniently, we just had a lecture on this topic in our algorithms class this week, so we knew that the Floyd Warshall algorithm could help us solve our problem.

After discussing where to implement this in our code, we decided to have it as a function that we could call at the start of every pass of the Louvain algorithm. Our first step to accomplish this was to turn our graph inputs into adjacency matrices, since this is the input that the Floyd Warshall algorithm needs. Also, Christina’s implementation of performance will also require this conversion so we can reuse some of our code! Our next steps involve testing the Floyd Warshall function with our new inputs to make sure it works and coming up with a solution to easily detect the community that each node is in for future calculations we will need to do in our algorithm.

Christina worked on her implementation of the performance metric. She wrote the methods to calculate performance on a graph where every node is its own community, to calculate the impact on performance of removing or adding a node from a community. She also modified the code that finds the best placement for a given node, in terms of change in modularity score, to select for performance instead. Going forward, she will be digging deeper into specific implementation details of the Louvain algorithm, especially surrounding the Community Aggregation phase.