Spelling suggestions: "subject:"diffusion processes ono graphs"" "subject:"diffusion processes onn graphs""
1 |
Application des processus stochastiques aux enchères en temps réel et à la propagation d'information dans les réseaux sociaux / Application of stochastic processes to real-time bidding and diffusion processes on networksLemonnier, Rémi 22 November 2016 (has links)
Dans cette thèse, nous étudions deux applications des processus stochastiques au marketing internet. Le premier chapitre s’intéresse au scoring d’internautes pour les enchères en temps réel. Ce problème consiste à trouver la probabilité qu’un internaute donné réalise une action d’intérêt, appelée conversion, dans les quelques jours suivant l’affichage d’une bannière publicitaire. Nous montrons que les processus de Hawkes constituent une modélisation naturelle de ce phénomène mais que les algorithmes de l’état de l’art ne sont pas applicables à la taille des données typiquement à l’œuvre dans des applications industrielles. Nous développons donc deux nouveaux algorithmes d’inférence non-paramétrique qui sont plusieurs ordres de grandeurs plus rapides que les méthodes précédentes. Nous montrons empiriquement que le premier a de meilleures performances que les compétiteurs de l’état de l’art, et que le second permet une application à des jeux de données encore plus importants sans payer un prix trop important en terme de pouvoir de prédiction. Les algorithmes qui en découlent ont été implémentés avec de très bonnes performances depuis plusieurs années à 1000 mercis, l’agence marketing d’avant-garde étant le partenaire industriel de cette thèse CIFRE, où ils sont devenus un actif important pour la production. Le deuxième chapitre s’intéresse aux processus diffusifs sur les graphes qui constituent un outil important pour modéliser la propagation d’une opération de marketing viral sur les réseaux sociaux. Nous établissons les premières bornes théoriques sur le nombre total de nœuds atteint par une contagion dans le cadre de graphes et dynamiques de diffusion quelconques, et montrons l’existence de deux régimes bien distincts : le régime sous-critique où au maximum $O(sqrt{n})$ nœuds seront infectés, où $n$ est la taille du réseau, et le régime sur-critique ou $O(n)$ nœuds peuvent être infectés. Nous étudions également le comportement par rapport au temps d’observation $T$ et mettons en lumière l’existence de temps critiques en-dessous desquels une diffusion, même sur-critique sur le long terme, se comporte de manière sous-critique. Enfin, nous étendons nos travaux à la percolation et l’épidémiologie, où nous améliorons les résultats existants. / In this thesis, we study two applications of stochastic processes in internet marketing. The first chapter focuses on internet user scoring for real-time bidding. This problem consists in finding the probability for a given user to perform an action of interest, called conversion, in the next few days. We show that Hawkes processes are well suited for modelizing this phenomena but that state-of-the-art algorithms are not applicable to the size of datasets involved. We therefore develop two new algorithms able to perform nonparametric multivariate Hawkes process inference orders of magnitude faster than previous methods. We show empirically that the first one outperforms state-of-the-art competitors, and the second one scales to very large datasets while keeping very high prediction power. The resulting algorithms have been implemented with very good performances for several years in 1000mercis, a pioneering marketing agency being the industrial partner of this CIFRE PhD, where they became an important business asset. The second chapter focuses on diffusion processes graphs, an important tool for modelizing the spread of a viral marketing operation over social networks. We derive the first theoretical bounds for the total number of nodes reached by a contagion for general graphs and diffusion dynamics, and show the existence of two well distinct regimes: the sub-critical one where at most $O(sqrt{n})$ nodes are infected, where $n$ is the size of the network, and the super-critical one where $O(n)$ nodes can be infected. We also study the behavior wrt to the observation time $T$ and reveals the existence of critical times under which a long-term super-critical diffusion process behaves sub-critically. Finally, we extend our works to different application fields, and improve state-of-the-art results in percolation and epidemiology.
|
Page generated in 0.1261 seconds