A network generated by the algorithm.Abstract
This study introduces the Large Network Generator, an algorithm capable of creating undirected graphs with three main characteristics of real-world networks: long-tailed degree distribution, short distances between nodes (small-world phenomenon), and large clustering coefficients. The main idea is to add one node to the network at each step, perform random walks on the existing nodes, and select a subset of marked nodes to connect to the new node. Additionally, with an adjustable probability, edges may be created between the marked nodes themselves. Key advantages of our algorithm are its simplicity, efficiency, and flexibility in creating networks with different characteristics without using global information about network topology. The parameters can be adjusted to generate networks with specific characteristics, producing a wide range of values for each parameter, including high clustering (up to 0.7), markedly short average distances (as low as 2.8 for N = 200 000), and a strong presence of hubs. Additionally, the algorithm’s near-linear time complexity allows the creation of networks with one million nodes in less than 60 s. The implementation of our algorithm is publicly available on a GitHub repository.