¿Cómo determinar las conexiones probables en una red social?

Tengo curiosidad por determinar un enfoque para abordar un algoritmo de "amigos sugeridos".

Facebook tiene una función en la que le recomendará personas que cree que puede conocer. Estos usuarios normalmente (excluyendo los casos extremos en los que un usuario recomienda específicamente a un amigo ) tienen una red muy similar a la suya. Es decir, el número de amigos en común es alto. Supongo que Twitter sigue un camino similar para su mecanismo "Who To Follow".

Stephen Doyle (Igy) , un empleado de Facebook sugirió que la fuente de noticias relacionada que usa la fórmula EdgeRank que parece indicar que se valora más que los amigos, como la apariencia, es publicaciones similares. Otro usuario sugirió el sistema Google Rank.

Facebook afirma su News Feed optimización como donde$\sum u_{e}w_{e}d_{e}$

= puntaje de afinidad entre el usuario visual y el creador del borde w e = peso para este borde (crear, comentar, dar me gusta, etiquetar, etc.) d e = factor de disminución de tiempo en función de cuánto tiempo hace que se creó el borde $u_{e}$
$w_{e}$
$d_{e}$

Se supone que la suma de estos elementos da el rango de un objeto, lo que supongo que Igy insinuó, significa que se usa algo en un formato similar para los amigos sugeridos.

Entonces, supongo que esta es la forma en que las conexiones para todos los tipos se realizan en general a través de un sistema de clasificación.

Se puede pensar en el gráfico social como una matriz . Un enfoque del problema es calcular primero M 2 , que dará todos los caminos de longitud dos entre dos actores en la red social. Esto puede verse como el peso de la conexión entre estos amigos de amigos. El siguiente paso es seleccionar las columnas de la fila de M 2 correspondiente a la persona de interés para obtener los mejores candidatos para nuevos amigos.$\mathbf{M}$$\mathbf{M}^2$$\mathbf{M}^2$

Lo que estás buscando es una heurística. Ningún algoritmo puede decir, dado un gráfico de amigos como la única entrada, si dos individuos que no están directamente conectados son amigos o no; No se garantiza que la relación de amistad / amistad sea transitiva (podemos suponer simetría, pero eso incluso podría ser una exageración en la vida real). Por lo tanto, cualquier buena heurística deberá basarse en una comprensión de cómo interactúan las personas, en lugar de una comprensión matemática de la naturaleza de los gráficos de las relaciones (aunque tendremos que cuantificar la heurística en estos términos).

Sugerir amigos de amigos con la misma probabilidad es una heurística relativamente barata pero imprecisa. Por ejemplo, mi padre tiene amigos, pero yo no diría que soy amigo de ninguno de ellos (aunque probablemente diría que soy amigo de mi padre para, por ejemplo, una red social). Tener una persona a una distancia relativamente cercana no necesariamente lo convierte en un gran candidato.

Sugerir a las personas con las que tiene muchas conexiones extendidas también parece una mala elección en general, porque esto tenderá a llevar a un crecimiento exponencial de amigos de personas que se adelantan desde el principio (los siete grados de separación del juego de Kevin Bacon es un ejemplo de esto).

$R$

  _____
 /     \
a---c   f
|   | /
b   d---e
| \ |
g   h   i

Digamos que queremos encontrar nuevos amigos para a. a's amigos actuales son b, cy f. Se evalúa la resistencia equivalente neto entre ay cada uno de d, e, g, h, y i:

pair   resistance
(a,d)   6/7
(a,e)  13/7
(a,g)   7/4
(a,h)   1/1
(a,i)   inf

Según esta heurística, des el mejor amigo candidato, seguido de cerca por h. ges la siguiente mejor apuesta, seguida de cerca por e. iNunca puede ser un candidato amigo por esta heurística. Lo importante es saber si los resultados de esta heurística son representativos de las interacciones sociales humanas reales. Hablando computacionalmente, esto implicaría encontrar una subgrafía que contenga todas las rutas entre dos individuos (o, quizás de manera interesante, un truncamiento significativamente seleccionado de esto), luego evaluar la resistencia equivalente entre los nodos fuente y sumidero.

EDITAR: Entonces, ¿cuál es mi motivación social para esto? Bueno, este podría ser un modelo aproximado de lo difícil que es ponerse en contacto y, posteriormente, comunicar posibles cantidades significativas de información a través de intermediarios (amigos). En términos de CS (en lugar de términos de física), esto podría interpretarse como ancho de banda entre dos nodos en un gráfico. Las extensiones de este sistema serían permitir diferentes tipos de enlaces entre personas con diferentes pesos (resistencia, ancho de banda, etc.) y proceder como se indica anteriormente.

Se ha trabajado mucho en este problema ya que la popularidad de las redes sociales ha despegado. El problema generalmente se denomina "Predicción de enlaces" y se pueden encontrar encuestas muy buenas y completas aquí y aquí . Los métodos van desde lo muy simple (por ejemplo, la similitud de Jaccard entre nodos) hasta lo muy complejo (por ejemplo, la construcción de modelos estadísticos del proceso de conexión generativa). Depende mucho de las características específicas que tenga disponibles en su conjunto de datos (por ejemplo, solo estructura de red, atributos de nodo ?, atributos de borde, ...), pero estas encuestas le darán una buena idea de dónde comenzar.

Descargo de responsabilidad: estoy adivinando salvajemente aquí; No he leído ninguna investigación de género.

Podrías ver cuántas conexiones a los nodos comparten en relación con el número de conexiones que tiene un nodo. Esta es una idea muy ingenua (como local), pero aquí va.

$N$$C_N$$N_1$$N_2$$N_2$$N_1$

$\qquad \displaystyle \frac{|C_{N_1} \cap C_{N_2}|}{|C_{N_1}|} \geq \alpha$

$\alpha \in [0,1]$

Otra idea es más global: determine un conjunto de nodos similar al que está a la mano y proponga conexiones que muchos de ellos comparten. Entonces, defina el conjunto de nodos similares

$\qquad \displaystyle S_N = \left\{M : \frac{|C_N \cap C_M|}{N} \geq \alpha\right\}$

y el conjunto de sugerencias plausibles por

$\qquad \displaystyle \left\{ S : \frac{\sum_{M \in S_N} [S \in M]}{|S_N|} \geq \beta \right\}$

$\alpha, \beta \in [0,1]$

$S_N$