New Seed Expansion Algorithm Detects Overlapping Communities in Complex Networks

A newly introduced seed expansion algorithm named DOC-WAN consistently achieves high-quality scores and exceptional stability across real-world attributed weighted networks, according to research published in Knowledge and Information Systems. The framework, developed by Abhinav Kumar, Pawan Kumar, and Ravins Dohare, is specifically designed for the Detection of Overlapping Communities in Weighted Attributed Networks. Identifying overlapping communities represents a fundamental but non-trivial aspect of network analysis, particularly in large-scale complex networks. The researchers established that DOC-WAN effectively detects these overlapping structures, providing a viable and stable computational approach for analyzing complex real-world systems where elements belong to multiple groups simultaneously.

The study focuses on attributed weighted networks because detecting overlapping communities becomes significantly more difficult when datasets incorporate both connection weights and node attributes. As highlighted by the authors, real-world examples of such complex environments include social media platforms like Facebook, X, and LinkedIn, alongside biological systems and neural networks. In these domains, nodes possess descriptive attribute data in addition to weighted relational ties. To address the dual challenge of handling structural connections and node attributes simultaneously, the authors designed DOC-WAN to navigate both feature dimensions rather than relying solely on network topology.

The procedural mechanics of DOC-WAN operate through a structured seed expansion routine that begins by selecting a seed node based on weighted centrality. After identifying this central seed node, the algorithm expands it into an initial community by leveraging both Hamming similarity and neighbourhood proximity. This dual mechanism ensures that both attribute-level similarities and structural adjacency guide the expansion process. The algorithm systematically repeats this seed selection and expansion procedure as long as unassigned nodes remain in the network. Once all nodes have been partitioned into initial groupings, DOC-WAN merges highly similar communities to construct the final overlapping community structure.

To validate the performance and reliability of the framework, the authors conducted rigorous experimental evaluations across ten real-world attributed networks. The chosen benchmark networks exhibited significant variation in size and structural properties, spanning the spectrum from sparse graph configurations to dense topological structures. To assess both effectiveness and stability in a thorough manner, the researchers evaluated DOC-WAN using four quality measures and four stability metrics, examining both individual metric outcomes and their overall average scores. Across almost all evaluated networks, the experimental results demonstrated that DOC-WAN consistently attained high-quality scores and exceptional stability, underscoring the algorithm’s operational robustness and adaptability.

From a computational perspective, the algorithm exhibits an overall time complexity of \mathcal{O}(nc_{\text{max}}(k_{\text{max}}^2 + \ell)), where n represents the total number of nodes, \ell represents the dimension of the node attributes, k_{\text{max}} designates the maximum degree of the nodes, and c_{\text{max}} is the maximum number of initial communities. While the systematic experiments demonstrate that DOC-WAN yields high-quality community structures and dependable stability, the authors noted that parameterization represents a primary limitation of the current implementation. Although default parameter values yielded the best results within this specific study, tuning these parameters for diverse datasets remains challenging, prompting the researchers to recommend the development of automated, self-tuning selection mechanisms in future research.

Subject of Research: Overlapping community detection in attributed weighted networks

Article Title: Overlapping community detection in real-world attributed weighted networks: a seed expansion approach

Article References: Kumar, A., Kumar, P., & Dohare, R. (2026). Overlapping community detection in real-world attributed weighted networks: a seed expansion approach. Knowledge and Information Systems, 68(1), Article 309. https://doi.org/10.1007/s10115-026-02919-7

Image Credits: AI Generated

DOI: 10.1007/s10115-026-02919-7

Keywords: community detection, overlapping communities, attributed weighted networks, seed expansion, complex networks, network analysis, DOC-WAN, graph algorithms, Overlapping, community, detection, real-world