Inférence de liens signés dans les réseaux sociaux, par apprentissage à partir d’interactions utilisateur

L’étude du comportement des individus à travers l’analyse de leur façon de penser et de leur façon d’agir a toujours suscitée un fort intérêt, et ce, bien avant l’arrivée des premiers réseaux sociaux sur internet. Aujourd’hui, la tâche se démocratise car les utilisateurs sont de plus en plus liés entre eux via de multiples plate-formes. Les réseaux se densifient et la diversité des données augmente également : contenus personnels (Facebook, Google+) ou professionnels (LinkedIn, Viadeo), partage de vidéos en ligne (Youtube), avis divers sur les produits issus de ventes en ligne (Amazon, Epinions) ou encore des plate-formes de vidéos ou de musique à la demande (Netflix, Deezer). La popularité des usages sur le web ouvre donc la porte à de nombreuses nouvelles tâches, car il devient possible de collecter facilement de grosses quantités de données sur les relations entre les utilisateurs. Le traitement et l’analyse de ces données requièrent des outils sophistiqués ; on utilise souvent la théorie des graphes, particulièrement adaptée aux données structurées sous forme de réseau. Les utilisateurs, les items ou les contenus sont représentés par des noeuds et ces noeuds sont reliés par des liens qui peuvent alors prendre diverses formes selon leur définition (simples, orientés, valués).

L’augmentation de la quantité de données disponibles et leur diversification permettent une meilleure analyse des utilisateurs, car chaque contenu apporte un renseignement. Malheureusement, cette quantité phénoménale d’informations devient parfois complexe à manipuler, aussi bien du point de vue technique que du point de vue de l’utilisateur. Celui-ci rencontre de plus en plus de difficultés à s’orienter, noyé dans l’abondance des choix qui lui sont offerts. C’est un réel paradoxe puisque le nombre grandissant de possibilités offertes et la richesse des contenus a l’effet inverse de ce qui est attendu : les utilisateurs ont de moins en moins de chance de trouver ce qu’ils recherchent. Alors que les utilisateurs peuvent facilement passer d’un service à un autre, satisfaire et fidéliser devient un véritable enjeu pour n’importe quel service en ligne qui doit maintenir (et augmenter) le trafic nécessaire à son succès, voire sa survie

Face à ce constat, de nombreuses tâches ont émergé, parmi lesquelles la recommandation dont l’objectif est d’identifier les items les plus susceptibles de plaire aux utilisateurs, la prédiction de liens (entre utilisateurs) ou encore la détection de communautés. De nombreux graphes contiennent implicitement ou explicitement des relations antagonistes (signées). Dans ce manuscrit, nous nous intéressons à leur sémantique. Nous proposons des mesures de similarité qui prennent en compte la polarité des jugements que les utilisateurs partagent à propos d’items et validons expérimentalement ce type d’approche en nous appuyant sur deux tâches : la recommandation et la prédiction de liens.

La problématique des relations signées 

Généralement, nous distinguons deux formes de liens entre les utilisateurs : les liens explicites ou les liens implicites. Les liens sont explicites lorsque les utilisateurs sont reliés au sein d’un même réseau social, ils sont implicites lorsque les utilisateurs partagent les mêmes groupes ou ont évalué un même item par exemple. Ces liens sont exploités pour tirer profit de l’homophilie et la régularité stipulant que les individus connectés entre eux partagent les mêmes caractéristiques de profil (âge, profession, hobbies) et tendent à appartenir aux mêmes communautés d’intérêt. Ainsi, ces liens sont exploités pour leur connotation positive (amitié, collaboration, partage). Pourtant, beaucoup de relations sociales opposent souvent deux forces antagonistes (ami/ennemi ou confiance/méfiance) et nous observons régulièrement des tensions entre les utilisateurs, résultats de controverses ou encore de désaccords. Dans le domaine du web, l’analyse des liens signés en est à ses débuts et peu de réseaux contiennent des relations de défiance. Pourtant, l’information qu’apportent les liens négatifs s’avère bien utile pour de nombreuses tâches [Kunegis et al., 2013] car ils viennent compléter l’information des liens positifs. Quelques travaux s’en sont servi pour améliorer une tâche de prédiction de liens classiques [Kunegis and Lommatzsch, 2009, Leskovec et al., 2010a] où les liens négatifs permettent une augmentation du nombre de bonnes prédictions de l’ordre de 5%. D’autres travaux s’en sont servi pour affiner des modèles de recommandation [Ma et al., 2009, Yang et al., 2012] permettant un gain du même ordre (5% en prédiction de notes).

