How to choose the root: centrality measures over tree structures

Cristian Riveros, Jorge Salas, Oskar Skibski

Abstract

Centrality measures are fundamental tools in network analysis, used to rank nodes based on their structural importance. However, different measures often yield conflicting results, even on simple acyclic graphs. This paper investigates the mathematical foundations of this disagreement by introducing the "tree rooting property" and a framework of potential functions. We characterize the class of measures that consistently identify a unique center (or root) in trees and provide an efficient $O(n \log n)$ algorithm for their identification. Our findings highlight why popular measures like PageRank fail to root trees intuitively and offer a methodology for designing application-specific, mathematically sound centrality measures.

Introduction

In network analysis, centrality measures are used to identify the most "important" nodes in a graph. Despite their widespread use, there is a surprising lack of consensus on what constitutes the center of a graph, even in simple structures like trees. For instance, while most measures favor the middle of a line graph, Google's PageRank can prioritize nodes near the leaves. This paper addresses this discrepancy by defining the mathematical properties required for a measure to "root" a tree—meaning it selects a clear center and shows a steady decline in importance toward the periphery.

Comparison of different centrality measures (Closeness, Eccentricity, AllSubgraphs, and Others) identifying distinct roots on the same tree structure.

The Tree Rooting Property and Potential Functions

The authors propose the Tree Rooting Property: a centrality measure roots a tree if it identifies exactly one node (or two adjacent nodes) as the maximum, with importance strictly decreasing along any path away from this center.

To characterize these measures, the paper introduces a framework of potential functions. In this model, node centrality is determined by comparing the "potential" of its attached subtrees. A measure is well-behaved if its potential function is symmetric. This local property ensures the global rooting behavior. Furthermore, the authors define consistency (or monotonicity): adding a leaf to a tree should only shift the root toward that leaf, preventing erratic jumps in the identified center.

Key Insights: The PageRank Paradox

A significant finding is that popular measures like PageRank and Degree centrality fail the rooting property. PageRank, in particular, can rank nodes near leaves higher than those in the structural middle of a tree, which is counter-intuitive for many tree-based applications. The paper proves that "tree rooting" (a global property) is equivalent to the "at-most-one-parent" property (a local property), allowing researchers to verify a measure's behavior by examining local neighborhood interactions rather than the entire graph.

Algorithmic Efficiency and Results

The research culminates in a Characterization Theorem: a centrality measure roots trees if and only if it admits a symmetric potential function. Based on this, the authors developed a "leaf-trimming" algorithm. By iteratively removing the least important subtrees using a priority queue, the algorithm finds the root in $O(|T| \log |T|)$ time. For "locally computable" functions, this complexity is further reduced to $O(|T|)$.

The study confirms that classical measures like Closeness (related to the median) and Eccentricity (related to the center) are consistent, while providing a methodology to construct an infinite family of new, mathematically sound centrality measures using algebraic structures called monoids.

Conclusion and Future Directions

While focused on trees, this work has broader implications for graph theory and data management. The authors suggest extending potential functions to general graphs by analyzing bridges—edges that disconnect the graph when removed. Additionally, these rooting techniques could optimize the Yannakakis algorithm for acyclic database queries by determining optimal join orders based on node centrality. Future work remains in extending these principles to Directed Acyclic Graphs (DAGs) and more complex cyclic networks.

Summary updated

BibTeX
@inproceedings{riveros2023how,
  author = {Cristian Riveros and Jorge Salas and Oskar Skibski},
  title = {{How to choose the root: centrality measures over tree structures}},
  booktitle = {Icdt},
  year = {2023},
  doi = {10.4230/lipics.icdt.2023.12},
}
Figure