An algorithm for generating random graphs with prescribed degree sequence - Austria, Darrwin Dearest C.; Yap, Jan Michael C. (Quezon City College of Engineering, University of the Philippines Diliman, 2018)
A random graph is a useful tool to represent a different possible interaction in a real life network, its current applications include the analysis of networks in science and engineering. Considering the possible applications of random graphs, there is a significant interest in designing algorithms that generate such graphs. Methods for generating random graphs can be classified into two: matching vertices, and switching of edges. The first method starts with isolated vertices and then connects two vertices repeatedly to form a graph, while the second method randomizes a pre existing graph by swapping edges between vertices. However, there are some problems arising in these methods: matching algorithms generate random graphs with the exact degree sequence as the reference graph without certainty, and switching algorithms have no definite number of edge switches needed for randomization. This work presents an algorithm that performs vertex matching, but ensures the generation of a random graph with the exact degree sequence as the reference graph. The algorithm checks for graphicality at each step to generate graphs with the exact degree sequence as the reference graph. The algorithm is compared to existing methods of random graph generation in terms of uniformity in distribution of generated graphs and running time. The algorithm created in this paper has a conjectured running time of O(n2log n) based on the analysis and tests done on the algorithm.
Thesis (Master of Science in Computer Science)--University of the Philippines Diliman
Keywords: Random graphs; Graph algorithms