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.