Robust network formation with biological applications

Jan Haskovec; Vybíral Jan; Jan Haskovec; Vybíral Jan

doi:10.3934/nhm.2024035

Networks and Heterogeneous Media

2024, Volume 19, Issue 2: 771-799. doi: 10.3934/nhm.2024035

Previous Article Next Article

Research article

Robust network formation with biological applications

Jan Haskovec ^{1
,
,},
Vybíral Jan ²

1.
Mathematical and Computer Sciences and Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Kingdom of Saudi Arabia
2.
Department of Mathematics, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University, Trojanova 12, 12000 Praha, Czech Republic

Received: 03 April 2024 Revised: 13 July 2024 Accepted: 05 August 2024 Published: 09 August 2024

We have provided new results on the structure of optimal transportation networks obtained as minimizers of an energy cost functional posed on a discrete graph. The energy consists of a kinetic (pumping) and a material (metabolic) cost term, constrained by a local mass conservation law. In particular, we have proved that every tree (i.e., graph without loops) represents a local minimizer of the energy with concave metabolic cost. For the linear metabolic cost, we have proved that the set of minimizers contains a loop-free structure. Moreover, we enriched the energy functional such that it accounts also for robustness of the network, measured in terms of the Fiedler number of the graph with edge weights given by their conductivities. We examined fundamental properties of the modified functional, in particular, its convexity and differentiability. We provided analytical insights into the new model by considering two simple examples. Subsequently, we employed the projected subgradient method to find global minimizers of the modified functional numerically. We then presented two numerical examples, illustrating how the optimal graph's structure and energy expenditure depend on the required robustness of the network.
- Optimal transportation networks,
- algebraic connectivity,
- robustness,
- Fiedler number
Citation: Jan Haskovec, Vybíral Jan. Robust network formation with biological applications[J]. Networks and Heterogeneous Media, 2024, 19(2): 771-799. doi: 10.3934/nhm.2024035

Related Papers:

Abstract

We have provided new results on the structure of optimal transportation networks obtained as minimizers of an energy cost functional posed on a discrete graph. The energy consists of a kinetic (pumping) and a material (metabolic) cost term, constrained by a local mass conservation law. In particular, we have proved that every tree (i.e., graph without loops) represents a local minimizer of the energy with concave metabolic cost. For the linear metabolic cost, we have proved that the set of minimizers contains a loop-free structure. Moreover, we enriched the energy functional such that it accounts also for robustness of the network, measured in terms of the Fiedler number of the graph with edge weights given by their conductivities. We examined fundamental properties of the modified functional, in particular, its convexity and differentiability. We provided analytical insights into the new model by considering two simple examples. Subsequently, we employed the projected subgradient method to find global minimizers of the modified functional numerically. We then presented two numerical examples, illustrating how the optimal graph's structure and energy expenditure depend on the required robustness of the network.

References

