Study of social-network-based information propagation

Abstract

Information propagation has attracted increasing attention from sociologists, marketing researchers and Information Technology entrepreneurs. With the rapid developments in online and mobile social applications like Facebook, Twitter, and LinkedIn, large-scale, high-speed and instantaneous information dissemination becomes possible, spawning tremendous opportunities for electronic commerce. It is non-trivial to make an accurate analysis on how information is propagated due to the uncertainty of human behavior and the complexity of the social environment. This dissertation is concerned with exploring models, formulations, and heuristics for the social-network-based information propagation process. It consists of three major parts: information diffusion through online social network, modeling social influence propagation, and social-network-based information spreading in opportunistic mobile networks.

Firstly, I consider the problem of maximizing the influence propagation through online social networks. To solve it, I introduce a probabilistic maximum coverage problem, and propose a cluster-based heuristic and a neighbor-removal heuristic for two basic diffusion models, namely, the Linear Threshold Model and the Independent Cascade Model, respectively. Realizing that the selection of influential nodes is mainly based on the accuracy and efficiency in estimating the social influence, I build a framework of up-to-2-hop hierarchical network to approximate the spreading of social influence, and further propose a hierarchy-based algorithm to solve the influence maximization problem. Our heuristic is proved to be efficient and robust with competitive performance, low computation cost, and high scalability.

The second part explores the modeling on social influence propagation. I develop an analytical model for the influence propagation process based on discrete-time Markov chains, and deduce a close-form equation to express the n-step transition probability matrix. We show that given any initial state the probability distribution of the converged network state could be easily obtained by calculating a matrix product.

Finally, I study the social-network-based information spreading in opportunistic mobile networks by analyzing the opportunistic routing process. I propose three social-network-based communication pattern models and utilize them to evaluate the performance of different social-network-based routing protocols based on several human mobility traces. Moreover, I discuss the fairness evaluation in opportunistic routing, and propose a fair packet forwarding strategy which operates as a plugin for traditional social- network-based routing protocols. My strategy improves the imbalance of success rates among users while maintaining approximately the same system throughput.