Computing the Tenacity of Network Based on Genetic Algorithm

Tenacity is an important index for evaluating network vulnerability, implying the difficulty of destroying the network when nodes were invalidated or network was attacked. Tenacity also indicates the communication capability of subnet and the difficulty of network restoration after parts of network were damaged. At present, there is no algorithm that can compute the tenacity in polynomial time because the computation of tenacity is an NP problem. To solve the problem of complicated exhaustive scheme, an algorithm based on genetic algorithm is proposed to compute the tenacity of network. Stochastic optimization technique is used to search optimum solution efficiently in parametric space of tenacity. The results of simulation suggest that the algorithm is always converging at optimum solution efficiently. This algorithm provides a feasible and valid method to measure the vulnerability of network.