How to Burn a Network or Spread Alarm

  • Marek Simon
  • Ladislav Huraj
  • Iveta Dirgova Luptakova
  • Jiri Pospichal
Keywords: centrality indices, burning number, complex networks, optimisation heuristics

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

Published
2019-12-20
How to Cite
[1]
Simon, M., Huraj, L., Dirgova Luptakova, I. and Pospichal, J. 2019. How to Burn a Network or Spread Alarm. MENDEL. 25, 2 (Dec. 2019), 11-18. DOI:https://doi.org/10.13164/mendel.2019.2.011.
Section
Research articles