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 216 nodes). Finally, concrete examples are provided to illustrate useful applications of the proposed approach, also in the presence of link failures.
|Titolo:||A Dynamic Random Graph Model for Diameter-Constrained Topologies in Networked Systems|
|Data di pubblicazione:||2014|
|Digital Object Identifier (DOI):||10.1109/TCSII.2014.2362676|
|Appare nelle tipologie:||1.1 Articolo in rivista|