×

Mittag-Leffler functions and their applications in network science. (English) Zbl 1490.33007

Summary: We describe a complete theory for walk-based centrality indices in complex networks defined in terms of Mittag-Leffler functions. This overarching theory includes as special cases well-known centrality measures like subgraph centrality and Katz centrality. The indices we introduce are parametrized by two numbers; by letting these vary, we show that Mittag-Leffler centralities interpolate between degree and eigenvector centrality, as well as between resolvent-based and exponential-based indices. We further discuss modelling and computational issues, and provide guidelines on parameter selection. The theory is then extended to the case of networks that evolve over time. Numerical experiments on synthetic and real-world networks are provided.

MSC:

33E12 Mittag-Leffler functions and generalizations
05C82 Small world graphs, complex networks (graph-theoretic aspects)
91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] L. Abadias, G. Estrada-Rodriguez, and E. Estrada, Fractional-order susceptible-infected model: definition and applications to the study of COVID-19 main protease, Fract. Calc. Appl. Anal., 23 (2020), pp. 635-655, https://doi.org/10.1515/fca-2020-0033. · Zbl 1488.92024
[2] M. Aprahamian, D. J. Higham, and N. J. Higham, Matching exponential-based and resolvent-based centrality measures, J. Complex Netw., 4 (2016), pp. 157-176, https://doi.org/10.1093/comnet/cnv016. · Zbl 1388.15012
[3] F. Arrigo and M. Benzi, Edge modification criteria for enhancing the communicability of digraphs, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 443-468, https://doi.org/10.1137/15M1034131. · Zbl 1336.05120
[4] F. Arrigo, M. Benzi, and C. Fenu, Computation of generalized matrix functions, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 836-860, https://doi.org/10.1137/15M1049634. · Zbl 1342.65121
[5] F. Arrigo, P. Grindrod, D. J. Higham, and V. Noferini, On the exponential generating function for non-backtracking walks, Linear Algebra Appl., 556 (2018), pp. 381-399, https://doi.org/10.1016/j.laa.2018.07.010. · Zbl 1394.05119
[6] F. Arrigo, D. J. Higham, and V. Noferini, Non-backtracking alternating walks, SIAM J. Appl. Math., 79 (2019), pp. 781-801, https://doi.org/10.1137/18M1183698. · Zbl 1422.05061
[7] F. Arrigo, D. J. Higham, and V. Noferini, Beyond non-backtracking: Non-cycling network centrality measures, Proc. A., 476 (2020), 20190653, https://doi.org/10.1098/rspa.2019.0653. · Zbl 1472.05081
[8] M. Ashtiani, A. Salehzadeh-Yazdi, Z. Razaghi-Moghadam, H. Hennig, O. Wolkenhauer, M. Mirzaie, and M. Jafari, A systematic survey of centrality measures for protein-protein interaction networks, BMC Syst. Biol., 12 (2018), 80, https://doi.org/10.1186/s12918-018-0598-2.
[9] J. L. Aurentz, A. P. Austin, M. Benzi, and V. Kalantzis, Stable computation of generalized matrix functions via polynomial interpolation, SIAM J. Matrix Anal. Appl., 40 (2019), pp. 210-234, https://doi.org/10.1137/18M1191786. · Zbl 1409.65030
[10] R. B. Bapat, Graphs and Matrices, Universitext, Springer, London; Hindustan Book Agency, New Delhi, 2010, https://doi.org/10.1007/978-1-84882-981-7. · Zbl 1248.05002
[11] B. Beckermann, D. Kressner, and M. Schweitzer, Low-rank updates of matrix functions, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 539-565, https://doi.org/10.1137/17M1140108. · Zbl 1390.15024
[12] M. Benzi, E. Estrada, and C. Klymko, Ranking hubs and authorities using matrix functions, Linear Algebra Appl., 438 (2013), pp. 2447-2474, https://doi.org/10.1016/j.laa.2012.10.022. · Zbl 1258.05067
[13] M. Benzi and C. Klymko, Total communicability as a centrality measure, J. Complex Netw., 1 (2013), pp. 124-149, https://doi.org/10.1093/comnet/cnt007.
[14] M. Benzi and C. Klymko, On the limiting behavior of parameter-dependent network centrality measures, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 686-706, https://doi.org/10.1137/130950550. · Zbl 1314.05113
[15] P. Boldi and S. Vigna, Axioms for centrality, Internet Math., 10 (2014), pp. 222-262, https://doi.org/10.1080/15427951.2013.865686. · Zbl 1461.91219
[16] P. Bonacich, Factoring and weighting approaches to status scores and clique identification, J. Math. Sociol., 2 (1972), pp. 113-120, https://doi.org/10.1080/0022250X.1972.9989806.
[17] P. Bonacich, Power and centrality: A family of measures, Am. J. Sociol., 92 (1987), pp. 1170-1182, https://doi.org/10.1086/228631.
[18] R. A. Brualdi, F. Harary, and Z. Miller, Bigraphs versus digraphs via matrices, J. Graph Theory, 4 (1980), pp. 51-73, https://doi.org/10.1002/jgt.3190040107. · Zbl 0401.05059
[19] T. A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Softw, 38 (2011), 1, https://doi.org/10.1145/2049662.2049663. · Zbl 1365.65123
[20] O. De la Cruz Cabrera, M. Matar, and L. Reichel, Analysis of directed networks via the matrix exponential, J. Comput. Appl. Math., 355 (2019), pp. 182-192, https://doi.org/10.1016/j.cam.2019.01.015. · Zbl 1417.90041
[21] E. Estrada, Generalized walks-based centrality measures for complex biological networks, J. Theoret. Biol., 263 (2010), pp. 556-565, https://doi.org/10.1016/j.jtbi.2010.01.014. · Zbl 1406.92239
[22] E. Estrada, The Structure of Complex Networks: Theory and Applications, Oxford University Press, Oxford, 2011.
[23] E. Estrada, Topological analysis of SARS CoV-2 main protease, Chaos, 30 (2020), 061102, https://doi.org/10.1063/5.0013029.
[24] E. Estrada and D. J. Higham, Network properties revealed through matrix functions, SIAM Rev., 52 (2010), pp. 696-714, https://doi.org/10.1137/090761070. · Zbl 1214.05077
[25] E. Estrada and J. A. Rodríguez-Velázquez, Subgraph centrality in complex networks, Phys. Rev. E, 71 (2005), 056103, https://doi.org/10.1103/PhysRevE.71.056103.
[26] E. Estrada and G. Silver, Accounting for the role of long walks on networks via a new matrix function, J. Math. Anal. Appl., 449 (2017), pp. 1581-1600. · Zbl 1355.05233
[27] C. Fenu, D. Martin, L. Reichel, and G. Rodriguez, Block Gauss and anti-Gauss quadrature with application to networks, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1655-1684, https://doi.org/10.1137/120886261. · Zbl 1425.65063
[28] R. Garrappa and M. Popolizio, Computing the matrix Mittag-Leffler function with applications to fractional calculus, J. Sci. Comput., 77 (2018), pp. 129-153, https://doi.org/10.1007/s10915-018-0699-5. · Zbl 1406.65031
[29] R. Gorenflo, A. A. Kilbas, F. Mainardi, and S. V. Rogosin, Mittag-Leffler Functions, Related Topics and Applications, Springer Monogr. Math., Springer, Heidelberg, 2014, https://doi.org/10.1007/978-3-662-43930-2. · Zbl 1309.33001
[30] P. Grindrod and D. J. Higham, A dynamical systems view of network centrality, Proc. R. Soc. A., 470 (2014), 20130835, https://doi.org/10.1098/rspa.2013.0835. · Zbl 1371.90039
[31] P. Grindrod, M. C. Parsons, D. J. Higham, and E. Estrada, Communicability across evolving networks, Phys. Rev. E, 83 (2011), 046120, https://doi.org/10.1103/PhysRevE.83.046120.
[32] J. B. Hawkins and A. Ben-Israel, On generalized matrix functions, Linear Multilinear Algebra, 1 (1973), pp. 163-171. · Zbl 0291.15004
[33] N. J. Higham, Functions of Matrices: Theory and Computation, SIAM, Philadelphia, 2008, https://doi.org/10.1137/1.9780898717778. · Zbl 1167.15001
[34] P. Holme, Congestion and centrality in traffic flow on complex networks, Adv. Complex Syst., 06 (2003), pp. 163-176, https://doi.org/10.1142/S0219525903000803. · Zbl 1203.90047
[35] P. Holme and J. Saramäki, Temporal networks, Phys. Rep., 519 (2012), pp. 97-125, https://doi.org/10.1016/j.physrep.2012.03.001.
[36] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, Cambridge, 2013. · Zbl 1267.15001
[37] L. Katz, A new status index derived from sociometric analysis, Psychometrika, 18 (1953), pp. 39-43. · Zbl 0053.27606
[38] M. G. Kendall, Rank correlation methods., Rank Correlation Methods, Griffin, Oxford, UK, 1948. · Zbl 0032.17602
[39] G. M. Mittag-Leffler, Sur la nouvelle fonction \(e_\alpha(x)\), C.R. Acad. Sci. Paris, 137 (1903), pp. 554-558. · JFM 34.0435.01
[40] C. Moler and C. Van Loan, Nineteen dubious ways to compute the exponential of a matrix, SIAM Rev., 20 (1978), pp. 801-836, https://doi.org/10.1137/1020098. · Zbl 0395.65012
[41] I. Moret and P. Novati, On the convergence of Krylov subspace methods for matrix Mittag-Leffler functions, SIAM J. Numer. Anal., 49 (2011), pp. 2144-2164, https://doi.org/10.1137/080738374. · Zbl 1244.65065
[42] I. Moret and M. Popolizio, The restarted shift-and-invert Krylov method for matrix functions, Numer. Linear Algebra Appl., 21 (2014), pp. 68-80, https://doi.org/10.1002/nla.1862. · Zbl 1324.65079
[43] M. Newman, Networks, 2nd ed., Oxford University Press, Oxford, 2018, https://doi.org/10.1093/oso/9780198805090.001.0001. · Zbl 1391.94006
[44] V. Noferini, A formula for the Fréchet derivative of a generalized matrix function, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 434-457, https://doi.org/10.1137/16M1072851. · Zbl 1367.65071
[45] S. Pozza and F. Tudisco, On the stability of network indices defined by means of matrix functions, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 1521-1546, https://doi.org/10.1137/17M1133920. · Zbl 1401.65050
[46] A. Stomakhin, M. B. Short, and A. L. Bertozzi, Reconstruction of missing data in social networks based on temporal patterns of interactions, Inverse Problems, 27 (2011), 115013, https://doi.org/10.1088/0266-5611/27/11/115013.
[47] D. L. Vargas, A. M. Bridgeman, D. R. Schmidt, P. B. Kohl, B. R. Wilcox, and L. D. Carr, Correlation between student collaboration network centrality and academic performance, Phys. Rev. Phys. Educ. Res., 14 (2018), 020112, https://doi.org/10.1103/PhysRevPhysEducRes.14.020112.
[48] S. Vigna, Spectral ranking, Netw. Sci., 4 (2016), pp. 433-445, https://doi.org/10.1017/nws.2016.21.
[49] A. Voltes-Dorta, H. Rodríguez-Déniz, and P. Suau-Sanchez, Vulnerability of the European air transport network to major airport closures from the perspective of passenger delays: Ranking the most critical airports, Transp. Res. Part A Policy Pract., 96 (2017), pp. 119-145, https://doi.org/10.1016/j.tra.2016.12.009.
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.