Pontificia Universidad Católica de Chile, Chile University of Warsaw, Poland
Jane Open Access and Joan R. Public [100]Data management systems.

# How do centrality measures choose the root of trees?111This paper is a
resubmission of the article titled “On the foundations of data centrality:the
trees case”. We marked in blue the changes made concerning the previous
version. In the appendix, we attached a response letter addressing the main
comments provided by the reviewers.

Cristian Riveros and Jorge Salas  Oskar Skibski

###### Abstract

Centrality measures are widely used to assign importance to graph-structured
data. Recently, understanding the principles of such measures has attracted a
lot of attention. Given that measures are diverse, this research has usually
focused on classes of centrality measures. In this work, we provide a
different approach by focusing on classes of graphs instead of classes of
measures to understand the underlying principles among various measures. More
precisely, we study the class of trees. We observe that even in the case of
trees, there is no consensus on which node should be selected as the most
central. To analyze the behavior of centrality measures on trees, we introduce
a property of _tree rooting_ that states a measure selects one or two adjacent
nodes as the most important, and the importance decreases from them in all
directions. This property is satisfied by closeness centrality but violated by
PageRank. We show that, for several centrality measures that root trees, the
comparison of adjacent nodes can be inferred by _potential functions_ that
assess the quality of trees. We use these functions to give fundamental
insights on rooting and derive a characterization explaining why some measure
root trees. Moreover, we provide an almost liner-time algorithm to compute the
root of a graph by using potential functions. Finally, using a family of
potential functions, we show that many ways of tree rooting exist with
desirable properties.

###### keywords:

Databases, centrality measures, data centrality, graph theory.

###### category:

##  1 Introduction

Centrality measures are fundamental tools for network analysis. They are used
in a plethora of applications from various areas of science, such as finding
people who are more likely to spread a disease in the event of an epidemic
[10] or highlighting cancer genes in proteomic data [15]. In all these
applications, people use centrality measures to assess graph data and rank
which nodes are the most relevant by only using the graph’s structure.

Database systems have also incorporated centrality measures to rank nodes in
graph data. The first significant use of a centrality measure in a data
management problem is by the Google search engine, which successfully
introduced PageRank [22] for assessing the importance of a website on the web.
Indeed, today graph databases, like Neo4j [1] or TigerGraph [2], natively
support centrality algorithms for ranking nodes or analyzing the graph
structure. Furthermore, new applications for centrality measures have emerged
over knowledge graphs for entity linking [19] or semantic web search engines
where ranking results is a core task [14]. More generally, centrality measures
play a central role in _network science_ , where they are one of the main
algorithmic metrics for analyzing graphs [20].

Although more than 200 measures have been proposed in the literature today, it
is less clear how one can compare them. Precisely, these measures assess the
position of a vertex in the network based on various elements (e.g., degree,
number of paths, eigenvector), which makes it hard to compare their
properties. Since people propose dozens of new measures every year, choosing a
measure for a specific application becomes more and more challenging. In
recent years, efforts at understanding and explaining differences between
existing measures have intensified, making the foundational aspects of
centrality measures an active research topic [5, 26, 24, 27]. Given the
diversity of these measures, people have usually followed an axiomatic
approach by considering classes of measures like game-theoretical [27] or
motif-based [24] measures. Until now, no research has focused on graph classes
to check some similarities between different centrality measures.

This paper aims to understand how centrality measures operate on trees (i.e.,
acyclic undirected graphs), as this is a crucial graph family where we can
compare different centrality measures and understand their underlying
principles. Indeed, even in the case of trees, centrality measures vary
significantly as different measures could indicate other vertices as the most
central in the same tree. For example, consider a line graph: while the middle
vertex (or vertices) are ranked first according to most centrality measures,
Google’s PageRank puts the second and the second-to-last vertices at the top
of the ranking. This simple example shows that not only do different measures
select different vertices, but even one measure may select several vertices
from different parts of the tree as the most important. Moreover, although
PageRank diverges, other centrality measures (e.g., closeness or all-subgraph)
coincide, probably following the same underlying principles.

A natural question here is why we should start considering centrality measures
over the class of trees. We see several reasons for studying the principle
aspects of centrality measures over trees. First, undirected trees are
arguably the simplest and non-trivial graph class to study centrality
measures. Indeed, trees have a more amenable structure than general graphs,
given that, among other properties, every edge is a cutting edge, and there is
a unique path between any two nodes. Second, every general result on
centrality measures should include trees, and it should answer similar
questions to the one studied in this paper. Thus, understanding centrality
measures over trees could guide the study of other graph families. Third and
last, trees are probably the most ubiquitous graph structure in computer
science and databases. Therefore, studying centrality measures over trees
could be helpful for the application of centrality measures in data management
and other areas (see Section 8 for some extensions and possible applications
of centrality measures over trees).

What principle aspect of centrality measures can we study over the class of
trees? In this paper, we focus on understanding one of the main questions over
trees: how centrality measures choose the most central nodes in trees, why
some measures define a single important node (usually called the root), and
why others do not. For answering these questions, the main contributions are
as follows:

  1. 1.

We introduce the _tree rooting property_ which states that a measure selects
one or two adjacent vertices in a tree as the most important, and the
importance decreases from them in all directions. We found that closeness,
eccentricity, and all-subgraphs centralities (see Section 2) satisfy this
rooting property but often rank different vertices at the top. Instead,
measures like degree and betweenness do not satisfy this property. We call the
vertex (or two vertices) ranked first the “root” and say that such measures
_root trees_.

  2. 2.

To understand what distinguishes measures that root trees we focus on the
question: how to choose which out of two adjacent vertices is more central? We
observe that most centrality measures, including all standard ones that root
trees, answer this question by comparing subtrees of both vertices. More
precisely, we introduce a framework of _potential functions_ that assess the
quality or “potential” of an arbitrary tree. Now, we show that most centrality
measures admit a potential function such that the vertex which subtree has
higher potential value is considered more central.

  3. 3.

We show that if a centrality measure has a potential function, then it roots
trees if, and only if, the potential function is _symmetric_. This property
means that the potential of a tree is larger than the potential of any proper
complete subtree. In particular, the potential function of closeness,
eccentricity, and all-subgraphs centrality are symmetric, but the potential
functions of degree and betweenness centralities are not; as a result, the
later centralities do not root trees.

  4. 4.

We use our framework of potential functions to understand better the class of
measures that root trees. More specifically, we show three applications of
potential functions. Our first application is to study efficient algorithms
for computing a root when centrality measures have potential functions and
root trees. By exploiting symmetric potential functions, we show that, given a
tree $T$, we can compute the most central vertex in time
$\mathcal{O}(|T|\log(|T|))$ whenever one can calculate the potential function
locally. Interestingly, this general algorithm works independently of the
centrality measures and only depends on the potential function.

  5. 5.

Our second application of potential functions is to understand desirable
properties over tree rooting measures. Although a centrality measure could
root trees, it can behave inconsistently. For instance, a rooting centrality
measure could choose the root of a tree $T$ close to a leaf when the size of
$T$ is even and far from the leaves when the size of $T$ is odd. Therefore, we
study when centrality measures consistently root trees through their potential
functions. We propose a monotonicity property that imposes additional
consistency conditions on how the root is selected and characterizes which
potential functions satisfy this property.

  6. 6.

Our last application shows how to design and build new potential functions
that consistently root trees. Specifically, we present infinitely many
constructive potential functions that satisfy all properties discussed so far.
In particular, the algorithm for finding the root applies to any of them. We
believe that this family of measures is interesting in its own right and can
be used in several data-driven scenarios.

#### Related work

Our work could be included into a broad literature that focuses on the
analysis of theoretical properties of centrality measures. The classic
approach is to analyze standard centrality measures with respect to simple
desirable properties. Different properties have been considered over the years
[25, 21, 6, 5]. Most of them, however, are very simple (e.g., invariance under
automorphism) or not satisfied by most measures. Similarly, in our work, we
propose several properties specific for trees. Focusing on trees allows us to
identify meaningful properties shared by many measures based on completely
different principles.

Another approach is to create a common framework for large classes of
centrality measures. In such frameworks, centrality measures are presented as
a function of some underlying structure of the graph. Hence, the emphasis is
focused on the differences between these functions and their implications for
various measures defined under such framework. In this spirit, classes of
measures based on distances [12], nodal statistics [4], coalitional game
theory [27], subgraphs [24] and vitality functions [26] have been analyzed in
the literature. On the opposite, our framework of potential functions can be
considered as an approach focused on classes of graphs instead of classes of
measures. Yet another approach, less related to our work, is to focus on one
or several similar measures and provide their full axiomatic characterization.
In this spirit, axiomatizations of PageRank [29], eigenvector [17], beta-
measure and degree [28] and many more have been developed in the literature.

There is also a line of research that studies methods for solely choosing one
most central vertex in a tree that does not necessarily come from the
centrality analysis (see, e.g., [23] for an overview). However, such methods
coincide with the top vertices selected by centrality measures that we
consider in our work. In particular, the center of a tree coincides with
eccentricity, and the median, as well as the centroid, coincides with
closeness centrality.

##  2 Preliminaries

#### Undirected graphs

In this paper, we consider _finite undirected graphs_ of the form $G=(V,E)$
where $V$ is a finite non-empty set and $E\subseteq 2^{V}$ such that $|e|=2$
for all $e\in E$. For convenience, given a graph $G=(V,E)$ we use $V(G)$ for
indicating the set of _vertices_ $V$ and $E(G)$ for the set of _edges_ $E$. We
write $N_{G}(v)$ for the _neighbourhood_ of $v$ in $G$, namely,
$N_{G}(v)\subseteq V(G)$ such that $u\in N_{G}(v)$ if, and only if,
$\\{u,v\\}\in E(G)$. If this is the case, we say that $u$ and $v$ are
_adjacent_.

We say that a graph $G^{\prime}=(V^{\prime},E^{\prime})$ is a _subgraph_ of
$G$, denoted $G^{\prime}\subseteq G$, if $V^{\prime}\subseteq V$ and
$E^{\prime}\subseteq E$. Note that $\subseteq$ forms a partial order between
graphs. For a sequence of graphs
$G_{1}=(V_{1},E_{1}),\ldots,G_{m}=(V_{m},E_{m})$ we denote by
$\cup_{i=1}^{m}G_{i}$ the graph $(V,E)$ such that $V=\bigcup_{i=1}^{m}V_{i}$
and $E=\bigcup_{i=1}^{m}E_{i}$. Given a graph $G$ and an edge $e=\\{u,v\\}$,
we write $G+e$ to be the new graph $G$ with the additional edge $e$, formally,
$V(G+e)=V(G)\cup e$ and $E(G+e)=E(G)\cup\\{e\\}$.

From now on, fix an enumerable set $\mathcal{V}$ of vertices. We define the
_set of all graphs_ using vertices from $\mathcal{V}$ as $\mathcal{G}$.
Further, we define the set $\mathcal{VG}$ as all pairs _vertex-graph_ $(v,G)$
such that $v\in V(G)$ and $G\in\mathcal{G}$. In the sequel, for a pair $(v,G)$
we assume that $(v,G)\in\mathcal{VG}$, unless stated otherwise. We say that
graphs $G_{1}$ and $G_{2}$ are _isomorphic_ , denoted by $G_{1}\cong G_{2}$,
if there exists an bijective function (_isomorphism_) $f:V(G_{1})\rightarrow
V(G_{2})$ such that $\\{u,v\\}\in E(G_{1})$ if, and only if,
$\\{f(u),f(v)\\}\in E(G_{2})$. We also say that $(v_{1},G_{1})$ and
$(v_{2},G_{2})$ are isomorphic, denoted by $(v_{1},G_{1})\cong(v_{2},G_{2})$,
if there exists an isomorphism $f$ between $G_{1}$ and $G_{2}$ and
$f(v_{1})=v_{2}$. Note that $\cong$ is an equivalence relation over
$\mathcal{G}$ and over $\mathcal{VG}$.

A _path_ in $G$ is a sequence of vertices $\pi=v_{0},\ldots,v_{n}$ such that
$\\{v_{i},v_{i+1}\\}\in E$ for every $i<n$, and we say that $\pi$ is a _path_
from $v_{0}$ to $v_{n}$. We say that $\pi$ is _simple_ if $v_{i}\neq v_{j}$
for every $0\leq i<j<n$. From now on, we usually assume that paths are simple
unless stated otherwise. We define the _length_ of $\pi$ as $|\pi|=n$. We
agree that $v_{0}$ is the _trivial path_ of length $0$ from $v_{0}$ to itself.
Given $R,R^{\prime}\subseteq V(G)$, we say that $\pi=v_{0},\ldots,v_{n}$ is a
path from $R$ to $R^{\prime}$ if $v_{0}\in R$, $v_{n}\in R^{\prime}$, and
$v_{i}\notin R\cup R^{\prime}$ for every $i\in[1,n-1]$. We say that a graph
$G$ is _connected_ if there exists a path between every pair of vertices.

