On the Number of Non-Zero Elements of Joint Degree Vectors

Éva Czabarka, Johannes Rauh, Kayvan Sadeghi, Taylor Short, László Székely

Abstract


Joint degree vectors give the number of edges between vertices of degree $i$ and degree $j$ for $1\le i\le j\le 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.


Keywords


Degree sequence; Joint degree distribution; Joint degree vector; Joint degree matrix; Exponential random graph model

Full Text: PDF