A comparison of centrality measures and their role in controlling the spread in epidemic networks

References

• Aldous, D., & Fill, J. A. (2002). Reversible Markov chains and random walks on graphs. Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/aldous/RWG/book.html.
   Google Scholar
• Amaku, M., Covas, D. T., Coutinho, F. A. B., Neto, R. S. A., Struchiner, C., Wilder-Smith, A., & Massad, E. (2021). Modelling the test, trace and quarantine strategy to control the COVID-19 epidemic in the state of São Paulo, Brazil. Infectious Disease Modelling, 6, 46–55. https://doi.org/10.1016/j.idm.2020.11.004
   PubMedGoogle Scholar
• Barabási, A.-L. (2016). Network science. Cambridge University Press.
   Google Scholar
• Barrat, A., Barthélemy, M., Pastor-Satorras, R., & Vespignani, A. (2004). The architecture of complex weighted networks. Proceedings of the National Academy of Sciences, 101(11), 3747–3752. https://doi.org/10.1073/pnas.0400087101.
   PubMed Web of Science ®Google Scholar
• Bastani, H., Drakopoulos, K., Gupta, V., Vlachogiannis, I., Hadjicristodoulou, C., Lagiou, P., Magiorkinis, G., Paraskevis, D., & Tsiodras, S. (2021). Efficient and targeted COVID-19 border testing via reinforcement learning. Nature, 599(7883), 108–113. https://doi.org/10.1038/s41586-021-04014-z
   PubMed Web of Science ®Google Scholar
• Bin, M., Cheung, P. Y. K., Crisostomi, E., Ferraro, P., Lhachemi, H., Murray-Smith, R., Myant, C., Parisini, T., Shorten, R., Stein, S., Stone, L., & Pascual, M. (2021). Post-lockdown abatement of COVID-19 by fast periodic switching. PLoS Computational Biology, 17(1), e1008604. https://doi.org/10.1371/journal.pcbi.1008604
   PubMed Web of Science ®Google Scholar
• Borgatti, S. P. (2006). Identifying sets of key players in a social network. Computational & Mathematical Organization Theory, 12(1), 21–34. https://doi.org/10.1007/s10588-006-7084-x
   Google Scholar
• Bovet, A., & Makse, H. A. (2019). Influence of fake news in twitter during the 2016 US presidential election. Nature Communications, 10(1), 1–14. https://doi.org/10.1038/s41467-018-07761-2
   PubMed Web of Science ®Google Scholar
• Breen, J., Crisostomi, E., Faizrahnemoon, M., Kirkland, S., & Shorten, R. (2018). Clustering behaviour in Markov chains with eigenvalues close to one. Linear Algebra and Its Applications, 555, 163–185. https://doi.org/10.1016/j.laa.2018.06.013.
   Web of Science ®Google Scholar
• Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 30(1), 107–117. https://doi.org/10.1016/S0169-7552(98)00110-X.
   Web of Science ®Google Scholar
• Castellano, C., & Pastor-Satorras, R. (2017). Relating topological determinants of complex networks to their spectral properties: Structural and dynamical effects. Physical Review X, 7(4), 041024. https://doi.org/10.1103/PhysRevX.7.041024
   Web of Science ®Google Scholar
• Choi, W., & Shim, E. (2021). Optimal strategies for social distancing and testing to control COVID-19. Journal of Theoretical Biology, 512, 110568. https://doi.org/10.1016/j.jtbi.2020.110568
   PubMed Web of Science ®Google Scholar
• Chung, F. R. K., & Graham, F. C. (1997). Spectral graph theory. American Mathematical Soc.
   Google Scholar
• Crisostomi, E., Kirkland, S., & Shorten, R. (2011). A google-like model of road network dynamics and its application to regulation and control. International Journal of Control, 84(3), 633–651. https://doi.org/10.1080/00207179.2011.568005.
   Web of Science ®Google Scholar
• de Abreu, N. M. M. (2007). Old and new results on algebraic connectivity of graphs. Linear Algebra and Its Applications, 423(1), 53–73. https://doi.org/10.1016/j.laa.2006.08.017.
   Web of Science ®Google Scholar
