A Note on Short-Range Network Communication and Clustering

Abstract

Complex systems of interacting components often can be modeled by a graph 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∈Rn×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 low-order powers reveal important properties of the graph and allow the enumeration of short paths and cycles that are important for determining short-range communication in the graph as well as node clustering. Closed-form expressions for path matrices of length up to four are derived, and a novel indicator of the structural propensity of the graph to form clusters is proposed. Numerical examples illustrate our analysis.