Graphon processes as a new model for large, sparse graphs
The theory of graph limits for dense graphs is by now well established, with graphons describing both the limit of a sequence of deterministic graphs, and a model for so-called exchangeable random graphs. Here a graphon is a function defined over a ``feature space’’ equipped with some probability measure, the measure describing the distribution of features for the nodes, and the graphon describing the probability that two nodes with given features form a connection. While there are rich models of sparse random graphs based on graphons, they require an additional parameter, the edge density, whose dependence on the size of the graph has either to be postulated as an additional function, or considered as an empirical observed quantity not described by the model.
In this talk I describe a new model, where the underlying probability space is replaced by a sigma-finite measure space, leading to both a new random model for exchangeable graphs, and a new notion of graph limits. The new model naturally produces a graph valued stochastic process indexed by a continuous time parameter, a “graphon process”, and describes graphs which typically have degree distributions with long tails, as observed in large networks in real life.