Fast Generation of Spatially Embedded Random Networks

2015/12/11 by Eric Parsonage, Matthew Roughan, Parsonage, Eric +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Social and Information Networks (cs.SI) #cs.DS #cs.SI

paper · pdf · doi:10.48550/arxiv.1512.03532

arxiv created 2015/12/11 · arxiv updated 2015/12/14

Abstract

Spatially Embedded Random Networks such as the Waxman random graph have been used in a variety of settings for synthesizing networks. However, little thought has been put into fast generation of these networks. Existing techniques are O(n²) where n is the number of nodes in the graph. In this paper we present an O(n + e) algorithm, where e is the number of edges.

Related

• Generating Random Networks Without Short Cycles
• A simple and flexible algorithm to generate real-world networks
• A Parallel Algorithm for Generating a Random Graph with a Prescribed Degree Sequence
• Parallel Algorithms for Generating Random Networks with Given Degree Sequences
• Fast generation of complex networks with underlying hyperbolic geometry