#### Centrality measures

A _centrality measure_ , or just a _measure_ , is any function
$C:\mathcal{VG}\to\mathbb{R}$ that assigns a score $C(v,G)$ to $v$ depending
on its graph $G$. Here, we use the standard assumption that, the higher the
score $C(v,G)$, the more important or “central” is $v$ in $G$. We also assume
that every centrality measure is _closed under isomorphism_ , namely, if
$(v_{1},G_{1})\cong(v_{2},G_{2})$ then $C(v_{1},G_{1})=C(v_{2},G_{2})$, which
is a standard assumption in the literature [8, 25].

Next, we recall four centrality measures that we will regularly use as
examples: _degree_ , _closeness_ , _eccentricity_ , and _all-subgraphs_
centralities. During this work, we also mention _betweenness_ [11], _decay_
[16], _PageRank_ [22], and _eigenvector_ [7] centralities. Given that we do
not use them directly, their definitions are in the appendix.

#### Degree centrality

Degree centrality is probably the most straightforward measure. Basically, the
bigger the neighborhood of a vertex (i.e., adjacent vertices), the more
central it is in the graph. Formally, we define _degree centrality_ as
follows: $\textsc{Degree}(v,G)=|N_{G}(v)|$.

#### Closeness centrality

For every graph $G$ and vertices $v,u\in V(G)$ we define the _distance_
between $v$ and $u$ in $G$ as $d_{G}(v,u)=|\pi_{v,u}|$ where $\pi_{v,u}$ is a
shortest path from $v$ to $u$ in $G$. Then _closeness centrality_ [25] is
defined as: $\textsc{Closeness}(v,G)=1/\sum_{u\in K_{v}(G)}d_{G}(v,u)$ where
$K_{v}(G)$ is the connected component of $G$ containing $v$. Closeness is
usually called a geometrical measure because it is based on the distance
inside a graph. The intuition behind closeness centrality is simple: the
closer a vertex is to everyone in the component (i.e., $\sum_{u\in
K_{v}(G)}d_{G}(v,u)$ is small) the more important it is.

#### Eccentricity centrality

Another important notion in graph theory is radius. In simple words, we can
define the center of a graph $G$ as the vertex that minimizes the maximum
distance in $G$. Formally, $v$ is the center of $G$ if it minimizes
$\max_{u\not=v\in V(G)}d_{G}(v,u)$. Then, the radius of $G$ is defined as the
maximum distance from the center. Now, _eccentricity measure_ [13] is
precisely the one centrality that selects the center of a graph as the most
important vertex, defined as $\textsc{Eccentricity}(v,G)=1/\max_{u\in
V(G)}d_{G}(v,u)$.

#### All-subgraphs centrality

Given a graph $G=(V,E)$ and a vertex $v\in V$, we denote by $\mathcal{A}(v,G)$
the set of all connected subgraphs of $G$ that contain $v$, formally,
$\mathcal{A}(v,G)=\\{S\subseteq G\mid v\in V(S)\text{ and }S\text{ is
connected}\\}$. Then _all-subgraphs centrality_ [24] of $v$ in $G$ is defined
as: $\textsc{AllSubgraphs}(v,G)=\log_{2}|\mathcal{A}(v,G)|$. All-subgraphs
centrality was recently proposed in [24], proving that it satisfies several
desirable properties as a centrality measure. Intuitively, it says that a
vertex will be more relevant in a graph if it has more connected subgraphs
surrounding it.

#### Undirected Trees

This paper is about _undirected trees_ (or just trees), so we use some special
notation for them. Specifically, we say that a graph $T$ is a _tree_ if it is
connected and for every $u,v\in V(T)$ there exists a unique path that connects
$u$ with $v$ in $T$. We usually use $T$ to denote a tree. Further, we say that
$v\in V(T)$ is a _leaf_ of $T$ if $|N_{T}(v)|=1$. If $v$ is a leaf and
$N_{T}(v)=\\{u\\}$, then we say that $u$ is the _parent_ of $v$. Note that
trees are a special class of undirected graphs, and all previous definitions
apply. In particular, we can use and apply centrality measures over trees.

We say that $T^{\prime}$ is a _subtree_ of $T$ if $T^{\prime}\subseteq T$ and
$T^{\prime}$ is a tree. We also say that $T^{\prime}$ is a _complete subtree_
of $T$ if $T^{\prime}\subseteq T$ and there is at most one vertex in
$V(T^{\prime})$ connected to some vertex in $V(T)\setminus V(T^{\prime})$,
namely, $|\\{v\in V(T^{\prime})\mid\exists u\in V(T)\setminus
V(T^{\prime}).\,\\{u,v\\}\in E(T)\\}|\leq 1$.

