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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

No Community Detection Method to Rule Them All!

  • Shrabani Ghosh,
  • Erik Saule

摘要

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.