Centrality in random trees
Date
2017-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
AFRIKAANSE OPSOMMING : Ons beskou twee konsepte van sentraliteit—naamlik, die tussensentraliteit van ’n punt en of dit ’n sentroïed is of nie—in families van eenvoudig gegenereerde en toenemende bome. Albei hierdie konsepte word gedefinieer in terme van paaie binne ’n boom: die tussensentraliteit van ’n punt v is die som, oor pare punte, van die verhouding van kortste paaie wat deur v beweeg; en v is ’n sentroïed indien dit die som van die afstande tot ander punte in die boom minimeer. Ons vind dat tussensentraliteit in ’n groot, lukrake eenvoudig gegenereerde boom is oor die algemeen lineêr in verhouding tot die grootte n van die boom, en as gevolg van die lang, dun aard van eenvoudig gegenereerde bome, sal die waarskynlikheid dat ’n ewekansige punt kwadratiese-orde tussensentraliteit sal hê verminder soos wat n vermeerder word. Dit lei tot ’n kde moment van orde n2k−(1/2), alhoewel daar ’n limietverdeling ontstaan sodra die tussensentraliteit lineêr herskaal word. Tussensentraliteit in ’n lukrake toenemende boom is ook gewoonlik lineêr, behalwe vir punte naby aan die wortel van die boom, wat tipies sentraliteite het van orde n2. Die kde moment van die tussensentraliteit van enige punt met ’n vaste kode is dus van orde n2k, maar weereens sal die verspreiding van die tussensentraliteit van ’n ewekansige punt konvergeer tot ’n limiet wanneer daar geskaal word met 1/n. Om by bekende resultate wat sentroïed punte in eenvoudig gegenereerde bome insluit aan te vul, lei ons ook limietverdelings af, saam met limiete van momente, vir die diepte, kode, en subboomgrootte van die sentroïed naaste aan die wortel in ’n toenemende boom. Die eerste twee van hierdie verdelings is gekonsentreer rondom die wortel, terwyl die laasgenoemde is ’n kombinasie van ’n puntmaat by 1 en ’n dalende digtheid op [1/2, 1). Daarbenewens wys ons dat die verdelings van die maksimum tussensentraliteit in eenvoudig gegenereerde en toenemende bome konvergeer, op geskikte skalerings, na limietverdelings, en die waarskynlikheid dat die sentroïed ook ’n maksimale tussensentraliteit bereik neig in albei gevalle tot limietkonstantes.
AFRIKAANSE OPSOMMING : Ons beskou twee konsepte van sentraliteit—naamlik, die tussensentraliteit van ’n punt en of dit ’n sentroïed is of nie—in families van eenvoudig gegenereerde en toenemende bome. Albei hierdie konsepte word gedefinieer in terme van paaie binne ’n boom: die tussensentraliteit van ’n punt v is die som, oor pare punte, van die verhouding van kortste paaie wat deur v beweeg; en v is ’n sentroïed indien dit die som van die afstande tot ander punte in die boom minimeer. Ons vind dat tussensentraliteit in ’n groot, lukrake eenvoudig gegenereerde boom is oor die algemeen lineêr in verhouding tot die grootte n van die boom, en as gevolg van die lang, dun aard van eenvoudig gegenereerde bome, sal die waarskynlikheid dat ’n ewekansige punt kwadratiese-orde tussensentraliteit sal hê verminder soos wat n vermeerder word. Dit lei tot ’n kde moment van orde n2k−(1/2), alhoewel daar ’n limietverdeling ontstaan sodra die tussensentraliteit lineêr herskaal word. Tussensentraliteit in ’n lukrake toenemende boom is ook gewoonlik lineêr, behalwe vir punte naby aan die wortel van die boom, wat tipies sentraliteite het van orde n2. Die kde moment van die tussensentraliteit van enige punt met ’n vaste kode is dus van orde n2k, maar weereens sal die verspreiding van die tussensentraliteit van ’n ewekansige punt konvergeer tot ’n limiet wanneer daar geskaal word met 1/n. Om by bekende resultate wat sentroïed punte in eenvoudig gegenereerde bome insluit aan te vul, lei ons ook limietverdelings af, saam met limiete van momente, vir die diepte, kode, en subboomgrootte van die sentroïed naaste aan die wortel in ’n toenemende boom. Die eerste twee van hierdie verdelings is gekonsentreer rondom die wortel, terwyl die laasgenoemde is ’n kombinasie van ’n puntmaat by 1 en ’n dalende digtheid op [1/2, 1). Daarbenewens wys ons dat die verdelings van die maksimum tussensentraliteit in eenvoudig gegenereerde en toenemende bome konvergeer, op geskikte skalerings, na limietverdelings, en die waarskynlikheid dat die sentroïed ook ’n maksimale tussensentraliteit bereik neig in albei gevalle tot limietkonstantes.
Description
Thesis (PhD)--Stellenbosch University, 2017
Keywords
Analytic combinatorics, Betweenness centrality, Simply generated trees, Increasing trees, Centroids, Random trees, UCTD