Beyond One Solution: a Comprehensive Exploration of Solution Space in Community Detection for Social Networks

This paper investigates the relevance of systematically exploring the solution space produced by commonly used community detection algorithms, emphasizing its role in enhancing the robustness and reliability of results, particularly in complex real-world social networks. Three core challenges are addressed: the multiplicity of solutions, input ordering bias, and the handling of outliers. Input ordering bias—where the outcome of an algorithm is influenced by the sequence in which nodes and edges are processed—can undermine the interpretability of results by introducing artifacts unrelated to the network topol-ogy. Similarly, the presence of outliers-nodes that do not clearly belong to any community—is often overlooked, with many algorithms either ignoring them or forcing them into existing clusters, thereby affecting the resulting partition. To address these limitations, we propose a methodological framework for systematically exploring the solution space across multiple algorithm runs, incorporating a Bayesian model to assess its stability and a taxonomy to classify its structure. This approach enables a deeper understanding of the variability and uncertainty inherent in community detection, paving the way for more accurate, consistent, and interpretable results.