Hi I am a beginner in graph theory, discrete math, and network analysis. I am reading a paragraph about Friendship Paradox (the mean number of friends of friends is always greater than the mean number of friends of individuals) in a notebook. In order to proof this argument, it defines average degree of vertices (see below, the first formula), and average degree of edges (see below, the second formula).
$$d_V(v)=\frac{1}{\deg(v)}\sum_{w\in N(v)}\deg(w)$$
$$d_{E}({v,w})=\frac{1}{2}(\deg(v)+\deg(w))$$
Theorem:
(1)$$<deg> \leq <d_V>$$
(2)$$<deg> \leq <d_E>$$
I can understand what average degree of vertices mean, which is the average of the number of friends that your friends have. We can proof the friendship paradox by proving the Mean of average degree of vertices is greater than average degree in the graph (as (1) of the above theorem).
But what does average degree of edges mean in this context, and what (2) are trying to say?
Thank you.
Best Answer
The average degree of an edge is the average number of friendships between two people who are friends. Note this definition double-counts the friendship between the two people in question.
For instance, suppose Alice and Bob are friends. Alice has 7 friends including Bob, and Bob has 5 friends including Alice. Then the average number of friendships shared between the two is $(7+5)/2 = 6$ friends.
I should also clarify your interpretation of the average degree of a vertex. You wrote that it is the number of friends that the friends of a given person has. However, what you meant to say is it is the average number of friends that the friends of a given person has. For example, suppose Alice has 7 friends; Bob, Christine, David, Ellie, Frank, Giselle, and Hieu. If Bob has 5 friends, Christine 9, David 3, Ellie 11, Frank 6, Giselle 15, and Hieu 10, where in each case we count among those friendships the one each has with Alice, then the average number of friends of Alice's friends is $$\frac{1}{7}(5 + 9 + 3 + 11 + 6 + 15 + 10) = \frac{59}{7}.$$