19-22 October 2011
Hotel Roanoke, Roanoke VA
US/Eastern timezone
<font color=red><b>To upload your file, log in (@ top right), then click on your talk title, then click "Add Material" at the bottom of the page.</b></font>

Degree-based graph construction and sampling

22 Oct 2011, 12:09
Crystal Ballroom B (Hotel Roanoke, Roanoke VA)

Crystal Ballroom B

Hotel Roanoke, Roanoke VA


Hyunju Kim (Virginia Tech)


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.

Presentation Materials

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now