Diffusion of information in network structures
Shohreh Shaghaghian · eScholarship@McGill (McGill) · 2018
Understanding the process by which a piece of data or information disseminates throughout a network is of great importance in many real world applications. Whether we are in charge of spreading the information or we are merely able to observe its traces, we need to model the process by which the diffusion occurs. In this thesis, we develop frameworks to model the information diffusion processes and propose multiple algorithms to both control and infer them.We first study how we can proactively control the process of diffusion of information among a set of mobile nodes in the absence of a physical network infrastructure. Data transfer in this setting must rely on unscheduled sporadic meetings between nodes. Therefore, the main challenge is to develop a mechanism based on which nodes can learn to make nearly optimal forwarding decision rules despite having no a priori knowledge of the network topology. The forwarding mechanism should ideally result in a high delivery probability, low average latency, and efficient usage of the network resources. We propose both centralized and decentralized single-copy message forwarding algorithms that, under relatively strong assumptions about the networks behaviour, minimize the expected latencies from any node in the network to a particular destination. After proving the optimality of our proposed algorithms, we develop a decentralized algorithm that involves a recursive maximum likelihood procedure to estimate the meeting rates. We finally propose Bayesian versions of the decentralized algorithm that can take into account some external information about the social ties among the nodes to improve the forwarding decisions. We also study how we can detect the underlying propagation structure by passively observing the traces of a diffusion process. The required sophistication of the inference approach depends on the type of patterns we want to extract as well as the number of observations that are available to us. We analyze scenarios in which not only the underlying network structure (parental relationships and link strengths) needs to be detected, but also the infection times must be estimated. We assume that our only observation of the diffusion process is a set of time series, one for each node of the network, which exhibit statistical changes when an infection occurs. Modelling the problem in a Bayesian framework, we propose both batch and online inference algorithms.