Expected rank
Expected rank
is a centrality measure based on
neighborhood inclusion
, which induces a partial ranking among nodes and has been shown to be preserved by many existing centrality indices [2]. Schoch and Brandes [3] formalized a simple principle: if a node has the same or a superset of the connections of another node, it cannot be less central. Formally,
\begin{equation*}
\mathcal{N}(u) \subseteq \mathcal{N}(v) \cup \{v\} \quad \Rightarrow \quad c(u) \leq c(v),
\end{equation*}
where \(\mathcal{N}(u)\) denotes the set of neighbors of node \(u\).
Neighborhood inclusion defines a
pre-order
(a reflexive and transitive binary relation) on the nodes of a graph. From this partial order, full rankings (linear extensions) can be generated by arranging the nodes into a total order that preserves all pairwise relations implied by the partial order. The expected rank of node \(i\), denoted \(c_{ER}(i)\), is then defined as
\[
c_{ER}(i) = \sum_{k=1}^{N} k \, \Pr[\mathrm{rk}(i) = k],
\]
where \(\Pr[\mathrm{rk}(i) = k]\) is the probability that node \(i\) occupies rank \(k\) in a full ranking.
A limitation of this approach is that enumerating all possible linear extensions is computationally prohibitive for large networks. Schoch and Brandes [2] suggest using approximation techniques, such as sampling or heuristic methods, to estimate expected ranks efficiently.