Un guide pour lier la prédiction - Comment prédire vos futures connexions sur Facebook

Aperçu

  • Une introduction pour lier la prédiction, comment elle fonctionne et où vous pouvez l'utiliser dans le monde réel
  • Découvrez l'importance de Link Prediction sur les réseaux sociaux
  • Créez votre premier modèle de prédiction de lien pour un cas d'utilisation Facebook à l'aide de Python

introduction

Vous êtes-vous déjà demandé qui pourrait être votre prochaine connexion Facebook? Vous voulez savoir de qui pourrait provenir la prochaine demande?

Et si je vous disais qu'il y avait un moyen de prédire cela?

J'adore le remue-méninges et trouver ces déclarations de problème lorsque je navigue sur mon compte Facebook. C'est l'un des avantages d'avoir l'état d'esprit d'un data scientist!

La plupart des plateformes de médias sociaux, y compris Facebook, peuvent être structurées sous forme de graphiques. Les utilisateurs enregistrés sont interconnectés dans un univers de réseaux. Et pour travailler sur ces réseaux et graphiques, nous avons besoin d'un ensemble différent d'approches, d'outils et d'algorithmes (au lieu des méthodes traditionnelles d'apprentissage automatique).

Donc, dans cet article, nous allons résoudre un problème de réseau social à l'aide de graphiques et d'apprentissage automatique. Nous allons d'abord comprendre les concepts et composants de base de la prédiction de liens avant de prendre une étude de cas Facebook et de l'implémenter en Python!

Je vous recommande de parcourir les articles ci-dessous pour vous familiariser avec les graphiques et leur fonctionnement:

Table des matières

  1. Un aperçu de l'analyse des réseaux sociaux
  2. Une introduction à la prédiction des liens
  3. Stratégie pour résoudre un problème de prédiction de lien
  4. Étude de cas: Prédire les connexions futures entre les pages Facebook - Comprendre les données - Construction d'un modèle de préparation de jeu de données - Extraction de fonctionnalités - Construction d'un modèle: modèle de prédiction de lien

Un aperçu de l'analyse des réseaux sociaux

Définissons un réseau social avant de plonger dans le concept de prédiction de lien.

Un réseau social est essentiellement une représentation des relations entre des entités sociales, telles que des personnes, des organisations, des gouvernements, des partis politiques, etc.

Les interactions entre ces entités génèrent des quantités inimaginables de données sous forme de publications, de messages de chat, de tweets, de likes, de commentaires, de partages, etc. Cela ouvre une fenêtre d'opportunités et de cas d'utilisation sur lesquels nous pouvons travailler.

Cela nous amène à l'analyse des réseaux sociaux (SNA). Nous pouvons le définir comme une combinaison de plusieurs activités effectuées sur les réseaux sociaux. Ces activités comprennent la collecte de données à partir de sites de médias sociaux en ligne et l'utilisation de ces données pour prendre des décisions commerciales.

Les avantages de l'analyse des réseaux sociaux peuvent être très gratifiants. Voici quelques avantages clés:

  • Vous aide à mieux comprendre votre public
  • Utilisé pour la segmentation client
  • Utilisé pour concevoir des systèmes de recommandation
  • Détectez les fausses nouvelles, entre autres

Une introduction à la prédiction des liens

La prédiction de liens est l'un des sujets de recherche les plus importants dans le domaine des graphiques et des réseaux. L'objectif de la prédiction de lien est d'identifier des paires de nœuds qui formeront ou non un lien à l'avenir.

La prédiction de lien a une tonne d'utilisation dans des applications du monde réel. Voici quelques-uns des cas d'utilisation importants de la prédiction de liens:

  • Prévoyez quels clients sont susceptibles d'acheter quels produits sur des marchés en ligne comme Amazon. Il peut aider à faire de meilleures recommandations de produits
  • Suggérer des interactions ou collaborations entre les employés d'une organisation
  • Extraire des informations vitales des réseaux terroristes

Dans cet article, nous explorerons un cas d'utilisation légèrement différent de la prédiction de liens - prédire des liens dans un réseau social en ligne!

Stratégie pour résoudre un problème de prédiction de lien

Si nous pouvons en quelque sorte représenter un graphique sous la forme d'un ensemble de données structuré ayant un ensemble de fonctionnalités, alors nous pouvons peut-être utiliser l'apprentissage automatique pour prédire la formation de liens entre les paires de nœuds non connectées du graphique.

Prenons un graphique factice pour comprendre cette idée. Ci-dessous, un graphique à 7 nœuds et les paires de nœuds non connectées sont AF, BD, BE, BG et EG:

Graphique au temps t

Maintenant, disons que nous analysons les données et avons créé le graphique ci-dessous. Quelques nouvelles connexions ont été établies (liens en rouge):

Graphique au temps t + n

Nous devons avoir un ensemble de variables prédictives et une variable cible pour construire tout type de modèle d'apprentissage automatique, non? Alors, où sont ces variables? Eh bien, nous pouvons l'obtenir à partir du graphique lui-même! Voyons comment cela se fait.

Notre objectif est de prédire s'il y aurait un lien entre 2 nœuds non connectés. Du réseau au temps t, nous pouvons extraire les paires de nœuds suivantes qui n'ont aucun lien entre elles:

  1. UN F
  2. BD
  3. ÊTRE
  4. BG
  5. PAR EXEMPLE

Veuillez noter que, pour plus de commodité, je n'ai considéré que les nœuds qui sont séparés par quelques liens.

La prochaine étape pour nous est de créer des fonctionnalités pour chaque paire de nœuds. La bonne nouvelle est qu'il existe plusieurs techniques pour extraire des fonctionnalités des nœuds d'un réseau. Disons que nous utilisons l'une de ces techniques et construisons des fonctionnalités pour chacune de ces paires. Cependant, nous ne savons toujours pas quelle est la variable cible. Rien à craindre - nous pouvons également l'obtenir facilement.

Regardez le graphique au temps t + n. Nous pouvons voir qu'il y a trois nouvelles liaisons dans le réseau pour les paires AF, BD et BE respectivement. Par conséquent, nous attribuerons à chacun d'eux une valeur de 1. Les paires de nœuds BG et EG recevront 0 car il n'y a toujours pas de liens entre les nœuds.

Par conséquent, les données ressembleront à ceci:

Maintenant que nous avons la variable cible, nous pouvons construire un modèle d'apprentissage automatique en utilisant ces données pour effectuer une prédiction de lien.

Donc, c'est ainsi que nous devons utiliser des graphes sociaux à deux moments différents pour extraire la variable cible, c'est-à-dire la présence d'un lien entre une paire de nœuds. Gardez à l'esprit, cependant, que dans les scénarios du monde réel, nous n'aurons que des données de l'heure actuelle.

Extraire des données d'un graphique pour construire votre modèle

Dans la section ci-dessus, nous avons pu obtenir des étiquettes pour la variable cible car nous avions accès au graphique au temps t + n. Cependant, dans des scénarios réels, nous n'aurions qu'un seul jeu de données de graphique en main. C'est ça!

Disons que nous avons le graphique ci-dessous d'un réseau social où les nœuds sont les utilisateurs et les bords représentent une sorte de relation:

Les paires de nœuds candidats, qui peuvent former un lien à un moment futur, sont (1 & 2), (2 & 4), (5 & 6), (8 & 10), etc. Nous devons construire un modèle qui prédira s'il y aura ou non un lien entre ces paires de nœuds. C'est à cela que sert la prédiction de liens!

Cependant, pour construire un modèle de prédiction de lien, nous devons préparer un ensemble de données d'apprentissage à partir de ce graphique. Cela peut être fait en utilisant une astuce simple.

Imaginez ceci - à quoi aurait ressemblé ce graphique à un moment donné dans le passé? Il y aurait moins de bords entre les nœuds car les connexions dans un réseau social se construisent progressivement au fil du temps.

Par conséquent, en gardant cela à l'esprit, nous pouvons masquer au hasard certains des bords du graphique donné, puis suivre la même technique que celle expliquée dans la section précédente pour créer l'ensemble de données d'apprentissage.

Supprimer les liens du graphique

Lors de la suppression de liens ou de bords, nous devons éviter de supprimer tout bord susceptible de produire un nœud isolé (nœud sans aucun bord) ou un réseau isolé. Enlevons certains des bords de notre réseau:

Comme vous pouvez le voir, les bords des paires de nœuds (1 & 4), (7 & 9) et (3 & 8) ont été supprimés.

Ajouter des étiquettes aux données extraites

Ensuite, nous aurions besoin de créer des fonctionnalités pour toutes les paires de nœuds non connectées, y compris celles pour lesquelles nous avons omis les bords. Les bords supprimés seront étiquetés comme «1» et les paires de nœuds non connectés comme «0».

La variable cible sera fortement déséquilibrée dans cet ensemble de données. C'est ce que vous rencontrerez également dans les graphiques du monde réel. Le nombre de paires de nœuds non connectés serait énorme.

Prenons une étude de cas et résolvons le problème de la prédiction de liens en utilisant Python.

Étude de cas: prédire les connexions futures entre les pages Facebook

C'est là que nous appliquerons tout ce qui précède dans un scénario génial du monde réel.

Nous travaillerons avec un ensemble de données de graphique dans lequel les nœuds sont des pages Facebook d'articulations alimentaires populaires et de chefs renommés du monde entier. S'il y a deux pages (nœuds) qui s'aiment, il y a un bord (lien) entre elles.

Vous pouvez télécharger l'ensemble de données ici.

Objectif: Construire un modèle de prédiction de lien pour prédire les futurs liens (likes mutuels) entre des nœuds non connectés (pages Facebook).

Allumons notre carnet Jupyter (ou Colab)!

Comprendre les données

Nous allons d'abord importer toutes les bibliothèques et modules nécessaires:

Chargeons les pages Facebook en tant que nœuds et les goûts mutuels entre les pages en tant que bords:

Sortie: (620, 2102)

Nous avons 620 nœuds et 2 102 liens. Créons maintenant une trame de données de tous les nœuds. Chaque ligne de cette trame de données représente un lien formé par les nœuds dans les colonnes 'node_1' et 'node_2', respectivement:

fb_df.head ()

Les nœuds «276», «58», «132», «603» et «398» forment des liens avec le nœud «0». Nous pouvons facilement représenter cet agencement de pages Facebook sous la forme d'un graphique:

Wow, cela ressemble à quelque chose. C'est ce que nous allons traiter - un treillis métallique de pages Facebook (points bleus). Les lignes noires sont les liens ou les bords reliant tous les nœuds les uns aux autres.

Préparation du jeu de données pour la construction de modèles

Nous devons préparer l'ensemble de données à partir d'un graphique non orienté. Cet ensemble de données aura des caractéristiques de paires de nœuds et la variable cible serait de nature binaire, indiquant la présence de liens (ou non).

Récupérer les paires de nœuds non connectés - Échantillons négatifs

Nous avons déjà compris que pour résoudre un problème de prédiction de lien, nous devons préparer un ensemble de données à partir du graphique donné. Une grande partie de cet ensemble de données est constituée des échantillons négatifs ou des paires de nœuds non connectés. Dans cette section, je vais vous montrer comment extraire les paires de nœuds non connectées d'un graphique.

Tout d'abord, nous allons créer une matrice d'adjacence pour trouver quelles paires de nœuds ne sont pas connectées.

Par exemple, la contiguïté du graphique ci-dessous est une matrice carrée dans laquelle les lignes et les colonnes sont représentées par les nœuds du graphique:

Les liens sont désignés par les valeurs de la matrice. 1 signifie qu'il existe un lien entre la paire de nœuds et 0 signifie qu'il existe un lien entre la paire de nœuds. Par exemple, les nœuds 1 et 3 ont 0 à leur jonction croisée dans la matrice et ces nœuds n'ont également aucun bord dans le graphique ci-dessus.

Nous utiliserons cette propriété de la matrice d'adjacence pour trouver toutes les paires de nœuds non connectées à partir du graphe d'origine G:

Voyons la forme de la matrice d'adjacence:

adj_G.shape

Sortie: (620, 620)

Comme vous pouvez le voir, c'est une matrice carrée. Maintenant, nous allons parcourir la matrice d'adjacence pour trouver les positions des zéros. Veuillez noter que nous n'avons pas à parcourir toute la matrice. Les valeurs dans la matrice sont les mêmes au-dessus et au-dessous de la diagonale, comme vous pouvez le voir ci-dessous:

Nous pouvons soit rechercher dans les valeurs au-dessus de la diagonale (partie verte) ou les valeurs ci-dessous (partie rouge). Cherchons les valeurs diagonales pour zéro:

Voici le nombre de paires de nœuds non connectés que nous avons dans notre ensemble de données:

len (all_unconnected_pairs)

Sortie: 19,018

Nous avons 19 018 paires non connectées. Ces paires de nœuds agiront comme des échantillons négatifs lors de la formation du modèle de prédiction de liaison. Gardons ces paires dans une trame de données:

Supprimer les liens des paires de nœuds connectés - Échantillons positifs

Comme nous l'avons vu ci-dessus, nous supprimerons aléatoirement certains bords du graphique. Cependant, la suppression aléatoire d'arêtes peut entraîner la coupure de nœuds et de fragments du graphique mal connectés. C'est quelque chose dont nous devons nous occuper. Nous devons nous assurer que dans le processus de suppression des bords, tous les nœuds du graphique doivent rester connectés.

Dans le bloc de code ci-dessous, nous vérifierons d'abord si la suppression d'une paire de nœuds entraîne la division du graphique (nombre_composants_connectés> 1) ou la réduction du nombre de nœuds. Si les deux choses ne se produisent pas, nous supprimons cette paire de nœuds et répétons le même processus avec la paire de nœuds suivante.

Finalement, nous obtiendrons une liste de paires de nœuds qui peuvent être supprimées du graphique et tous les nœuds resteraient intacts:

len (omissible_links_index)

Sortie: 1483

Nous avons plus de 1400 liens que nous pouvons supprimer du graphique. Ces fronts tombés serviront d'exemples d'apprentissage positifs lors de l'apprentissage du modèle de prédiction de lien.

Données pour la formation des modèles

Ensuite, nous ajouterons ces bords amovibles à la trame de données des paires de nœuds non connectées. Étant donné que ces nouveaux bords sont des échantillons positifs, ils auront une valeur cible de «1»:

Vérifions la distribution des valeurs de la variable cible:

data ['link']. value_counts ()

0 -19018 1 -1483

Il s'avère que ce sont des données très déséquilibrées. Le rapport lien / pas de lien est proche de 8%. Dans la section suivante, nous allons extraire les fonctionnalités de toutes ces paires de nœuds.

Extraction de caractéristiques

Nous utiliserons l'algorithme node2vec pour extraire les caractéristiques des nœuds du graphique après avoir supprimé les liens. Donc, créons d'abord un nouveau graphique après avoir supprimé les liens amovibles:

Ensuite, nous allons installer la bibliothèque node2vec. Il est assez similaire à l'algorithme DeepWalk. Cependant, cela implique des marches aléatoires biaisées. Pour en savoir plus sur node2vec, vous devriez absolument consulter ce papier node2vec: Scalable Feature Learning for Networks.

Pour le moment, gardez à l'esprit que node2vec est utilisé pour la représentation vectorielle des nœuds d'un graphique. Installons-le:

! pip installer node2vec

L'installation sur votre machine locale peut prendre un certain temps (c'est assez rapide si vous utilisez Colab).