The following notation will be useful in the paper to decompose trees. Given a
tree $T$ and two adjacent vertices $u,v\in V(T)$, we denote by $T_{u,v}$ the
maximum subtree of $T$ that contains $u$ and not $v$. For example, if $T=$ ,
then $T_{\circ,\bullet}=\raisebox{-2.27621pt}{\mbox{ \leavevmode\hbox
to13.1pt{\vbox to8.74pt{\pgfpicture\makeatletter\hbox{\hskip
11.48091pt\lower-4.36772pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}{}\pgfsys@moveto{1.41705pt}{0.0pt}\pgfsys@curveto{1.41705pt}{0.78262pt}{0.78262pt}{1.41705pt}{0.0pt}{1.41705pt}\pgfsys@curveto{-0.78262pt}{1.41705pt}{-1.41705pt}{0.78262pt}{-1.41705pt}{0.0pt}\pgfsys@curveto{-1.41705pt}{-0.78262pt}{-0.78262pt}{-1.41705pt}{0.0pt}{-1.41705pt}\pgfsys@curveto{0.78262pt}{-1.41705pt}{1.41705pt}{-0.78262pt}{1.41705pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.2}{0.0}{0.0}{0.2}{-1.4226pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{\minipage[t]{14.22638pt}\endminipage}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{}{{}}{}
{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{} {}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.2pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}\pgfsys@moveto{-1.36429pt}{0.51158pt}\pgfsys@lineto{-10.63187pt}{3.98685pt}\pgfsys@curveto{-11.04556pt}{4.14197pt}{-11.38092pt}{3.90956pt}{-11.38092pt}{3.46773pt}\pgfsys@lineto{-11.38092pt}{-3.46773pt}\pgfsys@curveto{-11.38092pt}{-3.90956pt}{-11.04556pt}{-4.14197pt}{-10.63187pt}{-3.98685pt}\pgfsys@lineto{-1.36429pt}{-0.51158pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\par\par
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$  and
$T_{\bullet,\circ}=\raisebox{-2.27621pt}{\mbox{ \leavevmode\hbox
to13.1pt{\vbox
to8.74pt{\pgfpicture\makeatletter\hbox{\hskip-6.91885pt\lower-4.36772pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
\par{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}{}\pgfsys@moveto{9.95296pt}{0.0pt}\pgfsys@curveto{9.95296pt}{0.78262pt}{9.31853pt}{1.41705pt}{8.5359pt}{1.41705pt}\pgfsys@curveto{7.75328pt}{1.41705pt}{7.11885pt}{0.78262pt}{7.11885pt}{0.0pt}\pgfsys@curveto{7.11885pt}{-0.78262pt}{7.75328pt}{-1.41705pt}{8.5359pt}{-1.41705pt}\pgfsys@curveto{9.31853pt}{-1.41705pt}{9.95296pt}{-0.78262pt}{9.95296pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{8.5359pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.2}{0.0}{0.0}{0.2}{7.1133pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{\minipage[t]{14.22638pt}\endminipage}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{}{{}}{}
{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{} {}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.2pt}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}\pgfsys@moveto{9.90019pt}{0.5116pt}\pgfsys@lineto{19.16779pt}{3.98685pt}\pgfsys@curveto{19.58148pt}{4.14197pt}{19.91684pt}{3.90956pt}{19.91684pt}{3.46773pt}\pgfsys@lineto{19.91684pt}{-3.46773pt}\pgfsys@curveto{19.91684pt}{-3.90956pt}{19.58148pt}{-4.14197pt}{19.16779pt}{-3.98685pt}\pgfsys@lineto{9.90019pt}{-0.5116pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\par\par
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$ .

Finally, we consider some special trees to give examples or show some
properties of centrality measures. For a vertex $v$ we define
$G_{v}=(\\{v\\},\emptyset)$, and for an edge $e$ we define
$G_{e}=(e,\\{e\\})$, namely, the graphs with _one isolated vertex_ $v$ or _one
isolated edge_ $e$, respectively. Similarly, for any $n\geq 1$ we write
$L_{n}$ for the _line_ with $n$ vertices where $V(L_{n})=\\{0,\ldots,n-1\\}$
and $E(L_{n})=\\{\\{i,i+1\\}\mid 0\leq i<n-1\\}$.

##  3 Tree rooting centrality measures

We start by giving a formal definition of when a centrality measure $C$ roots
trees. For this, let $C$ be a centrality measure. We define the set
$\textsc{Max}_{C}(T)$ to be the set of most central vertices with respect to
$C$ in a tree $T$, namely, $v\in\textsc{Max}_{C}(T)$ iff $C(u,T)\leq C(v,T)$
for every $u\in V(T)$.

######  Definition 3.1.

We say that a centrality measure $C$ _roots trees_ if for every tree $T$, the
set of most central vertices $\textsc{Max}_{C}(T)$ consists of one vertex or
two adjacent vertices. Moreover, for every $u\notin\textsc{Max}_{C}(T)$ if
$u_{0}u_{1}\ldots u_{n}$ is the unique path from $\textsc{Max}_{C}(T)$ to $u$,
then $C(u_{i},T)>C(u_{i+1},T)$ for every $i\in[0,n-1]$.

In the following, if a centrality measure roots trees, we also say that it
satisfies the _tree rooting property_ (i.e., Definition 3.1). We can motivate
this property as follows. We treat vertices with the highest centrality as
“roots”. For the first part of the definition, we assume there is a single
source of importance – one vertex or two adjacent vertices. We allow two
adjacent vertices to be the roots, as in some graphs, due to their symmetrical
structure, it is impossible to indicate one most central vertex. This is, for
example, the case of a line with an even number of vertices (e.g., ). In such
a scenario the edge between both can be considered the real root of the tree.
For the second part, we assume that the centrality should decrease from the
root through branches. This restriction aligns with the intuition that the
closer a vertex is to the root, the more central it is.

We continue by giving examples of measures that root trees, and some others
that do not.

Closeness

Eccentricity

AllSubgraphs

Others

Figure 1: The first three trees exemplify how closeness, eccentricity, and
all-subgraphs centralities root trees. We mark the most central vertex with a
black star. The colors show how the centrality value decreases through the
branches (i.e., whiter vertices are less central). The fourth tree is a
counter-example that shows why other centralities do not root trees.

######  Example 3.2.

Closeness, eccentricity, and all-subgraphs all root trees. It was already
noticed [18] that over trees, closeness and eccentricity define at most two
maximum vertices, and both are connected. On the other hand, it is more subtle
to show that all-subgraphs centrality roots trees. This fact, however, will
follow from the framework developed in Section 4. As an illustration, in
Figure 1 we show how closeness, eccentricity, and all-subgraphs behave over
the same tree. One can verify that each measure declares one vertex with the
maximum centrality (this vertex is marked with a black star). Moreover, the
centrality decreases through the branches (the lower the centrality the whiter
the color). It is interesting that, although the three measures root trees,
they declare different vertices as the most central.

######  Example 3.3.

One can easily check that degree centrality does not root trees. Indeed, the
last tree at Figure 1 is an example where degree centrality declares two
maximum vertices, and they are not adjacent. Indeed, all measures presented in
Section 2, except closeness, eccentricity, and all-subgraphs, do not root
trees. For all of them, the last tree at Figure 1 is a counterexample where
they violate the tree rooting property. At Figure 2, we show a table that
summarize which centrality measures considered in this paper root trees.

An important consequence of assigning a root to a tree is that each vertex has
a parent (except for the root). Here, the unique path from the root to the
vertex defines its parent. Another possibility would be to use the centrality
measure to find the neighbour with higher centrality, and declare it as the
parent. We capture this intuition in the following property.

######  Definition 3.4.

We say that a measure $C$ satisfies the _at-most-one-parent_ property if for
every tree $T$ and $v\in V(T)$ there exists at most one neighbour $u\in
N_{T}(v)$ such that $C(v,T)\leq\leavevmode\nobreak\ C(u,T)$.

Clearly, if a centrality measure $C$ roots trees, then it also satisfies at-
most-one-parent. The other direction is also true, providing an alternative
characterization for tree rooting.

######  Proposition 3.5.

A centrality measure roots trees if, and only if, it satisfies the at-most-
one-parent property.

Notice that tree rooting is a global property over a tree but, instead, at-
most-one-parent is a local property of the neighbourhoods of a tree, which is
easier to prove for a centrality measure. Indeed, in the next section we use
this alternative definition to prove our main characterization for tree
rooting.

In some trees the root is uniquely characterized solely by the tree rooting
property. This happens because every centrality must be closed under
isomorphism which implies that isomorphic vertices have the same centrality.
For example, one can verify that for the line $L_{n}$ the roots must be the
set $\\{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil\\}$. Indeed,
every vertex $i\leq\frac{n-1}{2}$ is isomorphic with the vertex $n-1-i$ in
$L_{n}$. Then, if $i$ is the root, then $n-1-i$ must be the root as well.
Given that vertices $i$ and $n-1-i$ are not connected if $i<\frac{n-1}{2}$, we
get that every centrality that roots trees must declare
$\\{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil\\}$ as the root.
This idea can be extended to all symmetric trees: if $T$ is a tree with a
vertex $\circ$ that connects two isomorphic subtrees (i.e., $T=$ ), then
$\circ$ must be the root of $T$. We generalize this property as follows.

######  Definition 3.6.

We say that a centrality measure $C$ is _symmetric over trees_ if for every
tree $T$, vertex $v$, and different neighbors $u_{1},u_{2}\in N_{T}(v)$ such
that $(u_{1},T_{u_{1},v})\cong(u_{2},T_{u_{2},v})$, then $C(u_{1},T)<C(v,T)$
and $C(u_{2},T)<C(v,T)$.

$v$$u_{1}$$u_{2}$$<$$>$$T^{\prime}$$T_{u_{1},v}$$T_{u_{2},v}$

Measures | Can root? | Potential function?
---|---|---
Closeness | Yes | Yes
Eccentricity | Yes | Yes
All-Subgraphs | Yes | Yes
Degree | No | Yes
Betweenness | No | Yes
Decay | No | Yes
PageRank | No | ?
EigenVector | No | ?

Figure 2: At the left, a graphic illustration of the symmetry property over a
tree $T$. Subtrees $T_{u_{1},v}$ and $T_{u_{2},v}$ are isomorphic, and subtree
$T^{\prime}$ represents the rest of $T$ hanging from $v$. At the right, a
table summarizes which centrality measures root trees and which one admits a
potential function.

Figure 2 (left) is a graphical representation of the symmetry property. It
generalizes the previously discussed intuition by considering any pair of
isomorphic subtrees in a (not necessarily symmetric) tree. Interestingly,
every centrality measure that roots trees must be symmetric over trees.

######  Proposition 3.7.

If a centrality measure $C$ roots trees, then $C$ is symmetric over trees.

A symmetric centrality measure may not root trees. For example, a centrality
measure could root trees with non-trivial automorphisms but not root trees
when there is none. Despite this, symmetry property is crucial for finding a
characterization for tree rooting, as we will show in the next section.

##  4 Potential functions

What have in common closeness, eccentricity, and all-subgraphs centralities?
What is the fundamental property so they can root trees? A crucial ingredient
for understanding the connection between these measures is what we call a
_potential function_ for a centrality measure.

######  Definition 4.1.

Given a centrality measure $C$, we say that $f:\mathcal{VG}\to\mathbb{R}$ is a
potential function for $C$ if $f$ is closed under isomorphism on
$\mathcal{VG}$ and, for every tree $T$ and every adjacent vertices $u,v\in
V(T)$, it holds that $C(u,T)\leq C(v,T)$ if, and only if, $f(u,T_{u,v})\leq
f(v,T_{v,u})$.

A potential function is a function that measures the “potential” of every
_rooted_ tree, i.e., a tree with one node selected and the assessment depends
on the selection. Now, a centrality measure admits some potential function if
the comparison between two adjacent vertices is determined by the potential of
their corresponding subtrees. Interestingly, in the following examples we show
that several centrality measures admit a potential function.

######  Example 4.2.

Degree, closeness, eccentricity, all-subgraphs centralities have the following
potential functions:

$\begin{array}[]{rcll}f_{\text{d}}(v,T)&:=&|N_{T}(v)|&(degree)\\\
f_{\text{c}}(v,T)&:=&|V(T)|&(closeness)\\\ f_{\text{e}}(v,T)&:=&\max_{u\in
V(T)}d_{T}(v,u)&(eccentricity)\\\
f_{\text{a}}(v,T)&:=&|\mathcal{A}(v,T)|&(all\text{-}subgraphs)\end{array}$

Let us verify that each function above is a potential function for its
corresponding measure. Take an arbitrary tree $T$ and two adjacent vertices
$u$ and $v$. It is straightforward to check that $f_{\text{d}}$ is a potential
function for degree centrality. Indeed, if $u$ has a smaller degree in its
subtree (i.e., without considering the common edge), then it also has a
smaller centrality.

For closeness centrality, the potential function $f_{\text{c}}$ is simply the
number of vertices in a tree. To see this, note that vertex $u$ has a distance
smaller by one than $v$ to all vertices from $T_{u,v}$; analogously, vertex
$v$ has a distance smaller by one than $u$ to all vertices from $T_{v,u}$. As
a result, out of both vertices, the one with the larger subtree has the
smaller sum of distances which results in the higher closeness centrality.

For eccentricity the potential function $f_{\text{e}}$ is the height of a
tree, i.e., the distance to the farthest vertex. This is because if subtree
$T_{u,v}$ is higher than $T_{v,u}$, then vertex $u$ has smaller distance to
the farthest vertex in $T$ which results in the higher eccentricity.
Interestingly, $f_{\text{e}}$ is an inverse of eccentricity.

Finally, for all-subgraphs centrality the potential function $f_{\text{a}}$ is
the number of subgraphs that contain vertex $v$. The reason is that we have
$|\mathcal{A}(u,T)|=|\mathcal{A}(u,T_{u,v})|+|\mathcal{A}(u,T_{u,v})|\cdot|\mathcal{A}(v,T_{v,u})|$
and, symmetrically,
$|\mathcal{A}(v,T)|=|\mathcal{A}(v,T_{v,u})|+|\mathcal{A}(u,T_{u,v})|\cdot|\mathcal{A}(v,T_{v,u})|$.
This implies that if $u$ has more subgraphs in $T_{u,v}$ than $v$ in
$T_{v,u}$, then it also has higher all-subgraphs centrality. Hence, as in the
case of degree centrality, the potential function coincides with the
centrality itself.

In the appendix, we also show that betweenness and decay centralities have a
potential function. As we will see later, there are centrality measures that
do not have potential functions. For the particular case of PageRank and
EigenVector it is not clear whether they admit a potential function. The table
at Figure 2 (right) summarizes which centrality measures have a potential
function.

A potential function determines the centrality order between two adjacent
vertices, but it does not imply the relation between non-adjacent vertices.
Although this information is weaker than the centrality measure itself, it is
exactly what we need to understand the centrality measures that root trees.
Precisely, which measures with potential functions root trees? To answer this
question, we first need to capture the symmetry property through the lens of
potential functions.

######  Lemma 4.3.

Let $C$ be a centrality measure and $f$ a potential function for $C$. Then $C$
is symmetric over trees if, and only if, for every tree $T$ and every pair of
adjacent vertices $u,v\in V(T)$, it holds that $f(u,T_{u,v})<f(v,T)$.

By the previous result, we will call potential functions with this property
_symmetric_. Next, we show that symmetric potential functions characterize the
tree rooting property.

######  Theorem 4.4.

Let $C$ be a centrality measure that admits a potential function $f$. Then $C$
roots trees if, and only if, $f$ is symmetric.

######  Example 4.5.

Continuing with Example 4.2 we can check that the potential functions
$f_{\text{c}}$, $f_{\text{e}}$, and $f_{\text{a}}$ for closeness,
eccentricity, and all-subgraphs, respectively, are symmetric. Indeed, for all
these functions a subtree always has less potential than the whole tree. For
this reason, $f_{\text{x}}(u,T_{u,v})<f_{\text{x}}(v,T)$ for
$\text{x}\in\\{\text{c},\text{e},\text{a}\\}$ since $T_{u,v}$ is a subgraph of
$T$. By Theorem 4.4, this proves that closeness, eccentricity, and all-
subgraphs root trees.

In turn, the potential functions of degree centrality (as well as betweenness
and decay centralities) are not symmetric and, therefore, do not root trees.
For example, for degree centrality we can take $T=$ u v , and check that
$f_{\text{d}}(u,T_{u,v})>f_{\text{d}}(v,T)$. Therefore, $f_{\text{d}}$ is not
symmetric.

We showed that all standard centrality measures that root trees can be defined
through potential functions. The natural question is: is it true for all
measures that root trees? In the following result, we show that this is not
the case and there exists a measure that roots a tree, but does not have a
potential function.

######  Proposition 4.6.

There exists a centrality measure that roots trees but does not admit a
potential function.

Potential functions and Theorem 4.4 explain why some measures root trees and
others do not. In the following sections, we use this framework to further
understand the tree rooting centrality measures in terms of algorithms,
consistency, and the design of new measures.

##  5 An algorithm to find the root

Even though not every tree rooting measure has a potential function, having
one gives us some essential properties that we can exploit. In particular,
having a symmetric potential function implies finding the root of any tree in
$\mathcal{O}(n\log(n))$-time under some assumptions on the efficiency to
compute the potential function. Notice that the naive approach of computing
the centrality for each vertex separately and then choosing the one with the
highest centrality runs in quadratic time (i.e., by assuming that computing
the centrality of a single vertex takes linear time). Instead, the algorithm
presented here runs in $\mathcal{O}(n\log(n))$ for every centrality measure
that admits a symmetric potential function.

The main intuition behind this algorithm is based on the following property
satisfied by centrality measures with a symmetric potential function.

######  Proposition 5.1.

Let $C$ be a centrality measure that has a symmetric potential function $f$.
Let $T$ be any tree, $w_{1},w_{n}\in V(T)$, and $w_{1}w_{2}...w_{n}$ be the
unique path connecting $w_{1}$ to $w_{n}$ in $T$. Whenever
$f(w_{1},T_{w_{1},w_{2}})\leq f(w_{n},T_{w_{n},w_{n-1}})$ then $C(w_{1},T)\leq
C(w_{2},T)$.

In other words, Proposition 5.1 says that if the potential of the subtree
hanging from $w_{1}$ is less than the potential of the subtree hanging from
$w_{n}$, then a root should be closer to the adjacent vertex of $w_{1}$ that
is towards the direction of $w_{n}$. This result gives us a way to traverse a
tree, starting from the leaves and going up until we find the root. More
specifically, starting from the leaves, by Proposition 5.1 we can compare the
potential of two opposite complete subtrees. Then, vertices with higher
potential in their subtree indicate the direction of higher centrality. When
we finally reach two connected vertices, the vertex with higher (or equal)
potential is a root.

1

Input: A non-trivial tree $T$ and a symmetric potential function $f$.

Output: The most central vertex of $T$ according to $f$.

2

3 Function  _Find-a-root(_$T,f$_)_:

4

5 $Q\leftarrow\texttt{Empty-queue}$

6 $H\leftarrow\\{(v,N_{T}(v))\mid v\in V(T)\\}$

7

8 foreach  _$v$ leaf of $T$_ do

9 $Q.\texttt{insert}(v,f(v,G_{v}))$

10

11 while  _$Q.\texttt{size}() >1$_

12 $v\leftarrow Q.\texttt{pull}()$

13

14 $u\leftarrow H[v]$

15 $H[u]\leftarrow H[u]\setminus\\{v\\}$

16

17 if  _$|H[u]|=1$_ then

18 $w\leftarrow H[u]$

19 $Q.\texttt{insert}(u,f(u,T_{u,w}))$

20

21

22 return $Q.\texttt{pull}()$

23

24

Algorithm 1 Find a root given a tree.

Algorithm 1 implements the above intuition based on Proposition 5.1. It
receives as input a tree $T$ and a symmetric potential function $f$, and
outputs a root of $T$ with respect to $f$. For implementing Algorithm 1 we
need two data structures, denoted by $H$ and $Q$. The first data structure $H$
is a _key-value map_ (i.e., a Hash-table), where a key can be any vertex $v\in
V(T)$ and its value is a subset of $N_{T}(v)$. We denote the value of $v$
(i.e., a key) in $H$ by $H[v]$. By some abuse of notation, when $H[v]$ is a
single vertex, we write $u\leftarrow H[v]$ to retrieve and store this vertex
in $u$. The second data structure $Q$ is a _priority-Queue_. For $v\in V(T)$
and $p\in\mathbb{R}$ we write $Q.\texttt{insert}(v,p)$ to insert $v$ in $Q$
with priority $p$. We also write $v\leftarrow Q.\texttt{pull}()$ to remove the
vertex with the lowest priority from $Q$, and store it in $v$. For both
structures, these operations can be implemented in $\mathcal{O}(\log(n))$-time
where $n$ is the number of inserted objects [9].

Algorithm 1 starts by initializing $Q$ as empty and $H$ with all key-value
pairs $(v,N_{T}(v))$ (lines 2-3). Then, it runs over all leaves $v$ of $T$ and
inserts it into $Q$ with priority $f(v,G_{v})$ where $G_{v}$ is the tree with
an isolated vertex $v$ (lines 4-5). As we already mentioned, the intuition is
to start from all leaves $v$ and use its potential (as a single vertex) for
comparing it with other vertices. Then we loop while the number of elements in
$Q$ is greater than $1$. Recall that any non-trivial tree has at least two
leaves, and therefore the algorithm reaches line 6 with $Q.\texttt{size}()\geq
2$ for the first time. Instead, if $T$ is trivial, we return the single vertex
directly in line 13.

We remove the vertex with the lowest priority from $Q$ in each iteration and
store it in $v$ (line 7). This step discards $v$ as a possible root (by
Proposition 5.1) and moves towards its “parent” represented by $u\leftarrow
H[v]$ (line 8). Given that we discarded $v$, we remove $v$ as a child of $u$,
where $H[u]$ contains the current children of $u$ (line 9). Indeed, when
$|H[u]|=1$ (line 10) this means that we have reached $u$, its parent is
$w\leftarrow H[u]$ (line 11) and its complete subtree $T_{u,w}$ hanging from
$u$ must be evaluated with $f$, and inserted in $Q$ (line 12). An important
invariant during the while-loop is that any vertex $v$ in $Q$ satisfies
$|H[v]|=1$ (except at the end of the last iteration). Conceptually, if
$H[v]=\\{w\\}$, this invariant means that $w$ is the parent of $v$ and we are
using the potential of the subtree $(v,T_{v,w})$ for comparing $v$ with other
vertices. Then when $v$ is the vertex with the lowest priority on $Q$, it
means that other vertices beat it, and a root must be towards its parent.

Finally, when there is only one vertex left in $Q$, it beats all other
vertices, and it should be one of the roots. It is necessary to mention that
if $T$ has two roots, we could also output the second root by slightly
modifying the algorithm.

Regarding time complexity, the reader can check that the for- and while-loops
take linear time on $|T|$. Each operation over $H$ and $Q$ take at most
$\log(|T|)$ steps, and overall it sum up to $\mathcal{O}(|T|\log(|T|))$ if
computing $f$ takes constant time.

Of course, the previous assumption is not always true, given that $f$ can be
any symmetric potential function. To solve this, we say that $f$ is _locally-
computable_ if, for every $T$ and $u\in V(T)$, $f(u,T)$ can be computed in
$\mathcal{O}(k)$-time from the values of its $k$-neighbors, namely, from
$f(u_{1},T_{u_{1},v}),\ldots,f(u_{k},T_{u_{k},v})$ where
$N_{T}(u)=\\{u_{1},\ldots,u_{k}\\}$. Note that by book-keeping the values
$f(u_{1},T_{u_{1},v}),\ldots,f(u_{k},T_{u_{k},v})$ of the neighbors of $u$, we
can compute $f(u,T_{u,w})$ (line 12) in $\mathcal{O}(|N_{T}(u)|)$-time. If we
sum this extra time over all vertices, it only adds $\mathcal{O}(|T|)$-steps
to the total running time of the algorithm.

######  Proposition 5.2.

Given a tree $T$ and a symmetric potential function $f$, Algorithm 1 returns a
root of $T$ with respect to $f$. Moreover, if $f$ is locally-computable, the
algorithms runs in $\mathcal{O}(|T|\cdot\log(|T|))$-time.

The reader can easily check that the potential functions of closeness,
eccentricity, and all-subgraphs are locally-computable (see also Section 7),
and then Algorithm 1 can be used for any of these measures to find the root of
any tree in $\mathcal{O}(|T|\cdot\log(|T|))$.

##  6 Consistent rooting

The tree rooting property fixes the “shape” of a centrality measure in every
possible tree. However, it does not impose any relation between roots in
different trees. As a result, even a small change (e.g., adding a leaf) may
move the root arbitrarily since there might be no relation between the roots
in a tree and the altered tree. To give an example, a centrality measure may
be defined in one way for trees with odd number of vertices, but in a
completely different way for trees with even number of vertices.

To this end, we propose a notion of _consistency_. Consistency states that if
we add a leaf to the tree, then the root may move only in its direction.

######  Definition 6.1.

We say that a centrality measure $C$ _consistently roots trees_ if it roots
trees and for every tree $T$ and vertices $u,v\in V(T)$, $w\not\in V(T)$ such
that $u\in\textsc{Max}_{C}(T)$ it holds
$\textsc{Max}_{C}(T+\\{v,w\\})\subseteq\pi_{u,w}\cup\textsc{Max}_{C}(T)$,
where $\pi_{u,w}$ is the path between $u$ and $w$ in $T+\\{v,w\\}$.

We can verify that closeness, eccentricity, and all-subgraphs centralities all
consistently root trees.

Consistency is a property of measures that root trees. However, it can be also
interpreted using a natural property for arbitrary centrality measures that we
call _monotonicity_. Monotonicity states that if vertex $v$ has a higher (or
equal) centrality than its neighbour $u$ in a tree, then this fact will not
change if we add a leaf on the side of vertex $v$.

######  Definition 6.2.

We say that a centrality measure $C$ is _monotonic_ if for every tree $T$,
vertices $v,u,w\in T$ such that $\\{v,u\\}\in E(T)$, $w\in T_{u,v}$ and vertex
$w^{\prime}\not\in V(T)$ if $C(v,T)<C(u,T)$, then
$C(v,T+\\{w,w^{\prime}\\})<C(u,T+\\{w,w^{\prime}\\})$.

Monotonicity is in fact a general property satisfied by many centrality
measures, including all geometric centralities such as closeness and decay.
The following result ties both concepts: monotonicity and consistency of
rooting.

######  Proposition 6.3.

Let $C$ be a centrality measure that roots trees. Then $C$ consistently roots
trees if, and only if, it is monotonic.

Let us turn our attention to the relation between tree rooting and potential
functions. If a centrality that roots trees admits a potential function, then
it must be consistent to some extent. However, as it turns out, it might not
consistently root trees, as we show in the following counterexample.

######  Example 6.4.

Consider the following ad-hoc centrality measure:

$C(v,T)=\textsc{Eccentricity}(v,T)-(1/|T|^{2})\cdot\textsc{Closeness}(v,T).$

Intuitively, if two vertices in a tree have different eccentricity, then their
eccentricity differs by more than $1/|T|^{2}$. Also,
$\textsc{Closeness}(v,T)\in(0,1]$. Hence, we have $C(u,T)<C(v,T)$ if, and only
if, $u$ has a smaller eccentricity than $v$ or equal eccentricity, but higher
closeness.

It is easy to verify that the following potential function corresponds to $C$:
$f(v,T)=h(v,T)-1/|T|$, where $h(v,T)$ is the distance from $v$ to the farthest
vertex in $T$.

To show that consistency is violated consider trees  and  (vertices with the
highest centrality are marked with white color). Consistency states that in
the second tree the root should stay on the left-hand side which is not the
case here.

To characterize which of the centrality measures with potential function root
trees consistently, we look at the restriction that monotonicity imposes on
the potential function.

######  Proposition 6.5.

Let $C$ be a centrality measure that admits a potential function $f$. Then $C$
is monotonic iff for every tree $T$, subtree $T^{\prime}$ of $T$, and $v\in
V(T^{\prime})$ it holds $f(v,T)\geq f(v,T^{\prime})$.

In particular, the potential function from Example 6.4 violates this
condition, as adding vertices to a tree without increasing its height
decreases the value of the potential function.

Now we can summarize rooting results and consistency regarding potential
functions as one of our principal theorems.

######  Theorem 6.6.

Let $C$ be a centrality measure that admits a potential function $f$. Then $C$
is monotonic and symmetric if, and only if, for every tree $T$, proper subtree
$T^{\prime}$ of $T$ and vertices $v\in V(T)$, $u\in V(T^{\prime})$ it holds
$f(v,T)\geq f(u,T^{\prime})$ and $f(v,T)>f(u,T^{\prime})$ if $u\neq v$.

##  7 Families of potential functions

In this section, we apply the previous results by showing how to design
potential functions that consistently root trees. Specifically, using the
following results, we can derive an infinite family of potential functions.
This family shows infinite ways to root trees with good characteristics,
namely, that are consistent and computable in $\mathcal{O}(n\log(n))$ time. In
the following, we recall some standard definitions of monoids, to then define
potential functions through them.

A _monoid_ (over $\mathbb{R}$) is a triple $(\mathbb{M},*,\mathbb{1})$ where
$\mathbb{M}\subseteq\mathbb{R}$, $*$ is a binary operation over $\mathbb{M}$,
$*$ is associative, and $\mathbb{1}\in\mathbb{M}$ is the identity of $*$
(i.e., $r*\mathbb{1}=\mathbb{1}*r=r$). We further assume that monoids are
commutative, namely, $*$ is commutative. Examples of (commutative) monoids are
$(\mathbb{R}_{\geq 0},+,0)$ and $(\mathbb{R}_{\geq 1},\times,1)$, where we use
$\mathbb{R}_{\geq c}$ for all reals greater or equal than $c$. For the sake of
presentation, in the following we will usually refer the monoid

######  Definition 7.1.

Given a monoid $(\mathbb{M},*,\mathbb{1})$ and
$\ell:\mathbb{M}\rightarrow\mathbb{M}$, we define the potential function
$f_{*,\ell}$ recursively as follows:

  1. 1.

For a vertex $v$, we define $f_{*,\ell}(v,G_{v})=\mathbb{1}$, where $G_{v}$ is
the tree with an isolated vertex $v$.

  2. 2.

For a tree $T$ and a leaf $v\in V(T)$ hanging from its parent $u\in V(T)$, we
define $f_{*,\ell}(v,T)=\ell(f_{*,\ell}(u,T_{u,v}))$. In other words, we apply
$\ell$ to the potential function of the subtree rooted at $u$. We call $\ell$
the _leaf-function_ of $f_{*,\ell}$.

  3. 3.

Given two trees $T_{1}$ and $T_{2}$ with $V(T_{1})\cap V(T_{2})=\\{v\\}$, we
define $f_{*,\ell}(v,T_{1}\cup
T_{2})=f_{*,\ell}(v,T_{1})*f_{*,\ell}(v,T_{2})$.

A potential function $f$ is _constructive_ if there exists a monoid $*$ and a
leaf-function $\ell$ such that $f=f_{*,\ell}$.

Notice that $f_{*,\ell}(v,T)$ is uniquely determined by the three cases above.
Specifically, suppose that $u_{1},\ldots,u_{k}\in N_{T}(v)$ are the neighbors
of $v$ on $T$. Then we can decompose $T$ by considering all subtrees
$T_{u_{i},v}+\\{u_{i},v\\}$ and compute $f_{*,\ell}(v,T)$ recursively:

$f_{*,\ell}(v,T)=\ell\big{(}f_{*,\ell}(u_{1},T_{u_{1},v})\big{)}*\ldots*\ell\big{(}f_{*,\ell}(u_{k},T_{u_{k},v})\big{)}$

until we reach a single vertex. Furthermore, $f_{*,\ell}$ is closed under
isomorphism over $\mathcal{VG}$ given that $*$ is associative and commutative.
Thus, we conclude that $f_{*,\ell}$ is well-defined and could work as a
potential function. In addition, $f_{*,\ell}$ is locally-computable since
$f_{*,\ell}(v,T)$ can be computed from its $k$-neighbors.

######  Example 7.2.

All potential functions presented in Example 4.2 are constructive by
considering the following monoids and leaf-functions:

$\begin{array}[]{lll}(\mathbb{R}_{\geq 0},+,0)&\ell(x)=1&(degree)\\\
(\mathbb{R}_{\geq 1},a+b-1,1)&\ell(x)=x+1&(closeness)\\\ (\mathbb{R}_{\geq
0},\max,0)&\ell(x)=x+1&(eccentricity)\\\ (\mathbb{R}_{\geq
1},\times,1)&\ell(x)=x+1&(all\text{-}subgraphs)\end{array}$

It is easy to check that each monoid and leaf-function defines the
corresponding potential function of the above measures.

One advantage of the previous definition is that it shows a way for
constructing potential functions. Moreover, we can study which properties are
necessary over $*$ and $\ell$ to guarantee that $f_{*,\ell}$ consistently root
trees. Towards this goal, we recall some standard definitions for monoids and
functions. A function $f$ is called _monotonic_ if $x\leq y$, implies
$f(x)\leq f(y)$ for every $x,y$. A monoid $(\mathbb{M},*,\mathbb{1})$ is
called _ordered_ if $x\leq y$, implies $x*z\leq y*z$ for every
$x,y,z\in\mathbb{M}$. Further, it is called _positively ordered_ if in
addition $\mathbb{1}\leq x$ for every $x\in\mathbb{M}$.

######  Lemma 7.3.

Let $(\mathbb{M},*,\mathbb{1})$ be a monoid and
$\ell:\mathbb{M}\rightarrow\mathbb{M}$ a leaf-function. The potential function
$f_{*,\ell}$ consistently roots trees whenever (1) $x<\ell(x)$ for every $x$,
(2) $\ell$ is monotonic, and (3) $(\mathbb{M},*,\mathbb{1})$ is positively
ordered.

For example, the monoids and leaf-functions of closeness, eccentricity, and
all-subgraphs (see Example 7.2), satisfy properties (1) to (3) and, as we
know, they consistently root trees. On the other hand, degree’s leaf-function
does not satisfy (1), and therefore, it does not root trees.

Lemma 7.3 shows sufficient conditions over $*$ and $\ell$ to consistently root
trees. To get a necessary condition, we need to add some technical
restrictions, and to slightly weaken conditions (2) and (3). Towards this
goal, let $\operatorname{Range}_{*,\ell}$ be the range of $f_{*,\ell}$. Define
$\bar{*}$ and $\bar{\ell}$ to be the monoid $(\mathbb{M},*,\mathbb{1})$ and
function $\ell$ restricted to $\operatorname{Range}_{*,\ell}$. For two values
$x$ and $y$, we say that $x$ is a _subtree-value_ of $y$ if there exist $T$
and $T^{\prime}$ such that $T$ is a subtree of $T^{\prime}$,
$f_{*,\ell}(u,T)=x$, and $f_{*,\ell}(u,T^{\prime})=y$ for some $u\in V(T)$.
Then we say that $\bar{\ell}$ is _monotonic over subtrees_ if $x\leq y$ and
$x$ is a subtree-value of $y$ implies that $\bar{\ell}(x)\leq\bar{\ell}(y)$.
Similarly, we say that $\bar{*}$ is _positively ordered over subtrees_ , if
$x\leq y$ and $x$ is a subtree-value of $y$, then $x*z\leq y*z$ for every
$z\in\operatorname{Range}_{*,\ell}$, and $\mathbb{1}\leq x$ for every
$x\in\operatorname{Range}_{*,\ell}$.

######  Theorem 7.4.

Let $(\mathbb{M},*,\mathbb{1})$ be a monoid and
$\ell:\mathbb{M}\rightarrow\mathbb{M}$ a leaf-function. The potential function
$f_{*,\ell}$ consistently roots trees if, and only if, (1) $x<\bar{\ell}(x)$
for every $x\in\operatorname{Range}_{*,\ell}$, (2) $\bar{\ell}$ is monotonic
over subtrees, and (3) $\bar{*}$ is positively ordered over subtrees.

Theorem 7.4 and, specifically, Lemma 7.3 give the ingredients to design
potential functions that consistently root trees and, further, we have an
algorithm to find the root in $\mathcal{O}(n\log(n))$. For instance, take a
triple $(a,b,c)\in\mathbb{R}^{3}$. Then define the monoid $(\mathbb{R}_{\geq
c},*_{c},c)$ and leaf-function $\ell_{a,b}$ such that: $x*_{c}y:=\frac{x\cdot
y}{c}$ and $\ell_{a,b}(x):=a\cdot x+b$. For example, if we consider $a=b=c=1$,
we get the monoid and leaf-function for the potential function of all-subgraph
centrality (see Example 7.2). Interestingly, one can verify that, if $a\geq
1$, $b>0$ and $c>0$, then $*_{c}$ is a monoid. Moreover, $*_{c}$ and
$\ell_{a,b}$ satisfy properties (1) to (3) of Lemma 7.3 and we get the
following result.

######  Proposition 7.5.

For every $(a,b,c)\in\mathbb{R}^{3}$ with $a\geq 1$, $b>0$, and $c>0$, the
potential function $f_{*_{c},\ell_{a,b}}$ consistently root trees.

Finally, we want to know if we can get different roots for different values
$(a,b,c)$. In other words, is it the case that for every different triples
$(a,b,c)$ and $(a^{\prime},b^{\prime},c^{\prime})$ there exists a tree $T$
such that the root of $T$ according to $f_{*_{c},\ell_{a,b}}$ is different to
one chosen by $f_{*_{c^{\prime}},\ell_{a^{\prime},b^{\prime}}}$? The next
result shows that $\\{f_{*_{c},\ell_{a,b}}\mid c\geq 1,b>0,c>0\\}$ is indeed
an infinity family of different potential functions for tree rooting.

######  Proposition 7.6.

There exists an infinite set $S\subseteq\mathbb{R}^{3}$ such that for every
$(a,b,c),(a^{\prime},b^{\prime},c^{\prime})\in S$, there exists a tree $T$
where the roots of $T$ according to $f_{*_{c},\ell_{a,b}}$ are not the same as
roots of $T$ according to $f_{*_{c^{\prime}},\ell_{b^{\prime},c^{\prime}}}$.

##  8 Discussion

We end the paper by discussing some extensions and applications.

#### Extensions to other classes of graphs

A natural criticism of focusing on trees is whether one can generalize the
know-how acquired on trees to other classes of graphs. We agree that further
research is needed to extend potential functions to new graph families.
Nevertheless, we see some exciting directions in which our work can be
extended. In particular, the idea of potential functions extends to arbitrary
graphs by considering the endpoints of a bridge instead of adjacent vertices
of a tree. More in detail, let $G$ be a connected graph and $\\{u,v\\}$ be an
edge such that $G_{u},G_{v}$ are two connected components of $G-\\{u,v\\}$
that contain $u,v$, respectively. We say that $f:\mathcal{VG}\to\mathbb{R}$ is
a _graph_ potential function for $C$ if for every such graph $G$ it holds
$C(u,T)\leq C(v,T)$ if, and only if, $f(u,G_{u})\leq f(v,G_{v})$. This
property generalizes (tree) potential functions, as every two adjacent nodes
in a tree form a bridge. As it turns out, all centrality measures listed on
Figure 2 that have (tree) potential functions (degree, closeness, betweenness,
eccentricity, all-subgraphs, decay) have identical graph potential functions.
For example, $\textsc{Eccentricity}(v,G)\leq\textsc{Eccentricity}(u,G)$ if and
only if $f_{e}(v,G_{v})\leq f_{e}(u,G_{u})$ for $f_{e}$ defined in Example
4.2. Interestingly, some centrality measures have identical potential
functions on trees but different ones on general graphs (for example,
closeness and random-walk closeness centralities).

#### Applications

In this work, we focused on the foundational aspects of understanding
centrality measures over trees, and we left for future work the application in
the context of data management. Given the axiomatic approach of our work and
given that tree structures are ubiquitous in data management, we believe that
potential functions and their implications on rooting trees could find several
exciting applications. In the following, we present some possible applications
of this work in data management scenarios.

In conjunctive query answering, the class of acyclic queries is of particular
interest, given that each query has a join tree that permits efficient
evaluation in linear time on data complexity [3]. For this, the so-called
Yannakakis algorithm [30] performs a bottom-up traversal of the join tree for
filtering the tuples that will not be part of the output. In particular, the
different ways one can root the join tree gives rise to several individual
computational schedules to obtain the same results [3]. Here, rooting the join
tree could be exploited to improve existing join evaluation algorithms by
using a particular potential function that uses the query structure and
database relations. We leave for future work on how one can use this principle
for query evaluation in the presence of join trees.

Another possible application is in the context of tree-structured data, like
XML or JSON documents. Although this data is usually rooted, assessing the
most crucial node using a centrality measure can lead to a better
understanding of the document’s structure. For instance, given a tree-
structured document, one could measure the difference between the root
provided by potential function and the original root and see how this
difference affects query evaluation, document representation, or other
metrics.

Finally, in a broader sense, one could see centrality measures over graphs as
an instance of a general database problem: find the most central data object
in the data model given its underlying structure. The data model could be a
relational database, an object-oriented database, an RDF database, or even a
tree-structure database. For all these cases, the principle should be the
same: the more relevant the data object is for its data model, the more
central it should be. The present work could be seen as the first step toward
this direction, namely, understanding data centrality in the case of trees. We
leave for future work on how to extend this line of research to other classes
of graphs or data models.

## References

  * [1] Neo4j: Centrality.  https://neo4j.com/docs/graph-data-science/current/algorithms/centrality/.  Accessed on 2022-09-21.
  * [2] Tigergraph: Centrality algorithms.  https://docs.tigergraph.com/graph-ml/current/centrality-algorithms/.  Accessed on 2022-09-21.
  * [3] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of databases, volume 8.  Addison-Wesley Reading, 1995.
  * [4] Francis Bloch, Matthew O. Jackson, and Pietro Tebaldi.  Centrality measures in networks.  arXiv preprint arXiv:1608.05845, 2019.
  * [5] Paolo Boldi, Alessandro Luongo, and Sebastiano Vigna.  Rank monotonicity in centrality measures.  Network Science, 5(4):529–550, 2017.
  * [6] Paolo Boldi and Sebastiano Vigna.  Axioms for centrality.  Internet Mathematics, 10(3-4):222–262, 2014.
  * [7] Phillip Bonacich.  Factoring and weighting approaches to status scores and clique identification.  Journal of mathematical sociology, 2(1):113–120, 1972.
  * [8] Ulrik Brandes.  Network analysis: methodological foundations, volume 3418.  Springer Science & Business Media, 2005.
  * [9] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms.  MIT press, 2009.
  * [10] Zoltán Dezső and Albert-László Barabási.  Halting viruses in scale-free networks.  Physical Review E, 65:055103, 2002.
  * [11] Linton C Freeman.  A set of measures of centrality based on betweenness.  Sociometry, pages 35–41, 1977.
  * [12] Manuj Garg.  Axiomatic foundations of centrality in networks.  Available at SSRN 1372441, 2009.
  * [13] Per Hage and Frank Harary.  Eccentricity and centrality in networks.  Social networks, 17(1):57–63, 1995.
  * [14] Aidan Hogan, Andreas Harth, Jürgen Umbrich, Sheila Kinsella, Axel Polleres, and Stefan Decker.  Searching and browsing linked data with swse: The semantic web search engine.  Journal of web semantics, 9(4):365–401, 2011.
  * [15] Gábor Iván and Vince Grolmusz.  When the web meets the cell: using personalized PageRank for analyzing protein interaction networks.  Bioinformatics, 27(3):405–407, 2010.
  * [16] Matthew O Jackson.  Social and economic networks.  Princeton university press, 2010.
  * [17] Mitri Kitti.  Axioms for centrality scoring with principal eigenvectors.  Social Choice and Welfare, 46(3):639–653, 2016.
  * [18] Dirk Koschützki, Katharina Anna Lehmann, Leon Peeters, Stefan Richter, Dagmar Tenfelde-Podehl, and Oliver Zlotowski.  Centrality indices.  In Network analysis, pages 16–61. Springer, 2005.
  * [19] Jose L Martinez-Rodriguez, Aidan Hogan, and Ivan Lopez-Arevalo.  Information extraction meets the semantic web: a survey.  Semantic Web, 11(2):255–335, 2020.
  * [20] Mark Newman.  Networks.  Oxford university press, 2018.
  * [21] Juhani Nieminen.  On the centrality in a directed graph.  Social Science Research, 2(4):371–378, 1973.
  * [22] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd.  The pagerank citation ranking: Bringing order to the web.  Technical report, Stanford InfoLab, 1999.
  * [23] K Brooks. Reid.  Centrality measures in trees.  In Advances in Interdisciplinary Applied Discrete Mathematics, pages 167–197. World Scientific, 2011.
  * [24] Cristian Riveros and Jorge Salas.  A family of centrality measures for graph data based on subgraphs.  In Carsten Lutz and Jean Christoph Jung, editors, ICDT, volume 155, pages 23:1–23:18, 2020.
  * [25] Gert Sabidussi.  The centrality index of a graph.  Psychometrika, 31(4):581–603, 1966.
  * [26] Oskar Skibski.  Vitality indices are equivalent to induced game-theoretic centralities.  In Zhi-Hua Zhou, editor, IJCAI, pages 398–404. International Joint Conferences on Artificial Intelligence Organization, 2021.
  * [27] Oskar Skibski, Tomasz P. Michalak, and Talal Rahwan.  Axiomatic characterization of game-theoretic centrality.  Journal of Artificial Intelligence Research, 62:33–68, 2018.
  * [28] René van den Brink and Robert P. Gilles.  Measuring domination in directed networks.  Social Networks, 22(2):141–157, 2000.
  * [29] Tomasz Wąs and Oskar Skibski.  Axiomatization of the PageRank centrality.  In IJCAI, pages 3898–3904. International Joint Conferences on Artificial Intelligence Organization, 2018.
  * [30] Mihalis Yannakakis.  Algorithms for acyclic database schemes.  In VLDB, volume 81, pages 82–94, 1981.

##  Appendix A Other examples of centrality measures

#### Betweenness centrality

For every graph $G$ and vertices $v,u$ in $V(G)$ we define the set of geodesic
paths between $u$ and $v$ as $D_{vu}=\\{\pi\subseteq G\mid\pi\text{ is a
shortest path from }v\text{ to }u\\}$. Analogously, for three vertices
$v,u,w$, we define the set of geodesic paths from $v$ to $u$ containing $w$ as
$D_{vu}(w)=\\{\pi\in D_{vu}\mid w\in V(\pi)\\}$. Thus, _betweenness
centrality_ [11] of $v$ in $G$ is defined as

$\textsc{Betweenness}(v,G)=\sum_{(u,w)\in(V(G)-\\{v\\})^{2}}\displaystyle\frac{|D_{uw}(v)|}{|D_{uw}|}.$

In some sense, betweenness centrality is based on the notion of distance.
However, we do not assign importance to the distance itself but to the
structures where vertex $v$ belong. This measure is closely related with
connectivity or flux between vertices.

#### Decay centrality

Distance is relevant in several centrality measures. In particular, we can
define the $i$th neighbourhood of a node $v$ in the graph $G$ as
$N^{i}_{G}(v)=\\{u\in V(G)\mid d_{G}(u,v)=i\\}$. In some applications, we
would like to give more importance to a node with more closer nodes to him.
This is essentially the idea of $\alpha-$Decay centrality [16]. We define it
as

$\textsc{Decay}^{\alpha}(v,G)=\sum_{i=1}^{|V(G)|}\alpha^{i}|N^{i}(v,G)|\text{
for }\alpha\in(0,1).$

Clearly, for every $\alpha$ in $(0,1)$ we might get a different centrality
measure. Therefore, we say that $\alpha-$Decay is a family of centrality
measures.

#### Eigenvector centrality

For every graph $G$, given an order of the nodes
$V(G)=\\{u_{1},...,u_{|V(G)|}\\}$ we define the adjacency matrix of $G$ as
$A_{ij}=1$ if $\\{u_{i},u_{j}\\}\in E(G)$. Then, $\lambda_{\max}$ is the
greatest eigenvalue of $A$. We define the unique $L^{2}$ normalized
eigenvector associated with $\lambda_{\max}$ as $\mathbf{v}_{\max}$. Thus, the
_eigenvector centrality_ [7] of $u_{i}$ in $G$ is the $i$-th entrance of
$\mathbf{v}_{\max}$:

$\textsc{EV}(u_{i},G)=\mathbf{v}_{\max}^{i}.$

#### PageRank centrality

_PageRank centrality_ is one of the main algorithms used in Google’s web
searching engine. For a graph $G$, define P as the column-stochastic matrix
such that:

$\textbf{P}_{ij}=\displaystyle\frac{A_{ij}}{|N(i,G)|}.$

In other words, P contains the probabilities of jumping from node $i$ to node
$j$ during a random walk over $G$. Let v be an stochastic vector
$(e^{T}\textbf{v}=1)$, and let $0<\alpha<1$ be a teleportation parameter.
Then, PageRank is defined as the vector who solves the equation
$(I-\alpha\textbf{P})\textsc{PageRank}=(1-\alpha)\textbf{v}$. Finally, we
define _PageRank centrality_ [22] as

$\textsc{PR}_{\alpha,\textbf{v}}(v_{i},G)=\textsc{PageRank}_{i}.$

##  Appendix B Proofs of Section 3

### Proof of Proposition 3.5

######  Proof B.1.

$(\Rightarrow)$ Suppose $C$ satisfies the rooting property. By contradiction,
suppose there exists a tree $T$ and node $v$ in $T$ with two neighbours in
$u_{1}\not=u_{2}$ in $N_{T}(v)$ where $C(v,T)\leq C(u_{1},T)$ and $C(v,T)\leq
C(u_{2})$. Set one root of $T$ according to $C$ as $r$ in $V(T)$. Now, without
lose of generality, assume that $\pi_{vr}=vu_{1}...r$. In other words, from
$v$ to $r$ we need to pass through $u_{1}$. This must be the case since
$r\not=v$. Otherwise, $v,u_{1}$ and $u_{2}$ are roots which is not possible.
Now, the unique path from $u_{2}$ to $r$ must go through $v$ and $u_{1}$.
However, the centrality values are not strictly increasing as it should be for
a rooting measure.

$(\Leftarrow)$ In first place, we will prove that for every tree $T$, $v$ in
$V(T)-\textsc{Max}_{C}(T)$ with a closest root $r\in\textsc{Max}_{C}(T)$, then
if $\pi_{rv}=u_{1}u_{2}...u_{n}$ we have that
$C(u_{1},T)>C(u_{2},T)>...>C(u_{n},T)$. Since $r$ is the closest root to $v$
in $T$, then necessarily $C(u_{1},T)=C(r,T)>C(u_{2})$. Now, suppose as
induction hypothesis that $C_{(}u_{i},T)>C(u_{i+1},T)$. Then, by at most one
parent we have that $C(u_{i+2},T)<C(u_{i+1},T)$. Otherwise $u_{i+1}$ would
have two neighbours with higher or equal centrality.

In second place, in order to prove that the set $\textsc{Max}_{C}(T)$ forms a
clique in $T$. Consider two roots $u,v$ in $T$. By contradiction suppose
$\\{u,v\\}\not\in E(T)$. Then, set the path connecting both nodes in $T$ as
$\pi_{vu}=w_{1}w_{2}...w_{n}$ where $n\geq 3$ because of our assumption. Now,
we have two options. First it could be the case that for every
$w_{i}\not\in\\{u,v\\}$ then $w_{i}$ is not a root of $T$. Then, we know the
centrality values must decrease and then increase, which violates what we
prove before. On the other hand, if there exists $w_{i}\not\in\\{u,v\\}$ such
that $w_{i}$ is a root of $T$ the same scenario will occur, violating the at
most one parent property. This prove that from every two roots in $T$, they
must be connected by an edge which concludes the proof.

### Proof of Proposition 3.7

######  Proof B.2.

Suppose by contradiction there exist a tree $T$, a node $v$ in $V(T)$ and two
different nodes $u_{1}$ and $u_{2}$ in $V(T)$ such that
$(u_{1},T_{u_{1}v})\cong(u_{2},T_{u_{2}v})$ but $C(v,T)\leq C(u_{1},T)$. This
means that there exists a node $z$ in $V(T_{u_{1}v})$ such that
$z\in\textsc{Max}_{C}(T)$ because the centrality is increasing in the
direction of $u_{1}$. However, since $T_{u_{1}v}\equiv T_{u_{2}v}$, there must
exists a node $z^{\prime}$ in $V(T_{u_{2}v})$ such that
$C(z,T)=C(z^{\prime},T)$ for the close under isomorphism property of $C$. In
consequence, we have that $z^{\prime}$ is in $\textsc{Max}_{C}(T)$ as well.
This means there are two roots of $T$ which are not connected, but at the same
time $C$ is a tree rooting measure.

##  Appendix C Proofs of Section 4

### A potential function for Betweenness (Example 4.2)

######  Proof C.1.

Take any two nodes $v_{1}$ and $v_{2}$ connected in a tree $T$. By definition
of Betweenness we have that

$\textsc{Betweenness}(v_{1},T)=\displaystyle\sum_{(u,w)\in(V(T)-\\{v_{1}\\})^{2}}\displaystyle\frac{D_{uw}(v_{1})}{|D_{uw}|}=$
$\displaystyle\sum_{(u,w)\in(V(T_{v_{1}v_{2}})-\\{v_{1}\\})^{2}}\displaystyle\frac{D_{uw}(v_{1})}{|D_{uw}|}+\displaystyle\sum_{(u,w)\in(V(T_{v_{1}v_{2}})-\\{v_{1}\\})\times
V(T_{v_{2}v_{1}})}2\cdot\displaystyle\frac{D_{uw}(v_{1})}{|D_{uw}|}.$

In other words, the shortest paths containing $v_{1}$ can be divided in two
groups. First, the ones connecting nodes inside $T_{v_{1}v_{2}}$ and second,
the ones connecting nodes from $T_{v_{1}v_{2}}$ to $T_{v_{2}v_{1}}$. In the
first group, we are exactly computing the betweenness value for $v_{1}$ in
tree $T_{v_{1}v_{2}}$. Meanwhile, for the second group, we have one shortest
path for every possible pair selection since we are force to pass through
$v_{1}$. Therefore, we can express the previous value as

$\textsc{Betwenness}(v_{1},T)=\textsc{Betwenness}(v_{1},T_{v_{1}v_{2}})+2(|T_{v_{1}v_{2}}|-1)|T_{v_{2}v_{1}}|=$
$\textsc{Betwenness}(v_{1},T_{v_{1}v_{2}})+2|T_{v_{1}v_{2}}||T_{v_{2}v_{1}}|-2|T_{v_{2}v_{1}}|.$

Finally, we can use this expression to prove that
$\textsc{Betweenness}(v_{1},T)\leq\textsc{Betweenness}(v_{2},T)$ if and only
if

$\textsc{Betwenness}(v_{1},T_{v_{1}v_{2}})+2|T_{v_{1}v_{2}}||T_{v_{2}v_{1}}|-2|T_{v_{2}v_{1}}|\leq\textsc{Betwenness}(v_{2},T_{v_{2}v_{1}})+2|T_{v_{2}v_{1}}||T_{v_{1}v_{2}}|-2|T_{v_{1}v_{2}}|.$

Rearranging and simplifying terms we get that
$\textsc{Betweenness}(v_{1},T)\leq\textsc{Betweenness}(v_{2},T)$ if and only
if

$\textsc{Betwenness}(v_{1},T_{v_{1}v_{2}})+2|T_{v_{1}v_{2}}|\leq\textsc{Betwenness}(v_{2},T_{v_{2}v_{1}})+2|T_{v_{2}v_{1}}|.$

Which proves that $f_{B}(v,T)=\textsc{Betweenness}(v,T)+2|T|$ is a potential
function for Betwenness. Clearly, $f_{B}$ is not symmetric since a leaf will
generally get less value than its parent before adding such leaf (as long as
the parent was not a leaf before).

### A potential function for $\textsc{Decay}^{\alpha}$ (Example 4.2)

######  Proof C.2.

In the same way we did for other centrality measures, for a pair of connected
nodes $v_{1}$ and $v_{2}$ inside $T$, we have the following relation:

$\textsc{Decay}^{\alpha}(v_{1},T)=\sum_{i=1}^{|V(T_{v_{1}v_{2}})|}\alpha^{i}|N^{i}(v_{1},T_{v_{1}v_{2}})|+\sum_{i=0}^{|V(T_{v_{2}v_{1}})|}\alpha^{i+1}|N^{i}(v_{2},T_{v_{2}v_{1}})|=$
$\textsc{Decay}^{\alpha}(v_{1},T_{v_{1}v_{2}})+\alpha(1+\textsc{Decay}^{\alpha}(v_{2},T_{v_{2}v_{1}})).$

To derive this expression we just divide the neighbourhoods $N^{i}(v_{1},T)$
in two groups. First, nodes coming from $T_{v_{1}v_{2}}$ and nodes from
$T_{v_{2}v_{1}}$ in the other hand. Using this equation and its symmetry for
$v_{2}$, we have that
$\textsc{Decay}^{\alpha}(v_{1},T)\leq\textsc{Decay}^{\alpha}(v_{2},T)$ if and
only if

$\textsc{Decay}^{\alpha}(v_{1},T_{v_{1}v_{2}})+\alpha(1+\textsc{Decay}^{\alpha}(v_{2},T_{v_{2}v_{1}}))\leq\textsc{Decay}^{\alpha}(v_{2},T_{v_{2}v_{1}})+\alpha(1+\textsc{Decay}^{\alpha}(v_{1},T_{v_{1}v_{2}})),$

by rearranging terms we have that this inequality holds if and only if

$(1-\alpha)\textsc{Decay}^{\alpha}(v_{1},T_{v_{1}v_{2}})\leq(1-\alpha)\textsc{Decay}^{\alpha}(v_{2},T_{v_{2}v_{1}}).$

In other words, the function
$f_{\alpha}(v,T)=(1-\alpha)\textsc{Decay}^{\alpha}(v,T)$ is a potential
function for $\alpha-$Decay centrality. It is important to notice that
$f_{\alpha}$ is a family of potential functions since it depends on how we
choose $\alpha$. Finally, this potential function is clearly not symmetric for
a similar reason to Betweenness.

### Proof of Lemma 4.3

######  Proof C.3.

$(\Rightarrow)$ Take a tree $T^{\prime}$ and node $u^{\prime}$ in $T^{\prime}$
such that $(u,T_{u,v})\equiv(u^{\prime},T^{\prime})$. Know, by symmetry, we
know that
$C(v,T+T^{\prime}+\\{v,u^{\prime}\\})>C(u^{\prime},T+T^{\prime}+\\{v,u^{\prime}\\})$.
Now, by potential functions definition that
$f(v,T)>f(u^{\prime},T^{\prime})=f(u,T_{u,v})$ which we can conclude by close
under isomorphism.

$(\Leftarrow)$ By counter positive suppose there exists a tree $T$ and nodes
$v,u$ in $T$ such that $f(u,T_{u,v})\geq f(v,T)$. Then, we could connect to
$v$ in $T$ a tree $T^{\prime}$ such that for $u^{\prime}$ in $T^{\prime}$ we
have that $(u,T_{u,v})\equiv(u^{\prime},T^{\prime})$. In this case, because of
isomorphism, we know that $f(u^{\prime},T^{\prime})=f(u,T_{u,v})\geq f(v,T)$.
Now, by definition of potential functions, we have that
$C(u^{\prime},T+T^{\prime}+\\{u^{\prime},v\\})\geq
C(v,T+T^{\prime}+\\{u^{\prime},v\\})$ concluding that $C$ is not symmetric.

### Proof of Theorem 4.4

######  Proof C.4.

We know by Proposition 3.7 that if $C$ roots trees, then $C$ is necessarily
symmetric. Thus, we just need to prove that symmetry implies tree rooting for
$C$. We will do this by proving that $C$ satisfies the at-most-one-parent
property. Fix an arbitrary tree $T$, vertex $v$ and let $u,w$ be two arbitrary
neighbours of $v$ in $T$. By removing edges $\\{u,v\\}$ and $\\{v,w\\}$ we get
a decomposition of $T$ into trees, $T_{u},T_{v},T_{w}$ containing $u,v,w$,
respectively, such that

$T=(T_{v}\cup T_{u}\cup T_{w})+\\{u,v\\}+\\{v,w\\}.$

Without loss of generality assume $f(w,T_{w})\leq f(u,T_{u})$. From symmetry
we have $f(u,T_{u})<f(v,(T_{u}+\\{u,v\\})\cup T_{v})$. Based on our assumption
$f(w,T_{w})\leq f(u,T_{u})$, we conclude $f(w,T_{w})<f(v,(T_{u}+\\{u,v\\})\cup
T_{v})$. This, combined with the potential function definition, implies that
$C(w,T)<C(v,T)$. Hence, we just proved that out of every two neighbours at
least one has smaller centrality than $v$, which implies the thesis.

### Proof of Proposition 4.6

######  Proof C.5.

In first place we will determine a fixed way to set the root of every tree
defined as a function $R:\mathcal{G}\to\mathcal{V}$ such that $R(T)\subset
V(T)$. For an arbitrary tree $T$, we define $R(T)$ in cases as follows:

  1. 1.

If $\arg\max_{v\in V(T)}\textsc{Eccentricity}(v,T)=\\{w_{1},w_{2}\\}$ then
$R(T)=\arg\max\\{|T_{w_{1},w_{2}}|,|T_{w_{2},w_{1}}|\\}.$ In other words, if
there are two roots according to Eccentricity we choose the one with bigger
subtree. In case we have a tie, we just keep both nodes as roots.

  2. 2.

If $\arg\max_{v\in V(T)}\textsc{Eccentricity}(v,T)=\\{w\\}$, define the set
$M(T,w)=\arg\max_{u\in N_{T}(w)}|T_{u,w}|$. If $|M(T,v)|=1$ we define
$R(T)=M(T,w)\cup\\{w\\}$. Otherwise, we just set $R(T)=\\{w\\}$. In simpler
words, if there is just one root according to Eccetricity we choose this root
plus the child with bigger subtree just in case there is a unique dominant
child.

Finally, we define

$C^{\star}(v,T)=\begin{cases}2&\text{ if }v\in R(T)\\\ \displaystyle\max_{u\in
R(T)}\frac{1}{d_{T}(v,u)}&\text{otherwise}\end{cases}.$

Clearly, $C^{\star}$ is a tree rooting measure since the most important node
is based on eccentricity and centrality values from the root decrease. Thus,
we will prove that $C^{\star}$ can not have a potential function. Consider the
rooted trees $(v_{1},T_{1})=$ , $(v_{2},T_{2})=$ and $(v_{3},T_{3})=$ . The
reader can corroborate that
$C^{\star}(v_{1},T_{1}+T_{2}+\\{v_{1},v_{2}\\})=C^{\star}(v_{2},T_{1}+T_{2}+\\{v_{1},v_{2}\\})$,
$C^{\star}(v_{2},T_{2}+T_{3}+\\{v_{2},v_{3}\\})=C^{\star}(v_{3},T_{2}+T_{3}+\\{v_{2},v_{3}\\})$
and
$C^{\star}(v_{1},T_{1}+T_{3}+\\{v_{1},v_{3}\\})<C^{\star}(v_{3},T_{1}+T_{3}+\\{v_{1},v_{3}\\})$.
Now, suppose by contradiction there exists a potential function $f$ for
$C^{\star}$. Therefore, the previous values for $C^{\star}$ would mean that
$f(v_{1},T_{1})=f(v_{2},T_{2})=f(v_{3},T_{3})$ but the fact that
$C^{\star}(v_{1},T_{1}+T_{3}+\\{v_{1},v_{3}\\})<C^{\star}(v_{3},T_{1}+T_{3}+\\{v_{1},v_{3}\\})$
means that $f(v_{1},T_{1})<f(v_{3},T_{3})$ which is a contradiction.

##  Appendix D Proofs of Section 5

### Proof of Proposition 5.1

######  Proof D.1.

By potential function definition we know that

$C(u,T)\leq C(w_{2},T)\text{ if, and only if, }f(u,T_{u,w_{2}})\leq
f(w_{2},T_{w_{2},u}).$

In consequence, we just have to prove the second inequality in the previous
equation. Now, by symmetry

$f(w_{2},T_{w_{2},u})>f(w_{3},T_{w_{3},w_{2}}).$

We can repeat this until we reach $w_{n}=v$ and then

$f(w_{2},T_{w_{2},u})>f(v,T_{v,w_{n-1}}).$

Finally, by hypothesis we know that $f(v,T_{v,w_{n-1}})>f(u,T_{u,w_{2}})$.
Thus, this fact plus the last equation implies that

$f(w_{2},T_{w_{2},u})>f(u,T_{u,w_{2}}).$

### Proof of Proposition 5.2

######  Proof D.2.

First we will prove that for every input $T,f$ such that $f$ is a symmetric
potential function, then the algorithm finish in finite time. We will prove
that for every pair $(u,f(u,T_{u,w}))\in Q$, then $|H(v)|=1$. In the first
iteration, for every leaf, it is clearly the case. Now, suppose this
assumption is true at the beginning of one iteration of the while loop.
Therefore, we have that $(u,f(u,T_{u,w}))$ enters the queue only if $|H[u]|=1$
concluding this invariant for every iteration. On the other hand, if $v$
leaves the queue, then necessarily $H[v]$ is more important than $v$ in $T$.
Since $v$ left the queue, there exists $w\in Q$ such that $f(w,T_{w,H(w)})\geq
f(v,T_{v,H[v]})$. Now, it is the case that $H[v]$ is in the path from $v$ to
$w$. To prove this, by induction we will prove that for every node $v$, then
every node $u$ in $N_{T}(v)/H[v]$ was already in the queue before $v$ if some
node in between was already in the queue. In the first iteration we have that
none of the nodes in $N_{T}(v)$ has passed through $Q$. Now, assume that at
some iteration this hypothesis holds. If we take $v$ from $Q$, then line $6$
implies that we remove $v$ from $H[u]$ which means that every node in
$N_{T}(u)/(H[u]-\\{v\\})$ already entered and left the queue maintaining this
invariant. Coming back to our previous statement, we have that if $v$ left the
queue there is a unique node $u=H[v]$ such that $u$ is in the path between $v$
and $w$. Otherwise $w$ would have left the queue before $v$. By Proposition
5.1 we have then that $u$ is more important than $v$ in $T$. Finally, when
$|Q|=1$ at the beginning of one iteration, we have $v\in Q$ such that for
every $u\in N_{T}(v)$ then $f(v,T_{v,u})\geq f(u,T_{u,v})$ concluding that the
last node in $Q$ is a root of $T$.

##  Appendix E Proofs of Section 6

### Proof of Proposition 6.3

######  Proof E.1.

$(\Rightarrow)$ If $C$ consistently roots trees, fix any tree $T$ and nodes
$v,u$ in $T$ such that ${u,v}\in E(T)$ and $C(v,T)<C(u,T)$. Now, for a node
$w$ in $T_{u,v}$ and node $w^{\prime}$ not in $V(T)$, we will prove that
$C(v,T+\\{w,w^{\prime}\\})<C(u,T+\\{w,w^{\prime}\\}).$ Since $C$ is a tree
rooting measure, the fact that $C(v,T)<C(u,T)$ implies that
$\textsc{Max}_{C}(T)\subseteq T_{u,v}$. Set the node $r\in\textsc{Max}_{C}(T)$
which is closer to $w$ in $T$. Now, by consistency we know that
$\textsc{Max}_{C}(T+\\{w,w^{\prime}\\})\subseteq\pi_{r,w^{\prime}}\cup\textsc{Max}_{C}(T)\subseteq
V(T_{u,v})\cup\\{w^{\prime}\\}$. Concluding by the rooting property of $C$
that $C(v,T+\\{w,w^{\prime}\\})<C(u,T+\\{w,w^{\prime}\\})$.

$(\Leftarrow)$ Suppose by contradiction there exists a tree $T$, nodes
$r\in\textsc{Max}_{C}(T)$ and $u\in V(T)$ such that for a node $w\not\in V(T)$
then there exists $r^{\prime}$ in $\textsc{Max}_{C}(T+\\{u,w\\})$ such that
$r^{\prime}$ is not in $\pi_{r,w}\cup\textsc{Max}_{C}(T)$. Define the path
$\pi_{r,w}:=z_{1}z_{2}...z_{n}$. Set $z^{\ast}\in\pi_{r,w}$ as the closest
node to $r^{\prime}$. Finally, set the path
$\pi_{r^{\prime}z^{\ast}}=s_{1}s_{2}...s_{k}$ connecting $z^{\ast}$ to
$r^{\prime}$. Now, we have that
$s_{1}s_{2}...s_{k}z^{\ast}z_{i-1}...r=\pi_{r^{\prime}r}$ is the path
connecting $r^{\prime}$ to $r$ in $T$. Then, since $r$ is a root in $T$ while
$r^{\prime}$ is not, we have that $C(z^{\ast},T)>C(s_{k},T)$. However, we have
that $C(z^{\ast},T+\\{u,w\\})\leq C(s_{k},T+\\{u,w\\})$ which contradicts
monotonicity.

### Proof of Proposition 6.5

######  Proof E.2.

$(\Rightarrow)$ Suppose by contradiction there exists a tree $T$, a subtree
$T^{\prime}\subseteq T$ and a node $v$ in $V(T)\cap V(T^{\prime})$ such that
$f(v,T^{\prime})>f(v,T)$. Set a tree $H^{\prime}$ and $v^{\prime}\in
V(H^{\prime})$ such that $(v,T^{\prime})\equiv(v^{\prime},H^{\prime})$ and
$V(T^{\prime})\cap V(H^{\prime})=\emptyset$. In the the same way, set $H$ as a
tree where $(v^{\prime},H)\equiv(v,T)$ and $V(H)\cap V(T)=\emptyset$. In other
words, $T$ is isomorphic to $H$ and $T^{\prime}$ is isomorphic to $H^{\prime}$
but they do not share nodes. Now, by close under isomorphism we have that
$f(v,T^{\prime})=f(v^{\prime},H^{\prime})$. On the other hand, there exists a
sequence of edges as new leaves for $H^{\prime}$, $e_{1},e_{2},...,e_{n}$ such
that $H^{\prime}+e_{1}+e_{2}+...+e_{n}=H$ which means that for some
$i\in\\{1,...,n\\}$ it must be the case that
$f(v^{\prime},H^{\prime}+e_{1}+...+e_{i})>f(v,T)$ but
$f(v^{\prime},H^{\prime}+e_{1},...+e_{i+1})\leq f(v,T)$. All of this implies
that
$C(v^{\prime},H^{\prime}+e_{1}+...+e_{i}+T+\\{v,v^{\prime}\\})>C(v,H^{\prime}+e_{1}+...+e_{i}+T+\\{v,v^{\prime}\\})$
but $C(v^{\prime},H^{\prime}+e_{1}+...+e_{i+1}+T+\\{v,v^{\prime}\\})\leq
C(v,H^{\prime}+e_{1}+...+e_{i+1}+T+\\{v,v^{\prime}\\})$ which means $C$ is not
monotonic.

$(\Leftarrow)$ Take a tree $T$ and nodes $u,v$ in $T$ such that $\\{u,v\\}\in
E(T)$ and $C(v,T)<C(u,T)$. Take nodes $w$ in $T_{u,v}$ and $w$ not in $T$. We
have by potential functions definition that $f(v,T_{v,u})<f(u,T_{u,v})$. Now,
by hypothesis we have that $f(u,T_{u,v})\leq f(u,T_{u,v}+\\{w,w^{\prime}\\})$
since $T_{u,v}$ is a subtree of $T_{u,v}+\\{w,w^{\prime}\\}$. Adding this two
facts together we have that
$C(v,T+\\{w,w^{\prime}\\})<C(u,T+\\{w,w^{\prime}\\})$ concluding that $C$ is
monotonic.

### Proof of Theorem 6.6

######  Proof E.3.

$(\Rightarrow)$ First, assume $u\not=v$ and set the path connecting $u$ and
$v$ in $T$ as $\pi_{u,v}=w_{1}w_{2}...w_{n}$. Since $T^{\prime}$ is a proper
subtree of $T$, there exists a set of edges as leaves $e_{1},e_{2},...,e_{k}$
such that $T^{\prime}+e_{1}+...+e_{k}=T_{u,w_{2}}$. Thus, by monotonicity and
proposition 6.5 we have that $f(u,T^{\prime})\leq f(u,T_{u,w_{2}})$. By
symmetry we have $f(u,T^{\prime})\leq
f(u,T_{u,w_{2}})=f(u,T-T_{w_{2},w_{1}})<f(w_{2},T-T_{w_{3},w_{2}})$. We can
repeat this process until we reach $v$. We get then that
$f(w_{n-1},T-T_{w_{n},w_{n-1}})<f(w_{n},T)=f(v,T)$ concluding the inequality
when $u\not=v$. Now, if $u=v$ we have by monotonicity and proposition 6.5 that
$f(u,T^{\prime})\leq f(u,T)$.

$(\Leftarrow)$ This direction is a direct application of lemma 4.3 and
proposition 6.5.

##  Appendix F Proofs of Section 7

### Proof of Lemma 7.3

######  Proof F.1.

To prove symmetry we will use lemma 4.3. Take any tree $T$ and two adjacent
nodes $u,v$. We have that
$f_{*,\ell}(v,T)=l(f_{*,\ell}(u,T_{u,v}))*f_{*,\ell}(v,T_{v,u})$. We have that
$l(f_{*,\ell}(u,T_{u,v}))>f_{*,\ell}(u,T_{u,v})$ by hypothesis. We also know
that $(\mathbb{M},*,\mathbb{1})$ is positively ordered and therefore, adding
the fact that $f_{*,\ell}(v,T_{v,u})\geq\mathbb{1}$ we conclude that
$f_{*,\ell}(v,T)>f_{*,\ell}(u,T_{u,v})*f_{*,\ell}(v,T_{v,u})\geq
f_{*,\ell}(u,T_{u,v})*\mathbb{1}=f_{*,\ell}(u,T_{u,v})$.

We will prove that $f_{*,\ell}$ is monotonic by exploding proposition 6.5. In
order to do this, we will prove that adding a leaf to the tree will not
decrease the potential of $v$ after adding the leaf. Fix a tree $T$ and nodes
$v,w$ in $V(T)$. For a node $h\not\in V(T)$ we will prove that
$f_{*,\ell}(v,T)\leq f_{*,\ell}(v,T+\\{w,h\\})$. Set the path connecting $v$
to $w$ in $T$ as $\pi_{w,u}=z_{1}z_{2}...z_{n}$. Now, by definition of
$f_{*,\ell}$ we have that
$f_{*,\ell}(v,T)=f_{*,\ell}(v,T_{v,w_{2}})*l(f_{*,\ell}(z_{2},T_{z_{2},v}))$.
Expanding this expression we have $f_{*,\ell}(z_{2},T_{z_{2},v})=f(z_{2},T-T-
T_{v,z_{2}}-T_{z_{3},z_{2}})*l(f_{*,\ell}(z_{3},T_{z_{3},z_{2}}))$. Adding up
we got $f_{*,\ell}(v,T)=f_{*,\ell}(v,T_{v,w_{2}})*l(f(z_{2},T-T-
T_{v,z_{2}}-T_{z_{3},z_{2}})*l(f_{*,\ell}(z_{3},T_{z_{3},z_{2}})))$. Expanding
until we reach $w$ we got

$f_{*,\ell}(v,T)=f_{*,\ell}(v,T_{v,w_{2}})*l(...*l(f_{*,\ell}(w,T_{w,z_{n-1}}))...).$

Now, when we add the leaf $h$ we have

$f_{*,\ell}(v,T+\\{w,h\\})=f_{*,\ell}(v,T_{v,w_{2}})*l(...*l(f_{*,\ell}(w,T_{w,z_{n-1}})*l(\mathbb{1}))...).$

Finally, the fact that $x<l(x)$ plus $(\mathbb{M},*,\mathbb{1})$ is positively
ordered, we got that
$f_{*,\ell}(w,T_{w,z_{n-1}})*l(\mathbb{1})>f_{*,\ell}(w,T_{w,z_{n-1}})*\mathbb{1}=f_{*,\ell}(w,T_{w,z_{n-1}})$.
Therefore,, $f_{*,\ell}(v,T)>f_{*,\ell}(v,T+h)$ by properties (1), (2) and
(3).

In order to finish the proof we must state the fact that, since $T^{\prime}$
is a subgraph of $T$, there must exists a sequence of edges as leaves
$e_{1},...,e_{k}$ such that $T^{\prime}+e_{1}+...+e_{k}=T$. Therefore,
applying previous result for every $e_{i}$ we conclude that
$f_{*,\ell}(v,T^{\prime})<f_{*,\ell}(v,T)$ and
$f_{*,\ell}(v,T^{\prime})=f_{*,\ell}(v,T)$ just in the case that
$T^{\prime}=T$.

### Proof of Theorem 7.4

######  Proof F.2.

$(\Rightarrow)$ First we will prove that $x<\bar{\ell}(x)$. Take any tree $T$,
node $v$ in $T$ and a leaf $w$ not in $V(T)$. By symmetry over potential
functions we know that
$f_{*,\ell}(v,T)<f_{*,\ell}(w,T+\\{v,w\\})=\bar{\ell}(f_{*,\ell}(v,T))$.
Therefore, $f_{*,\ell}$ satisfies (1).

In second place, we will prove (2). Take any tree $T$ ,node $v$ in $T$ and a
subtree $T^{\prime}$ such that $v\in(T^{\prime})$. Since $T^{\prime}\subset T$
we have by monotonicity that $f_{*,\ell}(v,T^{\prime})\leq f_{*,\ell}(v,T)$.
Now, for a node $w$ not in $V(T^{\prime})$, we have that
$T^{\prime}+\\{w,v\\}\subseteq T+\\{w,v\\}$. Thus, again by monotonicity we
have that
$\ell(f_{*,\ell}(v,T^{\prime}))=f_{*,\ell}(w,T^{\prime}+\\{w,v\\})\leq
f_{*,\ell}(w,T+\\{w,v\\})=\ell(f_{*,\ell}(v,T))$. In other words, if $x\leq
x^{\prime}$ and $x$ is a subtree of $x^{\prime}$ then
$\ell(x)\leq\ell(x^{\prime})$.

Finally, we have to prove (3). Take a tree $T$ and a subtree $T^{\prime}$.
Now, fix a third tree $H$ and node $v$ such that $\\{v\\}=V(T^{\prime})\cap
V(H)$. We have by monotonicity and proposition 6.5 that
$f_{*,\ell}(v,T^{\prime})\leq f_{*,\ell}(v,T)$ and
$f_{*,\ell}(v,T)*f_{*,\ell}(v,H)=f_{*,\ell}(v,T+H)\geq
f_{*,\ell}(v,T^{\prime}+H)=f_{*,\ell}(v,T^{\prime})*f_{*,\ell}(v,H)$ since
$T^{\prime}+H$ is a subtree of $T+H$. In other words if $x$ is a subtree of
$x^{\prime}$ then $x\leq x^{\prime}$ and $x*z\leq x^{\prime}*z$ for
$z\in\operatorname{Range}_{*,\ell}$ concluding the proof.

$(\Leftarrow)$ This proof is equivalent to the one of lemma 7.3 because we use
subtrees in every case.

### Proof of Proposition 7.5

######  Proof F.3.

We will use theorem 7.4 from right to left. For (1), take
$x\in\operatorname{Range}_{*,\ell}$. Then, $\ell(x)=ax+b\geq x+b>x$ for $a\geq
1$ and $b>0$. To prove (2), take $x\leq x^{\prime}$ such that $x$ is a subtree
of $x^{\prime}$. Then, $\ell(x)=ax+b\leq ax^{\prime}+b$. Finally, in order to
prove (3) we first need to prove that for every
$x\in\operatorname{Range}_{*,\ell}$ then $x\geq c$. First, we have that
$\mathbb{1}=c$. Now, by applying $\ell$, we got $\ell(\mathbb{1})=ac+b>c$ for
$a\geq 1$ and $b>0$. Now, by structural induction, take any tree $T$ and node
$v$ in $T$ such that $N_{T}(v)=\\{w_{1},...,w_{n}\\}$ and assume
$f_{*,\ell}(w_{i},T_{w_{i},v})\geq c$. We have that
$f_{*,\ell}(v,T)=\ell(f_{*,\ell}(w_{1},T_{w_{1},v}))*\ell(f_{*,\ell}(w_{2},T_{w_{2},v}))*...*\ell(f_{*,\ell}(w_{n},T_{w_{n},v}))=\prod_{i=1}^{n}a(f_{*,\ell}(w_{i},T_{w_{i},v}))+b\geq\displaystyle\frac{\prod_{i=1}^{n}ac+b}{c^{n-1}}>\displaystyle\frac{c^{n}}{c^{n-1}}=c.$
To conclude, take $x$ subtree of $x^{\prime}$ such that $x\leq x^{\prime}$.
Take any $z\in\operatorname{Range}_{*,\ell}$. We have that
$x*z=\displaystyle\frac{xz}{c}\leq\displaystyle\frac{x^{\prime}z}{c}=x^{\prime}*z$
since $\frac{z}{c}\geq 1$ because $z\geq c$ for every
$z\in\operatorname{Range}_{*,\ell}$.

### Proof of Proposition 7.6

######  Proof F.4.

For this purpose we will just study how $f_{*_{c},\ell_{a,b}}$ assign values
to the star graph with $n$ nodes, $S_{n}$, and the line graph with $m$ nodes,
$L_{m}$. In one side, we have that
$f_{*_{c},\ell_{a,b}}(0,S_{n})=\displaystyle\frac{(ac+b)^{n}}{c^{n-1}}$. On
the other hand, for the line we have that
$f_{*_{c},\ell_{a,b}}(0,L_{m})=\ell^{m}(c)=a\ell^{m-1}(c)+b=...=a^{m}c+\sum_{i=0}^{m-1}a^{i}b$.
Now, fix $c=1$ and we have that
$f_{*_{c},\ell_{a,b}}(0,S^{n})<f_{*_{c},\ell_{a,b}}(0,L_{m})$ if and only if
$\displaystyle(a+b)^{n}<a^{m}+\sum_{i=0}^{m-1}a^{i}b$. Now, for a fixed pair
$a,b$, and $n\geq 1$ take $m(a,b,n)=\arg\min_{m\geq
1}\\{(a+b)^{n}<a^{m}+\sum_{i=0}^{m-1}a^{i}b\\}$. Since
$a^{m}+\sum_{i=0}^{m-1}a^{i}b$ is unbounded in $m$ for $a\geq 1$ and $b>0$ we
have that $m(a,b,n)\in\mathbb{N}$. Finally, we have that $(a+b)^{n}\geq
a^{m(a,b,n)-1}+\sum_{i=0}^{m(a,b,n)-2}a^{i}b$. Therefore, we have that in the
tree $S_{n}+L_{m(a,b,n)-1}$ the root is in $S_{n}$ while in
$S_{n}+L_{m(a,b,n)}$ the root for $f_{*_{c},\ell_{a,b}}$ is in $L_{m(a,b,n)}$.
On the other hand, the values of $f_{*_{c},\ell_{a,b}}(0,S_{n})$ and
$f_{*_{c},\ell_{a,b}}(0,L_{m})$ are also unbounded for $a\geq 1$ and $b>0$. In
other words, for every value $n\geq 4$ there exists $a,b$ and value $m\geq n$
such that $m(a,b,n)=m$ concluding that there exists an infinite amount of
potential functions which differ in the ranking of $S_{n}+L_{m(a,b)-1}$ and
$S_{n}+L_{m(a,b,n)}$ for every choice of $n\geq 4$.