A Dynamic Random Graph Model for Diameter-Constrained Topologies in Networked Systems

Random graphs have been widely investigated in the literature because of their relevance to many scientific domains. In this brief, the attention is focused on diameter-constrained random graphs, which are useful in analyzing unstructured overlays for delay-bounded network applications and systems. To this end, a general process of arrivals is considered, which describes the sequence of vertex couples (i.e., node couples) among which a path composed of no more than D edges (i.e., links) has to be established. Accordingly, a topology formation mechanism M is formulated, expressing the rules that drive the addition of new edges, obeying to the constraint on the maximum diameter D. Third, using graph-theoretic arguments, an original discrete-time model is proposed, which describes the evolution of the average network degree (i.e., the average number of edges per node) subject to M and D. Fourth, the model is successfully validated using computer simulations in a wide range of scenarios (with up to 2¹⁶ nodes). Finally, concrete examples are provided to illustrate useful applications of the proposed approach, also in the presence of link failures.