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.
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.
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.
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
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.