Les sources de liens négatifs 

Les liens signés peuvent être collectés soit lorsqu’ils sont explicités par les utilisateurs, soit via les relations indirectes qui peuvent exister entre eux. Les liens signés explicites entre les utilisateurs sont les moins faciles à collecter. Notre hypothèse est que les utilisateurs (comme les fournisseurs de services) considèrent ces liens intrusifs et inconvenants. En effet, un lien négatif envers un autre utilisateur peut être perçu comme une agression, ce que les plate-formes en ligne cherchent déjà à combattre. Autoriser les relations hostiles représente donc un risque, d’autant plus que les utilisateurs ne perçoivent souvent même pas l’intérêt de les expliciter puisque cela ne permet pas d’améliorer leur profil contrairement aux liens positifs. Pour pallier l’absence de liens signés explicites, il est possible d’exploiter des sources issues d’interactions indirectes entre les utilisateurs. Il s’agit par exemple d’un utilisateur qui va juger le contenu d’un autre utilisateur lorsque ce dernier a exprimé un avis à propos d’un item (à l’instar des sites de ventes en ligne). En pratique, ces liens sont plus faciles à collecter, notamment parce que les utilisateurs s’adressent avant tout au contenu et les avis négatifs sont alors perçus comme tel ; les autres utilisateurs ne perçoivent pas cela comme une provocation.

Analyse de graphes sociaux signés 

Les liens signés soulèvent des difficultés si on veut les exploiter pour des tâches classiques d’accès à l’information ; d’une part parce que les règles de transitivité du type l’ami de mon ami est mon ami ne fonctionnent plus, d’autre part car le signe (et souvent l’orientation) des liens rend caduc une partie de l’arsenal mathématique à notre disposition. Les premiers travaux traitant le sujet des liens signés, à la frontière entre la sociologie et la théorie des graphes, ont avant tout porté sur leur sémantique [Harary, 1953, Davis, 1977]. Ces travaux ont permis d’étudier la manière dont interagissent les liens signés pour lesquels la simple transitivité ne peut être utilisée. De cette problématique est née la théorie de l’équilibre, stipulant que le produit du signe des trois liens d’une triade doit être positif (par exemple l’ennemi de mon ami est mon ennemi). Toutefois, cette théorie ne traite que le cas des liens réciproques entre utilisateurs, ce qui l’exclut de la majorité des graphes de terrain actuels. Les graphes de terrain ont été étudié bien plus tard, lorsque les premières plate-formes en ligne ont proposé ce type de relation. Les liens y sont plus systématiquement orientés et la sémantique est alors différente. Les premiers travaux [Guha et al., 2004, Kunegis and Lommatzsch, 2009,Kunegis et al., 2010,Kunegis et al., 2009,Kerchove and Dooren, 2008] ont étendu des méthodes existantes à base de marches aléatoires afin de prédire le signe des liens entre les utilisateurs, alors même que ces méthodes reposent sur une théorie qui n’est pas adaptée au cas des liens négatifs (la convergence des modèles n’est plus garantie). D’autres travaux [Leskovec et al., 2010a,Leskovec et al., 2010b] se sont intéressés à la sémantique de ces liens négatifs orientés qui peut être interprétée comme une relation d’ordre : c’est la théorie du statut. Ces auteurs ont alors proposé d’inférer le signe des relations en utilisant un classifieur basé sur des caractéristiques de voisinage, prenant en compte ces relations d’ordre.

Les tâches abordées 

Les systèmes de recommandation 

