Network connectivity analysis via shortest paths

Abstract Complex systems of interacting components often can be modeled by a simple graph $$\mathcal {G}$$ that consists of a set of n nodes and a set of m edges. Such a graph can be represented by an adjacency matrix $$A\in \mathbb {R}^{n\times n}$$ , whose ( ij )th entry is one if there is an edge pointing from node i to node j , and is zero otherwise. The matrix A and its positive integer powers reveal important properties of the graph and allow the construction of the path length matrix L for the graph. The ( ij )th entry of L is the length of the shortest path from node i to node j ; if there is no path between these nodes, then the value of the entry is set to $$\infty$$ . We are interested in how well information flows via shortest paths of the graph. This can be studied with the aid of the path length matrix. The path length matrix allows the definition of several measures of communication in the network defined by the graph such as the global K -efficiency, which considers shortest paths that are made up of at most K edges for some $$K<n$$ , as well as the number of such shortest paths. Novel notions of connectivity introduced in this paper help us understand the importance of specific edges for the flow of information through the graph. This is of interest when seeking to simplify a network by removing selected edges or trying to assess the sensitivity of the flow of information to changes due to exterior causes such as a traffic stoppage on a road network.