Status : Verified
| Personal Name | Austria, Darrwin Dearest C. |
|---|---|
| Resource Title | An Algorithm for Generating Random Graphs with Prescribed Degree Sequence |
| Date Issued | January 2018 |
| Abstract | 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 preexisting 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(n^2 log n) based on the analysis and tests done on the algorithm. |
| Degree Course | Master of Science in Computer Science |
| Language | English |
| Keyword | Generation Algorithm; Graphical Degree Sequence; Random Graph; Importance Sampling |
| Material Type | Thesis/Dissertation |
Preliminary Pages
532.19 Kb
Category : F - Regular work, i.e., it has no patentable invention or creation, the author does not wish for personal publication, there is no confidential information.
Access Permission : Open Access