Open AccessFast Generation of Sparse Random Kernel Graphs
Author(s) -
Aric Hagberg,
Nathan Lemons
Publication year - 2015
Publication title -
plos one
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.99
H-Index - 332
ISSN - 1932-6203
DOI - 10.1371/journal.pone.0135177
Subject(s) - random graph , assortativity , quadratic growth , computer science , degree distribution , modular decomposition , kernel (algebra) , graph kernel , algorithm , mathematics , graph , combinatorics , theoretical computer science , kernel method , pathwidth , variable kernel density estimation , line graph , complex network , artificial intelligence , support vector machine
The development of kernel-based inhomogeneous random graphs has provided models that are flexible enough to capture many observed characteristics of real networks, and that are also mathematically tractable. We specify a class of inhomogeneous random graph models, called random kernel graphs, that produces sparse graphs with tunable graph properties, and we develop an efficient generation algorithm to sample random instances from this model. As real-world networks are usually large, it is essential that the run-time of generation algorithms scales better than quadratically in the number of vertices n . We show that for many practical kernels our algorithm runs in time at most ( n (log n ) 2 ). As a practical example we show how to generate samples of power-law degree distribution graphs with tunable assortativity.