Suppose $\Gamma(V, E)$ is a finite simple graph. Let’s call a vertex $v \in V$ a hub if $deg(v)^2 > \Sigma_{w \in O(v)} deg(w)$. Here $deg$ stands for the vertex degree, and $O(v)$ for the set of all vertices adjacent to $v$. Let’s define $H(\Gamma)$ as the number of all hubs in $\Gamma$.
Now, suppose $G(n, p)$ is an Erdos-Renyi random graph with $n$ vertices and edge probability $p$. Does there exist some sort of explicit formula for $E(H(G(n, p)))$ (as a function of $n$ and $p$)?
How did this question arise:
I have recently heard of a so called «friendship paradox» that states, that the number of your friends usually does not exceed the average number of friends your friends have. When I at first heard about it, I wondered, if that is just some specifics of human society, or is there a mathematical explanation behind it. First I tried to translate the statement of the «friendship paradox» to the mathematical language as
Any graph with $n$ vertices has $o(n)$ hubs,
but then I quickly found, that it it is blatantly false this way:
Suppose $n > 2$, let’s take the full graph on $n$ vertices $K_n$ and then remove one edge from it, then, the resulting graph will have $n - 2$ hubs, which is clearly not $o(n)$.
So, the «friendship paradox» can not be translated to deterministic graph theory using the notion of «hubs». So it can not be interpreted that way. So, I thought, that maybe something similar with random graphs should work.
Also:
Later, I found out, that there actually is a consistent mathematical interpretation of «friendship paradox» without the usage of "hubs": Friendship paradox demonstration
However it does not solve my problem - which is finding the expectation of the number of hubs in a random graph. So, please do not mark my question as a duplicate of the aforementioned question.
Possible approach / non-closed-form solution...
Let $Bin(m,q)$ denote a binomial r.v. with $m$ trials and each trial's success probability being $q$.
By linearity of expectation, $E[H] = n \times A$ where $A=$ probability that a given node $v$ is a hub. This $A$ can be calculated exactly, by conditioning on the node degree $deg(v)$. I.e.
$A = P(v \text{ is a hub}) = \sum_{d=0}^{n-1} P(v \text{ is a hub} \mid deg(v) = d) P(deg(v) = d)$ where...
$P(deg(v) = d) = P(Bin(n-1,p) = d) = {n-1 \choose d} p^d (1-p)^{n-d-1}$ and
$P(v \text{ is a hub} \mid deg(v) = d)$ will be calculated explicitly below.
However, the answer is not a closed form.
Anyway, conditioned on $deg(v) = d$, lets consider $\sum_{w \in O(v)} deg(w)$. This sum consists of three types of edges:
Each edge $(w,v)$, where $w \in O(v)$, certainly exists. Together they contribute $d$ to the sum.
Each edge $(w_1, w_2)$, where $w_1, w_2 \in O(v), w_1 \neq w_2$, exists with probability $p$. If it exists, it contributes $2$ to the sum. So this type of edges together contribute $2\times Bin({d \choose 2}, p)$ to the sum.
Each edge $(w, x)$, where $w \in O(v), x \neq v, x \notin O(v)$, exists with probability $p$. If it exists, it contributes $1$ to the sum. So this type of edges together contribute $Bin(d(n-d-1), p)$ to the sum.
Thus, $P(v \text{ is a hub} \mid deg(v) = d) = P(d^2 > d + 2 Bin({d \choose 2}, p) + Bin(d(n-d-1), p))$. The RHS, while tedious, can be written out explicitly using the PMF of binomial r.v.s.
I don't know how to simplify without taking approximations. If you're willing to approximate, there are many ways to proceed, but I don't know which approximations are good and which are bad.