Speaker
Hyunju Kim
(Virginia Tech)
Description
Network representation and modeling has been one of the most comprehensive ways to study many complex systems. However, the network describing the system frequently has to be built from incomplete connectivity data, a typical case being degree-based graph construction, when only the sequence of node degrees is available. In this presentation I will introduce problems and results related to the construction of all the possible graphs and sampling from the class of graphs with fixed degree-sequence. Firstly, for graph construction, I will present necessary and sufficient conditions for a sequence of integers to be realized as a simple graph's degree sequence under the condition that a specific set of connections from an arbitrary node are avoided. Secondly, by using this result, I will show how to provide an efficient, polynomial time algorithm that generates graph samples with a given degree sequence. Unlike other existing algorithms, this method always produces statistically independent samples, without back-tracking or rejections. Also, the algorithm provides the weight associated with each sample, allowing graph observables to be measured uniformly over the graph ensemble.