• Doyle, P. G. (2009). The Kemeny constant of a Markov chain. arXiv preprint arXiv:0909.2636 [math]. Retrieved May 17, 2021, from http://arxiv.org/abs/0909.2636.
   Google Scholar
• Doyle, P. G., & Snell, J. L. (1984). Random walks and electric networks (Vol. 22). American Mathematical Soc.
   Google Scholar
• Fiedler, M. (1989). Laplacian of graphs and algebraic connectivity. Banach Center Publications, 25(1), 57–70. https://doi.org/10.4064/-25-1-57-70Retrieved May 17, 2021, from https://eudml.org/doc/267812
   Google Scholar
• Fouss, F., Saerens, M., & Shimbo, M. (2016). Algorithms and models for network data and link analysis. Cambridge University Press.
   Google Scholar
• Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1), 35–41. https://doi.org/10.2307/3033543.
   Google Scholar
• Freeman, L. C. (1978). Centrality in social networks conceptual clarification. Social Networks, 1(3), 215–239. https://doi.org/10.1016/0378-8733(78)90021-7.
   Web of Science ®Google Scholar
• Ghalmane, Z., El Hassouni, M., & Cherifi, H. (2019). Immunization of networks with non-overlapping community structure. Social Network Analysis and Mining, 9(1), 1–22. https://doi.org/10.1007/s13278-019-0591-9
   Web of Science ®Google Scholar
• Giordano, G., Blanchini, F., Bruno, R., Colaneri, P., Di Filippo, A., Di Matteo, A., & Colaneri, M. (2020). Modelling the COVID-19 epidemic and implementation of population-wide interventions in italy. Nature Medicine, 26(6), 855–860. https://doi.org/10.1038/s41591-020-0883-7
   PubMed Web of Science ®Google Scholar
• Gómez, S. (2019). Centrality in networks: Finding the most important nodes. In P. Moscato, and N. J. de Vries, (Eds.), Business and Consumer Analytics: New Ideas (pp. 401–433). Springer International Publishing. https://doi.org/10.1007/978-3-030-06222-48
   Google Scholar
• Goodman-Meza, D., Rudas, A., Chiang, J. N., Adamson, P. C., Ebinger, J., Sun, N., Botting, P., Fulcher, J. A., Saab, F. G., Brook, R., Eskin, E., An, U., Kordi, M., Jew, B., Balliu, B., Chen, Z., Hill, B. L., Rahmani, E., Halperin, E., …Urbanowicz, R. J. (2020). A machine learning algorithm to increase COVID-19 inpatient diagnostic capacity. PLoS ONE, 15(9), e0239474. https://doi.org/10.1371/journal.pone.0239474
   PubMed Web of Science ®Google Scholar
• Hartfiel, D. J., & Meyer, C. D. (1998). On the structure of stochastic matrices with a subdominant eigenvalue near 1. Linear Algebra and Its Applications, 272(1), 193–203. https://doi.org/10.1016/S0024-3795(97)00333-9.
   Web of Science ®Google Scholar
• Hufnagel, L., Brockmann, D., & Geisel, T. (2004). Forecast and control of epidemics in a globalized world. Proceedings of the National Academy of Sciences, 101(42), 15124–15129. https://doi.org/10.1073/pnas.0308344101.
   PubMed Web of Science ®Google Scholar
• Johnson, B. C., & Kirkland, S. (2019). Estimating random walk centrality in networks. Computational Statistics & Data Analysis, 138, 190–200. https://doi.org/10.1016/j.csda.2019.04.009.
   Web of Science ®Google Scholar
• Kamp, C., Moslonka-Lefebvre, M., & Alizon, S. (2013). Epidemic spread on weighted networks. PLoS Computational Biology, 9(12), e1003352. https://doi.org/10.1371/journal.pcbi.1003352
   PubMed Web of Science ®Google Scholar
• Kemeny, J., & Snell, L. (1960). Finite Markov chains. Van Nostrand.
   Google Scholar
