Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2512.19279 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909973481521152 |
|---|---|
| author | Rosa, Samuel Harman, Radoslav |
| author_facet | Rosa, Samuel Harman, Radoslav |
| contents | Designing networks to optimize robustness and other performance metrics is a well-established problem with applications ranging from electrical engineering to communication networks. Many such performance measures rely on the Laplacian spectrum; notable examples include total effective resistance, the number of spanning trees, and algebraic connectivity. This paper advances the study of Laplacian-based network optimization by drawing on ideas from experimental design in statistics. We present a theoretical framework for analyzing performance measures by introducing the notion of information functions, which captures a set of their desirable properties. Then, we formulate a new parametric family of information functions, Kiefer's measures, which encompasses the three most common spectral objectives. We provide a regular reformulation of the Laplacian optimization problem, and we use this reformulation to compute directional derivatives of Kiefer's measures. The directional derivatives provide a unified treatment of quantities recurring in Laplacian optimization, such as gradients and subgradients, and we show that they are connected to Laplacian-based measures of node distance, which we call node dissimilarities. We apply the node dissimilarities to derive efficient rank-one update formulas for Kiefer's criteria, and to devise a new edge-exchange method for network optimization. These update formulas enable greedy and exchange algorithms with reduced asymptotic time complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_19279 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Laplacian Network Optimization via Information Functions Rosa, Samuel Harman, Radoslav Social and Information Networks Discrete Mathematics Designing networks to optimize robustness and other performance metrics is a well-established problem with applications ranging from electrical engineering to communication networks. Many such performance measures rely on the Laplacian spectrum; notable examples include total effective resistance, the number of spanning trees, and algebraic connectivity. This paper advances the study of Laplacian-based network optimization by drawing on ideas from experimental design in statistics. We present a theoretical framework for analyzing performance measures by introducing the notion of information functions, which captures a set of their desirable properties. Then, we formulate a new parametric family of information functions, Kiefer's measures, which encompasses the three most common spectral objectives. We provide a regular reformulation of the Laplacian optimization problem, and we use this reformulation to compute directional derivatives of Kiefer's measures. The directional derivatives provide a unified treatment of quantities recurring in Laplacian optimization, such as gradients and subgradients, and we show that they are connected to Laplacian-based measures of node distance, which we call node dissimilarities. We apply the node dissimilarities to derive efficient rank-one update formulas for Kiefer's criteria, and to devise a new edge-exchange method for network optimization. These update formulas enable greedy and exchange algorithms with reduced asymptotic time complexity. |
| title | Laplacian Network Optimization via Information Functions |
| topic | Social and Information Networks Discrete Mathematics |
| url | https://arxiv.org/abs/2512.19279 |