Efficient edge-centrality measures based on matrix functions of the line graph

by Francesco Zigliotto

Tuesday 28 Apr 2026, 11:00 → Wednesday 29 Apr 2026, 00:00 Europe/Rome

Aula Magna (Dipartimento di Matematica)

While network centrality is predominantly studied from a node perspective, here we investigate edge-centrality measures based on matrix functions. Specifically, we examine centrality within the context of the line graph, a structure where the roles of nodes and edges are inverted. Although any standard node-centrality metric can theoretically be applied to a line graph to assess edge importance, line graphs generally possess significantly more nodes than their original counterparts, which makes computing matrix functions of their adjacency matrices computationally infeasible. To address this bottleneck, we introduce novel matrix function identities that reduce the dimensionality of the required calculations. By operating on matrices of a much smaller size, these identities yield edge-centrality algorithms that are, in practice, nearly as fast as their node-level equivalents. Both directed and undirected graphs are treated.