Print This Page

Jan Hagberg
-- doctoral thesis --

On Degree Variance in Random Graphs


Abstract
This thesis is concerned with degree moments and degree variance in random graphs. The degree of vertex i in a graph is the number of edges incident to vertex i.

In the first paper, degree moments and functions of degree moments are investigated for three random graph models. In statistical applications of random graph models the degree moments, and functions of the degree moments, have been found useful both as summary statistics and for inference on particular random graph models. Exact and asymptotic formulas are given for various degree statistics, in particular the degree variance.

The second paper focus on the degree variance. Exact and asymptotic distributions of the degree variance are investigated for Bernoulli graphs and uniform random graphs. For graphs of large order, we show that the degree variance is approximately gamma distributed with parameters obtained from the first two moments of the degree variance. The usefulness of the results is illustrated by a graph centrality test with a critical value obtained from the gamma distribution.

The third and last paper is concerned with extreme values and other attained values of the degree variance among graphs of fixed order and size, and among graphs of fixed order. The structure of the extreme graphs is investegated and it is shown that the maximum value of the degree variance can be obtained from integer sequences associated to the triangular numbers. Explicite formulas for the number of possible values and recurrence relations for the attained values of the degree variance are developed.

Key words: Degree Sequences, Uniform Random Graphs, Bernoulli Graphs, Degree Moments, Degree Statistics, Degree Variance, Gamma Approximation, Centrality Testing, Integer Sequences

Download report 1-->> General Moments of Degrees in Random Graphs
Download report 2-->> Random Graph Distributions of Degree variance
Download report 3-->> Extreme Values and Other Attained Values of the Degree Variance in Graphs