Beyond One Solution: a Comprehensive Exploration of Solution Space in Community Detection for Social Networks
Preprint
- 22 May 2025
- preprint
- Published by Springer Nature in Research Square
Abstract
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.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Exploring community detection methods and their diverse applications in complex networks: a comprehensive reviewSocial Network Analysis and Mining, 2024
- A comprehensive survey on community detection methods and applications in complex information networksSocial Network Analysis and Mining, 2024
- UCoDe: unified community detection with graph convolutional networksMachine Learning, 2023
- Embedding-based Silhouette community detectionMachine Learning, 2020
- A review of stochastic block models and extensions for graph clusteringApplied Network Science, 2019
- Community detection in networks: A user guidePhysics Reports, 2016
- Community detection in social networksWIREs Data Mining and Knowledge Discovery, 2016
- The use of different data sources in the analysis of co-authorship networks and scientific performanceSocial Networks, 2013
- The impact of network structure on knowledge transfer: an application of social network analysis in the context of regional innovation networksThe Annals of Regional Science, 2008
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005