Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


dissertation.pdf (466.8 KB)

ETD Abstract Container

Abstract Header

On Random k-Out Graphs with Preferential Attachment

Peterson, Nicholas Richard
http://rave.ohiolink.edu/etdc/view?acc_num=osu1370527839

Abstract Details

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.
Mathematics
Combinatorial probability; random graphs; random mappings; Hansen and Jaworski; digraphs; functional digraph; vertex connectivity; minimum vertex degree; k-core; total variation distance

Recommended Citations

Citations

  • Peterson, N. R. (2013). On Random k-Out Graphs with Preferential Attachment [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1370527839

    APA Style (7th edition)

  • Peterson, Nicholas. On Random k-Out Graphs with Preferential Attachment. 2013. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1370527839.

    MLA Style (8th edition)

  • Peterson, Nicholas. "On Random k-Out Graphs with Preferential Attachment." Doctoral dissertation, Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1370527839

    Chicago Manual of Style (17th edition)

osu1370527839
834
© 2013, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.