# graphon: graphon : a Collection of Graphon Estimation Methods In graphon: A Collection of Graphon Estimation Methods

## Description

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

W:[0,1]^2\rightarrow[0,1]

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,

• est.LG for empirical degree sorting in stochastic blockmodel.

• est.SBA for stochastic blockmodel approximation.

• est.USVT for universal singular value thresholding.

• est.nbdsmooth for neighborhood smoothing.

• est.completion for matrix completion from a partially revealed data.

Also, the current release has following graph models implemented,

• gmodel.P generates a binary graph given an arbitrary probability matrix.

• gmodel.ER is an implementation of Erdos-Renyi random graph models.

• gmodel.block is used to generate networks with block structure.

• gmodel.preset has 10 exemplary graphon models for simulation.

## Acknowledgements

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

Kisung You

## References

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.