• Kirkland, S. (2016). Random walk centrality and a partition of Kemeny's constant. Czechoslovak Mathematical Journal, 66(3), 757–775. https://doi.org/10.1007/s10587-016-0291-9.
   Web of Science ®Google Scholar
• Klein, D. J., & Randić, M. (1993). Resistance distance. Journal of Mathematical Chemistry, 12(1), 81–95. https://doi.org/10.1007/BF01164627.
   Web of Science ®Google Scholar
• Koeth, F. (2019). Graphs, networks and power systems. Retrieved May 17, 2021, from https://www.incite-itn.eu/blog/graphs-networks-and-power-systems/.
   Google Scholar
• Langville, A. N., & Meyer, C. D. (2006). Google's PageRank and beyond – the science of search engine rankings. Princeton University Press.
   Google Scholar
• Levene, M., & Loizou, G. (2002). Kemeny's constant and the random surfer. The American Mathematical Monthly, 109(8), 741–745. https://doi.org/10.1080/00029890.2002.11919905.
   Web of Science ®Google Scholar
• Lyng, G. D., Sheils, N. E., Kennedy, C. J., Griffin, D. O., & Berke, E. M. (2021). Identifying optimal COVID-19 testing strategies for schools and businesses: Balancing testing frequency, individual test technology, and cost. PLoS ONE, 16(3), e0248783. https://doi.org/10.1371/journal.pone.0248783
   PubMed Web of Science ®Google Scholar
• Manabe, Y. C., Sharfstein, J. S., & Armstrong, K. (2020). The need for more and better testing for COVID-19. JAMA, 324(21), 2153–2154. https://doi.org/10.1001/jama.2020.21694
   PubMed Web of Science ®Google Scholar
• Mei, W., Mohagheghi, S., Zampieri, S., & Bullo, F. (2017). On the dynamics of deterministic epidemic propagation over networks. Annual Reviews in Control, 44, 116–128. https://doi.org/10.1016/j.arcontrol.2017.09.002.
   Web of Science ®Google Scholar
• Newman, M. E. J. (2005). A measure of betweenness centrality based on random walks. Social Networks, 27(1), 39–54. https://doi.org/10.1016/j.socnet.2004.11.009.
   Web of Science ®Google Scholar
• Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113. https://doi.org/10.1103/PhysRevE.69.026113.
   PubMed Web of Science ®Google Scholar
• Noh, J. D., & Rieger, H. (2004). Random walks on complex networks. Physical Review Letters, 92(11), 118701. https://doi.org/10.1103/PhysRevLett.92.118701.
   PubMed Web of Science ®Google Scholar
• Oldham, S., Fulcher, B., Parkes, L., Suo, C., & Fornito, A. (2019). Consistency and differences between centrality measures across distinct classes of networks. PLoS ONE, 14(7), e0220061. https://doi.org/10.1371/journal.pone.0220061
   PubMed Web of Science ®Google Scholar
• Opsahl, T., Agneessens, F., & Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks, 32(3), 245–251. https://doi.org/10.1016/j.socnet.2010.03.006.
   Web of Science ®Google Scholar
• Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web (Technical Report No. 1999–66) [Previous number = SIDL-WP-1999-0120]. Stanford InfoLab. Stanford InfoLab. http://ilpubs.stanford.edu:8090/422/.
   Google Scholar
• Rahimi, I., Chen, F., & Gandomi, A. H. (2021). A review on COVID-19 forecasting models. Neural Computing and Applications, 1–11. https://doi.org/10.1007/s00521-020-05626-8
   PubMed Web of Science ®Google Scholar
• Rajeh, S., Savonnet, M., Leclercq, E., & Cherifi, H. (2021). Characterizing the interactions between classical and community-aware centrality measures in complex networks. Scientific Reports, 11(1), 1–15. https://doi.org/10.1038/s41598-021-89549-x
   PubMed Web of Science ®Google Scholar
