Friendship paradox

The friendship paradox is the phenomenon first observed by the sociologist Scott L. Feld in 1991 that on average, an individual's friends have more friends than that individual. It can be explained as a form of sampling bias in which people with more friends are more likely to be in one's own friend group. In other words, one is less likely to be friends with someone who has very few friends. In contradiction to this, most people believe that they have more friends than their friends have. The same observation can be applied more generally to social networks defined by other relations than friendship: for instance, most people's sexual partners have had (on the average) a greater number of sexual partners than they have. The friendship paradox is an example of how network structure can significantly distort an individual's local observations. In spite of its apparently paradoxical nature, the phenomenon is real, and can be explained as a consequence of the general mathematical properties of social networks. The mathematics behind this are directly related to the arithmetic-geometric mean inequality and the Cauchy–Schwarz inequality. Formally, Feld assumes that a social network is represented by an undirected graph G = (V, E), where the set V of vertices corresponds to the people in the social network, and the set E of edges corresponds to the friendship relation between pairs of people. That is, he assumes that friendship is a symmetric relation: if x is a friend of y, then y is a friend of x. The friendship between x and y is therefore modeled by the edge {x, y}, and the number of friends an individual has corresponds to a vertex's degree. The average number of friends of a person in the social network is therefore given by the average of the degrees of the vertices in the graph. That is, if vertex v has d(v) edges touching it (representing a person who has d(v) friends), then the average number μ of friends of a random person in the graph is The average number of friends that a typical friend has can be modeled by choosing a random person (who has at least one friend), and then calculating how many friends their friends have on average.

When Can Two Unlabeled Networks Be Aligned Under Partial Overlap?

Matthias Grossglauser, Ehsan Kazemi, Lyudmila Yartseva

Network alignment refers to the problem of matching the vertex sets of two unlabeled graphs, which can be viewed as a generalization of the classic graph isomorphism problem. Network alignment has applications in several fields, including social network an ...

2015

Positive network assortativity of influenza vaccination at a high school: implications for outbreak risk and herd immunity

Marcel Salathé

Schools are known to play a significant role in the spread of influenza. High vaccination coverage can reduce infectious disease spread within schools and the wider community through vaccine-induced immunity in vaccinated individuals and through the indire ...

Public Library of Science2014

When Can Two Unlabeled Networks Be Aligned Under Partial Overlap?

Positive network assortativity of influenza vaccination at a high school: implications for outbreak risk and herd immunity

Leveraging User-Generated Content for Information Discovery on the Web

When Can Two Unlabeled Networks Be Aligned Under Partial Overlap?