Diffusion is a ubiquitous process in real-world syetems. In many complex systems, ranging from neuronal networks to traffic in cities, diffusion is nonconservative (NC) in the sense that diffusive particles can be created/annihilated at the entities of the system. Here, we consider the important problem of identifying potential navigational bottlenecks in NC diffusion occurring in the networks representing skeletons of complex systems. We develop a first-principles approach based on an NC diffusion using the Lerman-Ghosh Laplacian on graphs. By solving analytically this NC diffusion equation at two different times, we get an index which characterizes the capacity of every vertex in a network to spread the diffusive particles across the network in a short time. Vertices having such capacity diminished are potential navigational bottlenecks in this kind of dynamics. We solve analytically the situations in which the vertices with the highest degree (hubs) are at different distances in the network, allowing us to understand the structural significance of the index. Using algebraic methods, we derive a Euclidean distance between vertices in the context of NC diffusion with potential navigational bottlenecks. We then apply these indices to study several real-world networks. First, we confronted our theoretical results with experimental data about traffic congestion in a city. Then, we illustrated the application of the new methodologies to the study of a neuronal system, an air transportation network and two urban street networks.
Citation: Giovanni G. Soares, Ernesto Estrada. Navigational bottlenecks in nonconservative diffusion dynamics on networks[J]. AIMS Mathematics, 2024, 9(9): 24297-24325. doi: 10.3934/math.20241182
Diffusion is a ubiquitous process in real-world syetems. In many complex systems, ranging from neuronal networks to traffic in cities, diffusion is nonconservative (NC) in the sense that diffusive particles can be created/annihilated at the entities of the system. Here, we consider the important problem of identifying potential navigational bottlenecks in NC diffusion occurring in the networks representing skeletons of complex systems. We develop a first-principles approach based on an NC diffusion using the Lerman-Ghosh Laplacian on graphs. By solving analytically this NC diffusion equation at two different times, we get an index which characterizes the capacity of every vertex in a network to spread the diffusive particles across the network in a short time. Vertices having such capacity diminished are potential navigational bottlenecks in this kind of dynamics. We solve analytically the situations in which the vertices with the highest degree (hubs) are at different distances in the network, allowing us to understand the structural significance of the index. Using algebraic methods, we derive a Euclidean distance between vertices in the context of NC diffusion with potential navigational bottlenecks. We then apply these indices to study several real-world networks. First, we confronted our theoretical results with experimental data about traffic congestion in a city. Then, we illustrated the application of the new methodologies to the study of a neuronal system, an air transportation network and two urban street networks.
| [1] | E. Estrada, The structure of complex networks: Theory and applications, New York: Oxford University Press, 2012. |
| [2] | E. Estrada, What is a complex system, after all? Found. Sci., 2023, 1–28. https://doi.org/10.1007/s10699-023-09917-w |
| [3] |
S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D. U. Hwang, Complex networks: Structure and dynamics, Phys. Rep., 424 (2006), 175–308. https://doi.org/10.1016/j.physrep.2005.10.009 doi: 10.1016/j.physrep.2005.10.009
|
| [4] |
L. D. Costa, O. N. Oliveira Jr, G. Travieso, F. A. Rodrigues, P. R. Villas Boas, L. Antiqueira, et al., Analyzing and modeling real-world phenomena with complex networks: A survey of applications, Adv. Phys., 60 (2011), 329–412. https://doi.org/10.1080/00018732.2011.572452 doi: 10.1080/00018732.2011.572452
|
| [5] |
L. Zhao, J. Zhao, Comparison study of three shortest path algorithm, Proc. Int. Conf. Comput. Technol. Eléctron. Commun. (ICCTEC), 3 (2017), 748–751. https://doi.org/10.1109/ICCTEC.2017.00165 doi: 10.1109/ICCTEC.2017.00165
|
| [6] | B. Golden, Shortest-path algorithms: A comparison, Op. Res., 24 (1976), 1164–1168. |
| [7] |
X. Z. Wang, The comparison of three algorithms in shortest path issue, J. Phys. Conf. Ser., 1087 (2018). https://dx.doi.org/10.1088/1742-6596/1087/2/022011 doi: 10.1088/1742-6596/1087/2/022011
|
| [8] |
J. Liu, M. Li, Y. Pan, W. Lan, R. Zheng, F. X. Wu, et al., Complex brain network analysis and its applications to brain disorders: A survey, Complexity, 2017 (2017), 1–27. https://doi.org/10.1155/2017/8362741 doi: 10.1155/2017/8362741
|
| [9] | J. Goñi, A. Avena-Koenigsberger, N. Velez de Mendizabal, M. P. van den Heuvel, R. F. Betzel, O. Sporns, Exploring the morphospace of communication efficiency in complex networks, PLoS One, 8 (2013). https://doi.org/10.1371/journal.pone.0058070 |
| [10] |
M. Boguna, D. Krioukov, K. C. Claffy, Navigability of complex networks, Nature Phys., 5 (2009), 74–80. https://doi.org/10.1038/nphys1130 doi: 10.1038/nphys1130
|
| [11] |
E. Estrada, Informational cost and networks navigability, App. Math. Comp., 397 (2021), 1–10. https://doi.org/10.1016/j.amc.2020.125914 doi: 10.1016/j.amc.2020.125914
|
| [12] |
C. Seguin, M. P. Van Den Heuvel, A. Zalesky, Navigation of brain networks, Proc. Natl. Acad. Sci., 115 (2018), 6297–6302. https://doi.org/10.1073/pnas.1801351115 doi: 10.1073/pnas.1801351115
|
| [13] |
M. Rosvall, A. Grönlund, P. Minnhagen, K. Sneppen, Searchability of networks, Phys. Rev. E, 72 (2005). https://doi.org/10.1103/PhysRevE.72.046117 doi: 10.1103/PhysRevE.72.046117
|
| [14] |
E. Estrada, J. Gómez-Gardeñes, L. Lacasa, Network bypasses sustain complexity, Proc. Natl. Acad. Sci., 120 (2023). https://doi.org/10.1073/pnas.2305001120 doi: 10.1073/pnas.2305001120
|
| [15] |
C. Seguin, O. Sporns, A. Zalesky, Brain network communication: concepts, models and applications, Nat. Rev. Neurosci., 24 (2023), 557–574. https://doi.org/10.1038/s41583-023-00718-5 doi: 10.1038/s41583-023-00718-5
|
| [16] | A. Avena-Koenigsberger, X. Yan, A. Kolchinsky, M. P. van den Heuvel, P. Hagmann, O. Sporns, A spectrum of routing strategies for brain networks, PLoS Comput. Biol., 15 (2019). https://doi.org/10.1371/journal.pcbi.1006833 |
| [17] |
N. Masuda, M. A. Porter, R. Lambiotte, Random walks and diffusion on networks, Phys. Rep., 716-717 (2017), 1–58 https://doi.org/10.1016/j.physrep.2017.07.007 doi: 10.1016/j.physrep.2017.07.007
|
| [18] |
I. Simonsen, Diffusion and networks: A powerful combination! Physica A, 357 (2005), 317–330. https://doi.org/10.1016/j.physa.2005.06.032 doi: 10.1016/j.physa.2005.06.032
|
| [19] | R. Kasprzak, Diffusion in networks, J. Telecommun. Inf. Technol., 2012, 99–106. |
| [20] |
W. Yu, G. Chen, M. Cao, Consensus in directed networks of agents with nonlinear dynamics, IEEE Trans. Automat. Contr., 56 (2011), 1436–1441. https://doi.org/10.1109/TAC.2011.2112477 doi: 10.1109/TAC.2011.2112477
|
| [21] | R. O. Saber, R. M. Murray, Consensus protocols for networks of dynamic agents, Proc. Am. Control. Conf., 2 (2003), 951–956. |
| [22] | M. Mesbahi, Graph theoretic methods in multiagent networks, Princeton University Press, 2010. |
| [23] | E. Estrada, Conservative vs. non-conservative diffusion towards a target in a networked environment, The target problem, Springer, Berlin, 2024 |
| [24] |
J. Tønnesen, S. Hrabĕtová, F. N. Soria, Local diffusion in the extracellular space of the brain, Neurobiol. Dis., 177 (2023), 105981. https://doi.org/10.1016/j.nbd.2022.105981 doi: 10.1016/j.nbd.2022.105981
|
| [25] |
C. Nicholson, Diffusion and related transport mechanisms in brain tissue, Rep. Prog. Phys., 64 (2001), 815–885. https://iopscience.iop.org/article/10.1088/0034-4885/64/7/202 doi: 10.1088/0034-4885/64/7/202
|
| [26] |
L. F. Agnati, D. Guidolin, M. Guescini, S. Genedani, K. Fuxe, Understanding wiring and volume transmission, Brain Res. Rev., 64 (2010), 137–159. https://doi.org/10.1016/j.brainresrev.2010.03.003 doi: 10.1016/j.brainresrev.2010.03.003
|
| [27] |
L. Liu, J. Tang, J. Han, S. Yang, Learning influence from heterogeneous social networks, Data Min. Knowl. Discov., 25 (2012), 511–544. https://doi.org/10.1007/s10618-012-0252-3 doi: 10.1007/s10618-012-0252-3
|
| [28] |
A. Zeng, C. H. Yeung, Predicting the future trend of popularity by network diffusion, Chaos, 26 (2016), 063102. https://doi.org/10.1063/1.4953013 doi: 10.1063/1.4953013
|
| [29] |
L. A. Overbey, B. Greco, C. Paribello, T. Jackson, Structure and prominence in Twitter networks centered on contentious politics, Soc. Netw. Anal. Min., 3 (2013), 1351–1378. https://doi.org/10.1007/s13278-013-0134-8 doi: 10.1007/s13278-013-0134-8
|
| [30] | S. Goel, D. J. Watts, D. G. Goldstein, The structure of online diffusion networks, Proc. 13th ACM Conf. Elect. Comm., 2012,623–638. https://doi.org/10.1145/2229012.2229058 |
| [31] |
J. Long, Z. Gao, H. Ren, A. Lian, Urban traffic congestion propagation and bottleneck identification, Sci. China. Ser. F-Inf. Sci., 51 (2008), 948–964. https://doi.org/10.1007/s11432-008-0038-9 doi: 10.1007/s11432-008-0038-9
|
| [32] |
J. Wang, Resilience of self-organised and top-down planned cities–-a case study on London and Beijing street networks, PloS One, 10 (2015), e0141736. https://doi.org/10.1371/journal.pone.0141736 doi: 10.1371/journal.pone.0141736
|
| [33] |
J. Buhl, J. Gautrais, N. Reeves, R. V. Solé, S. Valverde, P. Kuntz, et al., Topological patterns in street networks of self-organized urban settlements, Eur. Phys. J. B, 49 (2006), 513–522. https://doi.org/10.1140/epjb/e2006-00085-1 doi: 10.1140/epjb/e2006-00085-1
|
| [34] | A. Furno, N. E. El Faouzi, R. Sharma, V. Cammarota, E. Zimeo, A graph-based framework for real-time vulnerability assessment of road networks, Proc. Int. Conf. Smart. Comput. SMARTCOMP, 2018,234–241. |
| [35] |
P. Medina, S. C. Carrasco, M. S. Jofré, J. Rogan, J. A. Valdivia, Characterizing diffusion processes in city traffic, Chaos Soliton. Fract., 165 (2022), 112846. https://doi.org/10.1016/j.chaos.2022.112846 doi: 10.1016/j.chaos.2022.112846
|
| [36] | S. S. Kim, M. Chung, Y. K. Kim, Urban traffic prediction using congestion diffusion model, Proc. IEEE Int. Conf. Consum. Electron-Asia (ICCE-Asia), 2020, 1–4. |
| [37] | T. Anwar, C. Liu, L. V. Hai, M. S. Islam, Roadrank: Traffic diffusion and influence estimation in dynamic urban road networks, Proc. ACM Int. Conf. Inf. Knowl. Manag., 2015, 1671–1674. |
| [38] |
A. Bhaskar, T. Tsubota, E. Chung, Urban traffic state estimation: Fusing point and zone based data, Transport. Res. C Emer., 48 (2014), 120–142. https://doi.org/10.1016/j.trc.2014.08.015 doi: 10.1016/j.trc.2014.08.015
|
| [39] |
A. Bhaskar, E. Chung, A. G. Dumont, Estimation of travel time on urban networks with midlink sources and sinks. Transp. Res. Rec., 2121 (2009), 41–54. https://doi.org/10.3141/2121-05 doi: 10.3141/2121-05
|
| [40] |
Å. Brännström, D. J. Sumpter, Coupled map lattice approximations for spatially explicit individual-based models of ecology, Bull. Math. Biol., 67 (2005), 663–682. https://doi.org/10.1016/j.bulm.2004.09.006 doi: 10.1016/j.bulm.2004.09.006
|
| [41] |
K. H. Taber, R. A. Hurley, Volume transmission in the brain: Beyond the synapse, J. Neuropsychiatry. Clin. Neurosci., 26 (2014), E01–104. https://doi.org/10.1176/appi.neuropsych.13110351 doi: 10.1176/appi.neuropsych.13110351
|
| [42] |
K. Fuxe, D. O. Borroto-Escuela, A. Tarakanov, W. R. Fernandez, P. Manger, A. Rivera, K. van Craenenbroeck, et al., Understanding the balance and integration of volume and synaptic transmission. Relevance for psychiatry, Neurol. Psychiat. B. R., 19 (2013), 141–158. https://doi.org/10.1016/j.npbr.2013.10.002 doi: 10.1016/j.npbr.2013.10.002
|
| [43] |
E. Sykova, Extrasynaptic volume transmission and diffusion parameters of the extracellular space, Neuroscience, 129 (2004), 861–876. https://doi.org/10.1016/j.neuroscience.2004.06.077 doi: 10.1016/j.neuroscience.2004.06.077
|
| [44] |
D. O. Borroto-Escuela, M. P. De La Mora, P. Manger, M. Narvaez, S. Beggiato, M. Crespo-Ramírez, et al., Brain dopamine transmission in health and parkinson's disease: Modulation of synaptic transmission and plasticity through volume transmission and dopamine heteroreceptors, Front. Synaptic Neurosci., 10 (2018), 20. https://doi.org/10.3389/fnsyn.2018.00020 doi: 10.3389/fnsyn.2018.00020
|
| [45] |
K. Wiencke, A. Horstmann, D. Mathar, A. Villringer, J. Neumann, Dopamine release, diffusion and uptake: A computational model for synaptic and volume transmission, PLoS Comput. Biol., 16 (2020), e1008410. https://doi.org/10.1371/journal.pcbi.1008410 doi: 10.1371/journal.pcbi.1008410
|
| [46] |
H. Xiong, E. Lacin, H. Ouyang, A. Naik, X. Q. Xu, C. Xie, et al., Probing neuropeptide volume transmission in vivo by simultaneous near-infrared light-triggered release and optical sensing, Angew. Chem. Int. Ed. Engl., 61 (2022), e202206122. https://doi.org/10.1101/2021.09.10.459853 doi: 10.1101/2021.09.10.459853
|
| [47] |
H. Hamedmoghadam, M. Jalili, H. L. Vu, L. Stone, Percolation of heterogeneous flows uncovers the bottlenecks of infrastructure networks, Nat. Commun., 12 (2021), 1254. https://doi.org/10.1038/s41467-021-21483-y doi: 10.1038/s41467-021-21483-y
|
| [48] |
P. A. Witte, B. W. Wiegmans, F. G. van Oort, T. J. Spit, Chokepoints in corridors: Perspectives on bottlenecks in the European transport network, Res. Transp. Bus. Manag., 5 (2012), 57–66. https://doi.org/10.1016/j.rtbm.2012.10.001 doi: 10.1016/j.rtbm.2012.10.001
|
| [49] |
W. H. Lee, S. S. Tseng, J. L. Shieh, H. H. Chen, Discovering traffic bottlenecks in an urban network by spatiotemporal data mining on location-based services, IEEE Trans. Intell. Transp. Syst., 12 (2011), 1047–1056. https://doi.org/10.1109/TITS.2011.2144586 doi: 10.1109/TITS.2011.2144586
|
| [50] |
C. Li, W. Yue, G. Mao, Z. Xu, Congestion propagation based bottleneck identification in urban road networks, IEEE Trans. Veh. Technol., 69 (2020), 4827–4841. https://doi.org/10.1109/TVT.2020.2973404 doi: 10.1109/TVT.2020.2973404
|
| [51] |
X. He, C. Papadopoulos, J. Heidemann, U. Mitra, U. Riaz, Remote detection of bottleneck links using spectral and statistical methods, Comput. Netw., 53 (2009), 279–298. https://doi.org/10.1016/j.comnet.2008.10.001 doi: 10.1016/j.comnet.2008.10.001
|
| [52] |
Q. K. Qu, F. J. Chen, X. J. Zhou, Road traffic bottleneck analysis for expressway for safety under disaster events using blockchain machine learning, Saf. Sci., 118 (2019), 925–932. https://doi.org/10.1016/j.ssci.2019.06.030 doi: 10.1016/j.ssci.2019.06.030
|
| [53] |
S. Sreenivasan, R. Cohen, E. López, Z. Toroczkai, H. E. Stanley, Structural bottlenecks for communication in networks, Phys. Rev. E, 75 (2007), 036105. https://doi.org/10.1103/PhysRevE.75.036105 doi: 10.1103/PhysRevE.75.036105
|
| [54] |
R. Banner, A. Orda, Bottleneck routing games in communication networks, IEEE J. Sel. Areas Commun., 25 (2007), 1173–1179. https://doi.org/10.1109/JSAC.2007.070811 doi: 10.1109/JSAC.2007.070811
|
| [55] |
N. Hu, L. Li, Z. M. Mao, P. Steenkiste, J. Wang, Locating internet bottlenecks: Algorithms, measurements, and implications, ACM Sigcomm. Comp. Com., 34 (2004), 41–54. https://doi.org/10.1145/1030194.1015474 doi: 10.1145/1030194.1015474
|
| [56] |
P. Bonacich, Factoring and weighting approaches to status scores and clique identification, J. Math. Sociol., 2 (1972), 113–120. https://doi.org/10.1080/0022250X.1972.9989806 doi: 10.1080/0022250X.1972.9989806
|
| [57] |
P. Bonacich, Power and centrality: A Family of measures, Am. J. Sociol., 92 (1987), 1170–1182. https://doi.org/10.1086/228631 doi: 10.1086/228631
|
| [58] |
P. Bonacich, Some unique properties of eigenvector centrality, Soc. Networks, 29 (2007), 555–564. https://doi.org/10.1016/j.socnet.2007.04.002 doi: 10.1016/j.socnet.2007.04.002
|
| [59] |
E. Estrada, The communicability distance in graphs, Linear Algebra Appl., 436 (2012), 4317–4328. https://doi.org/10.1016/j.laa.2012.01.017 doi: 10.1016/j.laa.2012.01.017
|
| [60] |
E. Estrada, M. G. Sanchez-Lirola, J. A. De La Peña, Hyperspherical embedding of graphs and networks in communicability spaces, Discrete Appl. Math., 176 (2014), 53–77. https://doi.org/10.1016/j.dam.2013.05.032 doi: 10.1016/j.dam.2013.05.032
|
| [61] |
E. Estrada, N. Hatano, Communicability angle and the spatial efficiency of networks, SIAM Rev. Soc. Ind. Appl. Math., 58 (2016), 692–715. https://doi.org/10.1137/141000555 doi: 10.1137/141000555
|
| [62] |
E. Estrada, Every nonsingular spherical Euclidean distance matrix is a resistance distance matrix, Linear Algebra Appl., 656 (2023), 198–209. https://doi.org/10.1016/j.laa.2022.09.025 doi: 10.1016/j.laa.2022.09.025
|
| [63] |
G. Boeing, OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks, Comput. Environ. Urban. Syst., 65 (2017), 126–139. https://doi.org/10.1016/j.compenvurbsys.2017.05.004 doi: 10.1016/j.compenvurbsys.2017.05.004
|
| [64] |
R. Ghosh, K. Lerman, Parameterized centrality metric for network analysis, Phys. Rev. E, 83 (2011), 066118. https://link.aps.org/doi/10.1103/PhysRevE.83.066118 doi: 10.1103/PhysRevE.83.066118
|
| [65] |
R. Ghosh, K. Lerman, T. Surachawala, K. Voevodski, S. Teng, Non-conservative diffusion and its application to social network analysis, J. Complex. Netw., 12 (2024), cnae006. https://doi.org/10.48550/arXiv.1102.4639 doi: 10.48550/arXiv.1102.4639
|
| [66] |
E. Estrada, J. A. Rodriguez-Velazquez, Subgraph centrality in complex networks, Phys. Rev. E, 71 (2005), 056103. https://link.aps.org/doi/10.1103/PhysRevE.71.056103 doi: 10.1103/PhysRevE.71.056103
|
| [67] |
E. Estrada, N. Hatano, Communicability in complex networks, Phys. Rev. E, 77 (2008), 036111. https://link.aps.org/doi/10.1103/PhysRevE.77.036111 doi: 10.1103/PhysRevE.77.036111
|
| [68] |
E. Estrada, N. Hatano, M. Benzi, The physics of communicability in complex networks, Physics Rep., 514 (2012), 89–119. https://doi.org/10.1016/j.physrep.2012.01.006 doi: 10.1016/j.physrep.2012.01.006
|
| [69] |
A. R. Samani, S. N. Shetab-Boushehri, R. Mahmoudi, Reliable urban transportation network design problem considering recurrent traffic congestions, Adv. Ind. Eng., 55 (2021), 69–89. https://doi.org/10.22059/jieng.2021.326142.1784 doi: 10.22059/jieng.2021.326142.1784
|
Figures(9) / Tables(1)
Giovanni G. Soares, Ernesto Estrada. Navigational bottlenecks in nonconservative diffusion dynamics on networks[J]. AIMS Mathematics, 2024, 9(9): 24297-24325. doi: 10.3934/math.20241182
DownLoad: