Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2603.11050 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915935838797824 |
|---|---|
| author | Shekarriz, Mohammad Hadi Nazari, Asef Thiruvady, Dhananjay |
| author_facet | Shekarriz, Mohammad Hadi Nazari, Asef Thiruvady, Dhananjay |
| contents | The Soft Happy Colouring (SHC) problem, a mathematical framework for identifying homophilic network structures, seeks to maximise the number of $ρ$-happy vertices, i.e. vertices with at least a proportion $ρ$ of neighbours that share the same colour. Because this NP-hard problem makes exact solutions intractable for large networks, probabilistic metaheuristics such as the Cross-Entropy (CE) method are suitable candidates to be employed. However, pure CE frequently suffers from probabilistic stagnation and non-convergence in high-dimensional spaces. To address this, we introduce {\sf CE+LS}, synergising CE's adaptive learning with a fast, structure-aware local search ({\sf LS}). By restricting the search exclusively to local optima, {\sf CE+LS} learns from high-quality structural characteristics rather than raw random samples. We mathematically prove and empirically demonstrate that this search space reduction resolves CE's stagnation, yielding a strictly convergent algorithm characterised by an exponential decay in Kullback-Leibler divergence. Evaluating {\sf CE+LS} across 28,000 Stochastic Block Model graphs demonstrates that it consistently outperforms existing heuristic and memetic algorithms, exhibiting superior scalability and solution quality. Crucially, {\sf CE+LS} remains highly efficient even in the tight regime, where comparative algorithms fail. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_11050 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Overcoming Tight Constraints in Soft Happy Colouring Shekarriz, Mohammad Hadi Nazari, Asef Thiruvady, Dhananjay Social and Information Networks Combinatorics 91C20, 05C15, 68R10 The Soft Happy Colouring (SHC) problem, a mathematical framework for identifying homophilic network structures, seeks to maximise the number of $ρ$-happy vertices, i.e. vertices with at least a proportion $ρ$ of neighbours that share the same colour. Because this NP-hard problem makes exact solutions intractable for large networks, probabilistic metaheuristics such as the Cross-Entropy (CE) method are suitable candidates to be employed. However, pure CE frequently suffers from probabilistic stagnation and non-convergence in high-dimensional spaces. To address this, we introduce {\sf CE+LS}, synergising CE's adaptive learning with a fast, structure-aware local search ({\sf LS}). By restricting the search exclusively to local optima, {\sf CE+LS} learns from high-quality structural characteristics rather than raw random samples. We mathematically prove and empirically demonstrate that this search space reduction resolves CE's stagnation, yielding a strictly convergent algorithm characterised by an exponential decay in Kullback-Leibler divergence. Evaluating {\sf CE+LS} across 28,000 Stochastic Block Model graphs demonstrates that it consistently outperforms existing heuristic and memetic algorithms, exhibiting superior scalability and solution quality. Crucially, {\sf CE+LS} remains highly efficient even in the tight regime, where comparative algorithms fail. |
| title | Overcoming Tight Constraints in Soft Happy Colouring |
| topic | Social and Information Networks Combinatorics 91C20, 05C15, 68R10 |
| url | https://arxiv.org/abs/2603.11050 |