Knowledge and Information Systems Human-Computer Interaction
Overlapping community detection in real-world attributed weighted networks: a seed expansion approach
Abstract
Identifying overlapping communities is a fundamental but non-trivial aspect of network analysis, particularly in large-scale complex networks. This task becomes even more difficult when addressing attributed weighted networks, such as social media platforms (e.g. Facebook, X, and LinkedIn), biological systems, and neural networks. To address this, we developed a seed expansion-based algorithm named DOC-WAN, which stands for Detection of Overlapping Communities in Weighted Attributed Networks. The algorithm starts by selecting a seed node based on weighted centrality and then expand it using both Hamming similarity and neighbourhood proximity to form an initial community. This process is repeated as long as there are unassigned nodes. Finally, highly similar communities are merged to produce the overlapping community structure. DOC-WAN was rigorously evaluated on 10 real-world attributed networks, spanning from sparse to dense structures and exhibiting significant variation in size and structural properties. To assess its effectiveness and stability, the algorithm was evaluated using four quality measures and four stability metrics, along with their average scores. Results demonstrated that DOC-WAN consistently achieved high-quality scores and exceptional stability across almost all networks, underscoring its robustness and adaptability. The algorithm’s time complexity is $$ \mathcal {O}(nc_{\text {max}} (k_{\text {max}}^2 + \ell )) $$ O ( n c max ( k max 2 + ℓ ) ) , where $$n$$ n represents the number of nodes, $$\ell $$ ℓ represents the dimension of attributes, $$k_{\text {max}}$$ k max is the maximum degree of nodes, and $$c_{\text {max}}$$ c max is the maximum number of initial communities. Through systematic experimentation, we demonstrate that DOC-WAN effectively detects overlapping communities in attributed weighted networks. The framework yields high-quality community structures and stable performance, offering a viable approach for complex network analysis. However, a key limitation of the current framework lies in its parameterization; although the default parameters provided the best results in this study, tuning them for diverse datasets remains challenging. Therefore, developing automated, self-tuning selection mechanisms is highly recommended for future work.