A Computationally Efficient Connectivity Index for Weighted Directed Graphs With Application to Underwater Sensor Networks

Abstract

This paper investigates the global connectivity of complex networks with random links. An expected communication graph with weighted edges is used to model the network. The notion of weighted vertex connectivity (WVC) introduced in the literature as a generalization of the notion of vertex connectivity, is known to be effective in measuring the connectivity of this type of network. However, given the computational complexity of the WVC, a numerically efficient approximate measure for that is more desirable. In this paper, a polynomial-time approximation to the WVC is derived, which is less conservative than the previously introduced approximate measure. It is shown that under some conditions the proposed approximation is identical to the WVC. Simulation results demonstrate the usefulness of the proposed measure.

Keywords

• Graph connectivity
• directed weighted graphs
• sensor networks