Skip to main content

2022 | OriginalPaper | Buchkapitel

Convergence Properties of Optimal Transport-Based Temporal Networks

verfasst von : Diego Baptista, Caterina De Bacco

Erschienen in: Complex Networks & Their Applications X

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study network properties of networks evolving in time based on optimal transport principles. These evolve from a structure covering uniformly a continuous space towards an optimal design in terms of optimal transport theory. At convergence, the networks should optimize the way resources are transported through it. As the network structure shapes in time towards optimality, its topological properties also change with it. The question is how do these change as we reach optimality. We study the behavior of various network properties on a number of network sequences evolving towards optimal design and find that the transport cost function converges earlier than network properties and that these monotonically decrease. This suggests a mechanism for designing optimal networks by compressing dense structures. We find a similar behavior in networks extracted from real images of the networks designed by the body shape of a slime mold evolving in time.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
2.
Zurück zum Zitat Santambrogio, F.: Optimal transport for applied mathematicians. Birkäuser NY 55, 58–63 (2015)MATH Santambrogio, F.: Optimal transport for applied mathematicians. Birkäuser NY 55, 58–63 (2015)MATH
3.
Zurück zum Zitat Peyré, G., Cuturi, M., et al.: Computational optimal transport: with applications to data science. Found. Trends® Mach. Learn. 11(5–6), 355–607 (2019)CrossRefMATH Peyré, G., Cuturi, M., et al.: Computational optimal transport: with applications to data science. Found. Trends® Mach. Learn. 11(5–6), 355–607 (2019)CrossRefMATH
4.
Zurück zum Zitat Facca, E., Cardin, F., Putti, M.: Towards a stationary Monge-Kantorovich dynamics: the physarum polycephalum experience. SIAM J. Appl. Math. 78(2), 651–676 (2018)MathSciNetCrossRefMATH Facca, E., Cardin, F., Putti, M.: Towards a stationary Monge-Kantorovich dynamics: the physarum polycephalum experience. SIAM J. Appl. Math. 78(2), 651–676 (2018)MathSciNetCrossRefMATH
5.
Zurück zum Zitat Facca, E., Daneri, S., Cardin, F., Putti, M.: Numerical solution of Monge-Kantorovich equations via a dynamic formulation. J. Sci. Comput. 82, 1–26 (2020)MathSciNetCrossRefMATH Facca, E., Daneri, S., Cardin, F., Putti, M.: Numerical solution of Monge-Kantorovich equations via a dynamic formulation. J. Sci. Comput. 82, 1–26 (2020)MathSciNetCrossRefMATH
6.
Zurück zum Zitat Facca, E., Cardin, F.: Branching structures emerging from a continuous optimal transport model. J. Comput. Phys. (2020, Submitted) Facca, E., Cardin, F.: Branching structures emerging from a continuous optimal transport model. J. Comput. Phys. (2020, Submitted)
7.
Zurück zum Zitat Baptista, D., Leite, D., Facca, E., Putti, M., De Bacco, C.: Network extraction by routing optimization. Sci. Rep. 10(1), 1–13 (2020)CrossRef Baptista, D., Leite, D., Facca, E., Putti, M., De Bacco, C.: Network extraction by routing optimization. Sci. Rep. 10(1), 1–13 (2020)CrossRef
8.
Zurück zum Zitat Corson, F.: Fluctuations and redundancy in optimal transport networks. Phys. Rev. Lett. 104(4), 048703 (2010)CrossRef Corson, F.: Fluctuations and redundancy in optimal transport networks. Phys. Rev. Lett. 104(4), 048703 (2010)CrossRef
9.
Zurück zum Zitat Bohn, S., Magnasco, M.O.: Structure, scaling, and phase transition in the optimal transport network. Phys. Rev. Lett. 98(8), 088702 (2007)CrossRef Bohn, S., Magnasco, M.O.: Structure, scaling, and phase transition in the optimal transport network. Phys. Rev. Lett. 98(8), 088702 (2007)CrossRef
11.
Zurück zum Zitat Katifori, E., Szöllősi, G.J., Magnasco, M.O.: Damage and fluctuations induce loops in optimal transport networks. Phys. Rev. Lett. 104(4), 048704 (2010)CrossRef Katifori, E., Szöllősi, G.J., Magnasco, M.O.: Damage and fluctuations induce loops in optimal transport networks. Phys. Rev. Lett. 104(4), 048704 (2010)CrossRef
12.
Zurück zum Zitat Baumgarten, W., Hauser, M.J.: Functional organization of the vascular network of physarum polycephalum. Phys. Biol. 10(2), 026003 (2013)CrossRef Baumgarten, W., Hauser, M.J.: Functional organization of the vascular network of physarum polycephalum. Phys. Biol. 10(2), 026003 (2013)CrossRef
13.
Zurück zum Zitat Baumgarten, W., Ueda, T., Hauser, M.J.: Plasmodial vein networks of the slime mold physarum polycephalum form regular graphs. Phys. Rev. E 82(4), 046113 (2010)CrossRef Baumgarten, W., Ueda, T., Hauser, M.J.: Plasmodial vein networks of the slime mold physarum polycephalum form regular graphs. Phys. Rev. E 82(4), 046113 (2010)CrossRef
14.
Zurück zum Zitat Dirnberger, M., Mehlhorn, K.: Characterizing networks formed by p. polycephalum. J. Phys. D: Appl. Phys. 50(22), 224002 (2017)CrossRef Dirnberger, M., Mehlhorn, K.: Characterizing networks formed by p. polycephalum. J. Phys. D: Appl. Phys. 50(22), 224002 (2017)CrossRef
15.
Zurück zum Zitat Westendorf, C., Gruber, C., Grube, M.: Quantitative comparison of plasmodial networks of different slime molds. In: Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS), pp. 611–612 (2016) Westendorf, C., Gruber, C., Grube, M.: Quantitative comparison of plasmodial networks of different slime molds. In: Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS), pp. 611–612 (2016)
16.
Zurück zum Zitat Dirnberger, M., Mehlhorn, K., Mehlhorn, T.: Introducing the slime mold graph repository. J. Phys. D Appl. Phys. 50(26), 264001 (2017)CrossRef Dirnberger, M., Mehlhorn, K., Mehlhorn, T.: Introducing the slime mold graph repository. J. Phys. D Appl. Phys. 50(26), 264001 (2017)CrossRef
17.
Zurück zum Zitat Nakagaki, T., Yamada, H., Tóth, Á.: Maze-solving by an amoeboid organism. Nature 407(6803), 470 (2000)CrossRef Nakagaki, T., Yamada, H., Tóth, Á.: Maze-solving by an amoeboid organism. Nature 407(6803), 470 (2000)CrossRef
18.
Zurück zum Zitat Tero, A., Kobayashi, R., Nakagaki, T.: A mathematical model for adaptive transport network in path finding by true slime mold. J. Theor. Biol. 244(4), 553–564 (2007)MathSciNetCrossRefMATH Tero, A., Kobayashi, R., Nakagaki, T.: A mathematical model for adaptive transport network in path finding by true slime mold. J. Theor. Biol. 244(4), 553–564 (2007)MathSciNetCrossRefMATH
20.
Zurück zum Zitat Baptista, D., De Bacco, C.: Principled network extraction from images. R. Soc. Open Sci. 8, 210025 (2021) Baptista, D., De Bacco, C.: Principled network extraction from images. R. Soc. Open Sci. 8, 210025 (2021)
21.
Zurück zum Zitat Lonardi, A., Facca, E., Putti, M., De Bacco, C.: Optimal transport for multi-commodity routing on networks. arXiv preprint arXiv:2010.14377 (2020) Lonardi, A., Facca, E., Putti, M., De Bacco, C.: Optimal transport for multi-commodity routing on networks. arXiv preprint arXiv:​2010.​14377 (2020)
22.
Zurück zum Zitat Ibrahim, A.A., Lonardi, A., Bacco, C.D.: Optimal transport in multilayer networks for traffic flow optimization. Algorithms 14(7), 189 (2021)CrossRef Ibrahim, A.A., Lonardi, A., Bacco, C.D.: Optimal transport in multilayer networks for traffic flow optimization. Algorithms 14(7), 189 (2021)CrossRef
Metadaten
Titel
Convergence Properties of Optimal Transport-Based Temporal Networks
verfasst von
Diego Baptista
Caterina De Bacco
Copyright-Jahr
2022
DOI
https://doi.org/10.1007/978-3-030-93409-5_48

Premium Partner