‘Hubs-repelling’ Laplacian and related diffusion on graphs/networks. (English) Zbl 1435.05127
Summary: We define and study here a graph unsymmetric Laplacian matrix that operates a diffusive process biased towards low-degree nodes. We prove that this matrix is positive semidefine with all eigenvalues real. We also prove that the rate of convergence of a diffusive process controlled by the hubs-repelling Laplacian depends on the first nontrivial eigenvalue of this Laplacian. Such rate of convergence depends on the existence of low-degree nodes connected to high-degree ones. We find several bounds for the ‘algebraic connectivity’ based on this Laplacian. We then study two real-world scenarios with the hubs-repelling diffusion: the propagation of flight delays in the air transportation network of USA and the cost-efficient information diffusion across the human brain functional coactivation network. Finally, we find some conditions for the nodes of a network to be ‘good spreaders’ under the hubs-repelling dynamics.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 47N50 | Applications of operator theory in the physical sciences |
References:
| [1] | Avena-Koenigsberger, A.; Yan, X.; Kolchinsky, A.; Hagmann, P.; Sporns, O., A spectrum of routing strategies for brain networks, PLoS Comput. Biol., 15, Article e1006833 pp. (2019) |
| [2] | Banks, D. S.; Fradin, C., Anomalous diffusion of proteins due to molecular crowding, Biophys. J., 89, 2960-2971 (2005) |
| [3] | Batagelj, V.; Mrvar, A., Pajek Datasets (2006) |
| [4] | Black, F.; Scholes, M., The pricing of options and corporate liabilities, J. Polit. Econ., 81, 637-654 (1973) · Zbl 1092.91524 |
| [5] | Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U., Complex networks: structure and dynamics, Phys. Rep., 424, 175-308 (2006) · Zbl 1371.82002 |
| [6] | Bonaventura, M.; Nicosia, V.; Latora, V., Characteristic times of biased random walks on complex networks, Phys. Rev. E, 89, Article 012803 pp. (2014) |
| [7] | (Bunde, A.; Caro, J.; Kärger, J.; Vogl, G., Diffusive Spreading in Nature, Technology and Society (2017), Springer) · Zbl 1405.00009 |
| [8] | Burda, Z.; Duda, J.; Luck, J. M.; Waclaw, B., Localization of the maximum entropy random walk, Phys. Rev. Lett., 102, Article 160602 pp. (2009) |
| [9] | Crossley, N. A.; Mechelli, A.; Vértes, P. E.; Winton-Brown, T. T.; Patel, A. X.; Ginestet, C. E.; McGuire, P.; Bullmore, E. T., Cognitive relevance of the community structure of the human brain functional coactivation network, Proc. Natl. Acad. Sci. USA, 110, 11583-11588 (2013) |
| [10] | De Abreu, N. M., Old and new results on algebraic connectivity of graphs, Linear Algebra Appl., 423, 53-73 (2007) · Zbl 1115.05056 |
| [11] | Estrada, E., The Structure of Complex Networks: Theory and Applications (2012), Oxford University Press · Zbl 1267.05001 |
| [12] | Fiedler, M., Algebraic connectivity of graphs, Czechoslov. Math. J., 23, 298-305 (1973) · Zbl 0265.05119 |
| [13] | Fiedler, M., Laplacian of graphs and algebraic connectivity, Banach Cent. Publ., 25, 57-70 (1989) · Zbl 0731.05036 |
| [14] | Fleurquin, P.; Ramasco, J. J.; Eguiluz, V. M., Systemic delay propagation in the US airport network, Sci. Rep., 3, 1159 (2013) |
| [15] | Gerbaud, A.; Altisen, K.; Devismes, S.; Lafourcade, P., Comparison of mean hitting times for a degree-biased random walk, Discrete Appl. Math., 19, 104-109 (2014) · Zbl 1288.05253 |
| [16] | Grone, R.; Merris, R.; Sunder, V. S., The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl., 11, 218-238 (1990) · Zbl 0733.05060 |
| [17] | Grone, R.; Merris, R., The Laplacian spectrum of a graph II, SIAM J. Matrix Anal. Appl., 7, 221-229 (1994) · Zbl 0795.05092 |
| [18] | Masuda, N.; Porter, M. A.; Lambiotte, R., Random walks and diffusion on networks, Phys. Rep., 716, 1-58 (2017) · Zbl 1377.05180 |
| [19] | Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197, 143-176 (1994) · Zbl 0802.05053 |
| [20] | Merritt, D., Dynamics and Evolution of Galactic Nuclei, Princeton Series in Astrophysics (2013), Princeton University Press · Zbl 1276.85001 |
| [21] | Merton, R. C., Theory of Rational Option Pricing, in Theory of Valuation, 229-288 (2005), World Scientific |
| [22] | Mesbahi, M.; Egerstedt, M., Graph Theoretic Methods in Multiagent Networks (2010), Princeton University Press · Zbl 1203.93001 |
| [23] | Mohar, B., The Laplacian spectrum of graphs, (Alavi, Y.; Chartrand, G.; Oellermann, O. R.; Schwenk, A. J., Graph Theory, Combinatorics, and Applications, vol. 2 (1991), Wiley), 871-898 · Zbl 0840.05059 |
| [24] | Mondragón, R. J., Core-biased random walks in networks, J. Complex Netw., 6, 877-886 (2018) |
| [25] | Mugnolo, D., Semigroup Methods for Evolution Equations on Networks (2014), Springer International Publishing · Zbl 1306.47001 |
| [26] | Newman, M. E., The structure and function of complex networks, SIAM Rev., 45, 167-256 (2003) · Zbl 1029.68010 |
| [27] | Poignard, C.; Pereira, T.; Pade, J. P., Spectra of Laplacian matrices of weighted graphs: structural genericity properties, SIAM J. Appl. Math., 78, 372-394 (2018) · Zbl 1394.35298 |
| [28] | Rogers, E. M., Diffusion of Innovations (2003), Free Press |
| [29] | Seguin, C.; Van Den Heuvel, M. P.; Zalesky, A., Navigation of brain networks, Proc. Natl. Acad. Sci. USA, 115, 6297-6302 (2018) |
| [30] | Shiffler, R. E.; Harsha, P.d., Upper and lower bounds for the sample standard deviation, Teach. Stat., 2, 84-86 (1980) |
| [31] | Shiraishi, S.; Obata, T.; Daigo, M., Properties of a positive reciprocal matrix and their application to AHP, J. Oper. Res. Soc. Jpn., 4, 404-414 (1998) · Zbl 1003.15019 |
| [32] | Tomasi, D.; Wang, G. J.; Volkow, N. D., Energetic cost of brain functional connectivity, Proc. Natl. Acad. Sci. USA, 110, 13642-13647 (2013) |
| [33] | von Hansen, Y.; Sedlmeier, F.; Hinczewski, M.; Netz, R. R., Friction contribution to water-bond breakage kinetics, Phys. Rev. E, 84, Article 051501 pp. (2011) |
| [34] | Wu, C. W., Algebraic connectivity of directed graphs, Linear Multilinear Algebra, 53, 203-223 (2005) · Zbl 1065.05048 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
