Study Of Information Propagation Model For Large-Scale Social Networks And Its Applications

Recent years has witnessed the great development of social network. Social network has become a necessity for people’s life. They use it to spend spare time, get information and contact with their friends. This creator has brought endless possibility for people’s future life. For example, US president Obama use social network to get the votes for him and win the final campaign; Korea singer PSY use social network to maximally spread his work Gangnam style. How does the infor-mation propagate in social network and how to take advantage of social network to boost the information propagation, have become the hot problems in academia. In this paper, we will systematically research the information propagation model in social network.First, this paper has proposed an efficient information propagation model: linear influence model. Information propagation model is the basis for describing and computing the information propagation process. Although there have been many models, such as independent cascade model and linear threshold model, these models have many shortages. They are untractable, low-efficient, and has no closed-form expression, which make them only applicable to the small scale social networks. However, the real social networks (such as Facebbook, twitter) usually have billions of nodes. To overcome these obstacles, we proposed the linear influence model which is tunable, flexible and efficient. We could use it to approach the traditional models with little effort and complete its computation in linear time. We verified its performance in several large scale social networks, even with millions of nodes.Second, this paper studied the essential of PageRank, and proposed several enhanced PageRank algorithm. PageRank is the classical algorithm for authority computation. This paper re-analyzed this algorithm in the perspective of social influence and found the conclusion "the node authority is actually the sum of its influence on each node of social network". This paper also proved that PageRank is a fast approximation for node’s influence and could be improved by many ways. This paper proposed several enhanced PageRank, such as norm-PageRank, prior-PageRank. Moreover, This paper also proposed a general PageRank:influence-PageRank, which is applicable to any social network with arbitrary information transition probability matrix, and proposed a more-general PageRank:group-PageRank, which is used to compute the authority of a group of nodes. Finally, this paper verified the correctness of the conclusion and the advantage of those enhanced PageRank algorithms through experiments.At last, this paper worked on applying the linear influence model and group-PageRank to design viral marketing campaign. Viral marketing, also called as "word-of-mouth effect", targets at finding a small group of influential nodes-giving them free samples of a product-for triggering a cascade of product propagation that people recommend the product to their friends and friends’friends, with the hope that the product will be adopted by a maximum fraction of the social network. This paper proposed two algorithms:Linear and Bound, based on the linear influence model and group-PageRank respectively. We tested these two algorithms in many real data sets. The experimental results showed that both of Linear and Bound perform better than the state-of-the-art algorithms. Especially, Bound could make the optimal strategy in constant time, which is applicable to the social networks with billions of nodes.