What are some centrality measures that don't satisfy "star maximization?"

Question

Some have proposed that for a natural centrality measure, the most central a node can get is the center node in the star network. I've heard this called "star maximization." That is, for a measure $M(\cdot)$, and a star network $g^\star$ with center $c^\star$,

$$\{ (c^\star, g^\star)\} \in {\arg\max}_{(i,g)\in N\times \mathcal{G}(N)}M(i,g)$$

where $N$ is the set of nodes and $\mathcal{G}$ considers all unweighted network structures.

I'd like to learn about some centrality measures that don't satisfy this property, but "star maximization" isn't a heavily used term, so I am having trouble in searching for many such measures. What are some such measures of centrality?

Answer 1

A centrality measure will display star maximization under very weak conditions.

Suppose you normalize the sum of centralities to 1. Then as long as you assign zero centrality to peripheral nodes (those connected to just one other node) the centre must have the maximal centrality 1.

Answer 2

If you consider maximisation over all possible networks, it’s straightforward to construct counter-examples:

• If $g^*$ is a star network with $n+1$ nodes, $g'∈\mathcal{G}$ is a star network with $m+1>n+1$ nodes, and $M$ is the unnormalised degree (centrality), we have $M(c^*,g^*)=n<m=M(c',g')$ – independent of a normalisation of the centrality.

• If $M$ is the normalised eigenvector centrality, you have $M(c^*,g^*) = \frac{\sqrt{n}}{n+\sqrt{n}} > \frac{\sqrt{m}}{m+\sqrt{m}} = M(c',g')$, i.e., star maximisation does not hold for $g'$.

• If you consider other star networks cheating, just add an edge to the offending network (thus making it no star network anymore) and make the difference between $m$ and $n$ sufficiently large.

However if you consider maximisation within a network², i.e.:

$$ c^* ∈ \arg\max_i M(i,g^*),$$

I would consider star maximisation given for the following reason: I am not aware of a mathematical definition of centrality measure, but I if I had to make one, it would include star maximisation (within a network) either explicitly or as a consequence. If it didn’t, I would consider my definition a failure since it does not capture the colloquial essence of centrality measures, namely that they quantify importance of nodes¹. The centre of an unweighted star network is clearly the most important in that network¹. Or with other words: Nobody in their right minds would consider $M$ a centrality measure if it does not have star maximisation (within a network).

---

^{¹ as indicated by the network structure
² which is the practically more relevant case anyway}