No Community Detection Method to Rule Them All!
摘要
Community detection is a key tool for analyzing large real-world graphs. It is often used to derive additional local features of vertices and edges that will be used to perform a downstream task, yet the impact of community detection on downstream tasks is poorly understood. Prior work largely evaluates community detection algorithms by their intrinsic objectives (e.g., modularity). Or they evaluate the impact of using community detection onto on the downstream task. But the impact of particular community detection algorithm on downstream task is not well studied. We study that relationship on two particular applications. Our analysis links community-level properties to task metrics (F1, precision, recall, AUC) and reveals that the choice of detection method materially affects outcomes. We explore thousands of community structures generated by genetic algorithm and show that while the properties of communities are the reason behind the impact on task performance, no single property explains performance in a direct way. As such, no standard community detection algorithm will derive the best downstream performance. We show that a method combining random community generation and simple machine learning techniques can derive better performance.