Predavateljica: Eva Czabarka (University of South Carolina, ZDA)
The Havel-Hakimi theorem states that the space of graphs with a given degree sequence is connected
under 2-swaps (exchanging a pair of nonadjacent edges to another pair on the same four vertices).
This operation gives rise to a simple Markov chain that allows one to sample graphs with a given
degree sequence. Degree sequence alone does not capture the properties of a network: e.g.
social, biological, technical networks can have the very same degree sequence and different
assortativity. The assortativity coefficient of the graph is essentially the Pearson correlation
coefficient of degrees of adjacent vertices that gives the tendency of nodes of different or similar
degrees to be connected to each other. The joint degree matrix gives all information necessary
to compute the assortativity coefficient of a graph – the ij-th element of the matrix gives the
number of edges connecting degree i and degree j vertices. We will describe some Havel-Hakimi type
results related to the joint degree matrix and some generalizations of the concept.
under 2-swaps (exchanging a pair of nonadjacent edges to another pair on the same four vertices).
This operation gives rise to a simple Markov chain that allows one to sample graphs with a given
degree sequence. Degree sequence alone does not capture the properties of a network: e.g.
social, biological, technical networks can have the very same degree sequence and different
assortativity. The assortativity coefficient of the graph is essentially the Pearson correlation
coefficient of degrees of adjacent vertices that gives the tendency of nodes of different or similar
degrees to be connected to each other. The joint degree matrix gives all information necessary
to compute the assortativity coefficient of a graph – the ij-th element of the matrix gives the
number of edges connecting degree i and degree j vertices. We will describe some Havel-Hakimi type
results related to the joint degree matrix and some generalizations of the concept.
