A centrality measure scores how important each node of a network is. In a directed network, a new arc is like a new follower: for almost every classical measure it raises the score and the rank of the node it points to. In an undirected network a new edge is like a new friendship, shared by both endpoints, and one would expect both to gain. The figure shows that this can fail. With closeness centrality, another node can gain more from the new edge than one of its endpoints does, and overtake it.
With Paolo Boldi, Flavio Furia and Sebastiano Vigna we introduced a weaker property, semi-monotonicity, which asks only that at least one endpoint is not overtaken by any other node. We proved that closeness, a large class of distance-based centralities and, more surprisingly, betweenness all satisfy it. For the last two we proved a stronger property, basin dominance.