Our Project
The community detection problem is a common graph problem that involves detecting clusters of nodes in a graph that maximize some measure of quality Q. To gain insight into the problem as a whole, we studied three community detection algorithms with different approaches to finding communities: the Girvan-Newman algorithm, the Louvain method algorithm, and the Basic Variable Neighborhood Search algorithm. We ran these algorithms on synthetically generated graphs and graphs constructed from actual data from a variety of disciplines and compared their performance on a suite of metrics. We find that for our graphs that represent real-world data, there is no universally optimal community detection algorithm, as differences in graph structure and size and the varying definitions of real-world communities across applications significantly impact performance, leading no one algorithm to perform consistently the best across all of the metrics we collected.