Les systèmes de recommandation trouvent de plus en plus leur place dans les services qui proposent de nombreux items à leurs utilisateurs (films, musiques, etc.) ; ils permettent de suggérer aux utilisateurs quels items ont le potentiel de les intéresser – qu’il s’agisse de musique, de films ou de n’importe quel produit proposé par des sites de streaming ou ecommerce. L’explosion du contenu disponible est telle que les systèmes de recommandation sont aujourd’hui indispensables pour garantir le succès d’une plate-forme en ligne. Dans le domaine académique, c’est en particulier grâce au challenge Netflix [Bennett and Lanning, 2007] que ces systèmes ont été popularisés. Il existe deux principales familles de systèmes de recommandation [Bobadilla et al., 2013] : les systèmes de filtrage par contenu et les systèmes de filtrage collaboratif. Les systèmes de filtrage par contenu se basent sur la construction de profils explicites pour les items, basés sur leur contenu textuel (synopsis d’un film, résumé d’un livre) ainsi que sur les méta-données éventuellement à disposition comme par exemple le genre ou encore les noms des auteurs. L’idée est alors de recommander aux utilisateurs les items similaires à ceux qu’ils ont déjà évalués [Balabanović and Shoham, 1997]. Les systèmes de filtrage collaboratif construisent un profil par utilisateur et un profil par item en se basant sur l’historique des notes, de manière à recommander les mêmes items aux utilisateurs dont le comportement est similaire [Schafer et al., 2007, Koren et al., 2009]. Le filtrage collaboratif donne d’excellents résultats lorsqu’il peut exploiter une très grande quantité de données [Dror et al., 2012] ou encore tirer profit du voisinage explicite [Crandall et al., 2008] ou de toute mesure de similarité calculée à l’aide de l’historique des notes comme l’indice de Pearson ou le cosinus [Bellogín, 2013].

Table des matières

Introduction générale
Partie I État de l’art
Chapitre 1 Les systèmes de recommandation
Introduction
1.1 Les familles de méthodes
1.1.1 Filtrage collaboratif
1.1.2 Recommandation basée sur le contenu
1.2 Les modèles à facteurs latents pour le filtrage collaboratif
1.2.1 Techniques de factorisation matricielle
1.2.2 Exploitation d’informations supplémentaires
1.3 L’évaluation
1.3.1 Tâches et mesures
Conclusion
Chapitre 2 L’analyse des réseaux sociaux
Introduction
2.1 Définitions, notations et exemples de graphes de terrain
2.1.1 Graphes simples non orientés
2.1.2 Graphes simples orientés
2.1.3 Graphes pondérés orientés
2.2 Les grandes tâches de l’analyse des réseaux sociaux
2.2.1 Détection de communautés
2.2.2 Classification de nœuds
2.2.3 Prédiction de liens
2.3 Le cas non signé
2.3.1 Critères de qualité pour le détection de communautés
2.3.2 Méthodes semi-supervisées : proximité et propagation des étiquettes
2.3.3 Méthodes supervisées : modèles à base de caractéristiques
2.4 Le cas signé
2.4.1 Données difficiles à collecter
2.4.2 Deux théories pour l’interprétation des liens signés
2.4.3 Tâches étudiées dans le contexte signé
Conclusion
Partie II Contributions
Chapitre 3 Analyse de la sémantique des jugements communs dans le filtrage collaboratif
Introduction
3.1 L’intuition
3.2 Le modèle
3.2.1 Représentation latente et voisinage
3.2.2 Modèles
3.3 Les expériences
3.3.1 Jeux de données
3.3.2 Algorithme d’apprentissage
3.3.3 Calcul du graphe de similarité
3.4 Les résultats
3.4.1 Évaluation qualitative
3.4.2 Évaluation quantitative
Conclusion
Chapitre 4 Modèles utilisateur pour l’analyse de la sémantique des jugements communs
Introduction
4.1 L’intuition
4.1.1 Probabilité d’occurrence et son impact sur la sémantique d’un jugement
4.2 La surprise positive et la surprise négative
4.2.1 Calcul du score
4.2.2 Modèle 1 : Popularité item (Spo)
4.2.3 Modèle 2 : Preuve sociale (Sso)
4.2.4 Modèle 3 : Principe de cohérence (Sco)
4.2.5 Modèle 4 : Permutation aléatoire (Spa)
4.3 Les expériences
4.3.1 Mesure de la similarité
4.3.2 Sélection des voisins
4.3.3 Comparaison des approches
4.3.4 Résultats
Conclusion
Chapitre 5 Prédiction de liens signés à partir des seuls jugements utilisateur
Introduction
5.1 La prédiction de liens signés
5.1.1 Sources d’informations signée
5.2 Le modèle de prédiction
5.2.1 Caractéristiques sociales
5.2.2 Caractéristiques basées sur les interactions indirectes
5.2.3 Caractéristiques basées sur les jugements communs
5.3 L’évaluation
5.4 Les expériences
5.4.1 Performance avec des liens signés explicites (cas n˚1)
5.4.2 Performance sans liens signés mais avec interactions indirectes (cas n˚2) .
5.4.3 Performance avec uniquement les jugements communs (cas n˚3)
5.4.4 Étude de l’importance des caractéristiques
Conclusion
Partie III Conclusion

Télécharger le rapport complet