I don’t fully understand how this is a paradox. I guess it’s based on the fact that there are „super nodes“ in human social networks, where one person has many friends, while most others don’t? Or is there anything more to it?
It's the more expansive definition of paradox, meaning something like "counterintuitive result". In expectancy, a randomly chosen person has an average number of friends. You might therefore think that a random person and their friends, all of whom seem randomly chosen, would have the same expected number of friends. But you'd be wrong, because the friends weren't random after all: they had at least one friend. Not a logical paradox, but a surprising fact.