SAT-based models for overlapping community detection in networks

Communities in social networks or graphs are sets of well-connected, overlapping vertices. Network community detection is a hot research topic in social, biological and information networks analysis. The effectiveness of a community detection algorithm is determined by accuracy in finding the ground-truth communities. In this article, we present two models to detect overlapping communities in large complex networks. In the first model, we introduce a parametrized notion of community, called k-linked community, that allows us to characterize a vertex/edge centered k-linked community with bounded diameter. Such community possesses a vertex/edge with a distance at most k2 from any other vertex of that community. Next, we show how the problem of detecting vertex/edge centered k-linked communities can be expressed as a Partial Max-SAT optimization problem. Then, we propose a post-processing strategy to further enhance the overlaps between the final communities. Our second model called preference-based centroid model aims to constrain the choice of centroids communities in the first model. This new framework allows to integrate more easily the user preferences in order to discover high quality communities by selecting the most central vertices. For this, we exploit Weighted Partial Max-SAT to solve the underlying optimization problem. We evaluate the proposed frameworks empirically against several high-performing methods, with respect to three evaluation metrics and scalability, on a number of real-life datasets. The experimental results show that our algorithms outperform existing state-of-the-art methods in detecting relevant communities.