# Heuristics for Spreading Alarm throughout a Network
###### Abstract  
This paper provides heuristic methods for obtaining a burning number, which is a graph parameter measuring the speed of the spread of alarm, information, or contagion. For discrete time steps, the heuristics determine which nodes (centers, hubs, vertices, users) should be alarmed (in other words, burned) and in which order, when afterwards each alarmed node alarms its neighbors in the network at the next time step. The goal is to minimize the number of discrete time steps (i.e., time) it takes for the alarm to reach the entire network, so that all the nodes in the networks are alarmed. The burning number is the minimum number of time steps (i.e., number of centers in a time sequence alarmed \"from outside\") the process must take. Since the problem is NP complete, its solution for larger networks or graphs has to use heuristics. The heuristics proposed here were tested on a wide range of networks. The complexity of the heuristics ranges in correspondence to the quality of their solution, but all the proposed methods provided a significantly better solution than the competing heuristic. burning number; information spreading; centrality measures; complex networks; optimization heuristics +
Footnote †: journal: Applied Informatics  
0000-0002-4000-0000-0000-0000-0000-0000-0000-0000-0000-0000-00000-0000-00000-00000-0000-00000-00000-00000-00000-00000-00000  
et al. [1]. It was proved that computing a \"burning number\" is NP-complete [2]. The problem was further studied in papers [3; 4], where the bounds for the burning number (i.e., the minimum number of time steps, equal to the minimum size of the set of nodes, which are informed or alarmed \"from the outside\", not from their neighbor) are analyzed. The papers provided both the lower and the upper bounds, where the upper bound was accompanied by the actual sequence of the set of nodes to be informed from the outside. However, since the authors were graph theorists, they were not primarily concerned about an effective algorithm, how to find a solution close to the optimal one. Bounds for special types of graphs and special cases are also studied as graph theory problems in [5; 6; 7; 8]. A number of different approaches for disseminating information are studied in various areas, like the \(k\) center selection, the telephone model in gossiping, or the broadcasting of control or emergency packets in computer networks, viral marketing or influence maximization in social networks, or models of contagion in biology. In graph theory, the \(k\) center selection refers to a related problem, when the message is sent to all \(k\) centers (seeds) at once, so no time scheduled sequence is needed, and the parameter \(k\) is given in advance. Unlike a burning number problem, heuristic solutions for the \(k\) center problem have been studied more extensively [9; 10]. Recently the problem has been optimized by stochastic metaheuristics like tabu search or simulated annealing [11], paying for better results with computational time. Instead of spreading an alert through seed hubs, this problem can be interpreted as selecting hubs for sending an alert to a higher level of the network, so that an alert occurring in any node of the network is sent through the closest hub in the shortest time [12]. The alert routing can be employed e.g., in security [13]. In gossiping [14], each node has a unique item of information. By each connection between two nodes, both share all their information. How many connections are needed (a schedule determines, which edges are used in which order; edges may be used repeatedly), until each node has all the pieces of information? In broadcasting, one node has an item of information to be communicated to the rest of the nodes, which is closer to the \"burning number\" problem than gossiping [14]. In the typically used telephone model of information dissemination [14; 15], one node shares or sends information to one of its neighboring nodes.