Diffusion de l'information dans les médias sociaux : modélisation et analyse

Laboratoire ERIC

Université Lumière Lyon 2

Diffusion de l’information

dans les médias sociaux

Modélisation et analyse

Thèse de doctorat présentée et soutenue publiquement

par Adrien Guille

le 25 novembre 2014

Discipline : InformatiqueUniversité : Université Lumière Lyon 2École doctorale : Informatique et Mathématiques (InfoMaths, ED 512)Laboratoire : Entrepôts, Représentation & Ingénierie des Connaissances (ERIC, EA 3083)Directeur : Djamel ZighedCo-directrice : Cécile Favre

Laboratoire ERIC


Page

Diffusion de l’information dans les médias sociaux


Soutenance de thèse - 25 novembre 2014 Adrien Guille/ 33

Introduction

Pourquoi étudier les médias sociaux ?

• Manière nouvelle de produire, diffuser et consommer l’information

• Utilisateurs producteurs et consommateurs d’information

• Vecteurs d’information efficaces

• e.g. élection de Barack Obama [Hughes09]

• e.g. Printemps arabe [Howard11]

• Apparition d’un phénomène de surcharge informationnelle

• Cette thèse s’intéresse au phénomène de diffusion de l’information dans

les médias sociaux

• Objectif : fournir des moyens de modélisation et d’analyse

2

Laboratoire ERIC


Page




Introduction

Médias sociaux et diffusion de l’information

• Deux fonctionnalités essentielles

• Publication de messages sur une page de profil

• Connexion à d’autres utilisateurs afin de suivre leurs publications

• Influence sociale

• Diffusion de l’information

• Le média social type : Twitter

• Propositions génériques

• Expérimentations sur Twitter

• Accès aux données

• 500·106 utilisateurs

• 20·109 abonnements

3

�

Į ș

ȕ ࢥ

ȕ

ȕ Ȗ

��

Laboratoire ERIC


Page




Introduction

Travaux de recherche menés dans cette thèse

• Problématiques et contributions

• Quels éléments d’information retiennent l’attention des utilisateurs ?

• Algorithme pour détecter automatiquement les évènements significatifs

• Comment et pourquoi un élément d’information donné se diffuse-t-il ?

• Modèle pour prévoir la diffusion de l’information

• Quels utilisateurs peuvent influencer la diffusion d’un élément d’information ?

• Logiciel pour l’analyse de l’influence par rapport aux évènements

• Approche

• Fouille des données issues des médias sociaux

4

kÂ kÃ

kÅ

kÄ

ZÅ

ZÂ

ZÃ

ZÄ

ZÅ

ZÆ

ZÇ

ZÈ

jIZdh

ZÂ

ZÃ

ZÄ

ZÅ

jg<[EPI�jIZd]gIYYI

jIZdh

NgKf

