How to Burn a Network or Spread Alarm
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 alar...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Brno University of Technology
2019-12-01
|
| Series: | Mendel |
| Subjects: | |
| Online Access: | https://mendel-journal.org/index.php/mendel/article/view/103 |
| _version_ | 1818888629480587264 |
|---|---|
| author | Marek Simon Ladislav Huraj Iveta Dirgova Luptakova Jiri Pospichal |
| author_facet | Marek Simon Ladislav Huraj Iveta Dirgova Luptakova Jiri Pospichal |
| author_sort | Marek Simon |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-19T16:56:10Z |
| format | Article |
| id | doaj.art-91045335a56146689f23842c53368c01 |
| institution | Directory Open Access Journal |
| issn | 1803-3814 2571-3701 |
| language | English |
| last_indexed | 2024-12-19T16:56:10Z |
| publishDate | 2019-12-01 |
| publisher | Brno University of Technology |
| record_format | Article |
| series | Mendel |
| spelling | doaj.art-91045335a56146689f23842c53368c012022-12-21T20:13:25ZengBrno University of TechnologyMendel1803-38142571-37012019-12-0125210.13164/mendel.2019.2.011How to Burn a Network or Spread AlarmMarek SimonLadislav HurajIveta Dirgova LuptakovaJiri PospichalThis 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.https://mendel-journal.org/index.php/mendel/article/view/103centrality indicesburning numbercomplex networksoptimisation heuristics |
| spellingShingle | Marek Simon Ladislav Huraj Iveta Dirgova Luptakova Jiri Pospichal How to Burn a Network or Spread Alarm Mendel centrality indices burning number complex networks optimisation heuristics |
| title | How to Burn a Network or Spread Alarm |
| title_full | How to Burn a Network or Spread Alarm |
| title_fullStr | How to Burn a Network or Spread Alarm |
| title_full_unstemmed | How to Burn a Network or Spread Alarm |
| title_short | How to Burn a Network or Spread Alarm |
| title_sort | how to burn a network or spread alarm |
| topic | centrality indices burning number complex networks optimisation heuristics |
| url | https://mendel-journal.org/index.php/mendel/article/view/103 |
| work_keys_str_mv | AT mareksimon howtoburnanetworkorspreadalarm AT ladislavhuraj howtoburnanetworkorspreadalarm AT ivetadirgovaluptakova howtoburnanetworkorspreadalarm AT jiripospichal howtoburnanetworkorspreadalarm |