Prototype-based interpretable community detection

Community detection is a fundamental task in complex network analysis. Most existing methods prioritize accuracy while neglecting the interpretability of identified communities. As a result, how to accurately identify a set of communities in which each community is characterized in an interpretable manner remains an open issue. To fill this gap, we formulate the interpretable community detection problem as an optimization problem, in which each community is described through a central node and its coverage radius. After proving that such an optimization problem is a NP-Hard problem, we present a heuristic search algorithm to iteratively obtain a local optimal solution. Extensive experimental results demonstrate that, although the proposed method may show slight compromises in community detection performance compared to existing non-interpretable approaches, it significantly outperforms them in terms of interpretability and efficiency, particularly in large-scale networks. Overall, the proposed method can achieve a good balance between interpretability, effectiveness, and computational efficiency, making it an ideal choice for practical applications that require both accuracy and transparency. The source code of the proposed method can be found at: https://github.com/xuannnn523/PICD.