Upload
cecile-bothorel
View
7.023
Download
2
Embed Size (px)
DESCRIPTION
Les concepts de base de l'analyse de réseaux, réseaux sociaux réels, problématiques de l'analyse de grands graphes réels, pistes d'application au emarketing
Citation preview
18/01/10
Analyse de réseaux sociaux
Tour d’horizon
Pistes d’application pour le eMarketing
Cécile Bothorel, Département LUSSI
Cécile Bothorelpage 2 Département LUSSI
Quel point commun ?
Réseau physique d'Internet Graphe du Web qui modélise la structure
hypertextuelle du Web Réseaux sociaux en ligne Graphe de contact en épidémiologie Graphes d'échange en économie Graphe d'interactions protéines Réseaux sémantiques Réseau de co-auteurs Réseau de co-utilisation de tags
Cécile Bothorelpage 3 Département LUSSI
Quel point commun ?
http://complexnetworks.fr/
Cécile Bothorelpage 4 Département LUSSI
Graphes réels
Graphes réels, grands graphes terrain, complex networks
Propriétés structurelles communes
• faible densité en arcs,
• en moyenne des chemins courts (effet petit monde),
• existence de zones denses en arcs,
• incidence des sommets en loi de puissance. Structure de graphe rare d’un point de vue
probabiliste → un domaine de recherche jeune
→puise ses concepts dans l'analyse de réseaux sociaux
18/01/10
Analyse de réseaux sociaux
Généralités
Cécile Bothorelpage 6 Département LUSSI
Qu’est-ce qu’un réseau social ?
Point de vue utilisateur Point de vue analyste
Cécile Bothorelpage 7 Département LUSSI
Qu’est-ce qu’un réseau social ?
Entités sociales
• individus, • organisations…
Liens créés lors d’interactions sociales• relation d’amitié,• partenariat,• communication, • intérêt commun,• transmission de
maladie…
Cécile Bothorelpage 8 Département LUSSI
Analyse de réseaux sociaux
Décrire une population • non par les traits qui marquent ses membres (age, sexe,
revenu, niveau d'étude, etc.)
• mais par les relations entre eux Comprendre et interpréter la structure et le
comportement d’un réseau
Structure du point de vue performancePosition opportunités
Émergence de communautés
Cécile Bothorelpage 9 Département LUSSI
Comprendre un réseau
Cécile Bothorelpage 10 Département LUSSI
Analyse de réseaux sociaux
L’analyse des réseaux sociaux n’est pas une discipline nouvelle• 1933 : sociogramme de Jacob Levy Moreno
pour objectiver la dynamique du groupe
• 1954 : John A. Barnes introduit le terme « réseau social »
• 1967 : Stanley Milgram : effet du « petit monde », six degrés de séparation
• 1973 : Mark L. Granovetter : la force des contacts faibles
• 1998 : PageRank de Google : mesure de pertinence dans l’ordonnancement des réponses aux requêtes
http://fr.wikipedia.org/wiki/Fichier:Six_degrees_of_separation.png
Cécile Bothorelpage 11 Département LUSSI
Analyse de réseaux sociaux
Une multitude de représentations• Différents types de relations
- Relation directionnelle ou non (flux d’information)- Relation pondérée ou non (fréquence des interactions)- Relation unique ou multiple
• Différents types d’entités- Un seul type d’entités pour décrire un réseau d’amis, ou un réseau de blogs
ou de pages webs- Deux types d’entités pour décrire des relations médiatées : auteurs – articles,
acteurs - films
Cécile Bothorelpage 12 Département LUSSI
Analyse de réseaux sociaux
Des concepts de bases simples- Degré - Chemins (intermédiaires pour relier
deux nœuds, sans répéter les nœuds)- Longueur (nombre de liens séparant
deux nœuds)- Distance (longueur du plus court
chemin) = « distance géodésique »- Composantes (ensemble de nœuds
où chacun peut atteindre chacun des autres)
- Pont / cutpoint- Clique / quasi-clique- …
18/01/10
Analyse de réseaux sociaux
(1) Analyse de l’ensemble du réseau
(2) Analyse de positions
(3) Analyse de sous-groupes
18/01/10
Analyse de réseaux sociaux
(1) Analyse de l’ensemble du réseau
(2) Analyse de positions
(3) Analyse de sous-groupes
Cécile Bothorelpage 15 Département LUSSI
(1) Analyse de l’ensemble du réseau
Formes connues de graphes• Graphe aléatoire (Erdös et Rényi, 1959)• Scale-free : attachement préférentiel (A.-L. Barabasi & R.
Albert, 1999)• Réseau hiérarchique : scale-free dans les clusters (A.-L.
Barabasi et al., 2002)
• Petit-monde (D. Watts and S. Strogatz, 1998)
Barabasi & Oltvai, vol.5, p101 (february 2004)
Cécile Bothorelpage 16 Département LUSSI
(1) Analyse de l’ensemble du réseau
Graphe aléatoire (Erdös et Rényi, 1959)
• N = 10 et p = 0.2. Le réseau croît de façon homogène (pN (N-1)/2 liens)
• La plupart des noeuds ont le même degré (proche de la moyenne)
• Petit monde
Cécile Bothorelpage 17 Département LUSSI
(1) Analyse de l’ensemble du réseau
Scale-free : attachement préférentiel (A.-L. Barabasi & R. Albert, 1999)
• Modèle largement utilisé, trop ?
• Décrit une dynamique et une structure
Cécile Bothorelpage 18 Département LUSSI
(1) Analyse de l’ensemble du réseau
Scale-free : attachement préférentiel (A.-L. Barabasi & R. Albert, 1999)• La distribution des degrés en loi de puissance
• Présence de hubs rouges qui ont attiré un grand nombre de voisins verts
Cécile Bothorelpage 19 Département LUSSI
(1) Analyse de l’ensemble du réseau
• Réseau hiérarchique : scale-free dans les clusters (A.-L. Barabasi et al., 2002)
• Petit-monde : petit diamètre de l'ordre de log(N) et fort coefficient de clustering (D. Watts and S. Strogatz, 1998)
Barabasi & Oltvai, vol.5, p101 (february 2004)
Cécile Bothorelpage 20 Département LUSSI
(1) Analyse de l’ensemble du réseau
Comprendre la structure globale• Taille• Distance moyenne, diamètre• Connectivité, densité des
relations • Distribution des degrés, la
variance des degrés• Transitivité – coefficient de
clustering• La centralité du graphe Réseau très central qui peut
« tourner » autour d’un nœud. Si ce nœud disparaît…
Cécile Bothorelpage 21 Département LUSSI
(1) Analyse de l’ensemble du réseau
Comprendre la structure globale• Core/periphery• Cliques : nombre, taille des
cliques
18/01/10
Analyse de réseaux sociaux
(1) Analyse de l’ensemble du réseau
(2) Analyse de positions
(3) Analyse de sous-groupes
Cécile Bothorelpage 23 Département LUSSI
(2) Analyse de positions
Cécile Bothorelpage 24 Département LUSSI
(2) Analyse de positions
Positions clés, rôles
• Localement exemple : fort degré – beaucoup de voisins
immédiats
• Globalementexemple : PageRank : être connecté à des
nœuds importants me donne plus d’importance que d’être connecté à des nœuds peu importants
prestigieux
influent
pertinence
Cécile Bothorelpage 25 Département LUSSI
(2) Analyse de positions
Closeness centrality est l’inverse de la somme des distances entre ce nœud et chacun des autres
Betweenness centrality est le nombre de fois qu’un nœud se trouve sur le plus court chemin entre deux autres noeuds
1 0.73310 0.42311 0.42312 0.4232 0.4783 0.4784 0.4785 0.4786 0.4787 0.6118 0.6889 0.423
1 0.47310 0.00011 0.00012 0.0002 0.0093 0.0094 0.0095 0.0096 0.0097 0.1008 0.6189 0.000
Accès rapide à l’information d’où qu’elle parte
Médiateur
Cécile Bothorelpage 26 Département LUSSI
(2) Analyse de positions
Centralité(s)• Basée sur les calculs de plus courts chemins
- Degree centrality (popularité, comportement grégaire)
- Betweenness centrality (médiateur ou goulot d’étranglement)
- Closeness centrality (proximité, sera informé plus rapidement)
- Flow betweenness (contribution à augmenter le flot)
• Basée sur les marches (on peut repasser par un nœud ou un lien plusieurs fois)- Bonacich power = eigenvector centrality (version itérative
de la centralité de degré) (importance, haut-risque d’infection)
- Katz, Hubbel (influence, « qui a entendu ce qu’il a dit ? »)
Liste de calculs disponibles dans l’outil UCINET
PageRank(être pointé par des sites importants rendimportant)
Cécile Bothorelpage 27 Département LUSSI
(2) Analyse de positions
Liens faibles• Lien hors « triangle »• Liens d’ouverture qui donnent accès
à une variété d’information -> force des liens faibles (Granovetter, 1973)
• Exemple : 4 clusters (liens rouges) interconnectés par des liens faibles (gris)
– Plusieurs « hubs » ont tendance à se connecter : maximiser les échanges d’information
– Certains liens faibles vont donc se retrouver au centre de communautés plus large
– Pourtant certains liens faibles doivent rester faibles : ponts inter communautés, ils apportent de l’innovation
Cécile Bothorelpage 28 Département LUSSI
(2) Analyse de positions
• Trous structuraux- Mesure la redondance des ego-networks (les « triangles »
incluant ego) (Burt, 1992) - Séparation entre deux contacts non redondants- Zones peu denses confèrent du pouvoir au centre- Proche de la betwenness et de la densité des ego-network
• Equivalence structurelle- Nœuds de même voisinage, même centralité…
• Equivalence Régulière- Les voisinages sont eux-même équivalents, assurent le
même rôle- Comme deux médecins, deux chefs d’équipe.
• …
Cécile Bothorelpage 29 Département LUSSI
(2) Analyse de positions
Et puis de nouvelles métriques inventées tous les jours• Calcul d'influence dans twitter : RetweetRank• Détection de spam : SpamRank• Calculs de confiance : TrustRank, TidalTrust• Calculs de similarités : SimRank• ...
18/01/10
Analyse de réseaux sociaux
(1) Analyse de l’ensemble du réseau
(2) Analyse de positions
(3) Analyse de sous-groupes
Cécile Bothorelpage 31 Département LUSSI
(3) Analyse de sous-groupes
La délimitation en groupes n'est pas un a priori • On ne cherche pas qui appartient à une famille,
communauté ethnique ...
• Mettre en évidence une catégorie émergente, basée sur l'analyse de la topologie
En pratique, existence de zones denses
Cécile Bothorelpage 32 Département LUSSI
(3) Analyse de sous-groupes
Recherche de groupes• Cliques (ou 1-cliques), k-
cliques : ensemble max de nœuds tous reliés à une distance k.
• K-plex (ensemble de n nœuds où chacun a un lien avec au moins n-k nœuds)
Clique et 2-clique
2-plex
Cécile Bothorelpage 33 Département LUSSI
(3) Analyse de sous-groupes
Karate Club in an AmericanUniversity [Zachary 1977]
Détection de communautés• Formes plus lâches• Gros volumes de données• Thématique connaît un
renouveau avec l'étude de grands graphes réels
Cécile Bothorelpage 34 Département LUSSI
(3) Analyse de sous-groupes
Quatre types d’approches (thèse P. Pons, 2007)• Classiques• Séparatives• Agglomératives• Marches aléatoires
P. Pons, 2007
Trouver la partitionP = {C1, . . . , Ck} qui optimise la
fonction de qualité Q(P)
Cécile Bothorelpage 35 Département LUSSI
(3) Analyse de sous-groupes
Approches classiques• Partitionnement de graphe en k groupes
- Bissection spectrale (Spectral clustering) – théoriquement solide, basée sur le calcul de vecteur propre– Très coûteuse
- Méthode de Kernighan et Lin– Bissection en utilisant la coupe minimisant le nombre d’arêtes tombant
entre deux coupes
• Clustering hiérarchique- Mesure de similarité entre communauté (distance min, max ou
moyenne, ou des membres au centroïd de l’autre communauté)- Partant avec n communautés, méthode itérative où l’on fusionne des
communautés les plus proches- ou kmeans si on peut fixer k
Cécile Bothorelpage 36 Département LUSSI
(3) Analyse de sous-groupes
Approches séparatives• On part d’une communauté unique puis à chaque étape, on
retire une relation provoquant un découpage en sous-communautés- Relation la plus centrale par exemple (Girwan et Newman, 2002)
• Critère d’évalutation de la division en communautés- La modularité Q cherche à produire un découpage où le nombre
d’arêtes reliant les groupes est plus petit que le nombre « attendu », i.e. si on avait découpé aléatoirement.
Cécile Bothorelpage 37 Département LUSSI
(3) Analyse de sous-groupes
Approches agglomératives• On part de n communautés composées d’un seul nœud• Itérativement, on regroupe les nœuds en communautés, puis
les communautés entre elles, jusqu’à obtenir une seule communauté.
• Critère d’évalutation de la division en communautés- La modularité Q cherche à produire un découpage où le nombre
d’arêtes reliant les groupes est plus petit que le nombre « attendu », i.e. si on avait découpé aléatoirement.
Cécile Bothorelpage 38 Département LUSSI
(3) Analyse de sous-groupes
Computing Communities in Large Networks Using Random WalksPascal Pons and Matthieu Latapy, Journal of Graph Algorithms and Applicationshttp://jgaa.info/ vol. 10, no. 2, pp. 191–218 (2006)
Marches aléatoires • Intuition : les marcheurs
vont se faire piéger dans des zones denses
• Un marcheur va avoir tendance à rester dans sa communauté si marche courte
• Distance : deux marcheurs proches vont voir le même voisinage
• Clustering hiérarchique par fusions successives de communautés
18/01/10
Analyse de réseaux sociaux
Cas d’application : le eMarketing
Cécile Bothorel, Laboratoire LUSSI
Cécile Bothorelpage 40 Département LUSSI
Buzz
du Buzz au Marketing viral
Cécile Bothorelpage 41 Département LUSSI
Examples de Buzz positif (1)
2006. L’association des deux produits aurait provoqué la mort d’un jeune brésilien.
Documents powerpoint circulent par email.
Coca Cola s’est montré assez distant au départ vis à vis de l’affaire tandis que Mentos l’a pleinement exploité.
Mentos : économie d’au moins dix millions en pub et +15% de ventes.
Coca Cola : doublé son trafic webFritz Grobe & Stephen Voltzhttp://eepybird.com/history.html
Effet geyser de l'association Mentos et Coca cola light
Cécile Bothorelpage 42 Département LUSSI
Examples de Buzz positif (2)
Lu sur http://www.mediassociaux.com/
Vidéos virales 2009 Evian : 55 millions de vues
certifiées par Visible Measures T-mobile : opération « Live for
Sharing » pour le lancement du téléphone G1 (Google Phone) en Grande Bretagne ? un vrai événement terrain
Samsung : « Sheep LED Art ». Volkswagen : « FunTheory »
Cécile Bothorelpage 43 Département LUSSI
Examples de buzz négatif (1)
Kryptonite et ses cadenas que l'on ouvre avec un stylo Bic
• Un simple post sur un forum spécialisé en 2004, une vidéo et 3 jours après, plus d'un million d'internautes étaient au courant
• coût estimé pour la société : 10 millions de $ John Mac Cain malmené sur YouTube pendant la
campagne présidentielle en 2008
• Vidéo « John McCain vs John McCain » montrant des incohérences de discours à propos de l'Irak, de la religion, des mariages gays
• Vidéo toujours commentée depuis le 26/01/07
http://intelligenceeconomiquealgerie.blogspot.com/2010/01/e-reputation-12-cas-significatifs.htmlLu le 5 janv 2010
Cécile Bothorelpage 44 Département LUSSI
Examples de buzz négatif (2)
Les 3 suisses et la TV bradée (90% de réduction) a emflammé le web • Groupes FB• « google bombing » : la marque sort en tête à la
requête « inadmissible incompétence »• Résultat obtenu grâce à (à cause ) d'une dizaine de
bloggueurs Dominos Pizza réagit efficacement
• « garniture très spéciale» de pizzas en vidéo. • Excuses publiques, compte Twitter Corporate
http://intelligenceeconomiquealgerie.blogspot.com/2010/01/e-reputation-12-cas-significatifs.htmlLu le 5 janv 2010
Cécile Bothorelpage 45 Département LUSSI
Buzz
Bad buzz ou Stratégie bien ficelée ?
Tentant mais • difficilement maîtrisable car
fonctionne par bouche à oreille, le message peut être déformé
• durée de vie limitée, un buzz en chasse un autre
Les recettes pour faire du bu$$ : un marché à part entière
Cécile Bothorelpage 46 Département LUSSI
Marketing viral
A la différence du buzz, il s’agit d’une vraie campagne marketing
Un vrai message Particularité, ce sont les
clients qui véhiculent ce message
Actuellement, beaucoup de marques « utilisent » les médias sociaux
Cécile Bothorelpage 47 Département LUSSI
Réseaux sociaux et Marketing viral
Viadeo, le réseau social, vient de conclure un partenariat avec Hotel Reservation Service (HRS)
• HRS : nouveaux clients par “recommandation”, sans campagne publicitaire, en faisant juste un effort financier sur le prix des hôtels
• Viadeo vend des abonnements, fidélise ses membres, qui vont attirer leurs relations…
Mais aussi partenariat avec
• Msn Messenger,
• Club IGR (association des diplômés de l’IAE de Rennes),
• Partenariat avec l'Apec démarre en janv. 2010 : communauté Apec, consultation du profil viadéo des candidats par les recruteurs
• ...
Cécile Bothorelpage 48 Département LUSSI
Facebook met en avant des marques
Réseaux sociaux et Marketing viral
La marque vous invite à parrainer le message, à commenter et à propager.
Cécile Bothorelpage 49 Département LUSSI
Réseaux sociaux et eMarketing
Enjeu : Maîtriser le Bouche à oreille Comprendre la structure des sites communautaires,
mais également des réseaux de sites
Comment choisir le blogguer qui pourra mieux parler d'un produit/service ?
Par quel utilisateur twitter se faire suivre ?A quels clients proposer un produit en beta-test ?
Cécile Bothorelpage 50 Département LUSSI
Réseaux sociaux et eMarketing
Analyse de réseaux sociaux• Déterminer les individus par qui la compagne doit
démarrer/passer- Les leaders d’opinions (calcul de popularité – centralité de degré,
pageRank)- Les médiateurs (calcul de centralité « stress », « betwenness ») : les
acteurs qui contrôlent la propagation de l’information en tant que passages obligés
- Les points de référence (calcul de centralité « closeness ») : individus les plus proches de tous
Cécile Bothorelpage 51 Département LUSSI
Réseaux sociaux et eMarketing
Analyse de réseaux sociaux• Prédire la vitesse, la couverture de la diffusion
- Calcul de plus courts chemins, de flots maximum- Une rumeur sera plus efficace si elle provient de plusieurs sources
différentes
• Social contagion- Simulation sociale- Outils Repast, NetLogo...
Démo
Cécile Bothorelpage 52 Département LUSSI
Réseaux sociaux et eMarketing
Avec une analyse sémantique, on peut délimiter des communautés thématiques• Cibler les campagnes• Détecter les tendances• Les membres situés à la périphérie des communautés
peuvent servir de passerelle inter-communautés
Cécile Bothorelpage 53 Département LUSSI
Réseaux sociaux et eMarketing
Mais ... • Collecte des données pour faire
l'analyse du réseau...
• Peut-on intervenir sur la structure pour la rendre plus efficace ?
• Comprendre, modéliser le réseau de confiance/opinions : un calcul de force des liens ? Un TrustRank ?
Networks, Crowds, and Markets: Reasoning About a Highly Connected World By David Easley and Jon Kleinberg, à paraître en 2010
Cécile Bothorelpage 54 Département LUSSI
Réseaux sociaux et eMarketing
Et puis surtout• Créer un vrai contenu, en faciliter la réplication
• Surprendre• Mobiliser un réseau social, valoriser les clients qui se
prêtent au jeu. Le client est ROI...• Mesure de succès ?
18/01/10
Analyse de réseaux sociaux
Conclusion
Cécile Bothorel, Laboratoire LUSSI
Cécile Bothorelpage 56 Département LUSSI
Domaines d’application
Marketing … mais aussi : Recherche d’information
• Ordonnancement des résultats d’une requête, désambiguïsation linguistique, nuage de tags contextuels à une requête…
Recommandation • Prédiction d’opinion pour le cinéma, musique…
Terrorisme • Acteurs clés dans un réseau d’interaction
Médecine – épidémiologie• Prédiction de contamination
Transport, Biologie…
Cécile Bothorelpage 57 Département LUSSI
Les travaux actuels
Actuellement • On sait analyser
finement des petits graphes (quelques centaines de nœuds)
• Des données TIC maintenant accessibles et volumineuses
→ Grands graphes réels
Cécile Bothorelpage 58 Département LUSSI
Les travaux actuels
Grands graphes réels • On sait décrire globalement et statiquement ces graphes
- difficulté à décrire la dynamique, travaux sur la prédiction de liens- difficulté de calculer les métriques riches issues de l'analyse des réseaux
sociaux
• On commence à faire des approximations des mesures pour des très grands graphes simples- Exemple : approximation de la distance moyenne ou le diamètre
• Algorithmique empirique- Revisite les algorithmes pour les graphes « réels » pour tirer partie des
propriétés observées- Problèmes spécifiques à des jeux de données : exemple hypergraphes
pour les folksonomies
Cécile Bothorelpage 59 Département LUSSI
Les travaux actuels
Problèmes• comment collecter des données fidèles ? Vues partielles en pratique
• comment les modéliser pour ne pas perdre trop d’information ?
• comment analyser/prédire la dynamique ? - Au sens flux (probabilité d’être touché par une maladie ?)- Au sens structure (formation, fusion, dissolution de communautés)
• comment visualiser les grands réseaux ?
• comment savoir si les communautés découvertes sont pertinentes ? comparer les résultats de méthodes différentes ?
Vers une théorie de la complexité• des propriétés statiques communes mises en évidence
• trouver des caractéristiques communes de la dynamique des systèmes complexes (Barabasi, www.sciencemag.org, Science, Vol 325, 24 july 2009)
Cécile Bothorelpage 60 Département LUSSI
Merci http://www.slideshare.net/cecile_b/analyse-de-rseaux-sociaux-rels