Information Diffusion In Complex Networks Via Gossiping

With the rapid developments in hardware and software technology, so called networked systems have expanded significantly in the recent years. Due to their significant advantages, these networks grow continuously in size (number of agents, links) and complexity. However, this enormous growth brings potential problems, i.e., complexity issues and failure consequences. For this reason, in this study, we focus on efficient, scalable and reliable information diffusion algorithms on complex networks. We first focus on so called average consensus problem under finite rate communications. We utilize increasing spatial and correlation among node states to reduce quantization error in the system and propose coding with side information schemes for quantized consensus algorithms. We analyze the convergence behavior of the quantized consensus as well as analytically modeling the mean squared error of the algorithm. Moreover, we propose a gossiping algorithm, i.e.,broadcast gossiping, for consensus type problems on sensor networks. Similar to other gossiping algorithms, our scheme generates only local traffic and robust to link/node failures due to the iterative update structure. The main advantage of the algorithm is the fact that our updates rely on the wireless nature of the links in between nodes rather than point to point communications. We further analyze performance characteristics of our algorithm such as the speed of convergence and mean squared error. We also propose a gossiping based scheme for asymmetric information dif- fusion problem. In this particular problem, a subset of the network is interested in a separable function of the data which is stored in another subsets of the nodes. Given the underlying network connectivity and the source-destination sets, we provide necessary and sufficient conditions on the update weights (referred to as codes) so that the destination nodes converge to the desired function of the source values. We show that the evolution of the source states does not affect the feasibility of the problem, and we provide a detailed analysis on the spectral properties of the feasible codes. We also study the problem feasibility under some specific topologies and provide guidelines to determine infeasibility. We also formulate different strategies to design codes, and compare the performance of our solution with existing alternatives. Finally, we propose a gossiping based method for modeling opinion propagation through social networks. In particular, we model the individuals' opinions as binary variables (such as 0 or 1, democrat or republican, etc), and assume that there exists certain individuals in society who do not change their opinions. We analyze the behavior of individual's opinions as well as the collective opinion of the society in the long run. We completely characterize long term mean and variance of the average opinion in the networks as well as posing optimal stubborn agent replacement problem