Contributions to the analysis of vertex centrality in randomly growing tree models

Networks are ubiquitous in today's world, and can serve as useful models for a plethora of phenomena ranging from disease spread to information diffusion. In this thesis, we consider tree networks, which despite their restricted structure can serve as a stepping stone for understanding more complicated real-world networks. We are chiefly concerned with the analysis of vertex centrality in trees that grow randomly according to some probabilistic model. In particular, we are interested in how the most central vertices in the tree evolve as it grows and how we can use these vertices to draw insightful inferences about the tree. The analysis of randomly growing tree models naturally lends itself to many intriguing tools from probability theory, among them probabilistic inequalities; we devote part of our exposition to more closely examining some of these inequalities.

The thesis begins by exploring the idea of persistence of centrality in randomly growing tree models. For a given measure of vertex centrality and a fixed model, persistence refers to the phenomenon by which the most central vertex in the randomly growing tree remains most central starting from some time point. We revisit and provide new insight into the notion of persistence for Jordan centrality in the independent cascade model, which has previously been considered in the literature. The other main problem regarding randomly growing tree models that we consider in the thesis is that of seed-finding. In particular, instead of starting the model from a single vertex (the “root”), suppose that we initialize the model with a “seed” tree consisting of at least two vertices. The goal of seed-finding is then to recover as much of the seed as possible upon observing a large tree grown according to the model. Our contribution in this thesis is to extend some previous work in the seed-finding literature to several randomly growing tree models. We conclude the thesis by examining some probabilistic inequalities that arise from the analysis of root-/seed-finding algorithms in certain models.