Properties and Expressivity of Linear Geometric Centralities

Paolo Boldi, Flavio Furia, Chiara Prezioso · 2025

Read Properties and Expressivity of Linear Geometric Centralities by Paolo Boldi, Flavio Furia, Chiara Prezioso (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-19670.txt.

Introduction

Paolo Boldi, Flavio Furia, and Chiara Prezioso study a broad family of ways to rank the nodes of a network by importance. Many ranking scores rest on shortest-path distances between nodes. The scores they study, called linear geometric centralities, all come from one recipe: count how many nodes sit at each distance, then blend those counts with chosen weights.

The authors ask how much this family can express. They test whether its scores can tell nodes apart, and how many distinct rankings the scores can produce on a given network, a question with uses in settings where rankings face attack. They answer the ranking count with a method built on linear programming and a classic lemma from the field. The paper is an extended version of a workshop talk on network modeling and mining.

Catalog record

CREATORPaolo Boldi, Flavio Furia, Chiara Prezioso
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-19670

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Properties and Expressivity of Linear Geometric Centralities Thanks: This is an extended version of a paper presented at the 20th Workshop on Modelling and Mining Networks [ 6 ] . Affiliation: Dipartimento di Informatica, Università degli Studi di Milano, Italy Paolo Boldi, Flavio Furia, Chiara Prezioso Abstract Centrality indices are used to rank the nodes of a graph by importance: this is a common need in many concrete situations (social networks, citation networks, web graphs, for instance) and it was discussed many times in sociology, psychology, mathematics and computer science, giving rise to a whole zoo of definitions of centrality. Although they differ widely in nature, many centrality measures are based on shortest-path distances: such centralities are often referred to as geometric . Geometric centralities can use the shortest-path–length information in many different ways, but most of the existing geometric centralities can be defined as a linear transformation of the distance-count vector (that is, the vector containing, for every index t t , the number of nodes at distance t t ). In this paper we study this class of centralities, that we call linear (geometric) centralities , in their full generality. In particular, we look at them in the light of the axiomatic approach, and we study their expressivity: we show to what extent linear centralities can be used to distinguish between nodes in a graph, and how many different rankings of nodes can be induced by linear centralities on a given graph. The latter problem (which has a number of possible applications, especially in an adversarial setting) is solved by means of a linear programming formulation, which is based on Farkas’ lemma, and is interesting in its own right. 1 Introduction and Motivation Network science is a discipline focused on analyzing network structures in order to obtain information that can be used to understand the underlying domain of the network itself. One key problem that network scientists often face is to determine the importance of nodes in a network: this is crucial for understanding the dynamics of the system and for making informed decisions based on the network’s structure. Of course, the definition of importance is not unique, and it can vary depending on the context and the specific properties of the network being analyzed. Centralities have been defined and re-defined many times over the years, in different contexts and with different approaches, and they are used to rank nodes in a network by their importance [ 9 ] . In this work, we study indices that are often referred to as geometric , as they solely depend on how many nodes exist at every (shortest-path) distance. Notable examples of geometric centralities include in-degree, closeness [ 3 , 4 ] , and harmonic [ 9 ] centrality. In particular, we propose and study a wide class of geometric measures that can be computed as linear combination of the number of nodes at every distance: these centralities will be referred to as linear geometric centralities (or just linear centralities, for short). The vast majority of the most used geometric centralities are linear (in particular, all centralities mentioned above are equivalent to some linear centrality). A special case of linear centralities are those assigning larger weights to shorter distances: the intuition here is that nearby connections are more relevant than long-range ones. These types of decaying centralities first appeared in [ 17 ] (albeit with the equivalent but opposite postulation that smaller centrality values denote a higher importance). In [ 18 ] the same class was extended to directed graphs, and several of its properties were explored. In more recent years, decaying centralities appeared in [ 24 ] , where they are called additive and studied through the so-called “axiomatic approach” (pioneered in [ 21 ] ). Another example of this approach used to study these centralities can be found in [ 15 ] and [ 5 ] . In the latter, the impact of edge additions to the final scores and rankings yielded by these indices was investigated (obtaining, independently, results similar to those in [ 17 ] ). In the present paper, we relax the assumption of decaying weights, and study linear geometric centralities in their full generality: our aim is to analyze their properties, expressivity and to understand whether they capture a broader range of behaviors than decaying centralities. As it often happens, studying broader and more abstract classes of centralities allows us to understand better the properties of narrower classes. Our work focuses especially on expressivity, following the path opened, for instance, by [ 22 ] in that it attempts to find general results for large sets of centralities. In particular, the main goal of this work is to answer the following questions: • what can we say about general properties of linear centralities as a function of the vector of coefficients? from an axiomatic perspective: what numerical properties of the vector are related to common axioms, e.g., those discussed in [ 9 ] ? • given a pair of linear geometric centralities, is there always a graph on which they rank nodes differently? in other words: how different are linear centralities from one another? • given a graph, what is the maximum number of rankings of its nodes that linear centralities can induce? how can we characterize precisely those rankings? The latter problem is particularly interesting, as it has a number of possible applications, especially in an adversarial setting: for instance, if we want to design a graph so that all linear centralities will rank some nodes in a certain way (say, x is always ranked better than y , no matter what linear centrality is used), we can employ the results of this paper to determine whether it is possible to do so. 2 Notations and Basic Definitions For every natural number n , we let [n]=\{0,1,\dots,n-1\} . Graphs. A graph G=(V_{G},E_{G}) is given [ 10 ] by a finite set of nodes V_{G} and 1 1 1 For this and similar notations, the subscript G is dropped whenever it is clear from the context. a set of arcs E_{G}\subseteq V_{G}\times V_{G} . Without loss of generality, we always assume that V=[n] where n is the number of nodes. We write x\to y to mean that x,y\in V and (x,y)\in E . A graph is undirected iff x\to y implies y\to x . When drawing undirected graphs, pairs of opposite arcs are represented as a single undirected edge x\,\text{\textemdash}\,y . A path of length k from x\in V to y\in V is a sequence (x_{0},x_{1},\dots,x_{k}) of nodes such that x=x_{0} , y=x_{k} and x_{i}\to x_{i+1} for all i\in[k] . The (shortest path) distance from x to y in G , denoted by d_{G}(x,y) , is the length of a shortest path from x to y , or \infty if no path from x to y exists. Note that in this paper, unless otherwise specified, we will consider directed graphs, where d(x,y) and d(y,x) can be different (it can even be the case that one is finite and the other is not!). Graph homomorphisms. A graph homomorphism \varphi:G\to H is a function \varphi:V_{G}\to V_{H} such that x\to_{G}y iff \varphi(x)\to_{H}\varphi(y) , for all x,y\in V_{G} .

Read the complete text