Fast Generation of Sparse Random Kernel Graphs

Aric Hagberg; Nathan Lemons

doi:10.1371/journal.pone.0135177

Fast Generation of Sparse Random Kernel Graphs

PLoS One. 2015 Sep 10;10(9):e0135177. doi: 10.1371/journal.pone.0135177. eCollection 2015.

Authors

Aric Hagberg¹, Nathan Lemons²

Affiliations

¹ Center for Nonlinear Studies, Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico, United States of America.
² Applied Mathematics and Plasma Physics, Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico, United States of America.

Abstract

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(logn)2). As a practical example we show how to generate samples of power-law degree distribution graphs with tunable assortativity.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Algorithms*
Models, Theoretical
Time Factors

Grants and funding

This work was funded by the Department of Energy at Los Alamos National Laboratory under contract DE-AC52-06NA25396 through the Laboratory Directed Research and Development Program.