Gautam Rahul Kumar, Kare Anjeneya Swami, S Durga Bhavani
School of Computer and Information Sciences, University of Hyderabad, Hyderabad, India.
Appl Intell (Dordr). 2022;52(2):1351-1361. doi: 10.1007/s10489-021-02411-5. Epub 2021 May 20.
Graph burning is a process of information spreading through the network by an agent in discrete steps. The problem is to find an optimal sequence of nodes that have to be given information so that the network is covered in least number of steps. Graph burning problem is NP-Hard for which two approximation algorithms and a few heuristics have been proposed in the literature. In this work, we propose three heuristics, namely, Backbone Based Greedy Heuristic (BBGH), Improved Cutting Corners Heuristic (ICCH), and Component Based Recursive Heuristic (CBRH). These are mainly based on Eigenvector centrality measure. BBGH finds a backbone of the network and picks vertex to be burned greedily from the vertices of the backbone. ICCH is a shortest path based heuristic and picks vertex to burn greedily from best central nodes. The burning number problem on disconnected graphs is harder than on the connected graphs. For example, burning number problem is easy on a path where as it is NP-Hard on disjoint paths. In practice, large networks are generally disconnected and moreover even if the input graph is connected, during the burning process the graph among the unburned vertices may be disconnected. For disconnected graphs, ordering the components is crucial. Our CBRH works well on disconnected graphs as it prioritizes the components. All the heuristics have been implemented and tested on several bench-mark networks including large networks of size more than 50K nodes. The experimentation also includes comparison to the approximation algorithms. The advantages of our algorithms are that they are much simpler to implement and also several orders faster than the heuristics proposed in the literature.
图燃烧是一个信息通过网络中的一个代理以离散步骤传播的过程。问题在于找到一个必须给予信息的节点的最优序列，以便在最少的步骤内覆盖网络。图燃烧问题是NP难问题，文献中已经提出了两种近似算法和一些启发式算法。在这项工作中，我们提出了三种启发式算法，即基于骨干的贪婪启发式算法（BBGH）、改进的走捷径启发式算法（ICCH）和基于组件的递归启发式算法（CBRH）。这些算法主要基于特征向量中心性度量。BBGH找到网络的骨干，并从骨干的顶点中贪婪地选择要燃烧的顶点。ICCH是一种基于最短路径的启发式算法，从最佳中心节点中贪婪地选择要燃烧的顶点。在非连通图上的燃烧数问题比在连通图上更难。例如，在一条路径上燃烧数问题很容易，而在不相交路径上则是NP难问题。在实际中，大型网络通常是非连通的，而且即使输入图是连通的，在燃烧过程中未燃烧顶点之间的图也可能是非连通的。对于非连通图，对组件进行排序至关重要。我们的CBRH在非连通图上运行良好，因为它对组件进行了优先级排序。所有启发式算法都已在几个基准网络上实现并测试，包括节点数超过50K的大型网络。实验还包括与近似算法的比较。我们算法的优点是它们实现起来要简单得多，而且比文献中提出的启发式算法快几个数量级。
