Static and Dynamic Community Detection Methods That Optimize a Specific Objective Function: A Survey and Experimental Evaluation

Abstract

Most current survey papers classify community detection methods into broad categories and do not draw clear boundaries between the specific techniques employed by these methods. We survey in this paper all fine-grained community detection categories, the clustering methods that fall under these categories, and the techniques employed by these methods for optimizing each objective function. We provide methodology-based taxonomies that classify static and dynamic community detection methods into hierarchically nested, fine-grained, and specific classes. We classify the methods into the objective function they optimize. Each objective function class is classified into clustering categories. Each category is further classified into clustering methods. Methods are further classified into sub-methods and so on. Thus, the lowest subclass in a hierarchy is a fine-grained and specific method. For each method, we survey the different techniques in literature employed by the method. We empirically and experimentally compare and rank the different methods that fall under each clustering category. We also empirically and experimentally compare and rank the different categories that optimize a same objective function. In summary, the block-based, top-down divisive-based, random walk-based, and matrix eigenvector-based methods achieved good results. Finally, we provide fitness metrics for each objective function.

Keywords

• Clustering
• community detection
• objective function