[1]	R. Albert, H. Jeong, A. Barabasi, Error and attack tolerance of complex networks, Nature, 406 (2000), 378–382. https://doi.org/10.1038/35019019 doi: 10.1038/35019019
[2]	G. Albi, M. Burger, J. Haskovec, P. Markowich, M. Schlottbom, Continuum modelling of biological network formation, in N. Bellomo, P. Degond and E. Tamdor (eds.), Active Particles Vol.I–Theory, Models, Applications, Series: Modelling and Simulation in Science and Technology, Boston: Birkhäuser-Springer, (2017), 1–48. https://doi.org/10.1007/978-3-319-49996-3
[3]	J. P. Aubin, H. Frankowska, Set-valued analysis, In: Mutational and Morphological Analysis. Systems & Control: Foundations & Applications, Boston: Birkhäuser, 2008.
[4]	D. P. Bebber, J. Hynes, P. R. Darrah, L. Boddy, M. D. Fricker, Biological solutions to transport network design, Proc. Royal Soc. B, 274 (2007), 2307–2315. https://doi.org/10.1098/rspb.2007.0459 doi: 10.1098/rspb.2007.0459
[5]	K. Buchin, A. Schulz, On the Number of Spanning Trees a Planar Graph Can Have, in M. de Berg and U. Meyer (eds.), Algorithms–ESA 2010. Lecture Notes in Computer Science, Berlin: Springer, (2010), 110–121. https://doi.org/10.1007/978-3-642-15775-2_10
[6]	M. Burger, J. Haskovec, P. Markowich, H. Ranetbauer, A mesoscopic model of biological transportation networks, Commun. Math. Sci., 17 (2019), 1213–1234. https://doi.org/10.4310/CMS.2019.v17.n5.a3 doi: 10.4310/CMS.2019.v17.n5.a3
[7]	G. E. Cantarella, E. Cascetta, Dynamic processes and equilibrium in transportation networks: towards a unifying theory, Transp. Sci., 29 (1995), 303–375. https://doi.org/10.1287/trsc.29.4.305 doi: 10.1287/trsc.29.4.305
[8]	M. Fiedler, Algebraic connectivity of graphs, Czechoslov. Math. J., 23 (1973), 298–305. http://dx.doi.org/10.21136/CMJ.1973.101168 doi: 10.21136/CMJ.1973.101168
[9]	J. Haskovec, L. M. Kreusser, P. Markowich, ODE and PDE based modeling of biological transportation networks, Commun. Math. Sci., 17 (2019), 1235–1256. https://doi.org/10.4310/CMS.2019.v17.n5.a4 doi: 10.4310/CMS.2019.v17.n5.a4
[10]	J. Haskovec, P. Markowich, G. Pilli, Tensor PDE model of biological network formation, Commun. Math. Sci., 20 (2022), 1173–1191. https://doi.org/10.4310/CMS.2022.v20.n4.a10 doi: 10.4310/CMS.2022.v20.n4.a10
[11]	J. Haskovec, P. Markowich, S. Portaro, Emergence of biological transportation networks as a self-regulated process, Discrete Contin. Dyn. Syst., 43 (2023), 1499–1515. https://doi.org/10.3934/dcds.2022159 doi: 10.3934/dcds.2022159
[12]	J. B. Hiriart-Urruty, A.S. Lewis, The Clarke and Michel-Penot subdifferentials of the eigenvalues of a symmetric matrix, Comput Optim Appl, 13 (1999), 13–23. https://doi.org/10.1023/A:1008644520093 doi: 10.1023/A:1008644520093
[13]	A. Hoffman, H. Wielandt, The variation of the spectrum of a normal matrix, Duke Math. J., 20 (1953), 37–39. https://doi.org/10.1215/s0012-7094-53-02004-3 doi: 10.1215/s0012-7094-53-02004-3
[14]	D. Hu, D. Cai, Adaptation and optimization of biological transport networks, Phys. Rev. Lett., 111 (2013), 138701. https://doi.org/10.1103/PhysRevLett.111.138701 doi: 10.1103/PhysRevLett.111.138701
[15]	D. Hu, D. Cai, An optimization principle for initiation and adaptation of biological transport networks, Comm. Math. Sci., 17 (2019), 1427–1436. https://doi.org/10.4310/CMS.2019.v17.n5.a12 doi: 10.4310/CMS.2019.v17.n5.a12
[16]	T. Kato, A Short Introduction to Perturbation Theory for Linear Operators, New York: Springer-Verlag, 1982.
[17]	M. Laguna, S. Bohn, E. Jagla, The Role of Elastic Stresses on Leaf Venation Morphogenesis, PLoS Comput. Biol., 4 (2008), e1000055. https://doi.org/10.1371/journal.pcbi.1000055 doi: 10.1371/journal.pcbi.1000055
[18]	P. Van Mieghem, Graph Spectra for Complex Networks, Cambridge: Cambridge University Press, 2010.
[19]	B. Mohar, Isoperimetric numbers of graphs, J Comb Theory B, 47 (1989), 274–291. https://doi.org/10.1016/0095-8956(89)90029-4 doi: 10.1016/0095-8956(89)90029-4
[20]	C. Murray, The physiological principle of minimum work. I. the vascular system and the cost of blood volume, Proc. Natl. Acad. Sci., 12 (1926), 207–214. https://doi.org/10.1073/pnas.12.3.207 doi: 10.1073/pnas.12.3.207
[21]	M. Oehlers, B. Fabian, Graph metrics for network robustness–A survey, Mathematics, 9 (2021). https://doi.org/10.3390/math908089
[22]	B. N. Parlett, The Symmetric Eigenvalue Problem, Hoboken: Prentice-Hall, 1980.
[23]	F. Rellich, Störungstheorie der Spektralzerlegung, Math. Ann., 117 (1940), 356–382.
[24]	A. Runions, M. Fuhrer, B. Lane, P. Federl, A. G. Rolland-Lagan, P. Prusinkiewicz, Modeling and visualization of leaf venation patterns, ACM T Graph., 24 (2005), 702–711. https://doi.org/10.1145/1073204.1073251 doi: 10.1145/1073204.1073251
[25]	N. Z. Shor, Minimization Methods for Non-differentiable Functions, Heidelberg: Springer Berlin, 1985.
[26]	P. Stechlinski, Generalized derivatives of eigenvalues of a symmetric matrix, Linear Algebra Appl, 649 (2022), 63–95. https://doi.org/10.1016/j.laa.2022.04.019 doi: 10.1016/j.laa.2022.04.019
[27]	J. Sterbenz, D. Hutchison, E. Cetinkaya, A. Jabbar, J. Rohrer, M. Schöller, et al., Resilience and survivability in communication networks: Strategies, principles, and survey of disciplines, Comput Netw, 54 (2010), 1245–1265. https://doi.org/10.1016/j.comnet.2010.03.005 doi: 10.1016/j.comnet.2010.03.005
[28]	G. W. Stewart, J. G. Sun, Matrix Perturbation Theory, Boston: Academic Press, 1990.
[29]	J. G. Sun, Multiple eigenvalue sensitivity analysis, Linear Algebra Appl, 137/138 (1990), 183–211. https://doi.org/10.1016/0024-3795(90)90129-Z doi: 10.1016/0024-3795(90)90129-Z
[30]	G. D. Yancopoulos, S. Davis, N. W. Gale, J. S. Rudge, S. J. Wiegand, J. Holash, Vascular-specific growth factors and blood vessel formation, Nature, 407 (2000), 242–248. https://doi.org/10.1038/35025215 doi: 10.1038/35025215

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)