Independent Cascade Parameter Estimation with Markov Chains
Tarvainen, Aino (2024)
2024
Master's Programme in Computing Sciences and Electrical Engineering
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2024-12-16
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-2024120910893
https://urn.fi/URN:NBN:fi:tuni-2024120910893
Tiivistelmä
The study of network diffusion processes has traditionally focused on the field of epidemiology but since the beginning of the Internet age, the application fields have also greatly expanded to information diffusion and individuals’ social media activity patterns. To understand these dynamics is a relevant field of study, because it allows us to control them, for instance when we consider the countermeasures against epidemic spread, the utilization of word-of-mouth information propagation in the context of marketing or moderating the sharing of harmful online content.
One of the main parameters in commonly used diffusion process models is the transmission probability, which presents the rate at which something is transferred from one individual to other. In many cases when these models are applied in practice, researchers use some a priori knowledge when assigning their values, but there exists methods by which the transmission probabilities may be reconstructed from observed diffusion data.
However, many of these estimation methods tend to overestimate when the networks contain locally high density neighbourhoods. Therefore, this thesis’s objective is to describe and validate a new alternative method using Markov chain modelling, which would result in unbiased estimates in this kind of situation.
We base our estimation method in the Independent Cascade model and our approach in this thesis is to treat Independent Cascade data as a Markov process. The main contributions of the thesis are thus to firstly describe the translation process of Independent Cascade data to Markov chains and secondly, to provide the process for estimating transmission probabilities from this Markov chain translated data.
We tested the proposed method on small synthetic networks using varying sample sizes. Our chosen network topologies include the star-ring and block graphs, which are characterized by their notably highly connected nodes. Our results indicate that the method works as intended, i.e. it is capable of generating high quality estimates that do not contain the kind of bias observed in other methods.
The method described will therefore prove useful when we wish to analyse data from networks of well connected, clique-like neighbourhoods. In addition, since presenting diffusion processes as a Markov process is a simple and intuitive conversion, the method has plenty space for further development and modification.
One of the main parameters in commonly used diffusion process models is the transmission probability, which presents the rate at which something is transferred from one individual to other. In many cases when these models are applied in practice, researchers use some a priori knowledge when assigning their values, but there exists methods by which the transmission probabilities may be reconstructed from observed diffusion data.
However, many of these estimation methods tend to overestimate when the networks contain locally high density neighbourhoods. Therefore, this thesis’s objective is to describe and validate a new alternative method using Markov chain modelling, which would result in unbiased estimates in this kind of situation.
We base our estimation method in the Independent Cascade model and our approach in this thesis is to treat Independent Cascade data as a Markov process. The main contributions of the thesis are thus to firstly describe the translation process of Independent Cascade data to Markov chains and secondly, to provide the process for estimating transmission probabilities from this Markov chain translated data.
We tested the proposed method on small synthetic networks using varying sample sizes. Our chosen network topologies include the star-ring and block graphs, which are characterized by their notably highly connected nodes. Our results indicate that the method works as intended, i.e. it is capable of generating high quality estimates that do not contain the kind of bias observed in other methods.
The method described will therefore prove useful when we wish to analyse data from networks of well connected, clique-like neighbourhoods. In addition, since presenting diffusion processes as a Markov process is a simple and intuitive conversion, the method has plenty space for further development and modification.