Maintenant, nous allons former le modèle node2vec sur notre graphique (G_data):

Ensuite, nous appliquerons le modèle node2vec formé sur chaque paire de nœuds dans les données de la trame de données. Pour calculer les caractéristiques d'une paire ou d'une arête, nous additionnerons les caractéristiques des nœuds de cette paire:

x = [(n2w_model [str (i)] + n2w_model [str (j)]) pour i, j en zip (données ['node_1'], données ['node_2'])]]

Construire notre modèle de prédiction de liens

Pour valider les performances de notre modèle, nous devons diviser nos données en deux parties - une pour la formation du modèle et l'autre pour tester les performances du modèle:

Faisons d'abord un modèle de régression logistique:

Nous allons maintenant faire des prédictions sur l'ensemble de test:

predictions = lr.predict_proba (xtest)

Nous utiliserons le score AUC-ROC pour vérifier les performances de notre modèle.

roc_auc_score (test, prévisions [:, 1])

Sortie: 0,7817

Nous obtenons un score de 0,78 en utilisant un modèle de régression logistique. Voyons si nous pouvons obtenir un meilleur score en utilisant un modèle plus complexe.

La formation s'est arrêtée après la 208e itération car nous avons appliqué les critères d'arrêt précoce. Plus important encore, le modèle a obtenu un score impressionnant de 0,9273 AUC sur l'ensemble de test. Je vous encourage à consulter la documentation de lightGBM pour en savoir plus sur les différents paramètres.

Notes de fin

Le potentiel des graphiques est énorme. Nous pouvons exploiter cela pour résoudre un grand nombre de problèmes du monde réel, dont la prédiction de liens en est un.

Dans cet article, nous avons présenté comment un problème de prédiction de lien peut être résolu à l'aide de l'apprentissage automatique, et quelles sont les limites et les aspects importants que nous devons garder à l'esprit lors de la résolution d'un tel problème.

N'hésitez pas à poser des questions ou à laisser vos commentaires dans la section commentaires ci-dessous. Continuez à explorer!

Publié à l'origine sur https://www.analyticsvidhya.com le 16 janvier 2020.