How to Burn a Network or Spread Alarm
Abstract
This paper compares centrality indices usage within a heuristic method for a fast spread of alarm, or crucial information. Such indices can be used as a core part within more sophisticated optimisation methods, which should determine a graph parameter - burning number, defining, how fast can an alarm spread through all nodes. In this procedure at each time step a new chosen node is alarmed (i.e. burned) “from outside”, and already alarmed nodes at each time step then alarm their neighbours. The procedure ends, when all the nodes are alarmed (i.e. burned). The optimisation heuristic should choose such ordered sequence of nodes, which are to be alarmed “from outside”, that their number, equal the number of time steps (i.e. burning number) necessary to alarm the whole network, is minimised. The NP completeness of the problem necessitates a usage of heuristics. However, even the heuristics can be slower, reaching towards a global optimum, or faster, exchanging part of the quality for a time. This paper studies the usage of centrality indices in a simpler and faster heuristic. It should be useful e.g. for a mobile network of cars or drones, when an optimal solution cannot be computed in advance, or take too much CPU time, since the connections within the dynamic network might not exist any longer. A wide range of centrality indices was tested on selected networks, both real as well as artificially generated. While the performances of indices substantially differ for different types of networks, results show, which centrality indices work well across all tested networks.
References
Ashtiani, M., Mirzaie, M., and Jafari, M. 2018. CINNA: an R/CRAN package to decipher Central Informative Nodes in Network Analysis. Bioinformatics 35(8), pp. 1436–1437.
Benkerdagh, S. and Duvallet, C. 2019. Cluster‐based emergency message dissemination strategy for VANET using V2V communication. International Journal of Communication Systems, 32(5), p.e3897.
Bessy, S., Bonato, A., Janssen, J., Rautenbach, D., and Roshanbin, E. 2017. Burning a graph is hard. Discrete Applied Mathematics 232, pp. 73–87.
Bessy, S., Bonato, A., Janssen, J., Rautenbach, D., and Roshanbin, E. 2018. Bounds on the burning number. Discrete Applied Mathematics 235, pp. 16–22.
Bonato, A., Janssen, J., and Roshanbin, E. 2016. How to burn a graph. Internet Mathematics 12(1-2), pp. 85–100. [6] Bonato, A. and Kamali, S. 2019. Approximation Algorithms for Graph Burning. In T.V. Gopal, J. Watada (eds.) Theory and Applications of Models of Computation, pp. 74–92. Springer, Cham.
Finbow, S. and MacGillivray, G. 2009. The Firefighter Problem: a survey of results, directions and questions. Australasian J. Combinatorics 43, pp. 57–78.
Gabriska, D. and Olvecky, M. 2018. Analysis and Risk Reduction in Operation of Hazardous Programmable Electronic Systems. 2018 IEEE 16th International Symposium on Intelligent Systems and Informatics (SISY), IEEE. DOI: 10.1109/SISY.2018.8524642
Hochbaum, D. S. 1997. Approximation Algorithms for NP-Hard problems. PWS Publishing Company, Boston, pp. 346–398. DOI: 10.1145/261342.571216
Hosťovecký, M. and Babušiak, B. 2017. Brain activity: beta wave analysis of 2D and 3D serious games using EEG. Journal of Applied Mathematics, Statistics and Informatics 13, pp. 39–53.
Hromkovič, J., Klasing, R., Monien, B., and Peine, R. 1996. Dissemination of information in interconnection networks (broadcasting & gossiping). In Combinatorial network theory (pp. 125–212). Springer, Boston, MA.
Kotyrba, M., Volná, E., and Kominkova-Oplatkova, Z. 2014. Comparison of Modern Clustering Algorithms For Two-Dimensional Data. In Proceedings 28th European Conference on Modelling and Simulation, ECMS 2014, pp. 346–351. Brescia, Italy.
Mitsche, D., Prałat, P. and Roshanbin, E. 2017. Burning graphs: a probabilistic perspective. Graphs and Combinatorics 33(2), pp. 449–471.
Newman, M. 2018. Networks. Oxford University Press. ISBN: 9780198805090.
Rossi, R. and Ahmed, N. 2015. The network data repository with interactive graph analytics and visualization. In Twenty-Ninth AAAI Conference on Artificial Intelligence, pp. 4292–4293.
Samadi, M., Nagi, R., Semenov, A., and Nikolaev, A. 2018. Seed activation scheduling for influence maximization in social networks. Omega 77, pp. 96–114.
Siládi, V., Povinský, M. and Satymbekov, M. 2017. Adapted parallel Quine-McCluskey algorithm using GPGPU. In 14th International Scientific Conference on Informatics, IEEE, pp. 327–331.
Šimon, M., Huraj, L., Dirgová-Luptáková, I., Pospíchal, J. 2019. Heuristics for Spreading Alarm throughout a Network. Appl. Sci. 9, 3269. DOI: 10.3390/app9163269
Copyright (c) 2019 MENDEL
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
