Comment déterminer les connexions probables dans un réseau social?

Je suis curieux de déterminer une approche pour aborder un algorithme "d'amis suggérés".

Facebook a une fonctionnalité dans laquelle il vous recommandera des personnes qu'il pense que vous connaissez peut-être. Ces utilisateurs ont normalement (à l'exception des cas marginaux dans lesquels un utilisateur recommande spécifiquement un ami ) un réseau très similaire à lui-même. Autrement dit, le nombre d'amis en commun est élevé. Je suppose que Twitter suit un chemin similaire pour son mécanisme "Who To Follow".

Stephen Doyle (Igy) , un employé de Facebook, a suggéré que le fil d' actualité connexe qui utilise la formule EdgeRank, ce qui semble indiquer que plus est à valoriser que des amis, comme l'apparence, est similaire. Un autre utilisateur a suggéré le système Google Rank.

Facebook indique que son optimisation du fil d'actualités est où$\sum u_{e}w_{e}d_{e}$

$u_{e}$ = score d'affinité entre l'utilisateur qui regarde et le créateur du bord = poids pour ce bord (créer, commenter, aimer, tag, etc.) = facteur de décroissance temporelle basé sur la durée de création du bord
d $w_{e}$
$d_{e}$

La somme de ces éléments est censée donner le rang d'un objet que je suppose, comme Igy l'a laissé entendre, signifie que quelque chose dans un format similaire est utilisé pour les amis suggérés.

Je suppose donc que c'est la manière dont les connexions pour tous les types se font en général via un système de classement?

Vous pouvez considérer le graphe social comme une matrice . Une approche du problème consiste à calculer d'abord , qui donnera tous les chemins de longueur deux entre deux acteurs du réseau social. Cela peut être vu comme le poids de la connexion entre ces amis d'amis. L'étape suivante consiste à sélectionner les colonnes de la ligne de correspondant à la personne d'intérêt pour obtenir les meilleurs candidats pour de nouveaux amis.M 2 M$\mathbf{M}$$\mathbf{M}^2$$\mathbf{M}^2$

Ce que vous recherchez est une heuristique. Aucun algorithme ne peut dire, étant donné un graphique d'amis comme seule entrée, si deux personnes non directement connectées sont des amis ou ne le sont pas; la relation d'amitié / connaissance n'est pas garantie d'être transitive (nous pouvons supposer la symétrie, mais cela pourrait même être un tronçon dans la vie réelle). Toute bonne heuristique devra donc être basée sur une compréhension de la façon dont les gens interagissent, plutôt que sur une compréhension mathématique de la nature des graphiques des relations (bien que nous devrons quantifier l'heuristique en ces termes).

Suggérer des amis d'amis avec une probabilité égale est une heuristique relativement bon marché mais inexacte. Par exemple, mon père a des amis, mais je ne dirais pas que je suis ami avec l'un d'eux (même si je dirais probablement que je suis un ami de mon père dans le but, par exemple, d'un réseau social). Avoir une personne à une distance relativement proche ne fait pas nécessairement d'elle une excellente candidate.

Suggérer des personnes à qui vous avez de nombreuses connexions étendues semble également être un mauvais choix en général, car cela entraînera une croissance exponentielle d'amis de personnes qui avancent tôt (les sept degrés de séparation d'avec le jeu de Kevin Bacon sont un exemple).

Je suggère un modèle basé sur un circuit. On suppose que chaque liaison est une résistance de la résistance . Le meilleur candidat pour un nouvel ami pourrait alors être l'individu ayant la résistance équivalente la plus faible. Voici un exemple graphique ASCII mal exécuté:$R$

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

Disons que nous voulons trouver de nouveaux amis pour a. aLes amis actuels de b, sont c, et f. Nous évaluons la résistance nette équivalente entre aet chacun d, e, g, het i:

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

Selon cette heuristique, dest le meilleur ami candidat, suivi de près h. gest le prochain meilleur pari, suivi de près e. ine peut jamais être un ami candidat par cette heuristique. Que vous trouviez les résultats de cette heuristique représentatifs des interactions sociales humaines réelles est ce qui est important. En termes de calcul, cela impliquerait de trouver un sous-graphique contenant tous les chemins entre deux individus (ou, peut-être intéressant, une troncature sélectionnée de manière significative), puis d'évaluer la résistance équivalente entre les nœuds source et récepteur.

EDIT: Alors, quelle est ma motivation sociale pour cela? Eh bien, cela pourrait être un modèle approximatif de la difficulté à entrer en contact avec, et par la suite, à communiquer des quantités potentiellement importantes d'informations par le biais d'intermédiaires (amis). En termes CS (plutôt qu'en termes physiques), cela pourrait être interprété comme une bande passante entre deux nœuds dans un graphique. Les extensions de ce système seraient de permettre différents types de liens entre des personnes avec des poids différents (résistance, bande passante, etc.) et procéder comme ci-dessus.

Il y a beaucoup de travail sur ce problème car la popularité des réseaux sociaux a décollé. Le problème est généralement appelé "Link Prediction" et de très bonnes enquêtes complètes peuvent être trouvées ici et ici . Les méthodes vont du très simple (par exemple la similitude de Jaccard entre les nœuds) au très complexe (par exemple la construction de modèles statistiques du processus de connexion générative). Cela dépend beaucoup des fonctionnalités spécifiques dont vous disposez dans votre jeu de données (par exemple, juste la structure du réseau, les attributs de noeud?, Les attributs de bord, ...), mais ces enquêtes vous donneront une bonne idée par où commencer.

Avertissement: je devine énormément ici; Je n'ai lu aucune recherche de genre.

Vous pouvez voir combien de connexions aux nœuds partagent par rapport au nombre de connexions d'un nœud. C'est une idée très naïve (comme locale), mais voilà.

Chaque nœud (personne ou autre concept) possède un ensemble de connexions . Maintenant, étant donné deux nœuds et , suggérez à siC N N 1 N 2 N 2 N $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$

pour un raisonnable (et inversement).$\alpha \in [0,1]$

Une autre idée est plus globale: déterminer un ensemble de nœuds similaire à celui à portée de main et proposer des connexions que beaucoup d'entre eux partagent. Donc, définissez l'ensemble de nœuds similaires

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

et les suggestions plausibles établies par

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

à nouveau pour raisonnable .$\alpha, \beta \in [0,1]$

En réalité, vous voudrez certainement pondérer les connexions individuellement; par exemple, les éléments de lesquels vous êtes déjà connecté devraient avoir une importation plus importante que ceux qui sont loin de vous.$S_N$