A new topological index for capacity allocation problem in survivable networks

In this paper, we propose a new topological index, which is a numerical descriptor that characterizes survivable network topologies. A monotonically decreasing power law relationship can be found between this index and the total capacity allocation in the network. The new topological index is calculated based on the algebraic connectivity, which is adopted from spectral graph theory, more specifically it is based on the second-smallest eigenvalue of the Laplacian matrix of the network topology. Instead of the average nodal degree index that is usually used to characterize network connectivity in studies of the capacity allocation problem, our results suggest that this new topological index more accurately predicts the total capacity and is more informative. It can be used in studies on quantitative structure-performance relationships, in which the network performance or other properties of network are correlated with their topological structure. Initial studies of selected network topologies confirm that the connections between the total capacity and its network structure can be well described by this topological index in network survivability studies.