{"word_count": 331, "character_count": 3361}
In the introduction of my course next week, I will (briefly) mention networks, and I wanted to provide some illustration of the Friendship Paradox. On network of thrones (discussed in Beveridge and Shan (2016)), there is a dataset with the network of characters in Game of Thrones. The word "friend" might be abusive here, but let's continue to call connected nodes "friends". The friendship paradox states thatPeople on average have fewer friends than their friendsThis was discussed in Feld (1991) for instance, or Zuckerman &#38; Jost (2001). Let's try to see what it means here. First, let us get a copy of the datasetdownload.file("https://www.macalester.edu/~abeverid/data/stormofswords.csv","got.csv")GoT=read.csv("got.csv")library(networkD3)simpleNetwork(GoT[,1:2])Because it is difficult for me to incorporate some d3js script in the blog, I will illustrate with a more basic graph,Consider a vertex [latex]v\in V[/latex] in the undirected graph [latex]G=(V,E)[/latex] (with classical graph notations), and let [latex]d(v)[/latex] denote the number of edges touching it (i.e. [latex]v[/latex] has [latex]d(v)[/latex] friends). The average number of friends of a random person in the graph is [latex display="true"]\mu = \frac{1}{n_V}\sum_{v\in V} d(v)=\frac{2 n_E}{n_V}[/latex] The average number of friends that a typical friend has is [latex display="true"]\frac{1}{n_V}\sum_{v\in V} \left(\frac{1}{d(v)}\sum_{v'\in E_v} d(v')\right)[/latex]But[latex display="true"]\sum_{v\in V} \left(\frac{1}{d(v)}\sum_{v'\in E_v} d(v')\right)=\sum_{v,v' \in G} \left(\frac{d(v')}{d(v)}+\frac{d(v)}{d(v')}\right)[/latex][latex display="true"]=\sum_{v,v' \in G}\left(\frac{d(v')^2+d(v)^2}{d(v)d(v')}\right)=\sum_{v,v' \in G} \left(\frac{(d(v')-d(v))^2}{d(v)d(v')}+2\right){\color{red}{\succ}}\sum_{v,v' \in G} \left(2\right)=\sum_{v\in V} d(v)[/latex]Thus,[latex display="true"]\frac{1}{n_V}\sum_{v\in V} \left(\frac{1}{d(v)}\sum_{v'\in E_v} d(v')\right)\succ \frac{1}{n_V}\sum_{v\in V} d(v)[/latex]Note that this can be related to the variance decomposition [latex display="true"]\text{Var}[X]=\mathbb{E}[X^2]-\mathbb{E}[X]^2[/latex]i.e.[latex display="true"]\frac{\mathbb{E}[X^2]}{\mathbb{E}[X]} =\mathbb{E}[X]+\frac{\text{Var}[X]}{\mathbb{E}[X]}\succ\mathbb{E}[X][/latex](Jensen inequality). But let us get back to our network. The list of nodes isM=(rbind(as.matrix(GoT[,1:2]),as.matrix(GoT[,2:1])))nodes=unique(M[,1])and we each of them, we can get the list of friends, and the number of friendsfriends = function(x) as.character(M[which(M[,1]==x),2])nb_friends = Vectorize(function(x) length(friends(x)))as well as the number of friends friends have, and the average number of friends friends_of_friends = function(y) (Vectorize(function(x) length(friends(x)))(friends(y)))nb_friends_of_friends = Vectorize(function(x) mean(friends_of_friends(x)))We can look at the density of the number of friends, for a random node,Nb  = nb_friends(nodes)Nb2 = nb_friends_of_friends(nodes)hist(Nb,breaks=0:40,col=rgb(1,0,0,.2),border="white",probability = TRUE)hist(Nb2,breaks=0:40,col=rgb(0,0,1,.2),border="white",probability = TRUE,add=TRUE)lines(density(Nb),col="red",lwd=2)lines(density(Nb2),col="blue",lwd=2)and we can also compute the averages, just to checkmean(Nb)[1] 6.579439mean(Nb2)[1] 13.94243So, indeed, people on average have fewer friends than their friends.