Research On Information Diffusion And Influence Maximization In Social Networks

With the advent of Internet and proliferation of online social networks, we can ob-tain vast amount of historical data to track, model and predict the information diffusion process. As a new kind of media, information in social networks can spread "virally" between users and has attracted enormous attentions:on one hand, in comparison to the mass media such as radio, newspapers and TV, which broadcast information to people, information in social networks has the effect of "word of mouth", which is more trust-worthy; on the other hand, information diffusion can become cascade, and influences a lot of people. However, due to the complex micro-foundations of individuals and the intricate structures of social networks, it is very difficult to understand and make use of the information diffusion explicitly.In this thesis, we first analyze and predict the trace of information to understand the mechanics of information diffusion. And based on the model, we design mechanisms for influence maximization. The detailed contributions are:(1) We analyze the interplay between information diffusion and cascade struc-tures to predict the future spread of information. In social networks, the elusive micro-foundations of social behaviors and the complex underlying social networks make it very difficult to model and predict the information diffusion process precisely. In this paper, we explore the relationships between information diffusion and the cas-cade structures in social networks. By embedding the cascades in a lower dimensional space and employing spectral clustering algorithm, we find that the cascades generally evolve into five typical structure patterns with distinguishable characteristics. In addi-tion, these patterns can be identified by observing the initial footprints of the cascades. Based on this observation, we propose that the structure patterns can be predictive of the cascade growth. The experiment results show that the accuracy of predicting both the structure and virality of cascades can be improved significantly by incorporating the cascade structure patterns.(2) We investigate the model of interacting information, and identify the influ-ential users in social networks. Multiple pieces of information may spread in a social network simultaneously. And they may have the relationships such as mutually ben-efit or competing. In this paper, we first propose a generalized model for interacting information diffusion by explicitly characterizing the preference of nodes. Under this generalized model, we show that the problem is NP-hard. In addition, we propose an effective heuristic algorithm by tracing the information back according to a properly de-signed random walk on the network, based on the postulation that all initially inactive nodes can be influenced by our information. Extensive experiments are conducted to evaluate the performance of our algorithm. The results show that our algorithm outper-forms many other algorithms in most cases, and is very scalable due to its low running time.(3) We propose a budget allocation strategy to incentivize the initial adopters in social networks to maximize the spread of influence. A key issue in influence max-imization is often neglected:how to incentivize the initial adopters? Previously, the assumption is that each user has a fixed cost for being initial adopters; while in prac-tice, user decisions for accepting the budget to be initial adopters are often probabilistic. In this paper, we study optimal budget allocation in social networks to maximize the spread of viral advertising. In particular, a concave probability model is introduced to characterize each user’s utility for being an initial adopter. Under this model, we show that it is NP-hard to find an optimal budget allocation for maximizing the spread of viral advertising. We then present a novel discrete greedy algorithm with 1-1/e-o(1) performance guarantee, and further propose scaling-up techniques to improve the time-efficiency of our algorithm. Extensive experiments on real-world social graphs are im-plemented to validate the effectiveness of our algorithm in practice. The results show that our algorithm can outperform other intuitive heuristics significantly in almost all cases.