A Dynamic Random Graph Model for Diameter-Constrained Topologies in Networked Systems
Luigi Alfredo Grieco, Mahdi Ben Alaya, Thierry Monteil, Khalil Drira · IEEE Transactions on Circuits & Systems II Express Briefs · 2014
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 216nodes). Finally, concrete examples are provided to illustrate useful applications of the proposed approach, also in the presence of link failures.