An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing
We have developed a new simple iterative algorithm to determine entries of a normalized matrix given its marginal probabilities. Our method has been successfully used to obtain two different solutions by maximizing the entropy of a desired matrix and by minimizing its Kullback–Leibler divergence fro...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Académie des sciences
2023-05-01
|
| Series: | Comptes Rendus. Mathématique |
| Online Access: | https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.398/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825206255980904448 |
|---|---|
| author | Chlebus, Edward Kasapu, Viswatej |
| author_facet | Chlebus, Edward Kasapu, Viswatej |
| author_sort | Chlebus, Edward |
| collection | DOAJ |
| description | We have developed a new simple iterative algorithm to determine entries of a normalized matrix given its marginal probabilities. Our method has been successfully used to obtain two different solutions by maximizing the entropy of a desired matrix and by minimizing its Kullback–Leibler divergence from the initial probability distribution. The latter is fully equivalent to the well-known RAS balancing algorithm. The presented method has been evaluated using a traffic matrix of the GÉANT pan-European network and randomly generated matrices of various sparsities. It turns out to be computationally faster than RAS. We have shown that our approach is suitable for efficient balancing both dense and sparse matrices. |
| format | Article |
| id | doaj-art-a764b32d1c8f4a5291a791596b17193e |
| institution | Kabale University |
| issn | 1778-3569 |
| language | English |
| publishDate | 2023-05-01 |
| publisher | Académie des sciences |
| record_format | Article |
| series | Comptes Rendus. Mathématique |
| spelling | doaj-art-a764b32d1c8f4a5291a791596b17193e2025-02-07T11:07:37ZengAcadémie des sciencesComptes Rendus. Mathématique1778-35692023-05-01361G473774610.5802/crmath.39810.5802/crmath.398An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix BalancingChlebus, Edward0Kasapu, Viswatej1Department of Computer Science, Illinois Institute of Technology, 10 W. 31st St., Chicago, Illinois 60616, USADepartment of Computer Science, Illinois Institute of Technology, 10 W. 31st St., Chicago, Illinois 60616, USAWe have developed a new simple iterative algorithm to determine entries of a normalized matrix given its marginal probabilities. Our method has been successfully used to obtain two different solutions by maximizing the entropy of a desired matrix and by minimizing its Kullback–Leibler divergence from the initial probability distribution. The latter is fully equivalent to the well-known RAS balancing algorithm. The presented method has been evaluated using a traffic matrix of the GÉANT pan-European network and randomly generated matrices of various sparsities. It turns out to be computationally faster than RAS. We have shown that our approach is suitable for efficient balancing both dense and sparse matrices.https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.398/ |
| spellingShingle | Chlebus, Edward Kasapu, Viswatej An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing Comptes Rendus. Mathématique |
| title | An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing |
| title_full | An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing |
| title_fullStr | An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing |
| title_full_unstemmed | An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing |
| title_short | An Entropy Optimizing RAS-Equivalent Algorithm for Iterative Matrix Balancing |
| title_sort | entropy optimizing ras equivalent algorithm for iterative matrix balancing |
| url | https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.398/ |
| work_keys_str_mv | AT chlebusedward anentropyoptimizingrasequivalentalgorithmforiterativematrixbalancing AT kasapuviswatej anentropyoptimizingrasequivalentalgorithmforiterativematrixbalancing AT chlebusedward entropyoptimizingrasequivalentalgorithmforiterativematrixbalancing AT kasapuviswatej entropyoptimizingrasequivalentalgorithmforiterativematrixbalancing |