Note publique d'information : Les services de microblogging (comme Twitter ou Sina Weibo) sont devenu ces dernières
années des plateformes très importantes de partage d'information sur l'Internet. Les
microblogs sont fréquemment utilisé pour l'analyse de l'opinion, le marketing viral,
et les campagnes politiques. Comprendre les mécanismes sous-jacents de la diffusion
d'information sur les microblogs et comment des contenus deviennent populaires est
important.L‘analyse de la diffusion d'information dans les microblogs nécessite la
collecte de donnée des microblogs, la modélisation de la diffusion d'information et
l'application des modèles résultants. Traiter les données massives issues des microblogs
est un défi en soi. Concevoir des algorithmes efficaces et sans biais afin d'échantillonner
les microblogs est ainsi fondamental. Ceci doit prendre en compte la complexité du
phénomène de « retweet » qui dépend de la valeur éphémère de l'information, de la
topologie du réseau de microblogging et des caractéristiques particulières des éditeurs
et retweeteurs.Deux modèles ont été traditionnellement appliqués à la diffusion d'information :
les cascades indépendantes et modèle à seuil linéaire. Aucun de ces deux modèles n'est
à même de décrire le processus du retweeting de façon correcte. Il devient donc nécessaire
de de caractériser la diffusion d'information. De plus, une description complète de
la relation entre la diffusion d'information dans les microblogs et de popularité
des termes recherchés sur Internet serait utile.Ces travaux de thèse présentent une
analyse complète de la diffusion d'information dans les microblogs. Les contributions
ce cette thèse sont les suivantes :1) Il y'a deux technique d'échantillonnage sans
biais pour les réseaux sociaux : la marche aléatoire de Métropolis-Hastings (MHRW),
et la méthode d'échantillonnage sans biais de graphes dirigés (USDSG). Néanmoins ces
deux méthodes peuvent aboutit à un taux important d'auto-échantillonnage quand elles
sont appliquées à des microblogs. Pour résoudre ce problème, j'ai modélisé l'échantillonnage
d'un OSN par un processus de Markov et j'en ai déduit les conditions nécessaires et
suffisantes d'un échantillonnage sans biais. Ces conditions m'ont permis de proposer
un algorithme d'échantillonnage sans biais et efficace que j'ai nommé : échantillonnage
sans biais par liens vide (USDE). Cette nouvelle méthode d'échantillonage réduit fortement
l'auto-échantillonnage du MHRW. L ‘évaluation empirique montre que la moyenne des
dégrées des nœuds échantillonnés est proche de la vérité terrain alors que pour MHRW
et USDSG elle est 2 à 4 fois supérieure.2) La seconde contribution de cette thèse
vise les lacunes des modèles en cascades indépendantes et de seuils linéaires. J'ai
développé un modèle fondé sur les processus de Galton-Watson avec mort (GWK) qui prennent
en compte tous les facteurs importants du processus de retweet. Ce nouveau modèle
est validé par une application sur des données issues de Twitter et de Weibo.3) La
troisième contribution est relative au développement d'un modèle économique du marché
des acteurs actifs dans le domaine du marketing sur les mots clés dans les sites de
recherches. J'ai développé des méthodes de gestion de portfolios de mots clés et montrés
que ces portfolios permettent d'améliorer fortement les rendements sans augmenter
le niveau de risque.
Note publique d'information : Microblog service (such as Twitter and Sina Weibo) have become an important platform
for Internet content sharing. As the information in Microblog are widely used in public
opinion mining, viral marketing and political campaigns, understanding how information
diffuses over Microblogs, and explaining the process through which some tweets become
popular, are important.The analysis of the information diffusion in Microblogs involves
the data collection from Microblog, the modeling on information spreading and using
the resulting models. Dealing with the huge amount of data flowing through microblogs
is by itself a challenge. Designing an efficient and unbiased sampling algorithm for
Microblog is therefore essential. Besides, the retweeting process in Microblog is
complex because of the ephemerality of information, the topology of Microblog network
and the particular features (such as number of followers) of publisher and retweeters.Two
traditional models have been used for information diffusion : Independent Cascades
and Linear Threshold models. However no one of them can describe completely the retweeting
process in Microblog accurately. The analysis and design of new models to characterize
the information diffusion in Microblog is therefore necessary. Moreover, a comprehensive
description of the correlation between the information diffusion in Microblog and
the searching trends of keywords on search engines is lacking although some work has
been found some preliminary relationships.This work presnets a complete analysis of
information diffusion in Microblog from. The contributions and innovations of this
thesis are as follows:1)There are two popular unbiased Online Social Network (OSN)
sampling algorithms,Metropolis-Hastings Random Walk (MHRW) and Unbiased Sampling for
Directed Social Graph (USDSG) method. However they are both likely to yield considerable
self-sampling probabilities when applied to Microblogs where there is local. To solve
this problem, I have modelled the process of OSN sampling as a Markov process and
have deduced the sufficient and necessary conditions of unbiased sampling. Based on
this unbiased conditions, I proposed an efficient and unbiased sampling algorithms,
Unbiased Sampling method with Dummy Edges (USDE), which reduces strongly the self-sampling
probabilities of MHRW. The experimental evaluation demonstrate thats the average node
degree of samples of MHRW and USDSG is 2 - 4 times as high as the ground truth while
USDE can provide the approximation of ground truth when the sampling repetitions are
removed. Moreover the average sampling time per node in USDE is only a half of MHRW
and USDSG one.2)A second contribution targets the shortages of Independent Cascades
(IC) and Linear Threshold (LT) models in characterizing the retweeting process in
Microblogs. I achieve this by introducing a Galton Watson with Killing (GWK) model
which considers all the three important factors including the ephemerality of information,
the topology of network and the features of publisher and retweeters accurately. We
have validated the applicability of the of GWK model over two datasets from Sina Weibo
and Twitter and showed that GWK model can fit 82% of information receivers and 90%
of the maximum numbers of hops in the real retweeting process. Besides, the GWK model
is useful for revealing the endogenous and exogenous factors which affect the popularity
of tweets.3) Motivated by the correlation between popularity and trendiness of topicsin
Microblog and search trends, I have developed an economic analysis of the market involving
a third-party ad broker, which is a popular market in current SEM, and finds that
the adwords augmenting strategy with the trending and popular topics in Twitter enables
the broker to achieve, on average, four folds larger return on investment than with
a non-augmented strategy, while still maintaining the same level of risk.
paprika.idref.fr
data.idref.fr
Documentation