• Restrepo, J. G., Ott, E., & Hunt, B. R. (2006). Characterizing the dynamical importance of network nodes and links. Physical Review Letters, 97(9), 094102. https://doi.org/10.1103/PhysRevLett.97.094102
   PubMed Web of Science ®Google Scholar
• Ronqui, J. R. F., & Travieso, G. (2015). Analyzing complex networks through correlations in centrality measurements. Journal of Statistical Mechanics: Theory and Experiment, 2015(5), P05030. https://doi.org/10.1088/1742-5468/2015/05/P05030.
   Web of Science ®Google Scholar
• Salathé, M., Althaus, C. L., Neher, R., Stringhini, S., Hodcroft, E., Fellay, J., Zwahlen, M., Senti, G., Battegay, M., Wilder-Smith, A., Eckerle, I., Egger, M., & Low, N. (2020). COVID-19 epidemic in switzerland: on the importance of testing, contact tracing and isolation. Swiss Medical Weekly, 150(1112). https://doi.org/10.4414/smw.2020.20225
   Google Scholar
• Salathé, M., & Jones, J. H. (2010). Dynamics and control of diseases in networks with community structure. PLOS Computational Biology, 6(4), e1000736. https://doi.org/10.1371/journal.pcbi.1000736.
   PubMed Web of Science ®Google Scholar
• Sporns, O. (2018). Graph theory methods: Applications in brain networks. Dialogues in Clinical Neuroscience,, 20(2), 111–121. https://doi.org/10.31887/DCNS.2018.20.2/osporns
   PubMed Web of Science ®Google Scholar
• Wang, H., Hernandez, J. M., & Van Mieghem, P. (2008). Betweenness centrality in a weighted network. Physical Review E, 77(4), 046105. https://doi.org/10.1103/PhysRevE.77.046105.
   Web of Science ®Google Scholar
• Wang, X., Dubbeldam, J. L. A., & Van Mieghem, P. (2017). Kemeny's constant and the effective graph resistance. Linear Algebra and Its Applications, 535, 231–244. https://doi.org/10.1016/j.laa.2017.09.003.
   Web of Science ®Google Scholar
• Wang, Y., Chakrabarti, D., Wang, C., & Faloutsos, C. (2003). Epidemic spreading in real networks: An eigenvalue viewpoint. In 22nd International Symposium on Reliable Distributed Systems, 2003. Proceedings. (pp. 25–34). IEEE.
   Google Scholar
• Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684), 440–442. https://doi.org/10.1038/30918.
   PubMed Web of Science ®Google Scholar
• White, D. R., & Borgatti, S. P. (1994). Betweenness centrality measures for directed graphs. Social Networks, 16(4), 335–346. https://doi.org/10.1016/0378-8733(94)90015-9.
   Web of Science ®Google Scholar
• Wu, C. W. (2005). Algebraic connectivity of directed graphs. Linear and Multilinear Algebra, 53(3), 203–223. https://doi.org/10.1080/03081080500054810.
   Web of Science ®Google Scholar
• Yan, J., He, H., & Sun, Y. (2014). Integrated security analysis on cascading failure in complex networks. IEEE Transactions on Information Forensics and Security, 9(3), 451–463. https://doi.org/10.1109/TIFS.2014.2299404.
   Web of Science ®Google Scholar
• Yilmaz, S., Dudkina, E., Bin, M., Crisostomi, E., Ferraro, P., Murray-Smith, R., Parisini, T., Stone, L., & Shorten, R. (2020). Kemeny-based testing for COVID-19. PLOS ONE, 15(11), e0242401. https://doi.org/10.1371/journal.pone.0242401.
   PubMed Web of Science ®Google Scholar
• Yu, Y., Berger-Wolf, T. Y., & Saia, J. (2008). Finding spread blockers in dynamic networks. In International Workshop on Social Network Mining and Analysis (pp. 55–76). Springer.
   Google Scholar
• Zhang, Z., Shan, T., & Chen, G. (2013). Random walks on weighted networks. Physical Review E, 87(1), 012112. https://doi.org/10.1103/PhysRevE.87.012112
   Web of Science ®Google Scholar