Modeling information diffusion in social networks

Abstract

Interpersonal communication with network infrastructure creates mobile and online social networks, which shorten the distance among people. It naturally leads to an important question asking for a clear and detailed description of information dissemination and diffusion process in social networks. An in-depth understanding of the question may help in various aspects,e.g., designing better communication protocols and predicting the demand of hot contents. In the thesis we focus on two concrete sub-questions.

The first one is to describe the performance of mobile social networks under the practical constraint that information is only allowed to be shared among mutual social friends. Existing designs for mobile social networks enable opportunistic message exchange whenever two mobile devices are within the transmission range of each other. However in real life, people may only be willing to interact with their social friends instead of anyone upon contact. Under such a constraint message forwarding may behave differently. We concentrate on modeling the end-end delivery delay in this scenario under two message validity models, unlimited validity and limited validity. In the first case nodes try their best to relay a message to the destination. While in the latter case a relay node will delete its local copy of a message after carrying it for some time T. Mean-field equations for the dynamic of the population of spreader nodes are derived. With solutions of these equations and empirical studies, we get insightful results. First, more skewed distribution of the number of friends leads to larger delay. Second, the unicast delay is almost constant rather than quickly decreasing with the network size. Last, with a moderate choice of T, we can guarantee almost 100% delivery with a delay very close to the case of unlimited validity. It signifies that a good trade-off can be obtained between delivery efficiency and energy/storage overhead.

The second sub-question asks for a model of information diffusion in online social networks. Sharing information in OSN platforms like Twitter and Facebook has become an important part of human life. Thus understanding the dynamic is important as it may help, for example, predict the demand of media contents. We make use of the age-dependent branching process framework to describe the diffusion of content with constant popularity. We give explicit expression for the expected diffusion cascade size, analyze its asymptotic behavior and compare it with the prediction of traditional, over-simplified epidemic model. Also we analyze the diffusion of content with time-variant popularity. An integral equation governing the growth of cascade size is given. Some measurement observations are also explained and quantified. Lastly we design a new model incorporating the geographical locality of contents based on the study of multitype age-dependent branching processes, where the expression for expected cascade size is also given, offering a clear picture of the whole process. Extensive simulations verify the analytical expressions and offer straightforward insights into some other properties of the diffusion process which are not captured by the mathematical formulation.