Chiara Prezioso

dblp:407/0228 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2026
0009-0006-3533-3050ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2026 Properties and expressivity of linear geometric centralities
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 , the number of nodes at distance 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.
Paolo Boldi, Flavio Furia, Chiara Prezioso
Theor. Comput. Sci.3
2025 Linear Geometric Centralities
Paolo Boldi, Flavio Furia, Chiara Prezioso
WAW3