×

On the number of non-zero elements of joint degree vectors. (English) Zbl 1358.05256

Summary: Joint degree vectors give the number of edges between vertices of degree \(i\) and degree \(j\) for \(1\leq i\leq j\leq n-1\) in an \(n\)-vertex graph. We find lower and upper bounds for the maximum number of nonzero elements in a joint degree vector as a function of \(n\). This provides an upper bound on the number of estimable parameters in the exponential random graph model with bidegree-distribution as its sufficient statistics.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C07 Vertex degrees
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] Y. Amanatidis, B. Green, and M. Mihail. Graphic realizations of joint-degree matrices. In preprint.arXiv:1509.07076, 2011. · Zbl 1398.05065
[2] O. E. Barndorff-Nielsen. Information and Exponential Families in Statistical Theory. John Wiley and Sons, Chichester, UK, 1978. · Zbl 0387.62011
[3] Joseph Blitzstein and Persi Diaconis. A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet Math., 6(4):489-522, 2010. · Zbl 1238.60084
[4] L. Brown. Fundamentals of Statistical Exponential Families, volume 9. IMS Lecture Notes—Monograph Series, Hayward, CA, USA, 1986. · Zbl 0685.62002
[5] Sourav Chatterjee, Persi Diaconis, and Allan Sly. Random graphs with a given degree sequence. Annals of Applied Probability, 21(4):1400-1435, 2011. · Zbl 1234.05206
[6] E. Czabarka, A. Dutle, P. L. Erd˝os, and I. Mikl´os. On realizations of a joint degree matrix. Discrete Applied Mathematics, 181:283 – 288, 2015. · Zbl 1304.05020
[7] Xenofontas Dimitropoulos, Dmitri Krioukov, Amin Vahdat, and George Riley. Graph annotations in modeling complex network topologies. ACM Transactions on Modeling and Computer Simulation, 19(4):17:1-17:29, 2009. · Zbl 1390.90134
[8] O. Frank.Statistical analysis of change in networks.Statistica Neerlandica, 45(3):283-293, 1991. · Zbl 0745.62094
[9] M. S. Handcock and M. Morris. A simple model for complex networks with arbitrary degree distribution and clustering. Statistical Network Analysis: Models, Issues and New Directions, 4503:103-114, 2007.
[10] P. Mahadevan, D. Krioukov, K. Fall, and A. Vahdat. Systematic Topology Analysis and Generation Using Degree Correlations. SIGCOMM 2006, 36(4):135-146, Sep 2006.
[11] M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167-256, 2003. · Zbl 1029.68010
[12] A.N. Patrinos and S.L. Hakimi. Relations between graphs and integer-pair sequences. Discrete Math., 15(4):358-437, 1976. · Zbl 0328.05139
[13] Alessandro Rinaldo, Sonja Petrovi´c, and Stephen E. Fienberg. Maximum lilkelihood estimation in the beta model. Annals of Statistics, 41(3):1085-1110, 2013. · Zbl 1292.62052
[14] Kayvan Sadeghi and Alessandro Rinaldo. Statistical models for degree distributions of networks. In NIPS workshop, Montreal, Canada.arXiv:1411.3825, 2014. · Zbl 1398.62218
[15] Isabelle Stanton and Ali Pinar. Constructing and sampling graphs with a prescribed joint degree distribution. J. Exp. Algorithmics, 17:3.5:3.1-3.5:3.25, 2012. · Zbl 1284.05248
[16] Nanwei Wang, Johannes Rauh, and H´el‘ene Massam. Approximating faces of marginal polytopes in discrete hierarchical models.arXiv:1603.04843, 2016. · Zbl 1417.62144
[17] Stanley Wasserman and Philippa Pattison. Logit models and logistic regressions for social networks: I. an introduction to Markov graphs and p∗. Psychometrika, 61(3):401-425, 1996. · Zbl 0866.92029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.