Parallel Algorithms for Median Consensus Clustering in Complex Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917754802536448 |
|---|---|
| author | Hussain, Md Taufique Halappanavar, Mahantesh Chatterjee, Samrat Radicchi, Filippo Fortunato, Santo Azad, Ariful |
| author_facet | Hussain, Md Taufique Halappanavar, Mahantesh Chatterjee, Samrat Radicchi, Filippo Fortunato, Santo Azad, Ariful |
| contents | We develop an algorithm that finds the consensus of 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 from single-cell experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_11331 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parallel Algorithms for Median Consensus Clustering in Complex Networks Hussain, Md Taufique Halappanavar, Mahantesh Chatterjee, Samrat Radicchi, Filippo Fortunato, Santo Azad, Ariful Information Retrieval Computers and Society Data Structures and Algorithms Social and Information Networks We develop an algorithm that finds the consensus of 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 from single-cell experiments. |
| title | Parallel Algorithms for Median Consensus Clustering in Complex Networks |
| topic | Information Retrieval Computers and Society Data Structures and Algorithms Social and Information Networks |
| url | https://arxiv.org/abs/2408.11331 |