kI[

EI

�QNNkhQ][�GI�Y�Q[N]gZ<jQ][�G<[h�YIh�ZKGQ<h�h]EQ<kr

�KjIEjIg�YIh�KpJ[IZI[jh

!]GKYQhIg�YI�dg]EIhhkh�GI�GQNNkhQ][

�GI[jQNQIg�YIh�kjQYQh<jIkgh�Q[NYk<[j�Y<�GQNNkhQ][

+��"$!�"��01��

+.$� �!�/

ZÆ

ZÇ

ZÈ

$"0.��10�$"/

ZÄ

ZÇZÃ

ZÂ

ZÆ

ZÈ

ZÂ

ZÃ

ZÄ

ZÅ

ZÆ

jIZdh

ZÂ

ZÃ

ZÄ

ZÅ


ZÆ

ZÇ

ZÈ

� 18��/ .�0

� 18� $"0�"1

kÆZÉ

ZÉ

ZÉ

ZÇ

ZÈ

ZÉ

ZÉ

ZÇ

³kÂ�7Ps�G][�j�s]k�I[E]kg<OI�s]kg�.IdkDYQE<[�YIOQhY<j]gh�j]�jPQ[X�]N��

�[<YshI�GIY�Q[NYkI[EI

�KjIEjQ][G�KpJ[IZI[jh

/j]EX<OI�GIh�

G][[KIh

�[jIgN<EI�kjQYQh<jIkg��

+gKd<g<jQ][�Ij�Z<[QdkY<jQ][�GIh�G][[KIh

�IhjQ][[<QgI�G�IrjI[hQ][h

�Zd]gj�GI�G][[KIh�¥ZIhh<OIh�Ij�gKhI<k¦��

/$"�9

� � �

kÂ kÃ kÄ

kÂ

kÃ

kÄ

�

�

�

p]YkZI

jIZdhj j jkÂ kÃ kÄ

�

j

j�jkÄ

j�j kÂ

j�j kÃ

kjQYQh<jIkgh�Q[QjQ<kr

Kj<dI�Â

Kj<dI�Ã

Kj<dI�Ä

Kj<dI�Å

�"6��Â �"6��Ã

�"6��Ä

IÂ IÃ IÄ IÅIÆ

IÇ IÈ

Į ș v q

ȕ

7

hIkQY�d]kg�Y<�N]gZ<jQ][�GIh�KpJ[IZI[jh

KpJ[IZI[j�¾Â

KpJ[IZI[j�¾Ã

KpJ[IZI[j�¾Ä

KpJ[IZI[j�¾Å

KpJ[IZI[j�¾Æ

��qÂ��qÃ��qÄ��qÅ��qÆ��qÇ��qÈ��qÉ��qÊ��qÂÁ�� qÂ��qÃ��qÄ��qÅ��qÆ��qÇ��qÈ��qÉ��qÊ��qÂÁ��

jPKZ<jQfkI�Â��jg<[EPI�Â jPKZ<jQfkI�Â��jg<[EPI�Ã

dg]

D<D

QYQjK


!

jIZdh

NgKf

kI[

EI

qÃ qÂ

ࢥ�

NgKf

kI[

EI

kÂ kÃ

kÅ

kÄ

ZÅ

ZÄ

ZÇZÃ

ZÂ

ZÆ

ZÈ

kÆZÉ

jÂ

jÃ

jÄ

Â Ã Ä

/ �

/ � .

/ �ȕ

ȕ Ȗ

jIZdh

j<QYYI�Gk�E]Zd<g

jQZI[

j

� ./

jÅ

� � �

�

�

!<O¿��¿ !<OÀ��À

� � �

�

!<O¿��¿

� ��

�

!<O¿��¿

/KYIEjQ][ +gK�jg<QjIZI[j 0g<[hN]gZ<jQ][�rdY]g<jQ][�GIh�

G][[KIh�[jIgdgKj<jQ][��p<Yk<jQ][�][[KIh�

DgkjIh ][[<Qh�h<[EI

!��!I[jQ][��[]Z<Ys��<hIG�

�pI[j��IjIEjQ][

0��/� 0QZI��<hIG�

�/s[EPg][]kh��[GIdI[GI[j� <hE<GIh

/$"�9/$EQ<Y�"Ijq]gX�

�9[<ZQEh

kÂ

kÃ

kÅ

kÄ

kÆ

jÂ

jÃ

jÄ

jIZdh

!]sI[[I�Z]DQYI�=�E]kgj�jIgZI

!]sI[[I�Z]DQYI�=�Y][O�jIgZI

!� �

Á�ÁÉ

Á�ÂÉ

Á�ÁÆ

Á�Ã

Á�Å

Á�ÁÅ

Á�ÁÅ

Á�ÂÃ

Á�ÁÊ

Á�ÃÃ Á�ÂÂ

GQNNkhQ][0�kÂ�kÃ�jÂ [][�GQNNkhQ][

0�kÂ�kÅ�jÂ

GQNNkhQ][0�kÃ�kÄ�jÃ

[][�GQNNkhQ][0�kÃ�kÆ�jÃ

pÂ

pÃ

pÂÄ

��N��hIkQY��

qÂ

qÃ

qÂÄ

jÂ jÃ jÄ jÅ jÆ jÇ

qÁ

s

P<dQjgI�Ä

P<dQjgI�Å P<dQjgI�Æ

Å

� � �

�

!<O¿��¿

� ��

�

!<O¿��¿

� �

�g<dPI�GIh�KpJ[IZI[jh

�g<dPI�GIh�gIG][G<[EIh

�g<dPI�GIh�KpJ[IZI[jh

�p<[j�Y<�NkhQ][�GIh�KpJ[IZI[jh�GkdYQfkKh �dgJh�Y<�NkhQ][

/IgpQEI�GI�GKjIEjQ][�Ij�GI�pQhk<YQh<jQ][�GIh�

KpJ[IZI[jh

/IgpQEI�G�<[<YshI�Ij�GI�pQhk<YQh<jQ][�Gk�

gKhI<k�h]EQ<Y

/IgpQEI�GI�Z<[QdkY<jQ][�GIh�

G][[KIh

/IgpQEI�G�QZd]gj�G�<YO]gQjPZIh

/KYIEjQ][ +gK�jg<QjIZI[j 0g<[hN]gZ<jQ][�rdY]g<jQ][�GIh�

G][[KIh�[jIgdgKj<jQ][��p<Yk<jQ][�][[KIh�

DgkjIh ][[<Qh�h<[EI

�][[KIh�EQDYIh �][[KIh�dgK�jg<QjKIh�][[KIh�

jg<[hN]gZKIh!]jQNh

Laboratoire ERIC

Université Lumière Lyon 2Diffusion de l’information dans les médias sociaux


Soutenance de thèse - 25 novembre 2014 Adrien Guille

Première contribution

Détecter les évènements

significatifs dans les

médias sociaux

Laboratoire ERIC


Page





Introduction

• Comment détecter automatiquement les évènements significatifs à partir des médias sociaux ?

• Évènements significatifs : potentiellement traités par les médias traditionnels [McMinn13]

• Messages liés noyés par des messages sans rapport, i.e. bruit

• Analyse de l’évolution temporelle des thématiques [Leskovec09]

• On suppose que les thématiques «saillantes» signalent les évènements [Kleinberg02]

6

�

Į ș

ȕ ࢥ

ȕ

ȕ Ȗ

��

Laboratoire ERIC


Page





État de l’art et proposition

• Approches existantes

• Pondération statistique des termes [Shamma11, Benhardus13]

• Modélisation probabiliste des thématiques latentes [Lau12, Yuheng12]

• Classification non supervisée des termes [Weng11, Li12, Parikh13]

• Limitations des approches existantes

• Durée des évènements fixée à l’avance [Romero11]

• Prise en compte du contenu textuel uniquement

• Proposition

• Estimer dynamiquement la durée de chaque évènement

• Exploiter l’aspect social du flux de messages via les mentions

• Mention : lien dynamique inséré dans un message

7

Laboratoire ERIC


Page





Méthode proposée

• MABED : Mention-Anomaly-Based Event Detection

8

��

��

��

��

��

��

��

• Entrée

• Un corpus de messages partitionné en n tranches temporelles

• Sortie

• Les k évènements aux k plus fortes magnitudes d’impact

• Définitions

• Évènement : une thématique saillante et une valeur Mag traduisant sa magnitude d’impact

• Thématique saillante : un intervalle temporel I, un terme principal t, un ensemble pondéré S de mots liés

Laboratoire ERIC


Page





Méthode proposée

• MABED : Mention-Anomaly-Based Event Detection

8

��

��

��

��

��

��

��

• Entrée

• Un corpus de messages partitionné en n tranches temporelles

• Sortie

• Les k évènements aux k plus fortes magnitudes d’impact

• Définitions

• Évènement : une thématique saillante et une valeur Mag traduisant sa magnitude d’impact

• Thématique saillante : un intervalle temporel I, un terme principal t, un ensemble pondéré S de mots liés

Laboratoire ERIC


Page





Méthode proposée : phase I

• Mesurer l’anomalie

• Par rapport à la fréquence de création de mention à la tranche temporelle i

• Pour chaque mot t

• Détecter les évènement à partir de l’anomalie

• Trouver l’intervalle qui maximise l’anomalie

• Pour tous les mots

9


tranche temporelle, puis nous montrons comment mesurer la magnitude d’impactd’un mot pour une séquence contiguë de longueur quelconque de tranches tempo-relles. Enfin, nous expliquons comment identifier les intervalles qui maximisent lamagnitude d’impact pour tous les mots de V@.

Calcul de l’anomalie en un point. Avant de formuler la mesure d’anomalie, nousdéfinissons le nombre espéré de messages contenant le mot t et au moins une mentionpour chaque tranche temporelle i 2 [1; n], en supposant que ce mot ne soit lié àaucun évènement. Pour cela, nous supposons que le nombre de tels messages à la ième

tranche temporelle, N i@t , suit un modèle génératif probabiliste. Ainsi il est possible de

calculer la probabilité P(N i@t) d’observer N i

@t . Pour un corpus suffisamment grand, ilsemble raisonnable de modéliser ce type de probabilité avec une loi binomiale (Funget al., 2005). Par conséquent nous pouvons écrire :

P(N i@t) =✓

N i

N i@t

◆p

N i@t

@t (1� p@t)Ni�N i

@t ,

où p@t est la probabilité qu’un message contienne le mot t et au moins une men-tion, quelle que soit la tranche temporelle. Comme le nombre de messages N i estgrand dans le contexte des médias sociaux, nous pouvons raisonnablement supposerque P(N i

@t) peut être approximée par une loi normale, c’est-à-dire :

P(N i@t)⇠N (N i p@t , N i p@t(1� p@t)).

Il en découle que la quantité espérée de messages contenant le mot t et au moinsune mention à la ième tranche temporelle est :

E[t|i] = N i p@t , où p@t = N@t/N .

Enfin, nous définissons l’anomalie dans la fréquence de création de mentions liéeau mot t à la ième tranche temporelle comme suit :

anomalie(t, i) = N i@t � E[t|i].

Avec cette formulation, l’anomalie est positive uniquement lorsque la fréquenceobservée de création de mentions est strictement supérieure à l’espérance. Les mots

59







P(N i@t) =✓

N i

N i@t

◆p

N i@t


@t ,









59







P(N i@t) =✓

N i

N i@t

◆p

N i@t


@t ,









59

3.3. Méthode proposée

liés à des évènements et spécifiques à une période temporelle particulière auronttendance à avoir des valeurs d’anomalie positives élevées durant cette période. Aucontraire, les mots récurrents (i.e. triviaux) qui ne sont pas liés à un évènement aurontdes valeurs d’anomalie qui divergeront peu par rapport à l’espérance. Par ailleurs,contrairement à des approches plus sophistiquées comme par exemple la modélisationdes fréquences à l’aide de mixtures gaussiennes, cette formulation passe facilement àl’échelle et s’adapte donc facilement à la taille du vocabulaire.

Calcul de la magnitude d’impact. La magnitude d’impact, Mag, d’un évènementassocié à l’intervalle I = [a; b] et au mot principal t est donnée par la formule ci-dessous. Elle correspond à l’aire algébrique sous la fonction d’anomalie sur l’intervalle[a; b].

Mag(t, I) =

bZ

a

anomalie(t, i)di

=bX

i=a

anomalie(t, i)

L’aire algébrique est obtenue en intégrant la fonction discrète d’anomalie, ce quirevient dans ce cas à une somme.

Identification des évènements. Pour chaque mot t 2 V@, nous cherchons à iden-tifier l’intervalle qui maximise la magnitude d’impact, c’est-à-dire :

I = argmaxI

Mag(t, I).

Or, nous avons montré précédemment que la magnitude d’impact d’un évènementdécrit par le mot principal t et l’intervalle I = [a; b] correspond à la somme de l’ano-malie sur cet intervalle. Par conséquent, cela revient à résoudre un problème du type« Sous-séquence contiguë de somme maximale » (SSCSM), un type de problème cou-rant en fouille de flots de données (Lappas et al., 2009), qui trouve également desapplications dans divers domaines tels que la bio-informatique (Fan et al., 2003) oula fouille de règles d’associations (Fukuda et al., 1996). En d’autres termes, pour un

60




Mag(t, I) =

bZ

a

anomalie(t, i)di

=bX

i=a

anomalie(t, i)



I = argmaxI

Mag(t, I).


60




Mag(t, I) =

bZ

a

anomalie(t, i)di

=bX

i=a

anomalie(t, i)



I = argmaxI

Mag(t, I).


60

³�X<GP<NQ

< D

�¥X<GP<NQ¦

��Þ�§<�D¨

X<GP<NQNQ[<[EK

ÃÁÁÈ

< D

X<GP<NQ��Z<jgQEI�GIh�E]]EEkgI[EIh

<��D��

��

"X<GP<NQ

"NQ[<[EK

q

!<O��

"

E<Zd<O[I

NQ[<[EKh<gX]vs

Q

Q

Q

!<O¥�¦

h<gX]vs

E<dQj<Y

!Ç

Q[pQjK

q

- ++

Laboratoire ERIC


Page





Méthode proposée : phase II

• Identifier les mots décrivant au mieux les évènements

• Identification des mots candidats selon la cooccurrence

• Sélection selon l’intensité de la corrélation entre leur fréquence

• Mesurée selon le coefficient de Erdem [Erdem12]

• Comparée à un seuil θ

• Générer la liste des k évènements ayant eu le plus grand impact

• Construction de la liste à l’aide du graphe des évènements

• Détection des évènements redondants selon

• La connectivité des mots principaux

• Le recouvrement des intervalles temporels, seuil σ• Modélisation des redondances avec un second graphe

• Fusion des évènements dupliqués via l’analyse des composantes connexes

10

³�X<GP<NQ

< D

�¥X<GP<NQ¦

��Þ�§<�D¨

X<GP<NQNQ[<[EK

ÃÁÁÈ

< D


<��D��

��

"X<GP<NQ

"NQ[<[EK

q

!<O��

"

E<Zd<O[I

NQ[<[EK

Q

Q

Q

!<O¥�¦

h<gX]vs

E<dQj<Y

!Ç

Q[pQjK

q

³�X<GP<NQ

< D

�¥X<GP<NQ¦

��Þ�§<�D¨

X<GP<NQNQ[<[EK

ÃÁÁÈ

< D


<��D��

��

"X<GP<NQ

"NQ[<[EK

q

!<O��

"

E<Zd<O[I

NQ[<[EK

Q

Q

Q

!<O¥�¦

h<gX]vs

E<dQj<Y

!Ç

Q[pQjK

q

³�X<GP<NQ

< D

�¥X<GP<NQ¦

��Þ�§<�D¨

X<GP<NQNQ[<[EK

ÃÁÁÈ

< D


<��D��

��

"X<GP<NQ

"NQ[<[EK

q

!<O��

"

E<Zd<O[I

NQ[<[EK

Q

Q

Q

!<O¥�¦

h<gX]vs

E<dQj<Y

!Ç

Q[pQjK

q

Laboratoire ERIC


Page





Expérimentations

• Protocole

• Deux corpus : Cen (1,5·106 tweets [Yang11]) et Cfr (2·106 tweets [ANR ImagiWeb])

• Méthodes comparées : TS [Benhardus13] ET [Parikh13] et α-MABED

• Juges humains : 2 juges humains évaluent les top 40 évènements (κ = 0.72)

• Métriques d’évaluation : Précision, rappel, F-mesure, DERate [Li12], temps de calcul

• Évaluation quantitative

• MABED est la méthode la plus performante en terme de précision et de F-mesure

• Gain moyen concernant la F-mesure de 17,2% par rapport à α-MABED

• Gain plus important pour le corpus le plus bruité, Cen

11

3.4. Expérimentations

Corpus : CenMéthode Précision F-mesure DERate Temps de calcul

MABED 0,775 0,682 0,193 96s↵-MABED 0,625 0,571 0,160 126s

ET 0,575 0,575 0 3480sTS2 0,600 0,514 0,250 80sTS3 0,375 0,281 0,4 82s

Corpus : C f rMéthode Précision F-mesure DERate Temps de calcul

MABED 0,825 0,825 0 88s↵-MABED 0,725 0,712 0,025 113s

ET 0,700 0.674 0,071 4620sTS2 0,725 0,671 0,138 69sTS3 0,700 0,616 0,214 74s

TABLE 3.4 – Performances des cinq méthodes sur les deux corpus.

compte le comportement des utilisateurs des médias sociaux en matière de créationde mentions permet une détection plus robuste des évènements à partir d’un flux detweets bruité. Le DERate révèle que MABED n’a dédoublé aucun évènement signifi-catif parmi ceux détectés dans C f r , mais que – en dépit de la gestion explicite de laredondance par le troisième composant – 6 (DERate = 0, 193) des 31 (P = 0,775)évènements significatifs détectés dans Cen sont redondants. Ce DERate reste toutefoisinférieur à celui mesuré pour les méthodes TS2 ou TS3, et MABED obtient néanmoinsle meilleur rappel sur ce corpus.

Explication de la performance de MABED. Il apparaît que les évènements signi-ficatifs détectés par les méthodes de référence sont un sous-ensemble de ceux détectéspar MABED. L’analyse plus approfondie des résultats d’↵-MABED, TS2 et TS3 révèleque la plupart des évènements jugés non-significatifs sont aisément assimilables à duspam. La non-détection de ces évènements non-significatifs par MABED suggère quela prise en compte des mentions limite la sensibilité au spam, ce qui expliquerait enpartie l’amélioration plus importante de la F-mesure de MABED sur Cen que C f r parrapport aux méthodes de référence. En ce qui concerne ET, nous remarquons quela longueur moyenne des descriptions des évènements est de 17,25 bigrammes (i.e.plus de 30 mots). Nous constatons que les descriptions des évènements détectés parcette méthode à base de classification non supervisée sont bruitées. Les descriptions

72


Corpus : CenMéthode Précision F-mesure DERate Temps de calcul

MABED 0,775 0,682 0,193 96s↵-MABED 0,625 0,571 0,160 126s

ET 0,575 0,575 0 3480sTS2 0,600 0,514 0,250 80sTS3 0,375 0,281 0,4 82s

Corpus : C f rMéthode Précision F-mesure DERate Temps de calcul

MABED 0,825 0,825 0 88s↵-MABED 0,725 0,712 0,025 113s

ET 0,700 0.674 0,071 4620sTS2 0,725 0,671 0,138 69sTS3 0,700 0,616 0,214 74s

TABLE 3.4 – Performances des cinq méthodes sur les deux corpus.

compte le comportement des utilisateurs des médias sociaux en matière de créationde mentions permet une détection plus robuste des évènements à partir d’un flux detweets bruité. Le DERate révèle que MABED n’a dédoublé aucun évènement signifi-catif parmi ceux détectés dans C f r , mais que – en dépit de la gestion explicite de laredondance par le troisième composant – 6 (DERate = 0, 193) des 31 (P = 0,775)évènements significatifs détectés dans Cen sont redondants. Ce DERate reste toutefoisinférieur à celui mesuré pour les méthodes TS2 ou TS3, et MABED obtient néanmoinsle meilleur rappel sur ce corpus.

Explication de la performance de MABED. Il apparaît que les évènements signi-ficatifs détectés par les méthodes de référence sont un sous-ensemble de ceux détectéspar MABED. L’analyse plus approfondie des résultats d’↵-MABED, TS2 et TS3 révèleque la plupart des évènements jugés non-significatifs sont aisément assimilables à duspam. La non-détection de ces évènements non-significatifs par MABED suggère quela prise en compte des mentions limite la sensibilité au spam, ce qui expliquerait enpartie l’amélioration plus importante de la F-mesure de MABED sur Cen que C f r parrapport aux méthodes de référence. En ce qui concerne ET, nous remarquons quela longueur moyenne des descriptions des évènements est de 17,25 bigrammes (i.e.plus de 30 mots). Nous constatons que les descriptions des évènements détectés parcette méthode à base de classification non supervisée sont bruitées. Les descriptions

72

Laboratoire ERIC


Page




• Évaluation qualitative

• Extrait de la liste d’évènements détectés par MABED dans Cen

• Graphe des redondances Graphe des évènements


Expérimentations

12


# Intervalle Thématique

1 du 25 09h30 thanksgiving, turkey : hope (0.72), happy (0.71)au 28 06h30 Les twittos célèbrent Thanksgiving

2 du 25 09h30 thankful : happy (0.77), thanksgiving (0.71)au 27 09h00 Lié à l’évènement # 1

3 du 10 16h00 veterans : served (0.80), country (0.78), military (0.73), happy (0.72)au 12 08h00 Commémoration du 11 novembre, « Veterans Day »

4 du 26 13h00 black : friday (0.95), amazon (0.75)au 28 10h30 Les twittos discutent des offres proposées par Amazon la veille du « Black Friday »

5 du 07 13h30 hcr, bill, health, house, vote : reform (0.92), passed (0.91), passes (0.88)au 09 04h30 La Chambre des représentants des États-Unis adopte la réforme de santé

6 du 05 19h30 hood, fort : ft (0.92), shooting (0.83), news (0.78), army (0.75), forthood (0.73)au 08 09h00 Une fusillade a lieu dans l’enceinte de la base militaire américaine de Fort Hood

7 du 19 04h30 chrome : os (0.95), google (0.87), desktop (0.71)au 21 02h30 Google rend public le code source de Chrome OS pour PC

8 du 27 18h00 tiger, woods : accident (0.91), car (0.88), crash (0.88), injured (0.80)au 29 05h00 Tiger Woods est victime d’un accident de la route

9 du 28 22h30 tweetie, 2.1, app : retweets (0.93), store (0.90), native (0.89), geotagging (0.88)au 30 23h30 L’application Tweetie sort sur l’apple store et inclut de nouvelles fonctions, e.g. retweets

10 du 29 17h00 monday, cyber : deals (0.84), pro (0.75)au 30 23h30 Les twittos partagent les offres commerciales high-tech du « Cyber Monday »

11 du 10 01h00 linkedin : synced (0.86), updates (0.84), status (0.83), twitter (0.71)au 12 03h00 Linkedin permet à ses utilisateurs de synchroniser leurs statuts avec Twitter

12 du 04 17h00 yankees, series : win (0.84), won (0.84), fans (0.78), phillies (0.73), york (0.72)au 06 05h30 Les Yankees, l’équipe de baseball de New York remporte la World Series face aux Philies

13 du 15 09h00 obama : chinese (0.75), barack (0.72), twitter (0.72), china (0.70)au 17 23h30 Lors d’une visite en Chine, Barack Obama admet n’avoir jamais utilisé Twitter

14 du 25 10h00 holiday : shopping (0.72)au 26 10h00 Les twittos réagissent par rapport au « Black Friday », un jour férié dédié au shopping

15 du 19 21h30 oprah, end : talk (0.81), show (0.79), 2011 (0.73), winfrey (0.71)au 21 16h00 Oprah Winfrey annonce la fin de son talk-show en septembre 2011

16 du 07 11h30 healthcare, reform : house (0.91), bill (0.88), passes (0.83), vote (0.83)au 09 05h00 Lié à l’évènement #5

17 du 11 03h30 facebook : app (0.74), twitter (0.73)au 13 08h30 Pas d’évènement correspondant

18 du 18 14h00 whats : happening (0.76), twitter (0.73)au 21 03h00 Twitter demande maintenant « What’s happening ? » et plus « What are you doing ? »

19 du 20 10h00 cern : lhc (0.86), beam (0.79)au 22 00h00 Les faisceaux de particules circulent à nouveau dans l’accélérateur LHC du CERN

20 du 26 08h00 icom : lisbon (0.99), roundtable (0.98), national (0.88)au 26 15h00 Tenue de la table ronde de l’ICOM à propos des marchés financiers portugais

TABLE 3.5 – Liste des 20 évènements ayant eu le plus fort impact sur les utilisateurs,détectés par MABED à partir du corpus Cen. Les mots principaux sont en gras et lepoids de chaque mot lié est donné entre parenthèses. Les intervalles temporels sontexprimés en temps UTC.

74

³�X<GP<NQ

< D

�¥X<GP<NQ¦

��Þ�§<�D¨

X<GP<NQNQ[<[EK

ÃÁÁÈ

< D


<��D��

��

"X<GP<NQ

"NQ[<[EK

q

!<O��

"

E<Zd<O[I

NQ[<[EK

Q

Q

Q

!<O¥�¦

h<gX]vs

E<dQj<Y

!Ç

Q[pQjK

q

jqIIjQI<dd

Ã�Â

P]]G N]gj

jQOIg q]]GhZ][G<s EsDIg

jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g

�g<dPI�GIh�gIG][G<[EIh �g<dPI�GIh�KpJ[IZI[jh<p<[j�NkhQ][

jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g

Q[WkgIG

jQOIgq]]Gh<EEQGI[j

q]]Gh

Eg<hP

E<g

�g<dPI�GIh�KpJ[IZI[jh<dgJh�NkhQ][

Q[WkgIG

³�X<GP<NQ

< D

�¥X<GP<NQ¦

��Þ�§<�D¨

X<GP<NQNQ[<[EK

ÃÁÁÈ

< D


<��D��

��

"X<GP<NQ

"NQ[<[EK

q

!<O��

"

E<Zd<O[I

NQ[<[EK

Q

Q

Q

!<O¥�¦

h<gX]vs

E<dQj<Y

!Ç

Q[pQjK

q

jqIIjQI<dd

Ã�Â

P]]G N]gj


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g

Q[WkgIG

jQOIgq]]Gh<EEQGI[j

q]]Gh

Eg<hP

E<g


Q[WkgIG

Évènement #8

Laboratoire ERIC


Page








Expérimentations

12
























74

³�X<GP<NQ

< D

�¥X<GP<NQ¦

��Þ�§<�D¨

X<GP<NQNQ[<[EK

ÃÁÁÈ

< D


<��D��

��

"X<GP<NQ

"NQ[<[EK

q

!<O��

"

E<Zd<O[I

NQ[<[EK

Q

Q

Q

!<O¥�¦

h<gX]vs

E<dQj<Y

!Ç

Q[pQjK

q

jqIIjQI<dd

Ã�Â

P]]G N]gj


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g

Q[WkgIG

jQOIgq]]Gh<EEQGI[j

q]]Gh

Eg<hP

E<g


Q[WkgIG

³�X<GP<NQ

< D

�¥X<GP<NQ¦

��Þ�§<�D¨

X<GP<NQNQ[<[EK

ÃÁÁÈ

< D


<��D��

��

"X<GP<NQ

"NQ[<[EK

q

!<O��

"

E<Zd<O[I

NQ[<[EK

Q

Q

Q

!<O¥�¦

h<gX]vs

E<dQj<Y

!Ç

Q[pQjK

q

jqIIjQI<dd

Ã�Â

P]]G N]gj


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g

Q[WkgIG

jQOIgq]]Gh<EEQGI[j

q]]Gh

Eg<hP

E<g


Q[WkgIG

Évènement #8

Laboratoire ERIC


Page








Expérimentations

12
























74

³�X<GP<NQ

< D

�¥X<GP<NQ¦

��Þ�§<�D¨

X<GP<NQNQ[<[EK

ÃÁÁÈ

< D


<��D��

��

"X<GP<NQ

"NQ[<[EK

q

!<O��

"

E<Zd<O[I

NQ[<[EK

Q

Q

Q

!<O¥�¦

h<gX]vs

E<dQj<Y

!Ç

Q[pQjK

q

jqIIjQI<dd

Ã�Â

P]]G N]gj


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g

Q[WkgIG

jQOIgq]]Gh<EEQGI[j

q]]Gh

Eg<hP

E<g


Q[WkgIG

Évènement #8

Laboratoire ERIC


Page








Expérimentations

12
























74

³�X<GP<NQ

< D

�¥X<GP<NQ¦

��Þ�§<�D¨

X<GP<NQNQ[<[EK

ÃÁÁÈ

< D


<��D��

��

"X<GP<NQ

"NQ[<[EK

q

!<O��

"

E<Zd<O[I

NQ[<[EK

Q

Q

Q

!<O¥�¦

h<gX]vs

E<dQj<Y

!Ç

Q[pQjK

q

jqIIjQI<dd

Ã�Â

P]]G N]gj


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g

Q[WkgIG

jQOIgq]]Gh<EEQGI[j

q]]Gh

Eg<hP

E<g


Q[WkgIG

³�X<GP<NQ

< D

�¥X<GP<NQ¦

��Þ�§<�D¨

X<GP<NQNQ[<[EK

ÃÁÁÈ

< D


<��D��

��

"X<GP<NQ

"NQ[<[EK

q

!<O��

"

E<Zd<O[I

NQ[<[EK

Q

Q

Q

!<O¥�¦

h<gX]vs

E<dQj<Y

!Ç

Q[pQjK

q

jqIIjQI<dd

Ã�Â

P]]G N]gj


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g


jQOIg<EEQGI[j

q]]Gh

Eg<hP

E<g

Q[WkgIG

jQOIgq]]Gh<EEQGI[j

q]]Gh

Eg<hP

E<g


Q[WkgIG

Évènement #8

Laboratoire ERIC




Seconde contribution

Modéliser et prévoir la

diffusion de l’information

dans les médias sociaux

Laboratoire ERIC


Page




Modéliser et prévoir la diffusion

Introduction

• Comment modéliser et prévoir la diffusion de l’information dans les médias sociaux ?

• Tâche ardue en raison de l’intrication entre

• Les dynamiques humaines

• Les structures sociales

• On en sait encore peu à propos des facteurs qui gouvernent la diffusion de l’information

14

�

Į ș

ȕ ࢥ

ȕ

ȕ Ȗ

��

?

Laboratoire ERIC


Page






• Approches existantes

• Modélisation ignorant la structure du réseau [Leskovec07, Yang10, Wang12]

• Modélisation basée sur la structure du réseau [Saito10, Galuba10, Motoda11]

• Limitations des approches existantes

• Perte d’information en ignorant la structure du réseau [Katona11]

• Estimation coûteuse des paramètres des modèles basés sur le réseau

• Modèles prédictifs mais pas explicatifs

• Proposition

• Modèle basé sur la structure du réseau

• Formulation des paramètres comme des fonctions de caractéristiques observables des utilisateurs

15

Laboratoire ERIC


Page





Méthode proposée

16

• T-BASIC : Time-Based ASynchronous Independent Cascades

• Entrée

• Structure du réseau

• Activité passée des utilisateurs

• Thématique à étudier

• Décrite par un mot principal et un ensemble de mots liés

• Ensemble d’utilisateurs initiant la diffusion de la thématique

• Sortie

• Série temporelle traduisant l’évolution du nombre d’utilisateurs relayant l’information décrite par la thématique

kÃ

kÄ

�ÂÃ

�ÄÃ

�ÄÂ

�ÃÄ

d��¥j¦ÄÃ

d��¥j¦ÃÄd��¥j¦ÄÂ

d��¥j¦ÂÃ

�hjQZIg�YIh�dg]D<DQYQjKh�GI�GQNNkhQ][�Ij�YIh�GKY<Qh�GI�jg<[hZQhhQ][

/

jIZdh

Ihj�Ird]hK�=

<�Q[NYkI[EK

YKOI[GI��

YKOI[GI��

j

kÂ

+gKp]Qg�Y<�GQNNkhQ][�=�d<gjQg�G�k[�I[hIZDYI�/�G�kjQYQh<jIkgh�Q[QjQ<YIZI[j�Q[N]gZKh

�"��

.�"

��/

�+�.�!

�0.�/

��

�

+.�6

�/�$

"��

��

��1

/�$"

Laboratoire ERIC


Page





Méthode proposée

16

• T-BASIC : Time-Based ASynchronous Independent Cascades

• Entrée

• Structure du réseau

• Activité passée des utilisateurs

• Thématique à étudier

• Décrite par un mot principal et un ensemble de mots liés

• Ensemble d’utilisateurs initiant la diffusion de la thématique

• Sortie

• Série temporelle traduisant l’évolution du nombre d’utilisateurs relayant l’information décrite par la thématique

kÃ

kÄ

�ÂÃ

�ÄÃ

�ÄÂ

�ÃÄ

d��¥j¦ÄÃ


d��¥j¦ÂÃ

�hjQZIg�YIh�dg]D<DQYQjKh�GI�GQNNkhQ][�Ij�YIh�GKY<Qh�GI�jg<[hZQhhQ][

/

jIZdh

Ihj�Ird]hK�=

<�Q[NYkI[EK

YKOI[GI��

YKOI[GI��

j

kÂ

+gKp]Qg�Y<�GQNNkhQ][�=�d<gjQg�G�k[�I[hIZDYI�/�G�kjQYQh<jIkgh�Q[QjQ<YIZI[j�Q[N]gZKh

�"��

.�"

��/

�+�.�!

�0.�/

��

�

+.�6

�/�$

"��

��

��1

/�$"

Laboratoire ERIC


Page





Méthode proposée : description du modèle

• Modèle probabiliste

• Extension du modèle AsIC [Saito10]

• Deux paramètres pour chaque lien (ux →uy)

• pux,uy(t) ∈ [0;1] : probabilité que l’utilisateur uy influence ux à l’instant t

• μux,uy > 0 : délai après lequel ux publie un message si uy l’a influencé

• Déroulement de la prévision

• Ensemble S d’utilisateurs initialement activés

• Un utilisateur uy nouvellement activé à l’instant t

influence ses voisins inactifs ux avec la probabilité pux,uy(t)

• En cas de succès, ux devient actif en t+μux,uy

17

kÃ

kÄ

�ÂÃ

�ÄÃ

�ÄÂ

�ÃÄ

d��¥j¦ÄÃ


d��¥j¦ÂÃ

/

jIZdh

Ihj�Ird]hK�=

<�Q[NYkI[EK

YKOI[GI��

YKOI[GI��

j

kÂ

kÃ

kÄ

�ÂÃ

�ÄÃ

�ÄÂ

�ÃÄ

d��¥j¦ÄÃ


d��¥j¦ÂÃ

/

jIZdh

Ihj�Ird]hK�=

<�Q[NYkI[EK

YKOI[GI��

YKOI[GI��

j

kÂ

Laboratoire ERIC


Page





Méthode proposée : estimation des paramètres

• Caractérisation des paires d’utilisateurs

• Vecteur v de 13 attributs ∈ [0;1] : aspects sociaux, thématiques et temporels

• Formulation et estimation des paramètres

• Probabilité de diffusion : fonction sigmoïde d’une combinaison linéaire de v

• Délai de transmission : fonction du degré d’activité de ux

18


instance positive : (vt yux ,uy , 1). Les valeurs des attributs Re(ux) et Re(uy) – qui me-

surent la réceptivité des utilisateurs – sont mesurées en t y , c’est-à-dire au momentde la journée où uy a relayé l’information. Les attributs Th(ux) et Th(uy) sont quantà eux évalués pour le terme principal de la thématique T . Par ailleurs, pour chaquepaire (ux , uy) identifiée à partir de la séquence d’activation liée à la thématique T ,nous choisissons un utilisateur uz, tel que :

— Premièrement, l’utilisateur uz n’a pas relayé l’information décrite par T , c’est-à-dire qu’il n’apparaît pas dans la séquence d’activation ;

— Deuxièmement, l’utilisateur uz est exposé aux messages publiés par uy , c’est-à-dire qu’il appartient à l’ensemble � uy , l’ensemble des voisins entrants de uydans G.

Ainsi, pour un utilisateur uz satisfaisant ces conditions, nous construisons une ins-tance négative : (vt y

uz,uy , 0). Au final, nous obtenons un jeu de données équilibré àpartir duquel nous pouvons estimer la fonction f . La figure 4.6 illustre ce processus :les nœuds u1, u2 et u3 ont relayé l’information décrite par une thématique T respec-tivement en t1, t2 et t3, tandis que les nœuds u4 et u5 n’ont pas relayé l’information.

Estimation des paramètres de f. Nous définissons la probabilité pux ,uy(t) – laprobabilité que l’utilisateur uy influence ux à un instant t à propos d’une théma-tique donnée – comme une fonction du vecteur d’attributs les décrivant, c’est-à-dire :pux ,uy(t) = f (vt

ux ,uy). Comme nous souhaitons que cette fonction soit interprétable etnous permettent d’analyser l’impact des différents attributs sur la probabilité de dif-fusion, nous proposons d’exprimer f comme une fonction monotone à valeurs dans[0;1] d’une combinaison linéaire des composantes du vecteur d’attributs v de la formew0 +P13

j=1 wj vj. Pour simplifier l’écriture de cette combinaison linéaire, nous modi-fions le vecteur v de sorte à avoir v0 = 1, ce qui nous permet de la ré-écrire commele produit scalaire w · v. La fonction f étant monotone, l’analyse du vecteur de coef-ficients w permet de quantifier l’impact, négatif ou positif, des différents attributs surla probabilité de diffusion de l’information entre deux utilisateurs. Plusieurs formesparamétriques pour la fonction f sont envisageables. Nous choisissons ici d’utiliser lafonction sigmoïde et définissons donc f de la manière suivante :

f (v) =exp(w · v)

1+ exp(w · v) .

110









ux ,uy). Comme nous souhaitons que cette fonction soit interprétable etnous permettent d’analyser l’impact des différents attributs sur la probabilité de dif-fusion, nous proposons d’exprimer f comme une fonction monotone à valeurs dans[0; 1] d’une combinaison linéaire des composantes du vecteur d’attributs v de la formew0 +P13


f (v) =exp(w · v)

1+ exp(w · v) .

110

bw = argmaxw

L(D, w),bw = argmaxw

`(D, w).


FIGURE 4.7 – Représentation du classifieur linéaire construit à partir de la fonction f .

degré d’activité de l’utilisateur ux , Ac(ux), c’est-à-dire : µux ,uy = g(Ac(ux)). Plusparticulièrement, nous définissons g de la façon suivante, de sorte que le délai detransmission minimum soit d’une heure :

g(Ac(ux)) =

(w0+ w1Ac(ux) si w0+ w1Ac(ux)> 1,1 sinon.

Pour estimer les paramètres w0 et w1, nous construisons un jeu de données dérivéde D, noté D0. Ce jeu de données est constitué de m= n/2 instances décrites par deuxvariables (xi, zi), selon le principe suivant :

— Pour chaque instance (vi, yi) de D décrite par un vecteur vi = vux ,uy et telleque yi = 1, nous créons l’instance suivante (Ac(ux),�ux ,uy), où �ux ,uy est ledélai de transmission entre uy et ux exprimé en heures. Autrement dit, pourchaque paire d’utilisateurs (ux , uy) identifiée lors de la construction du jeu dedonnées D et entre lesquels l’information s’est diffusée (cf. figure 4.6), nouscréons une instance de D0 décrite par le délai de transmission observé, et ledegré d’activité de l’utilisateur ux qui a été influencé par uy .

Nous proposons d’estimer les paramètres w = {w0, w1} selon la méthode desmoindres carrés (Cornillon et Matzner-Løber, 2007), i.e. en minimisant la somme descarrés des différences entre les délais de transmission observés et les délais prédits, lecritère des moindres carrés étant le suivant :

bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114

bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

• Maximisation de la vraisemblance

• Minimisation du critère des moindres carrés











f (v) =exp(w · v)

1+ exp(w · v) .

110











f (v) =exp(w · v)

1+ exp(w · v) .

110

) = f ) = f ) = ff ( f (




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114

g( g(g( g(

g(

Laboratoire ERIC


Page





Méthode proposée : estimation des paramètres

• Caractérisation des paires d’utilisateurs

• Vecteur v de 13 attributs ∈ [0;1] : aspects sociaux, thématiques et temporels

• Formulation et estimation des paramètres

• Probabilité de diffusion : fonction sigmoïde d’une combinaison linéaire de v

• Délai de transmission : fonction du degré d’activité de ux

18











f (v) =exp(w · v)

1+ exp(w · v) .

110









ux ,uy). Comme nous souhaitons que cette fonction soit interprétable etnous permettent d’analyser l’impact des différents attributs sur la probabilité de dif-fusion, nous proposons d’exprimer f comme une fonction monotone à valeurs dans[0; 1] d’une combinaison linéaire des composantes du vecteur d’attributs v de la formew0 +P13


f (v) =exp(w · v)

1+ exp(w · v) .

110

Modéliser et prédire la diffusion de l’information

Nous proposons d’estimer le vecteur de coefficients w à l’aide du jeu de donnéesD = (vi, yi)ni=1 par maximisation de la vraisemblance. Étant donnée une instance dece jeu de données, nous avons la relation suivante :

f (vi) = P(Y = 1|vi).

Par ailleurs, la probabilité qu’un vecteur vi soit associé à la modalité yi 2 {0; 1}s’écrit comme suit :

P(Y = yi|vi) =

(P(Y = 1|vi) si yi = 1,1� P(Y = 1|vi) si yi = 0.

Bénéficiant du fait que yi 2 {0; 1}, nous pouvons écrire cette probabilité d’unefaçon plus compacte :

P(Y = yi|vi) = P(Y = 1|vi)yi(1� P(Y = 1|vi))1�yi .

Ainsi, en supposant l’indépendance entre les instances du jeu de données D, nousmesurons la vraisemblance du vecteur w pour le jeu de données D (i.e. P(D|w))comme suit :

L(D, w) =nY

i=1

P(Y = yi|vi)

=nY

i=1

P(Y = 1|vi)yi(1� P(Y = 1|vi))1�yi

=nY

i=1

✓exp(w · vi)

1+ exp(w · vi)

◆yi✓

1� exp(w · vi)1+ exp(w · vi)

◆1�yi

Estimer le vecteur w s’apparente donc au problème d’optimisation qui consiste àmaximiser la vraisemblance du jeu de données D :

bw = argmaxw

L(D, w),

ce qui se fait en dérivant L(D, w) par rapport à w. Or, le logarithme naturel étantune fonction strictement croissante, maximiser L(D, w) équivaut par conséquent à

111


maximiser la log-vraisemblance, `(D, w) – dont la dérivation est plus simple. Nousavons donc le problème d’optimisation suivant, équivalent au précédent :

bw = argmaxw

`(D, w).

Nous exprimons la log-vraisemblance comme suit :

`(D, w) = ln

nY

i=1

✓exp(w · vi)

1+ exp(w · vi)

◆yi✓

1� exp(w · vi)1+ exp(w · vi)

◆1�yi!

=nX

i=1

Çyi ln

✓exp(w · vi)

1+ exp(w · vi)

◆+ (1� yi) ln

✓1� exp(w · vi)

1+ exp(w · vi)

◆1�yiå

.

En exploitant le fait que :

P(Y = 0|vi) = 1� P(Y = 1|vi) = 1� exp w · vi

1+ exp w · vi=

11+ exp(w · vi)

,

on obtient alors :

`(D, w) =nX

i=1

�yi(w · vi)� yi ln(1+ exp(w · vi))� (1� yi) ln(1+ exp(w · vi))

�

=nX

i=1

(yi(w · vi)� ln(1+ exp(w · vi)).

Enfin, nous exprimons la dérivée partielle de `(D, w) par rapport à w comme suit :

@ `(D, w)@ wk

=@

@ wk

nX

i=1

(yi(w · vi)� ln(1+ exp(w · vi))

=nX

i=1

✓yi vik � 1

1+ exp(w · vi)vik exp(w · vi)

◆

=nX

i=1

vik

✓yi � exp(w · vi)

1+ exp(w · vi)

◆.

112




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114

�

Į ș

ȕ ࢥ

ȕ

ȕ Ȗ

��

• Maximisation de la vraisemblance

• Minimisation du critère des moindres carrés











f (v) =exp(w · v)

1+ exp(w · v) .

110











f (v) =exp(w · v)

1+ exp(w · v) .

110











f (v) =exp(w · v)

1+ exp(w · v) .

110











f (v) =exp(w · v)

1+ exp(w · v) .

110











f (v) =exp(w · v)

1+ exp(w · v) .

110











f (v) =exp(w · v)

1+ exp(w · v) .

110











f (v) =exp(w · v)

1+ exp(w · v) .

110




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114




g(Ac(ux)) =





bw = argminw0,w1

mX

i=1

(zi � w0� w1 xi)2.

114

Laboratoire ERIC


Page





Expérimentations

• Protocole

• Réseau : 5,7·106 abonnements pour 52·103 utilisateurs de Twitter [Kwak10]

• Trois corpus : C1 (oct. 09) C2 (nov. 09) C3 (déc. 09), au total 4·106 tweets [Yang11]

• Jeux de données d’apprentissage : construits à l’aide de C1 et C2 , et MABED

• Jeux de données de test : construits à l’aide de C2 et C3 , et MABED

• Évaluation de la procédure d’estimation des probabilités de diffusion

• Classifieur h basé sur f avec un seuil θ = 0,5

• Classifieurs courants

• Classifieur à vaste marge

• Classifieur bayésien naïf

19


Métrique (h | f,✓ ) SVM-l SVM-g SVM-p2 SVM-p3 Bayésien naïfPrécision 0,700 0,712 0,712 0,721 0,688 0,708

Rappel 0,822 0,799 0,798 0,755 0,692 0,777F-mesure 0,756 0,753 0,753 0,738 0,690 0,741

TABLE 4.4 – Performances des six classifieurs sur le jeu de données Dtest.

dation croisée sur D, pour des valeurs comprises entre 10�4 et 104 afin d’identifier lecouple (�, C) donnant les meilleurs résultats. Enfin, nous fixons ✓ = 1

2, ce qui signifie

que le classifieur h basé sur la fonction f prédit la modalité la plus probable.Métriques d’évaluation. Puisque nous sommes intéressés par la capacité à pré-

dire la diffusion de l’information entre des paires d’utilisateurs connectés, nous me-surons donc la précision par rapport à la modalité y = 1, comme le rapport entre lenombre d’instances de Dtest correctement associées par le classifieur à la modalité 1 etle nombre total d’instances associées par le classifieur à la modalité 1, c’est-à-dire :

P =nombre d’instances correctement associées par le classifieur à la modalité y = 1

nombre d’instances associées par le classifieur à la modalité y = 1.

De même, nous définissons le rappel par rapport à la modalité y = 1 commele rapport entre le nombre d’instances correctement associées par le classifieur à lamodalité 1 et le nombre total d’instances associées à la modalité 1 dans Dtest, c’est-à-dire :

R=nombre d’instances correctement associées par le classifieur à la modalité y = 1

nombre d’instances réellement associées à la modalité y = 1.

Enfin, nous combinons précision et rappel en calculant la F-mesure, définie commela moyenne harmonique de ces deux métriques :

F =2PRP + R

.

La table 4.4 reporte la précision, le rappel et la F-mesure obtenus par chaqueclassifieur sur le jeu de données Dtest .

Validité de la procédure d’estimation des paramètres de la fonction f. La lec-ture de la table 4.4 révèle que tous les classifieurs obtiennent des performances sa-tisfaisantes sur le jeu de données équilibré Dtest, la F-mesure la plus faible (0,690)

119

�

Į ș

ȕ ࢥ

ȕ

ȕ Ȗ

��

Laboratoire ERIC


Page





Expérimentations

• Évaluation de T-BASIC pour la prévision de la diffusion

• Méthodes comparées : One-time-lag Predictor [Yang10] et αT-BASIC

• Données : 30 séries temporelles extraites à l’aide de MABED

• Métrique d’évaluation : erreur relative par rapport au volume [Yang10]

• Réduction de l’erreur par rapport au One-time-lag Predictor

• 21,2% pour T-BASIC et 14,3% pour αT-BASIC

• Analyse de l’effet des caractéristiques des utilisateurs (ux →uy)

• Taux de mention (aspect social)

• Rôle (aspect social)

• Thématique

• Réceptivité (aspect temporel)

• Degré d’activité (aspect social)

20


10�2 10�1 100 101 102

Th(T )=1Th(T )=0

Re(t)=1Re(t)=0

Ac=1Ac=0

Ro=1Ro=0

Tm=1Tm=0

attribut variant pour uxattribut variant pour uy

FIGURE 4.10 – Rapports de cotes pour différents attributs, mesurés par rapport auxutilisateurs ux et uy . La direction des barres traduit la direction de la relation entrechaque attribut et la probabilité de diffusion : vers la gauche, l’effet est négatif, versla droite, l’effet est positif.

celles correspondant à Th(ux), qui vaut 1 pour v1 et 0 pour v2. Par définition, unrapport de cotes est toujours supérieur ou égal à 0, i.e. odds-ratio(v1, v2) 2 [0;+1[,et s’interprète dans le cas présent de cette façon :

— Lorsque odds-ratio(v1, v2) vaut 1, l’attribut qui varie entre v1 et v2 n’a aucuneffet sur la probabilité de diffusion ;

— Lorsque le rapport est supérieur à 1, la valeur de l’attribut considéré a un effetpositif sur la probabilité de diffusion ;

— Au contraire, lorsque odds-ratio(v1, v2) est inférieur à 1, l’attribut étudié à uneffet négatif sur la probabilité de diffusion.

La figure 4.10 donne les rapports de cotes en fonction de pux ,uy(t) pour différentsattributs, mesurés par rapport à ux et uy . Comme les attributs sont soit numériquesà valeurs dans [0; 1] ou binaires avec pour valeur 1 ou 0, nous mesurons les rapportsde cotes pour un attribut valant soit 1 soit 0. Bénéficiant du fait que le logarithmenaturel est monotone et qu’il s’annule en 1, les rapports de cotes sont présentés selonune échelle logarithme, ce qui facilite la lecture du diagramme en faisant ressortirclairement la direction de la relation entre chaque attribut et la probabilité de diffu-sion.

125

effet négatif effet positif

Laboratoire ERIC




Troisième contribution

Un logiciel libre pour la

fouille des données issues

des médias sociaux

Laboratoire ERIC


Page




Un logiciel libre pour la fouille des données issues des médias sociaux

Introduction

• Comment identifier les utilisateurs influents par rapport à la diffusion de l’information dans les médias sociaux ?

• Besoin de nombreux acteurs de la sociétés, e.g. entreprises, services gouvernementaux, journalistes

• Marketing viral

• Sécurité

• Investigation journalistique

• etc.

• Scénario de base

• Détecter des évènements puis identifier les utilisateurs influant par rapport à ces évènements

• Éventuellement agir en conséquence

22

Laboratoire ERIC


Page






• Logiciels existants

• Prototypes fermés pour la détection d’évènements [Bernstein10, Marcus11, Lee13]

• Logiciels libres pour l’analyse de l’influence [Gephi, Tulip, SNAP]

• Limitations des logiciels existants

• Fossé entre détection d’évènements et analyse de l’influence

• Proposition

• Analyse conjointe des évènements et de l’influence

• Identification des utilisateurs influents par rapport aux évènements détectés

• Logiciel libre

• Autonome (interface utilisateur) ou bibliothèque (interface de programmation)

23

Laboratoire ERIC


Page





Logiciel proposé

• SONDY : SOcial Network DYnamics

• Publics visés

• Non-experts : interface utilisateur avancée et visualisations adaptées

• Chercheurs du domaine : interface de programmation et import d’algorithmes

• Architecture

• Quatre services : import/préparation des données, détection d’évènements, analyse de l’influence, import d’algorithmes

24

�

Į ș

ȕ ࢥ

ȕ

ȕ Ȗ

��

Laboratoire ERIC


Page





SONDY : import et préparation des données

• Import

• Deux fichiers CSV

• Corpus de messages

• Réseau social

• Pré-traitement

• Partitionnement du corpus de messages

• Segmentation du texte

• Racinisation

• Lemmatisation

• Filtrage

• Sélection d’une sous-période de temps

• Suppression des mots vides

25

Laboratoire ERIC


Page





SONDY : détection et visualisation des évènements

• Algorithmes implémentés

• Peaky Topics [Shamma11]

• Persistent Conversations [Shamma11]

• Trending Score [Benhardus13]

• EDCoW [Weng11]

• ET [Parikh13]

• Pont vers On-line LDA

• MABED

• Visualisations

• Liste des évènements

• Courbe de fréquence et MACD [Lu12]

• Liste des messages liés aux évènements

• Frise chronologique

26

Laboratoire ERIC


Page





SONDY : analyse et visualisation de l’influence

• Algorithmes implémentés

• Page Rank [Page98]

• Décomposition en k couches [Kitsak10]

• Log-décomposition en k couches [Brown11]

• Centralité d’intermédiarité [Freeman77]

• Capitalistes sociaux [Dugué14]

• Visualisations

• Distribution des rangs des utilisateurs

• Coloration du réseau social

• Liste des messages des utilisateurs

• Séquence d’activation

27

Laboratoire ERIC


Page





Scénario d’utilisation : non-expert

• Analyser les évènements liés à la société Google

28

Laboratoire ERIC


Page







28

Laboratoire ERIC


Page







28

Laboratoire ERIC


Page







28

Laboratoire ERIC


Page







28

Laboratoire ERIC


Page






• Identifier les utilisateurs influant à propos de la société Google

29

Laboratoire ERIC


Page






• Identifier les utilisateurs influant à propos de la société Google

29

Laboratoire ERIC


Page





Scénario d’utilisation : chercheur du domaine

• Utilisation de l’interface de programmation de SONDY

• Pour automatiser des expérimentations

• Pour réutiliser les méthodes implémentées dans un autre programme

30

import fr.ericlab.sondy.*;import org.apache.commons.io.FileUtils;public class Programme { public static void main(String[] args) { AppVariables state; DataManipulation dataManipulation; // import d’un jeu de données dataManipulation.importDataset("messages.csv","network.csv", "Nom","Description optionnelle",state); // préparation du jeu de données dataManipulation.prepareStream(60,"English",false,state); // chargement de la méthode MABED EventDetectionAlgorithm mabed = (EventDetectionAlgorithm) Class.forName("MABED").newInstance(state); for(double i = 0.2; i <= 1; i += 0.1){ // variation du paramètre sigma de la méthode mabed.sigma = i; mabed.k = 40; mabed.theta = 0.7 mabed.p = 10; mabed.apply(); EventDetectionResults results = mabed.getResults(); // écriture des résultats FileUtils.write("chemin",results); } }}

Laboratoire ERIC


Page




• MABED : détection efficace des évènements significatifs

• Considérer les mentions dans les messages

• Conduit à une détection plus précise des évènements significatifs

• Avec une plus grande robustesse en présence de bruit

• T-BASIC : modélisation explicative du phénomène de diffusion

• Les caractéristiques sociales, thématiques et temporelles des utilisateurs

• Influent de diverses façons sur le phénomène de diffusion

• Notamment les caractéristiques des utilisateurs subissant l’influence

• SONDY : analyse de l’influence par rapport aux évènements

• Accessibilité de l’interface utilisateur par des non-experts

• Grâce notamment à des visualisations adaptées

• Accessibilité de l’interface de programmation

• e.g. implémentation d’un algorithme par des étudiants de master

Conclusion

Résultats obtenus

31

Laboratoire ERIC


Page




• Globalement

• Diversifier les sources de données

• Propositions génériques mais interprétation des résultats liée aux données

• MABED

• Caractériser plus précisément les interactions (e.g. re-tweets, localisations)

• Faire le lien entre détection d’évènements et détection de communautés

• T-BASIC

• Relaxer certaines hypothèses

• Ne plus considérer la seule influence interne au réseau étudié

• Ne plus considérer indépendamment les processus de diffusion simultanés

• SONDY

• Adapter le logiciel aux données volumineuses

• Faciliter l’implémentation d’algorithmes parallèles voire distribués

Conclusion

Perspectives de travail

32

Laboratoire ERIC


Page




• Publications

✴ * Invitation à rédiger une version étendue pour la revue internationale SNAM (Springer)

• Citations

• Plus de 90 citations selon Google Scholar, au 25 novembre 2014

• Téléchargements

• Plus de 750 téléchargements de SONDY, au 25 novembre 2014

Conclusion

Impact des travaux de thèse

33

Revue

internationale

Conférence

internationale

Atelier

international

Conférence

nationale

SIGMOD Record, vol.42, 2013

ASONAM 2014, SIGMOD 2013

MSND @ WWW 2012

EGC 2012, 2013, 2014)

Revue

internationale

Conférence

internationale

Atelier

international

Conférence

nationale

• ACM SIGMOD Record (volume 42) 2013

• IEEE/ACM ASONAM 2014 *

• ACM SIGMOD 2013 (démo)

• PhD @ ACM SIGMOD 2013

• MSND @ ACM WWW 2012

• EGC 2014

• EGC 2013 (démo)

• EGC 2012

Laboratoire ERIC


Page




• Publications

✴ * Invitation à rédiger une version étendue pour la revue internationale SNAM (Springer)

• Citations

• Plus de 90 citations selon Google Scholar, au 25 novembre 2014

• Téléchargements

• Plus de 750 téléchargements de SONDY, au 25 novembre 2014

Conclusion

Impact des travaux de thèse

33

Revue

internationale

Conférence

internationale

Atelier

international

Conférence

nationale

SIGMOD Record, vol.42, 2013

ASONAM 2014, SIGMOD 2013

MSND @ WWW 2012

EGC 2012, 2013, 2014)

Revue

internationale

Conférence

internationale

Atelier

international

Conférence

nationale

• ACM SIGMOD Record (volume 42) 2013

• IEEE/ACM ASONAM 2014 *

• ACM SIGMOD 2013 (démo)

• PhD @ ACM SIGMOD 2013

• MSND @ ACM WWW 2012

• EGC 2014

• EGC 2013 (démo)

• EGC 2012

Merci pour votre attention !

Science

Diffusion de l'information dans les médias sociaux : modélisation et analyse