Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2412.15776 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915364715102208 |
|---|---|
| author | Blanco, Víctor González, Gabriel Gagrani, Praful |
| author_facet | Blanco, Víctor González, Gabriel Gagrani, Praful |
| contents | In this paper, we introduce the concept of self-amplifying structures for hypergraphs, positioning it as a key element for understanding propagation and internal reinforcement in complex systems. To quantify this phenomenon, we define the maximal amplification factor, a metric that captures how effectively a subhypergraph contributes to its own amplification. We then develop an optimization-based methodology to compute this measure. Building on this foundation, we tackle the problem of identifying the subhypergraph maximizing the amplification factor, formulating it as a mixed-integer nonlinear programming (MINLP) problem. To solve it efficiently, we propose an exact iterative algorithm with proven convergence guarantees. In addition, we report the results of extensive computational experiments on realistic synthetic instances, demonstrating both the relevance and effectiveness of the proposed approach. Finally, we present a case study on chemical reaction networks, including the Formose reaction and E. coli core metabolism, where our framework successfully identifies known and novel autocatalytic subnetworks, highlighting its practical relevance to systems chemistry and biology. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_15776 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Identifying Self-Amplifying Hypergraph Structures through Mathematical Optimization Blanco, Víctor González, Gabriel Gagrani, Praful Optimization and Control Computational Engineering, Finance, and Science In this paper, we introduce the concept of self-amplifying structures for hypergraphs, positioning it as a key element for understanding propagation and internal reinforcement in complex systems. To quantify this phenomenon, we define the maximal amplification factor, a metric that captures how effectively a subhypergraph contributes to its own amplification. We then develop an optimization-based methodology to compute this measure. Building on this foundation, we tackle the problem of identifying the subhypergraph maximizing the amplification factor, formulating it as a mixed-integer nonlinear programming (MINLP) problem. To solve it efficiently, we propose an exact iterative algorithm with proven convergence guarantees. In addition, we report the results of extensive computational experiments on realistic synthetic instances, demonstrating both the relevance and effectiveness of the proposed approach. Finally, we present a case study on chemical reaction networks, including the Formose reaction and E. coli core metabolism, where our framework successfully identifies known and novel autocatalytic subnetworks, highlighting its practical relevance to systems chemistry and biology. |
| title | Identifying Self-Amplifying Hypergraph Structures through Mathematical Optimization |
| topic | Optimization and Control Computational Engineering, Finance, and Science |
| url | https://arxiv.org/abs/2412.15776 |