¿Tus amigos, en promedio, tienen más amigos que tú?

Question

Estaba viendo este TED talk, lo que sugiere que, en promedio, sus amigos tienden a individualmente tienen más amigos que tú. Para definir esto de manera más formal, estamos comparando el número promedio de amigos con:

average over each person p of:
    friend popularity, defined as:
    average over each friend f of p:
        number of friends f has

Intuitivamente, esto parece tener sentido. Después de todo, si alguien tiene un gran número de amigos, tienden a aumentar amigo popularidad y afectan a un número elevado de personas, mientras que aquellas personas que disminuir amigo popularidad sólo afectan a un número reducido de personas. ¿Este resultado se mantenga para todos los gráficos?

Dado que una persona p, deje t soporte para:

sum over each friend f of p:
    number of friends f has

Está bastante claro que la sum(t)=sum(f^2) como una persona con f amigos tiene un valor de f hacia su f amigos valor de t.

Entonces estamos tratando de determinar si: sum(t/f)>sum(f) tiene para todos los gráficos.

Answer 1

La respuesta es sí, esto es válido para cualquier gráfica (con la debilidad de la desigualdad, como Jon puntos).

Vamos a configurar algunas anotaciones. La gráfica de la amistad es $G$. El conjunto de vértices de $G$ (de la gente) es $V$; el conjunto de aristas (la amistad) es $E$. Para una persona $v$, el número de amigos que la persona tiene es $\deg v$. El número total de personas es $n$.

Queremos mostrar que $$\frac{1}{n} \sum_{v \in V} \deg v \leq \frac{1}{n} \sum_{v \in V} \frac{1}{\deg v} \sum_{(u,v) \in E} \deg(u).$$

Cancelar la $1/n$'s de ambos lados. Después de un poco de volver a escribir, queremos mostrar que $$\sum_{v \in V} \sum_{(u,v) \in E} 1 \leq \sum_{v \in V} \sum_{(u,v) \in E} \frac{\deg u}{\deg v}. \quad (*)$$

Vamos a considerar lo que es un borde dado $(u,v)$ contribuye a cada lado de la $(*)$. A la izquierda, se contribuye $1+1=2$. A la derecha, contribuye $(\deg u)/(\deg v) + (\deg v)/(\deg u)$. Para cualquiera de los dos números positivos $x$$y$,$2 \leq x/y+y/x$. Así que cada borde contribuye más a la derecha de $(*)$ que a la izquierda, y tenemos el resultado reivindicado.

Answer 2

Comentario Trivial, pero soy nuevo, así que tengo que publicarlo como una respuesta: La desigualdad estricta definitivamente no se mantienen en general, ya que las sumas son iguales para regular los gráficos.