Parallel median consensus clustering in complex networks
Abstract We develop an algorithm that finds the consensus among many different clustering solutions of a graph. We formulate the problem as a median set partitioning problem and propose a greedy optimization technique. Unlike other approaches that find median set partitions, our algorithm takes grap...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2025-01-01
|
| Series: | Scientific Reports |
| Online Access: | https://doi.org/10.1038/s41598-025-87479-6 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832571801997148160 |
|---|---|
| author | Md Taufique Hussain Mahantesh Halappanavar Samrat Chatterjee Filippo Radicchi Santo Fortunato Ariful Azad |
| author_facet | Md Taufique Hussain Mahantesh Halappanavar Samrat Chatterjee Filippo Radicchi Santo Fortunato Ariful Azad |
| author_sort | Md Taufique Hussain |
| collection | DOAJ |
| description | Abstract We develop an algorithm that finds the consensus among many different clustering solutions of a graph. We formulate the problem as a median set partitioning problem and propose a greedy optimization technique. Unlike other approaches that find median set partitions, our algorithm takes graph structure into account and finds a comparable quality solution much faster than the other approaches. For graphs with known communities, our consensus partition captures the actual community structure more accurately than alternative approaches. To make it applicable to large graphs, we remove sequential dependencies from our algorithm and design a parallel algorithm. Our parallel algorithm achieves 35x speedup when utilizing 64 processing cores for large real-world graphs representing mass cytometry data from single-cell experiments. |
| format | Article |
| id | doaj-art-8855dfa6c9d0435cba42073bd0a150e2 |
| institution | Kabale University |
| issn | 2045-2322 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Scientific Reports |
| spelling | doaj-art-8855dfa6c9d0435cba42073bd0a150e22025-02-02T12:19:51ZengNature PortfolioScientific Reports2045-23222025-01-0115111510.1038/s41598-025-87479-6Parallel median consensus clustering in complex networksMd Taufique Hussain0Mahantesh Halappanavar1Samrat Chatterjee2Filippo Radicchi3Santo Fortunato4Ariful Azad5Department of Intelligent Systems Engineering, Indiana UniversityData Sciences and Machine Intelligence Group, Pacific Northwest National LaboratoryData Sciences and Machine Intelligence Group, Pacific Northwest National LaboratoryCenter for Complex Networks and Systems Research (CNetS), Indiana UniversityCenter for Complex Networks and Systems Research (CNetS), Indiana UniversityDepartment of Intelligent Systems Engineering, Indiana UniversityAbstract We develop an algorithm that finds the consensus among many different clustering solutions of a graph. We formulate the problem as a median set partitioning problem and propose a greedy optimization technique. Unlike other approaches that find median set partitions, our algorithm takes graph structure into account and finds a comparable quality solution much faster than the other approaches. For graphs with known communities, our consensus partition captures the actual community structure more accurately than alternative approaches. To make it applicable to large graphs, we remove sequential dependencies from our algorithm and design a parallel algorithm. Our parallel algorithm achieves 35x speedup when utilizing 64 processing cores for large real-world graphs representing mass cytometry data from single-cell experiments.https://doi.org/10.1038/s41598-025-87479-6 |
| spellingShingle | Md Taufique Hussain Mahantesh Halappanavar Samrat Chatterjee Filippo Radicchi Santo Fortunato Ariful Azad Parallel median consensus clustering in complex networks Scientific Reports |
| title | Parallel median consensus clustering in complex networks |
| title_full | Parallel median consensus clustering in complex networks |
| title_fullStr | Parallel median consensus clustering in complex networks |
| title_full_unstemmed | Parallel median consensus clustering in complex networks |
| title_short | Parallel median consensus clustering in complex networks |
| title_sort | parallel median consensus clustering in complex networks |
| url | https://doi.org/10.1038/s41598-025-87479-6 |
| work_keys_str_mv | AT mdtaufiquehussain parallelmedianconsensusclusteringincomplexnetworks AT mahanteshhalappanavar parallelmedianconsensusclusteringincomplexnetworks AT samratchatterjee parallelmedianconsensusclusteringincomplexnetworks AT filipporadicchi parallelmedianconsensusclusteringincomplexnetworks AT santofortunato parallelmedianconsensusclusteringincomplexnetworks AT arifulazad parallelmedianconsensusclusteringincomplexnetworks |