Graph Resistance-Based Approach to Identify Articulation Sets

Connectivity is a very important aspect of a multi-agent system (MAS) since it determines the ability of the MAS to accomplish cooperative tasks successfully. It then follows that developing algorithms to design networks/graphs that not only ensure connectivity nominally but also provide guarantees of connectivity despite node failures is essential. This quality of achieving and maintaining connectivity even in the face of node failure is referred to as biconnectivity. In this paper, the notion of graph resistance is utilized to check connectivity in the presence of articulation nodes, when node failures occur. First, an algorithm is provided to determine articulation nodes in the graph and the connected components into which failure of such articulation nodes splits the graph up into. Subsequently, we present an index of connectivity to quantify the extent of connectivity loss when a node fails. Since we are interested in improving the connectivity in the event of node failure, we present a method (of re-designing a network) to preserve connectivity against failure of that node which has a minimum index of connectivity. Additionally, certain methods to render connectivity with the addition of a minimum number of edges to the existing graph are provided. Simulation results show the effectiveness of the proposed method which results in ensuring biconnectivity even in the presence of a node failure.