A Comparative Analysis of Geometric Graph Models For Modelling Backbone Networks


Many researchers have studied Internet topology, and the analysis of complex and multilevel Internet structure is nontrivial. The emphasis of these studies has been on logical level topologies, however physical level topologies are necessary to study resilience realistically, given the geography and multilevel nature of the Internet. In this paper, we investigate the representativeness of the synthetic Gabriel, geometric, population-weighted geographical threshold, and location-constrained Waxman graph models to the actual fibre backbone networks of six providers. We quantitatively analyse the structure of the synthetic geographic topologies whose node locations are given by those of actual physical level graphs using well-known graph metrics, graph spectra, and the visualisation tool we have developed. Our results indicate that the synthetic Gabriel graphs capture the grid-like structure of physical level networks best. Furthermore, given that the cost of physical level topologies is an important aspect from a design perspective, we also compare the cost of synthetically generated geographic graphs and find that the synthetic Gabriel graphs achieve the smallest cost among all the graph models that we consider. Finally, based on our findings we propose a graph generation method to model physical level topologies, and show that it captures both grid and star structures ideally.


Electrical and Computer Engineering


National Science Foundation (U.S.)

Keywords and Phrases

Complex Networks; Costs; Geometry; Graphic Methods; Internet; Back-Bone Network; Connectivity; Gabriel Graph; Geometric Graphs; Graph Metrics; Graph Spectra; Network Costs; Physical Level; Resilience; Threshold Graphs; Waxman Graph; Weighted Graph; Graph Theory

International Standard Serial Number (ISSN)


Electronic OCLC #


Print OCLC #


Document Type

Article - Journal

Document Version


File Type





© 2014 Elsevier, All rights reserved.