Browsing by Author "Durant, Kevin"

Now showing 1 - 3 of 3
  • 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.
  • Thumbnail Image
    Item
    Investigating the non-termination of affine loops
    (Stellenbosch : Stellenbosch University, 2013-03) Durant, Kevin; Visser, Willem; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Computer Science.
    ENGLISH ABSTRACT: The search for non-terminating paths within a program is a crucial part of software verification, as the detection of anfinite path is often the only manner of falsifying program termination - the failure of a termination prover to verify termination does not necessarily imply that a program is non-terminating. This document describes the development and implementation of two focussed techniques for investigating the non-termination of affine loops. The developed techniques depend on the known non-termination concepts of recurrent sets and Jordan matrix decomposition respectively, and imply the decidability of single-variable and cyclic affine loops. Furthermore, the techniques prove to be practically capable methods for both the location of non-terminating paths, as well as the generation of preconditions for non-termination.
  • Thumbnail Image
    Item
    On the centroid of increasing trees
    (Episciences.org, 2019) Durant, Kevin; Wagner, Stephan
    A centroid node in a tree is a node for which the sum of the distances to all other nodes attains its minimum, or equivalently a node with the property that none of its branches contains more than half of the other nodes. We generalise some known results regarding the behaviour of centroid nodes in random recursive trees (due to Moon) to the class of very simple increasing trees, which also includes the families of plane-oriented and d-ary increasing trees. In particular, we derive limits of distributions and moments for the depth and label of the centroid node nearest to the root, as well as for the size of the subtree rooted at this node.