graphon: graphon : a Collection of Graphon Estimation Methods

Description What is Graphon? Composition of the package Acknowledgements Author(s) References


The graphon provides a not-so-comprehensive list of methods for estimating graphon, a symmetric measurable function, from a single or multiple of observed networks. It also contains several auxiliary functions for generating sample networks using various network models and graphons.

What is Graphon?

Graphon - graph function - is a symmetric measurable function


that arise in studying exchangeable random graph models as well as sequence of dense graphs. In the language of graph theory, it can be understood as a two-stage procedural network modeling that 1) each vertex/node in the graph is assigned an independent random variable u_j from uniform distribution U[0,1], and 2) each edge (i,j) is randomly determined with probability W(u_i,u_j). Due to such procedural aspect, the term probability matrix and graphon will be interchangeably used in further documentation.

Composition of the package

The package mainly consists of two types of functions whose names start with 'est' and 'gmodel' for estimation algorithms and graph models, respectively.

The 'est' family has 4 estimation methods at the current version,

Also, the current release has following graph models implemented,


Some of the codes are translated from a MATLAB package developed by Stanley Chan (Purdue) and Edoardo Airoldi (Harvard).


Kisung You


Erdos, P. and Renyi, A. (1959) On Random Graphs I. Publications Mathematicae, Vol.6:290-297.

Gilbert, E.N. (1959) Random Graphs. Annals of Mathematical Statistics, Vol.30, No.4:1141-1144.

Channarond, A., Daudin, J., and Robin, S. (2012) Classification and estimation in the SBM based on empirical degrees. Electronic Journal of Statistics, Vol.6:2574-2601.

Airoldi, E.M., Costa, T.B., and Chan, S.H. (2013) Stochastic blockmodel approximation of a graphon: Theory and consistent estimation. Advances in Neural Information Processing Systems, 692-700.

Chan, S.H. and Airoldi, E.M. (2014) A consistent histogram estimator for exchangeable graph models. Journal of Machine Learning Research Workshop and Conference Proceedings, Vol.32, No.1:208-216.

Chatterjee, S. (2015) Matrix estimation by universal singular value thresholding. The Annals of Statistics, Vol.43, No.1:177-214.

Zhang, Y., Levina, E., and Zhu, J. (2015) Estimating neighborhood edge probabilities by neighborhood smoothing. Arxiv:1509.08588

Mukherjee, S.S., Sarkar, P., and Lin, L. (2016) On estimating a mixture of graphons. Arxiv:1606.02401

graphon documentation built on Nov. 17, 2017, 5:28 a.m.

Related to graphon in graphon...