Search ETDs:
On Random k-Out Graphs with Preferential Attachment
Peterson, Nicholas Richard

2013, Doctor of Philosophy, Ohio State University, Mathematics.
In a series of papers, Hansen and Jaworski explored a very general model for choosing random mappings with exchangeable in-degrees. The special case in which the in-degrees are obtained by conditioning independent random variables with a specially chosen negative binomial distribution on their sum corresponds in distribution to a process for choosing random mappings which exhibits preferential attachment - images are chosen one at a time, and vertices chosen as images earlier in the process are more likely to be chosen again. They consider the functional digraph as a random object, and study its properties.

We generalize Hansen and Jaworski’s preferential attachment model to a new setting: our model produces digraphs with labeled arcs and uniform out-degree k; other than a few technical wrinkles, the graph obtained by ignoring arc directions, loops, and multiple arcs is essentially a preferential attachment version of the k-out graph model first studied by Fenner and Frieze. This dissertation splits nicely in to three parts: first, we build a collection of analytical tools for studying our mapping; second, we study structural properties of its induced graph, including minimum vertex degree, vertex connectivity, and the k-core; finally, we present a very strong measurement of the differences and similarities between our model and a limiting case that is uniformly random.
Boris Pittel (Advisor)
Jeffery McNeal (Committee Member)
Neil Falkner (Committee Member)
85 p.

Recommended Citations

Hide/Show APA Citation

Peterson, N. (2013). On Random k-Out Graphs with Preferential Attachment. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Peterson, Nicholas. "On Random k-Out Graphs with Preferential Attachment." Electronic Thesis or Dissertation. Ohio State University, 2013. OhioLINK Electronic Theses and Dissertations Center. 25 Sep 2017.

Hide/Show Chicago Citation

Peterson, Nicholas "On Random k-Out Graphs with Preferential Attachment." Electronic Thesis or Dissertation. Ohio State University, 2013. https://etd.ohiolink.edu/

Files

dissertation.pdf (466.8 KB) View|Download