🚄 👧🏻 🏩 Identifiez la communauté intercommunautaire sur Instagram pour identifier les intérêts des utilisateurs 👨🏾‍⚕️ 🧙🏽 👩🏻‍🤝‍👨🏾

Combien un profil sur un réseau social peut-il dire sur une personne? Photos, articles, commentaires, abonnements - un champ vierge pour l'analyse. Aujourd'hui, nous allons parler de la façon dont nous déterminons les intérêts des utilisateurs en fonction de leurs abonnements Instagram.

Source

L'approche évidente consiste à classer les abonnements d'une personne. Par exemple, parmi les abonnements de l'utilisateur Ivan, nous avons trouvé deux autoblogueurs et trois comptes avec des images amusantes, le reste des profils n'est pas thématique (nous supposons qu'il s'agit d'amis, de parents, de collègues, etc.). De cela, nous concluons: Ivan est une personne joyeuse, friande de voitures. Bénéfice Tout ce dont nous avons besoin, c'est de la correspondance «blogueur + thème de contenu», mais tout n'est pas si simple ici.

Qui est blogueur? Un blogueur sur Instagram n'est pas différent d'un compte régulier (et en général, c'est quelque chose comme un état d'esprit). Idéalement, nous sommes intéressés par les comptes thématiques avec une large part d'audience live, alors que nous ne voudrions pas simplement couper le nombre d'abonnés, nous pourrions manquer quelque chose.

Où trouver une bonne taxonomie? Si vous inventez les catégories vous-même, alors quelque chose d'intéressant se perdra certainement dans «des choses différentes», et quand tout est prêt, il s'avère que les catégories sont trop larges. Nous voulons obtenir une partition naturelle, et donc nous allons regrouper les blogueurs.

Un blogueur peut-il appartenir à plusieurs catégories? Comme ça! Très souvent, il est à la fois un Suisse, un faucheur et un mec qui joue (et aussi les voyages, le style de vie, la femme et la mère).
Nous avons donc besoin d'un ensemble de données avec un très grand nombre de blogueurs et d'un algorithme de clustering avec des clusters qui se croisent à la sortie.

Comment tout a commencé

Nous sommes approchés par les clients qui souhaitent placer leurs annonces auprès des leaders d'opinion sur Instagram le plus efficacement possible. Parfois, il y a une liste de blogueurs, puis nous résolvons le problème d'optimisation - pour atteindre plus de personnes pour moins d'argent, et parfois il n'y a pas de liste et les blogueurs concernés doivent être trouvés. Cette fois, ils ont recherché des profils d'ophtalmologistes.

Nous avons utilisé une approche similaire à un système de recommandation:

Choisissez 3-7 profils appropriés avec vos mains («communauté principale»)
En utilisant l'intersection des abonnés, nous identifions les personnes intéressées par le sujet («enthousiastes»)
Nous recherchons de nouveaux médecins dans les abonnements de personnes «enthousiastes»
Si nécessaire, répétez les étapes 1 à 3 (en ajoutant de nouveaux médecins au «noyau» ou en le modifiant)

Maintenant plus en détail sur un exemple.

Étape 1. En utilisant une recherche Instagram, nous avons sélectionné 6 comptes d'ophtalmologistes de différentes régions de Russie:

La liste est assez aléatoire, mais il nous a suffi que le blog corresponde vraiment au sujet et que les abonnés ne soient pas moins de 1000 personnes.

Étape 2. Après avoir croisé tous les abonnés, nous regardons la distribution.

Nombre de suivis mutuels	Nombre de comptes
6	2
5	3
4	24
3	102
2	693
1	30025

Hourra! Il y a des intersections.

De plus, il y a deux personnes qui sont abonnées aux six profils! Donc, maintenant, vous devez déterminer qui nous considérons comme une ophtalmologie «enthousiaste». Nous avons décidé de prendre tout le monde, en commençant par trois abonnements. Comme on dit, 1 fois est un accident, 2 fois est une coïncidence, 3 est une régularité. Ainsi, 131 (2 + 3 + 24 + 102) utilisateurs «enthousiastes» ont été trouvés.

Étape 3. Téléchargez les abonnements de personnes «enthousiastes» et agrégez à nouveau de toutes les manières possibles.

Nous avons obtenu une liste impressionnante de comptes, à partir de laquelle nous allons maintenant sélectionner de nouveaux ophtalmologistes. La colonne de droite indique combien des 131 personnes sélectionnées lors de la deuxième étape sont abonnées au profil. En haut se trouvaient des profils de nos six originaux, ce qui n'est pas surprenant. Si nous sélectionnons maintenant le seuil et disons: «Tous les profils dont la valeur de comptage est supérieure à dix sont de nouveaux médecins», nous risquons d'attribuer des comptes populaires comme Olga Buzova à des ophtalmologistes tout en perdant des profils petits mais pertinents, alors ajoutez-en un de plus colonne le nombre d'abonnés et calculer le pourcentage d'utilisateurs enthousiastes parmi les abonnés.

Pour plus de commodité, la fraction est multipliée par 100 (donc la part est le pourcentage en fait). En conséquence, avec le nombre de conditions> = 6 et le partage> = 0,05, 166 nouveaux ophtalmologistes ont reçu. Classe!

Étape 4. 172 comptes sont devenus le nouveau «noyau» de la communauté, ce qui a permis de trouver environ 500 nouveaux ophtalmologistes, mais le résultat a déjà été déplacé vers des comptes étrangers.

Comptes similaires dans les recommandations Instagram

Bien sûr, tout cela est intéressant et maintenant nous savons comment trouver des comptes similaires, mais nous rêvons toujours de répartir tous les installateurs en catégories. Et puis l'idée m'est venue à l'esprit de regarder les recommandations instagram prêtes à l'emploi.

Le fait est que les comptes thématiques ont des recommandations, mais pas les gens ordinaires. Voici la réponse à la question de savoir qui considérer les blogueurs et moins un mal de tête. Hourra!

Dans les recommandations, un blogueur a jusqu'à 80 profils similaires. Nous avions une liste de 1000 blogs russes, nous avons commencé avec. Ils en ont pris des similaires, puis des similaires, puis ... eh bien, vous comprenez :)

Le plan était qu'un jour ce processus se termine, car les petits profils avec quelques centaines d'abonnés ne seront pas inclus dans les recommandations, mais en fait nous nous sommes arrêtés lorsque la patience a pris fin. Vous pouvez toujours continuer à collecter l'ensemble de données, mais jusqu'à présent, il n'a pas été utile, avec une forte probabilité que nous ayons couvert presque tous les blogueurs russes, et d'accord.

Nous avons maintenant un graphique avec 3 428 453 sommets (blogueurs) et 96 967 974 arêtes (similitude de deux blogueurs).

Voici à quoi ressemble notre graphique sur un très petit échantillon

Soit dit en passant, il s'est avéré que nous n'étions pas les premiers à choisir cette approche.

Apparemment, des recommandations sur Instagram sont formées en fonction des personnes qui suivent ce profil, donc un médecin de Bryansk aura des comptes Bryansk populaires et d'autres médecins dans les recommandations. Cela est similaire à notre recherche d'ophtalmologistes, mais maintenant nous pouvons prendre en compte toutes les communautés auxquelles appartient le blogueur en même temps. De plus, la vitesse de traitement augmente considérablement, car il n'est pas nécessaire d'analyser tous les abonnés du blogueur, il suffit de prendre seulement 80 comptes recommandés.

Sélection et description de l'algorithme

Super! Les données ont été préparées, nous devons maintenant choisir un outil et un algorithme qui peuvent faire face à un si grand graphique, de préférence en un temps suffisant. Permettez-moi de vous rappeler qu'à la sortie, nous voulons obtenir un ensemble de communautés où un blogueur peut appartenir à plusieurs d'entre elles.

Nous avons opté pour la bibliothèque Stanford Network Analysis Platform (SNAP)

La plate-forme d'analyse de réseau de Stanford (SNAP) est une bibliothèque d'analyse de réseau et d'exploration de graphiques à usage général. Il est écrit en C ++ et s'adapte facilement à des réseaux massifs avec des centaines de millions de nœuds et des milliards d'arêtes. Il manipule efficacement les grands graphiques, calcule les propriétés structurelles, génère des graphiques réguliers et aléatoires et prend en charge les attributs sur les nœuds et les bords.

Notre attention a été attirée par l'algorithme AGMfit (AGM - Affilated Graph Model), et finalement nous avons utilisé BIGCLAM (Cluster Affiliation Model for Big Networks). Ils ne diffèrent que par le fait que dans le premier cas, le problème d'optimisation est résolu de manière combinatoire, ce qui le rend moins évolutif, et le second vous permet simplement d'alimenter des graphiques comme le nôtre.

L'idée principale et plutôt intuitive: plus deux nœuds ont de communautés communes, plus la probabilité de communication entre ces deux nœuds est grande. Les deux algorithmes sont basés sur le modèle de graphique affilié, nous allons donc nous y attarder plus en détail:

Supposons que nous ayons un graphique bipartite dans lequel les pics ronds sont des communautés (

A

$A$ et

B

$B$ ), et carré - les utilisateurs du réseau social et chaque personne (

u

$u$ ) fait référence à différentes communautés avec des poids spécifiques (

F_{u A}

$F_ {uA}$ et

F_{u B}

$F_ {uB}$ ) Plus le poids est élevé, plus la probabilité que le participant soit connecté (familier) avec d'autres membres de la communauté est grande.

Exemple: des collègues qui ont étudié dans la même université se suivent sur Instagram. Tous deux sont diplômés de la même université (communauté 1) et travaillent dans la même entreprise (communauté 2), nous ne savons pas ce qui a causé «l'amitié» sur le réseau et quand ils se sont rencontrés. Laissez un diplômé de l'université et obtenir un emploi, et les seconds diplômés il y a cinq ans et ont travaillé dans l'entreprise pendant tout ce temps, alors le poids de l'appartenance à la première communauté 1 sera plus, et la communauté 2 moins et vice versa.

Pour chaque communauté commune de deux personnes, nous avons une chance indépendante de nous familiariser:

1 - e x p (- F_{u c} c d o t F_{v c})

$1 - exp (-F_ {uc} \ cdot F_ {vc})$

Ainsi, plus les communautés sont communes, plus elles sont susceptibles de se connaître:

1 - e x p (- s u m_{c} F_{u c} c d o t F_{v c})

$1 - exp (- \ sum_c F_ {uc} \ cdot F_ {vc})$

Si nous calculons la probabilité d'une connexion entre chaque paire d'utilisateurs, à la sortie, nous obtenons un graphique où les sommets sont des personnes et les bords entre eux sont un fait de connaissance ou d'abonnement les uns aux autres.

Ainsi, de la vue de gauche, nous sommes passés à l'image de droite.

Maintenant, comprenons comment ce modèle est utilisé dans la découverte de la communauté.

Nous avons un graphique de blogueurs similaires et notre objectif est de découvrir

K

$K$ communautés utilisant le modèle décrit ci-dessus, en sélectionnant la matrice de poids la plus appropriée

F

$F$ (sa dimension

N

$N$ nœuds sur

K

$K$ communautés) afin que le graphique obtenu en sortie soit similaire à notre graphique d'origine. Cela se fait en maximisant la fonction de vraisemblance.

l (F) = l o g P (G | F)

$l (F) = log P (G | F)$

Et pourtant, tout cela peut être représenté comme une décomposition matricielle non négative, ce qui donne juste un plus dans l'évolutivité de l'algorithme BIGCLAM par rapport à AGMfit.

En savoir plus ici et ici .

Numérotation et lancement de la communauté

Dans BIGCLAM, vous pouvez spécifier à la fois le nombre exact de communautés et l'intervalle. L'algorithme sélectionne 20% des paires de nœuds par test, et le modèle avec un nombre différent de communautés est ajusté de 80%.

Nous avons formé un fichier d'entrée avec une liste d'arêtes et exécuté:

./bigclam -o:bloggers -i:query_graph_all.edgelist -c:-1 -nc:20 -mc:50000 -xc:200000 -nt:10

Les paramètres vous permettent de spécifier le nombre de tentatives, le nombre minimum et maximum de communautés (ou exact, si nécessaire), le nombre de threads pour la parallélisation et le préfixe des fichiers de sortie. Dans notre cas, nous avons défini l'intervalle de 50 à 200 000 communautés avec 20 tentatives sur 10 threads. Toute cette splendeur a été comptée cinq jours sur 2 CPU Intel® Xeon® Gold 6150 à 2,70 GHz. La sortie a reçu deux fichiers, un pour Gephi, le deuxième texte, dans lequel chaque ligne est une communauté.

En fait, nous avons exécuté l'algorithme deux fois et, pour la première fois, nous avons atteint la limite supérieure de 50 000 communautés, le résultat n'était pas mauvais, mais des communautés mixtes se rencontraient souvent. Cette fois, nous avons de nouveau atteint la valeur maximale de 200 000 communautés, mais elles étaient bien meilleures, et nous nous sommes arrêtés à cela. Vous pourriez probablement obtenir le résultat encore mieux, mais deux cent mille communautés anonymes ont effrayé notre imagination.

Belle photo

Que faire maintenant avec tout ça?

D'une part, les communautés qui en résultent nous aident à rechercher rapidement des groupes étroits de blogueurs (comme chez les ophtalmologistes alors). S'il y a quelques blogueurs comme exemple, alors nous prenons toutes les communautés auxquelles ils appartiennent, jetons celles qui ne sont pas nécessaires et c'est tout. Vous pouvez utiliser une recherche par nom, par exemple, l'une des communautés sur la décoration et la décoration intérieure:

D'autre part, afin de déterminer les intérêts des utilisateurs, toutes ces communautés doivent être appelées d'une manière ou d'une autre de manière significative. Ou peut-être que tout n'est pas nécessaire.

CRank

Malheureusement, toutes les communautés reçues ne sont pas aussi bonnes, et pour trouver les plus intéressantes, nous avons décidé d'essayer d'utiliser la méthode de priorisation CRank de la même bibliothèque SNAP. Il est conçu pour correspondre automatiquement au rang de chaque communauté en fonction de la structure du graphique: plus la valeur est élevée, meilleure est la communauté.

À l'entrée du programme, nous soumettons les communautés que nous avons trouvées plus tôt, pour chacune d'entre elles, des mesures prioritaires sont calculées (4 pièces), puis ces mesures sont agrégées et nous obtenons une estimation.

Lisez plus ici .

Lancement

 ./crank -i:bloggers_cmtyvv.txt -c:query_graph_all.edgelist -o:bloggers_prioritization.txt

Lors du lancement, ils ont rencontré un problème de compatibilité avec Ubuntu 18.04, ils proposent ici une solution.

Étant donné que notre fichier de communauté bloggers_cmtyvv.txt et la liste des bords query_graph_all.edgelist contenaient initialement des surnoms (de type chaîne), nous avons dû les hacher pour qu'ils soient int, sinon jure.

Voyons comment cela fonctionne avec un exemple:

Nous allons sélectionner plusieurs communautés où il y a des profils qui contiennent la chaîne «lokomotiv» dans le nom, comme prévu, cela devrait être la communauté des fans de football du club Lokomotiv, et voyons ce que c'est vraiment. Les membres de la communauté sont marqués en rouge, sous chaque image il y a un score correspondant.

Communauté 1, score 0,4

Communauté 2, score 0,41

Communauté 3, score 0,34

Communauté 4, score 0,13

Ensuite, après avoir regardé tous les profils de ce sous-graphique, nous sélectionnons ceux qui appartiennent vraiment à la communauté souhaitée, il s'est avéré comme ceci:

Il s'avère que les deux premières communautés contiennent en fait ce dont nous avons besoin, presque sans erreurs (sauf pour le profil de l'équipe de football russe en Russie), la troisième communauté est bonne, mais couvre moins de comptes que les deux premières, donc le score est plus petit et le quatrième la communauté, bien qu'il s'agisse de récits sur un sujet footballistique (voici les joueurs des autres clubs, leurs épouses, et les managers), mais par, cela ne nous convient pas.
Nous pouvons conclure que CRank fonctionne assez bien.

Marquage manuel pour la coloration et les résultats.

Pour résoudre le problème de la coloration des utilisateurs par intérêts, nous analysons également les textes des articles et nous voulions voir où le résultat est meilleur / plus intéressant (dans les textes ou dans les abonnements) et s'il y a des correspondances. Pour un petit échantillon de personnes, environ 800 communautés ont dû être étiquetées indépendamment. Nous étions plus que satisfaits du résultat et avons décidé de développer cette approche. La méthode de détection communautaire vous permet de trouver des catégories d'intérêt très étroites et inhabituelles, par exemple, en vous abonnant à des profils de rats (dans le sens de petits rongeurs gris) et d'autres choses étonnantes, vous pouvez découvrir quel type de sport une personne est censée intéresser, et ne pas tout pousser dans la catégorie «extrême» et ainsi de suite

Nous ne marquerons probablement pas les 200 000 communautés, mais peut-être allons-nous jouer avec les résultats de CRank et ne laisser que les communautés à grande vitesse, et peut-être les marquerons-nous comme nécessaires. De telles choses :)

Je vous remercie!

Cet article a été écrit conjointement avec mon superviseur Artyom Korolev ( korolevart ) R&D Dentsu Aegis Network Russia

Source