Explainable community detection

Community detection is a fundamental task in complex network analysis, aiming to partition networks into tightly multiple dense subgraphs. While community detection has been widely studied, existing methods often lack interpretability, making it challenging to explain key aspects such as node assignments, community boundaries, and inter-community relationships. In this paper, the explainable community detection issue is addressed, in which each community is characterized using a central node and its corresponding radius. The central node represents the most representative node in the community, while the radius defines its influence scope. Such an explainable community detection issue is formulated as an optimization problem in which the objective is to maximize central node’s coverage and accuracy in explaining its associated community. To solve this problem, two algorithms are developed: a naive algorithm and a fast approximate algorithm that incorporate heuristic strategies to improve computational efficiency. Experimental results on 9 real-world networks demonstrate that the proposed methods can effectively interpret community structures with high accuracy and efficiency. More precisely, the objective function values achieved by the identified pairs of center and radius exceed 0.7 on most communities and the running time is generally no more than 10 s on a network with approximatively one thousand nodes. The source code of the proposed methods can be found at: https://github.com/xuannnn523/CCTS.