Code optimization of contraction operation in agglomeration-based node importance analysis

Networks are used for modelling different systems like chemical systems, neural networks, and social systems. A communication network consists of nodes and links connecting these nodes. Damage to an important node in the network often leads to damage to the entire network. Therefore, it is important to determine the critical nodes of the networks. In this paper, an advanced novel algorithmic method that uses agglomeration-based node contraction is proposed to solve this problem. The algorithm is designed, then it is tested on randomly produced connected undirected networks and its correctness is proven by comparing it with the brute-force method. The calculation of the shortest path after each contraction in the original algorithm is accelerated by a dynamic method. Then, the algorithm is tested on computers with different configurations. Statistics obtained from these tests are also presented in this paper.HighlightsDetermination of node importanceComplex network analysisDynamic agglomeration-based node contraction algorithm