Doctoral Degrees (Mathematical Sciences)

Permanent URI for this collection

https://scholar.sun.ac.za/handle/10019.1/852

Browse

Browsing Doctoral Degrees (Mathematical Sciences) by Subject "Analytic combinatorics"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Centrality in random trees
    (Stellenbosch : Stellenbosch University, 2017-12) Durant, Kevin; Wagner, Stephan; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
    ENGLISH ABSTRACT : We consider two notions of centrality—namely, the betweenness centrality of a node and whether or not it is a centroid—in families of simply generated and increasing trees. Both of these concepts are defined in terms of paths within a tree: the betweenness centrality of a node v is the sum, over pairs of nodes, of the proportions of shortest paths that pass through v; and v is a centroid (there can be at most two) if it minimises the sum of the distances to the other nodes in the tree. We find that betweenness centrality in a large, random simply generated tree is generally linear in the size n of the tree, and that due to the tall, thin nature of simply generated trees, the probability of a random node having quadratic-order betweenness centrality decreases as n increases. This leads to a kth moment of order n2k−(1/2) for the betweenness centrality of a root node, even though a limiting distribution arises upon linearly rescaling the betweenness centrality. The class of labelled subcritical graphs, which are tree-like in structure, behave similarly. Betweenness centrality in a random increasing tree is also usually linear, except for nodes near to the root of the tree, which typically have centralities of order n2. The kth moment of the betweenness centrality of any node with a fixed label is thus of order n2k, but once again the distribution of the betweenness centrality of a random node converges to a limit when scaled by 1/n. To complement known results involving centroid nodes in simply generated trees, we also derive limiting distributions, along with limits of moments, for the depth, label, and subtree size of the centroid nearest to the root in an increasing tree. The first two of these distributions are concentrated around the root, while the latter is a combination of a point measure at 1 and a decreasing density on [1/2, 1). In addition, we show that the distributions of the maximum betweenness centrality in simply generated and increasing trees converge, upon suitable rescalings, to limiting distributions, and that the probability of the centroid attaining maximal betweenness centrality tends in both cases to a limiting constant.